Printer Friendly

Research on the anti-perspective correction algorithm of QR barcode.

1. Introduction

Compared with one-dimensional bar code, 2-D barcode has advantages such as high information density, high security, and strong error correction capability. In recent years, it has gotten more and more attention [1].

2-D barcode image is subject to kinds of distortions which may result in a degeneration of quality during acquisition. Deformation of 2D barcode image includes barrel distortion caused by the image acquisition device itself. Skew distortion, perspective distortion, scale distortion and other geometric distortions, those distortions are caused by the relative rotation angle between the optical axis and the bar code plane, the relative angle and the difference between the distance and bar code image plane bending and other factors. In order to improve the recognition rate of the bar code, image deformation correction is prerequisite. D'Angelo et al. proposed an objective quality metric for geometrically distorted image [2]. Due to wide-angle conuguration of the camera lens, Vijayan Asari and Tsai proposed aradial lens distortion model which describes a 2-D image correction technique [3, 4]. Baggenstoss used a Polynomial technique to correct deformed image by comparing the deformed images with the un-deformed images [5]. Richetin used the zero-curvature points of their contours to solve the inverse perspective problem [6]. Kutulakos and Dyer proposed a method for recovering surface shape from the occluding contour using an active observer [7].

In the process of 2-D bar code image recognition, distorted barcode images obtained by acquisition device are the result of the superposition of various factors. According to different factors which cause image distortion, we can use corresponding methods to correct distortions. This approach can obtain a good image correction effect.

However, this approach will greatly increase the time of image processing, and has no practical value. From the practical application point of view, image distortion caused by each factor alone is not serious, so we can ignore specific factor that lead to image distortion. In recent years, scholars in the field of bar code image processing begin to seek those algorithms which can meet the actual needs and have good efficiency.

Kato and Tan proposed the special point of the QR barcode image transformation, but had no detailed description of specific method [8]. Liu and other scholars have proposed linear correction method, which uses the method of scanning and get four vertices of the image periphery, but these methods has poor noise immunity and limited accuracy [9, 10]. Liu Ning-Zhong et al. reduce the amount of computation by improving the method of calculation, under the assumptions that the four vertices of the images have already existed [11].

In this paper, we use anti-perspective transformation method based on a fixed point, which was proposed by Richetin et al. [6], Kutulakos and Dyer [7], we accurately select the four feature points of the image periphery as control points of anti-perspective transformation and compare the effects with related algorithms. The results show that our proposed algorithm has better performance, to meet the requirements of the bar code image recognition.

2. The basis of algorithm

2.1. Descriptions on QR code features

AS is shown in Figure 1, QR Code image composes by blank region, searching graphics, correcting graphics, positioning graphics, code word module. The blank region is distributed in the region of the image around with four modules width, mainly in order to isolate the image area and the complex background of the bar code. searching graphics respectively located in the upper left, top right, and the lower left corner of the symbol, top right, and the lower left corner, and the module width ratio is 1:1:3:1:1. According to the mutual positional relationship of searching graphics, the position and orientation of the symbols can be determined. The overall QR Code image is a square; the corresponding edge of two images in one edge of the square is in a line.

2.2 The parallel lines analysis in the perspective image

From the characteristics of the perspective projection transformation, points in a straight line in the scene are still in a straight line after perspective projection transformation. When the angle of the observation plane is different to scene plane, parallel lines in the scene will converge on the vanishing point after perspective transformation. It means that, there is a certain degree of change in the angle between two Parallel lines after perspective projection transformation.

Let spacing h, length l parallel line, with the angle of the optical axis [theta], as is shown in Figure 2, in the plane perpendicular to the lens, l can be decomposed a rectangle in the direction of the optical axis direction, and the length of the rectangle is l cos [theta], the height of the rectangle is h.

[[alpha].sub.1] = arctan [h/z]

[[alpha].sub.2] = arctan [h/[z + l cos [theta]]] (1)

Here z is the sum of object distance and image distance, and the angle change of two straight lines after perspective as follows:

[[alpha].sub.3] = arctan [h/z] - arctan [h/[z + l cos [theta]]] (2)

From the standards of 2D bar code, the Side length of searching graphics of QR code is l, line width is h = l/8, and z is the sum of the object distance and image distance, z [much greater than] l, from (1) (2), we can get:

[[alpha].sub.1] = arctan [h/z] [right arrow] [[alpha].sub.2] [approximately equal to] [h/z] (3)

[[alpha].sub.2] = arctan [h/[z + l cos [theta]]] [right arrow] [[alpha].sub.2] [approximately equal to] [h/[z + l cos [theta]]] (4)

Angle difference [[alpha].sub.3] leaded by perspective:

[[alpha].sub.3] = [[alpha].sub.1] - [[alpha].sub.2] [approximately equal to] [hlcos/[z(z + l cos [theta])]] [congruent to] 0 (5)

3. Anti-perspective algorithm process

The accuracy of the correction image is determined by the precise extent of the images of the four vertex position [5]. The analysis in introduction shows that many scholars have proposed the method of getting the four vertex of the image. In this paper, we make image correction basing on the characteristics graphics of the QR Code image. The algorithm processes is shown in Figure 3.

3.1. Finding the positioning point of QR image

In the entire image, we Search the segments whose corresponding ratio in the horizontal and vertical directions is 1:1:3:1:1, and set its center as the center of the searching graphic.

3.2 Determine fitting line corresponding to Feature image

From the position relationship of searching graphics in the QR Code image in Figure 1, we can get edges of searching graphics which need to be scanned. As is shown in Figure 4: For three searching graphics, the corresponding edges which need to be scanned are as follows:[a.sub.1,1], [a.sub.2,1], [b.sub.1,2], [b.sub.1,3], [c.sub.1,3], [c.sub.1,4].

3.3 Building the line determined by two Feature image

We can learn from the characteristics of QR Code image and the corresponding dimension those segments [a.sub.1,1], [b.sub.1,2] are in a line. From the perspective principle, the point in a straight line is still in a straight line after perspective. Taking into account the discrete nature of the scan points, we select scan segments [a.sub.1,1], [b.sub.1,2] and connect the distribution median point along the Y axis, to get the line L2.Similarly, according to segments [b.sub.1,3], [c.sub.1,3], we get line L3.

3.4 Building the line determined by the individual searching graphics

For straight line along the edge of [a.sub.1,1] and [c.sub.1,4], we can fit a straight line along the scanning point. However, the date obtained by corresponding edge of searching graphs is less and large discrete, which will affect the accuracy of image correction. From the formula (5) and the basic characteristics of the QR Code, the edges [a.sub.1,1], [a.sub.2,1] of searching graphics a remain parallel in the same direction after perspective transformation. Thus we can fit a straight line using the corresponding points in those two straight lines. Because of the edge [a.sub.1,1] of searching graphic is more susceptible to noise than edge [a.sub.2,1], after several fitting experiments, we set the angle weighting of [a.sub.1,1] to 0.6 and the angle weighting of external linear to 0.4. We suppose the angle determined by [a.sub.1,1] is [[beta].sub.1], the Angle determined by [a.sub.2,1] is [[beta].sub.2], the angle of the final fitting straight line is:

[beta] = 0.4 [[beta].sub.1] + 0.6 [[beta].sub.2] (6)

We rank the scanned point of edge [a.sub.1,1] according to their X coordinate, and choose the middle value as the linear fitting point [P.sub.a]. We get fitting straight lines [L.sub.1] from the straight line angle [beta] and [P.sub.a]. Similarly, a fitting straight line [L.sub.4] can be obtained by searching graphics C.

3.5. Obtaining the vertices of the image

We intersect the straight lines [L.sub.1], [L.sub.2], [L.sub.3], [L.sub.4] obtained by searching graphics C, D, and take the corresponding point of intersection as four vertices [p.sub.1], [p.sub.2], [p.sub.3], [p.sub.4] of obtained deformation images.

3.6 Getting the corrected image by inverse perspective transformation

Take the average value of distance between four intersections [p.sub.1], [p.sub.2], [p.sub.3], [p.sub.4] as the side length of the corrected QR Code image, and get the corrected image by use of the anti-perspective correction algorithm of four standard points.

4.The Analysis Of Final Results

To validate the performance of the algorithm, we apply the algorithm to pieces of QR images of different sizes which have perspective transformation, and compare the effect of processing time and recognition rate to other algorithms. In table 1, Algorithm 1 is the algorithm proposed by Liu et al [11], Algorithm 2 is the algorithm proposed by Liu Hui-Juan et al. [9], and Algorithm 3 is our proposed algorithm.

Table 1 shows the average time consumption for processing different processing algorithms on the 50 images. As is shown in Table 1, the performance of our proposed algorithm is stable and efficiency.

5. Conclusions

This paper proposes a correction algorithm for the QR Code image perspective deformation, this algorithm makes fitting for the edge of bar code image in two kinds of circumstances. The edges composed by two searching graphics are constituted by midpoint Connection of corresponding searching graphics edges. Bar code edges which determined by a single VF graphics fit a straight line in the same criteria after perspective deformation according to the parallel lines adjacent to the smaller distance. We analyze the effect of image correction after the perspective deformation, and find that image recognition rate is very high. What's more, we compare our proposed algorithm with other algorithms proposed by other scholars, and the results show that our proposed algorithm has a good efficiency and higher accuracy.


[1] Kato, H., Tan, K. T. (2007). Pervasive 2D barcodes for camera phone applications, IEEE Trans. Pervasive Computing, 6 (4) 76-85.

[2] D'Angelo, A., Li, ZH. P., Barni, M. (2010). A full-reference quality metric for geometrically distorted Images, IEEE Trans. Image Processing, 19 (4) 867-881.

[3] Vijayan Asari, K., Kumar, S., Radhakrishnan, D. (1999). A new approach for nonlinear distortion correction in endoscopic images based on least squares estimation IEEE Trans. Medical image, 18 (4) 345-354.

[4] Tsai, R. Y. (1986). An efficient and accurate camera calibration technique for 3D machine vision, IEEE Trans. Computer Vision Pattern Recognition, p. 364-374, June.

[5] Baggenstoss, P. M. (2004). mage distortion analysis using polynomial series expansion, IEEE Trans. Pattern analysis and machine intelligence, 26 (11) Nov.

[6] Richetin, M., Dhome, M., Lapreste, J. T., Rives, G. (1999). Inverse perspective transform using zero curvature contour points : application to the localization of some generalized cylinders from a single view, IEEE Trans. Pattern analysis and machine intelligence, 13 (2), Feb.

[7] Kutulakos, K. N., Dyer, C. R. (1992). Recovering shape by purposive viewpoint adjustment, IEEE Proc. Computer vision and pattern recognition, p. 16-22.

[8] Kato, H., Tan, K. T. (2007). Pervasive 2D barcodes for camera phone applications, IEEE Pervasive computing, p. 76-85.

[9] Liu, H. J. (2006). Location and segmentation of quick response code image, Journal of electronic measurement and instrument, 1 (20) 32-35.

[10] Zh. Y. Fan, Fan, J., Zh. W. Liu. (2008). Recognition of PDF 417 barcode on captured imaages, Journal of Beijing institute of technology, 12 (28) 1088-1092.

[11] Zh, N., Liu, H. Y., You, Sun, N. (2010). Recognition of data matrix two-dimensional bar code based on mobile phones, Journal of image and graphics, 2, p. 287-293, Feb.

Jianhua Li, Yi-Wen Wang, YiJun Wang, Yi Chen, Guocheng Wang

Key Laboratory of Electronic Thin Films and Integrated Devices

University of Electronic Science and Technology of China

Chengdu China 610054

Information engineer School of Nanchang University

Nanchang China 330031)

{Jianhua703, wgch19890113}, {wangyijun007, chenyi261},

Table 1. Comparison of various algorithms

Algorithm       Image     Processing   Recognition
types            size      time/ms        rate

Algorithm 1   320 x 240      308           86%
              640 x 480      724           92%
Algorithm 2   320 x 240      500           94%
              640 x 480     1300           93%
Algorithm 3   320 x 240      359           96%
              640 x 480      410           94%
COPYRIGHT 2013 Digital Information Research Foundation
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Li, Jianhua; Wang, Yi-Wen; Wang, YiJun; Chen, Yi; Wang, Guocheng
Publication:Journal of Digital Information Management
Article Type:Report
Date:Jun 1, 2013
Previous Article:Parameters selection in the discrete particle swarm optimization algorithm solving gate and runway combinational optimization problem.
Next Article:Fault prediction of nonlinear system using time series novelty estimation.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters