代写 R C algorithm Scheme game graph Reconstruct Argorithm of 2D Barcode for Reading the QR Code on Cylindrical Surface

Reconstruct Argorithm of 2D Barcode for Reading the QR Code on Cylindrical Surface
Xiaochao Li, Zhifeng Shi, Donghui Guo, Shan He* Department of Electronic Engineering, Xiamen University, Xiamen, China *Correspondence to He Shan: heshan@xmu.edu.cn
Abstract—Traditional barcode recognition algorithm usually do not fit the cylindrical code but the one on flat surface. This paper proposes a low-cost approach to implement recognition of the curved QR codes printed on bottles or cans. Finder patterns are extracted from detecting module width proportion and corners of contours and an efficient direct least-square ellipse fitting method is employed to extract the elliptic edge and the boundary of code region. Then the code is reconstructed by direct mapping from the stereoscopic coordinates to the image plane using the 3D back- projection, thus the data of code could be restored. Compared with previous approaches, the proposed algorithm outperforms in not only the computation amount but also higher accuracy of the barcode recognition, whether in the flat or the cylindrical surface.
Keywords-QR codes extraction; Ellipse fitting; Cylindrical surface; 3D back-projection
I. INTRODUCTION
QR barcodes have received a wide range of attention since the day it appeared because of its excellent features, e.g. large storage capacity, high secrecy, strong resistance to damage and low cost [1]. In Figure 1, Each QR code symbol shall be constructed of nominally square modules set out in a regular square array and shall consist of an encoding region and function patterns, namely finder, separator, timing patterns and alignment patterns [2].
Figure 1. Structure of a QR code symbol
Two essential problems of code recognition are localization and correction. In the scenario of decoding QR-Codes on flat surface, paper [3] uses Hough transformation to locate the four corners of the barcode region, but it is simplified by assuming that the images just contain one code at the center without complex background; Paper [4] uses the page segmentation to
This study is supported by Fujian Provincial Department of Science & Technology( 2010H6026)，the Natural Science Foundation of China (61274133),
divide the image into blocks, and then applies the edge detection and eight lines of different directions to find the four corners of the code region; The system proposed in paper [5] applies the Canny edge detection and then found the external contours to extract the code region; Paper [6] utilizes the gradient feature of the code to locate the code regions. In a word, these methods can only be applied to codes printed on flat surface. While QR-Codes were printed on cans, conventional perspective transformation would lead to a correction error. Chu [1] extract the sample points on a skewed code by detecting the position of timing pattern modules, but the performance depends on unambiguous timing patterns.
This paper considers the problem of extracting QR-Codes from a cylindrical surface. We locate the finder pattern utilizing the feature of module proportion and estimate the boundary by direct least-square ellipse fitting. Moreover, the mapping of sample points in a cylindrical code is proposed.
The rest of this paper is organized as follows. Section II presents the overview. In Section III and IV, we propose the recognition algorithm. The experimental results are shown in Section V. Finally, we conclude this paper in Section VI.
II. OVERVIEW OF ALGORITHM
The overview of our algorithm is shown in Figure 2. Original images should be preprocessed with RGB conversion and thresholding. Then we locate the code from the finder patterns and boundary. Finder patterns are extracted by the feature of module width proportion and corners. After fitting the boundary, geometric correction is employed to acquire sample points. The final decoding could be accomplished.
input image
thresholding
image preprocessing
barcode localization
grid sampling
decoding
barcode decoding
RGB conversion
contour extraction
finder pattern detection
geometric correction
boundary location
Figure 2. QR code recognition system overview

III. BARCODE LOCALIZATION
Extraction of finder patterns is one of the major procedures for locating a QR code. In the preprocessing stage, source gray image is converted to binary image using the adaptive thresholding method [7] which is very robust and less computational complexity; Finder pattern candidates is located by roughly scanning and further confirmed by contour tracing [8] and corner detection.
A. Locating Finder Patterns
Three finder patterns located at the corners on the QR code have fixed ratio(1:1:3:1:1) of the widths of the black and white regions. While being scanned in arbitrary direction (as shown in Figure 3), these patterns are able to help quickly locating the QR code and speeding up the QR code reading.
Pi is set to be a corner if its s exceeds a predetermined threshold. This method has the advantage of avoiding false
alarms for superfluous corners on circular arcs [9].
We collect every point fitting the fixed ratio as a candidate and check the comers to identify the finder patterns. Figure 4 illustrates the locating results. The belt fitting the module width ratio(1:1:3:1:1) is marked between yellow lines while corners are displayed as green asterisks.
AB
A 11311
C
11311 11311
Figure 3. The feature of finder pattern
B C
Figure 4. Finder pattern locating through proposed criteria
Boundary Extraction
B.
We can obtain the candidates by roughly scanning in horizontal and vertical direction. Because of the noises, we compensate the distortion by calculating the corners of contours surrounding candidate points. There are three contours which can be described as a sequence of points(P{pi (xi,yi),i1,2,…,n}).Denote Sk(pi)asasmall curve segment of P, which is denoted by the region of support
between points pik and pik for some integer k, The covariance matrix C [9] of a curve segment Sk ( pi ) is given by:
After finding the three position detection patterns, we devise a corner searching algorithm to obtain the four corner points. It is necessary to model the boundaries as a precondition to determine the fourth corner under the circumstances that other three corner points have been located previously.
When QR codes are printed on cans, the circular profile of code in 3D space is projected onto image plane; one 2D ellipses could be obtained, which fit the equation as:
where
c [ 11
c12 [2k1 c21 c12
c [ 22
c c C11 12
are acquired, the least-square error
c21 c22 
(3)
i y](4)
1k 1k x2][ x]2
AX2 BXY CY2 DX EY F 0
(6)
On image plane, if a series of projected point
labelsXi,Yi,i1,2, ,K;
method can be used to estimate the parameters of the projected
ellipse. Fitzgibbon[11] presents an algorithm named a direct least-square ellipse fitting method to estimate these six parameters of the general ellipse equation in (6). There are mainly four steps to estimate these parameters by using K groups of position vectors:
1) Normalize the input data(Xi,Yi),i=1,2,…,K;
i
i
2k 1ik 2k 1ik
i 1k1k1k

ik ik
y]2 i
 xy][2k1 x][2k1
 ik
ii
i
1K 1K
1k 1k
 2k 1ik
y2][ i
 2k 1ik
xmaxX minX  ii
y  max Y   min Y  ii
 x i   X i  m x   x y Y my y
Two eigenvalues of the matrix C can be used to extract the shape information about the curve. The smaller eigenvalue s
can be utilized to measure the prominence of a corner for each boundary point [9].
s1[c c  (c c )2 4c2 ] (5) 21122 1122 12
i i
mx  K  X i1
 i1
my  K Y
i
2) Form the column vectors, where T means matrix or vector transpose;

T x[x1,x2, xK]
IV. GEOMETRIC CORRECTION
After obtaining boundary of a QR code, we transform the curved QR code to the square plane. Since QR codes might be perspective distorted because the camera can be held in a rotation or elevation angle. Back-projection [15] is employed to calculate the coordinates of sample points and reconstruct the code. On the scenario of using a linear camera, we can describe the perspective projection with a 3*4 matrix, called projection matrix[15]. The relationship between world Euclidean coordinate system and image Euclidean coordinate system is described as (9) [15]:
y[y,y,y]T 12K
T xx[x1x1,x2x2, xKxK] (7)
T xy[x1y1,x2y2, xKyK]
yy[yy,yy, yy]T 1122KK
3) Form the scatter matrix M and the constraint matrix R. S is a K*6 matrix, M and R are both 6×6 matrices.
Sxx,xy,yy,x,y,1 MSTS
0 0 2 0 0 0  
u m m m m X
   31 32 
0 1 0 0 0 0
R20 0 000 (8)
33 34  1
Where u and v are the coordinates of points on the image
0 0 0 0 0 0 
plane; (X, Y, Z) represent the position in the world Euclidean coordinate system; k denotes a scale factor, m to m34 are the
components of the projection matrix, denoted as M. Eliminate k; equation (9) is simplified as:
0 0 0 0 0 0 0 0 0 0 0 0
11

4)Calculate the eigenvalues and eigenvectors with
S R, and then find the eigenvector  corresponding to  x1
 x1u1
 y1u1
 z1u1 m11 u1 m12  
the only negative eigenvalue  , which is the estimation of the  
y1
z1
0
1000
1000
0 x y z 111
0 x y z 555
Equation (10) is now a linear equation with eleven unknowns; it could be solved by 6 points (ui , vi ) in the image plane with each peer of (Xi,Yi,Zi). In Figure 6，Four corners
(PP P P ) and two midpoints (P P ) could be appropriate to fix 1234 56
up the projection matrix M.
From the known projection matrix we can get the coordinates of the other sample points on the image plane. It is calculated by (11):
um11xm12ym13zm14 vm21xm22ym23zm24 m31xm32ym33z1 m31xm32ym33z1
One QR code on a bottle could be normalized as shown in Figure 6, then we utilize the perspective transformation with the coordinates of the six points to obtain the correct code. The radius of cylindrical surface, denoted by r in Figure 6, equals to semi-major axis of the ellipse fitted before. And then, the 3D coordinates of every sample points can be obtained.
13 14Y
 11 12 kvmmmm (9)
   21 22 23 24Z 1 m m m m  
T  vector   A,B,C,D,E,F . Therefore, the estimation of the   
 m 13 m14 m21   
six parameters in (5) is obtained.
From Figure 5, the position records in each part of contour x6 y6 z6

denoted as AB and CD are used to fit the curve of the elliptic   edge, and the rest records such as EF are used to evaluate the 
0
1 xv yv zvm v

0 0 0
z6u6  m22   u6  (10)
x6u6
11 11 1123 1
y6u6
precision of the fitting algorithm.  
m24  m  31  m32 
0 0 0 After acquiring these six parameters of the ellipse equation, 
1 xv yv zvm v 55 55 5533 5
the boundary of the code can be estimated.
In Figure 5, the boundary constructed by elliptical and straight segment is extracted and marked as green curves from the position data.
Figure 5. Boundary of code on cylindrical surface
(11)

o o’ PPPyo
220 200 180 160 140 120 100
80
this paper
BSE libqrencode
12 z5v
x o36
P PP4
y1
o’ r y
Figure 6. Perspective transformation of cylindrical code
In Figure 6, we utilize the perspective transformation with the matrix M to rectify the space distortion QR code with low complexity. The coordinates of sample points on image plane could be calculated from equation (11). This algorithm is able to correctly reconstruct the skewed QR code (sample points marked as yellow dots and reconstructed as Figure 7).
Figure 7. Reconstruct a QR code from sample points code.
V. EXPERIMENTAL RESULTS
In our implementation and testing, the above algorithm can fast and precisely locate the 2D barcode from the complex- background image, with limited computation power. Several experiments are introduced to evaluate the performance of this algorithm. 500 images containing codes are captured in different illumination with various rotation angles and then be resized from 64*64 to 1024*1024.
Figure 8 compares the accuracy for different algorithms with various elevation angles and QR-code versions. It shows that the proposed algorithm achieves the highest accuracy compared with others (BSE is the method of paper [1] while libqrencode is famous open-source QR decoder ).
Figure 9a shows that the execution time of paper[1] is much larger than that of our approach while code was printed on cylindrical surface. In Figure 9b, our approach also achieves a high performance.
The above results show that our approach is feasible for recognizing QR codes, especially those printed on cylindrical surface like cans or cups.
z1
A
u
260 240 220 200 180 160 140 120 100
80
64*64 256*256
512*512 1024*1024
Image Size
(a) Time consume of flat code with different image sizes.
this paper
BSE libqrencode
64*64 256*256
512*512 1024*1024
Image Size
(b) Time consume of cylindrical code with different image sizes.. Figure 8. Comparison of the time consume of different algorithms.
100 95 90 85 80 75 70
64*64 256*256
512*512 1024*1024
this paper
BSE libqrencode
Image Size
(a) Accuracy of cylindrical code with different image sizes.
Accuracy(%) Time Consume(ms) Time Consume(ms)

100 95 90 85 80 75 70
Figure 9. Comparison of accuracy of different algorithms.
Figure 10 demonstrates that our approach can correctly restore and extract a QR code in the complex color backgrounds. In addition, with 3D perspective projection, our approach can effectively reconstruct the skewed QR code.
Figure 10. Result of the code reconstruction in various environment.
VI. CONCLUSION
A method for QR-code extraction is presented in this paper and it is quite suitable to extract the finder patterns and code boundary. Compared to paper [1], the recognition of cylindrical code has less dependence on unambiguous timing patterns. The experimental results have shown that our approach is suitable for recognizing QR-codes on both flat and cylindrical surface with high performances.
REFERENCES
[1] C.-H. Chu, D.-N. Yang, Ya-Lan Pan, and M.-S. Chen, “Stabilization and Extraction of 2D Barcodes for Camera Phones” ACM Multimedia System Journal, Vol. 17, No. 2, pp. 113-133, March 2011.
[2] International Standard ISO/IEC 18004:2000(E).
[3] Hao Wang and Yanming Zou, “Camera Readable 2D Bar Codes Design and Decoding for Mobile Phones”, International Conference on Image Processing, 2006, pp. 469-472.
[4] Yu-Hsuan Chang, Chung-Hua Chu and Ming-Syan Chen, “A General Scheme for Extracting QR Code from a non-uniform background in Camre Phones and Applications”, Ninth IEEE International Symposium on Multimedia, 2007, pp. 123-130.
[5] Aidong Sun, Yan Sun and Caixing Liu, “The QR-code reorganization in illegible snapshots taken by mobile phones”, International Conference on Computational Science and its Applications, 2007
[6] Ouaviani,E., Pavan,A., Bottazzi,M., Brunelli,E., and Guerrero,M., “A common image processing framework for 2D barcode reading”, Seventh International Conference on Image Processing and Its Applications. 1999. pp. 652-655.
[7] Derek Bradley and Gerhard Roth, “Adaptive Thresholding Using the Integral Image”, Journal of Graphics, GPU, & Game Tools, Volume 12, number 2/2007, pp. 13-21.
[8] Fu Chang and Chun-Jen Chen, “A Component-Labeling Algorithm Using Contour Tracing Technique”, Seventh International Conference on Document Analysis and Recognition, 2003.
[9] Du-Ming Tsai, H.-T. Hou, H.-J. Su, “Boundary-based corner detection using eigenvalues of covariance matrices”, Pattern Recognition Letters, v 20, n1, Jan 1999, pp. 31-40.
[10] Liao Zhao-lai; Huang Ting-lei; Wang Rui; Zhou Xiao-yan; , “A method of image analysis for QR code recognition,” Intelligent Computing and Integrated Systems (ICISS), 2010 International Conference on , vol., no., pp.250-253, 22-24 Oct. 2010
[11] A. Fitzgibbon, M. Pilu, and R. B. Fisher, “Direct least square fitting of ellipses,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 21, no. 5, pp. 476– 480, May 1999..
[12] Gonzalez and Woods,”Digital Image Processing, Second Edition”, Prentice-Hall, 2002
[13] Sun Ming, Fu Long-sheng, Yang Xin-ting and Zhang Shu-huai, “Image Analysis Method for QR Code’s Automatic Recognition”, Journal of University of Electronic Science and Technology of China, Vol.38， No.6，2009
[14] Keiji Taniguchi, “The Basics of Digital Image Processing”. Science Press, 2001
[15] Milan Sonka, Vaclav Hlavac, Roger Boyle,”Image Processing, Analysis and Machine Vision”, Thomson Learning, Third Edition, 2008
this paper
BSE libqrencode
64*64 256*256
512*512 1024*1024
Image Size
(b) Accuracy of flat code with different image sizes.
Accuracy(%)