# 2D Barcode Image Decoding

Authors: Jeng-An Lin; Chiou-Shann Fuh
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Barcode technology is one of the most important parts of Automatic Identification and Data Capture (AIDC). Quick Response code (QR code) is one of the most popular types of two-dimensional barcodes. How to decode various QR code images efficiently and accurately is a challenge. In this paper, we revise the traditional decoding procedure by proposing a serial of carefully designed preprocessing methods. The decoding procedure consists of image binarization, QR code extraction, perspective transformation and resampling, and error correction. By these steps, we can recognize different types of QR code images. The experiment results show that our method has better accuracy than Google open-source 1D/2D barcode image processing library Zxing-2.1. Moreover, we evaluate the execution time for different-size images. Our method can decode these images in real time.


---

## Body

## 1. Introduction

Barcode technology is one of the most important parts of Automatic Identification and Data Capture (AIDC); we can obtain decoded data through analysis of a barcode. According to the encoding type of barcodes, we divide barcode into two categories: one-dimensional barcode and two-dimensional barcode. One-dimensional barcode typically consists of varying the widths and spacings of parallel lines. Moreover, two-dimensional barcode is a graphical image that stores information both horizontally and vertically. Two-dimensional barcode compared with the one-dimensional barcode has the following advantages:(1) high data capacity; (2) no additional storages; (3) error correction ability.Quick Response code (QR code) is one of the most popular types of two-dimensional barcodes developed in Japan by Denso Corporation in 1994. Although QR code was first designed for the automotive industry, QR codes are now used over much wider range of applications, including commercial tracking, transport ticketing, website Uniform Resource Locator (URL), and identity verification. QR code has several advantages. First, QR code has strong error correcting capability, which can restore 30% data for the maximum error correction level. Second, QR code can be scanned from any direction because the proportion of position detection patterns is not changed with the scanning direction. Third, QR code supports different encoding types and versions. We can choose an appropriate encoding type and version to reduce the size of QR code image.Although there exist many commercial programs for QR code decoding, inventing more robust QR code decoding strategy still attracts many attentions from researchers. Many works are proposed recently. In [1, 2], Belussi and Hirata proposed a fast component-based two-stage approach for detecting QR codes in arbitrarily acquired images. Moreover Ohbuchi et al. [3] and Liu et al. [4] focused on enabling mobile phone to recognize QR code under poor conditions in real time. For decoding QR code image correctly and efficiently, we confront some challenges as follows. (1) When we capture QR code images using a phone camera in nonuniform background or uneven light, it might affect the decoded result. (2) The shooting angle might cause perspective distortion; to restore a distorted QR image is an important issue for decoding QR code images. (3) Decoding QR code images needs a sequence of sophisticated image processing. How to reduce the complexity of image processing and maintain the decoding accuracy rate is also a challenge.In this paper, we focus on revising preprocessing methods in the traditional decoding procedure that is straightforward but still have much improving potential to overcome the above challenges. The decoding steps consist of image binarization, QR code extraction, perspective transformation and resampling, and error correction. In image binarization, we use a modified local threshold method to resolve the nonuniform background and uneven light problems. Our QR code extraction algorithm uses the position detection patterns of QR code efficiently and accurately to locate the QR code position. After locating the QR code position, we restore a distorted image through perspective transformation and resample. Finally, we get the corrected data by Reed-Solomon error correction algorithm.


## 2. Related Work

QR code recognition technology has been studied in past years. We can simply divide the recognition into two steps, image preprocessing and QR code extraction.In image preprocessing, some researchers focus on image denoising [5] or camera shaking [6]. In order to improve the performance of low resolution QR-code recognition, a previous work [7] uses the super-resolution technique that generates a high resolution image from multiple low-resolution images. Moreover, some researchers use different binarizations to improve the nonuniform background and uneven light problems [8, 9].In QR code extraction, researchers propose several different methods to locate and extract the QR code of images. Some researchers use the feature of finder pattern to find rough QR code position [10–12]. After estimating the QR code’s four corners using the rough QR code position, they effectively extract the QR code of images. In research [6, 13], they use edge detection to find possible rough barcode area. Then, morphological dilation and closing are used to generate more compact regions. Finally, the position of QR code of images can be detected.Although these researches have their contributions, there are some shortcomings we can improve. In [5], researchers only focus on image denosing, but locating QR code position is an important part of QR decoding. They did not propose their method to process this problem. Previous works [6, 7, 10] need enormous calculation. Their methods are difficult to decode QR code image in real time. In research [9], their binarizaiton method needs to know the version of QR code in advance. In this paper, we propose a decoding method to improve the deficiencies in previous work.


## 3. Background

### 3.1. Perspective Transformation

QR code images may be distorted due to camera perspective projection. Therefore, we use perspective transformation to restore the distorted QR code images. The general representation of a perspective transformation [14] is
(1)[x′y′w′]=[uv1][a11a12a13a21a22a23a31a32a33],
where x=x′/w′ and y=y′/w′. In (1), each original coordinate (u, v) can be transformed to a new coordinate (x, y) by using the 3 by 3 matrix. Based on (1), x and y can be written as
(2)x=x′w′=a11u+a21v+a31a13u+a23v+a33,y=y′w′=a12u+a22v+a32a13u+a23v+a33.Without loss of generality, the 3 by 3 matrix can be normalized, so thata33=1. Equation (2) can be rewritten as
(3)x=a11u+a21v+a31-a13ux-a23vx,y=a12u+a22v+a32-a13uy-a23vy.Applying four pairs of correspondence points to (3), we can get a linear system as follows:
(4)[u0u1u2u30000v0v1v2v30000111100000000u0u1u2u30000v0v1v2v300001111-u0x0-u1x1-u2x2-u3x3-u0y0-u1y1-u2y2-u3y3-v0x0-v1x1-v2x2-v3x3-v0y0-v1y1-v2y2-v3y3]×[a11a21a31a12a22a32a13a23]=[x0x1x2x3y0y1y2y3].The value of unknown coefficients will be determined by solving the linear system in (4).


### 3.2. Reed-Solomon Error Correction

Reed-Solomon codes are nonbinary cyclic error-correcting codes [15]. In QR code decoding procedures, we might obtain some error information because of distorted images or inappropriate binarization. Reed-Solomon codes help us to correct the error information. The general decoding algorithm [16] of RS codes consists of computing the syndromes, determining an error locator polynomial, and solving the error values.For computing the syndromes, the received message is viewed as the coefficients of a polynomialS(x):
(5)S(x)=∑i=0n-1rixi,
where ri is the received message at position i. Therefore, the syndromes (S0,S1,…,S2t-1) are defined as
(6)S0=S(α0),S1=S(α1),…,S2t-1=S(α2t-1),
where 2t is equal to the number of codewords available for error correction and α is the primitive element on the Galois field. Syndrome polynomial is defined as(7)S(x)=∑i=02t-1Sixi.After computing syndrome polynomial, we use Euclidean algorithm to construct the error locator polynomial and error evaluator polynomial. Error locator polynomial can be used to find the error positions. Error evaluator polynomial is used to find the error values. The Euclidean algorithm is based on the key equation in(8)Ω(x)=S(x)Λ(x)(modx2t).Given onlyS(x) and t, we want to obtain the error locator polynomialΛ(x) and the error evaluator polynomial Ω(x). Equation (8) means that
(9)θ(x)x2t+S(x)Λ(x)=Ω(x)
for some polynomial θ(x). Finally, we can use Euclidean algorithm to generate the error locator polynomial and error evaluator polynomial.For solving the error values, Forney's algorithm is selected. The error values for a Reed-Solomon code are computed by(10)eik=-Ω(Xk-1)Λ′(Xk-1),
where eik is the corrected value at position ik; Xk-1 is the root ofΛ(x) at position k; and Λ′(x) is the formal derivative ofΛ(x). By (10), we obtain the corrected data of QR code images.


## 3.1. Perspective Transformation

QR code images may be distorted due to camera perspective projection. Therefore, we use perspective transformation to restore the distorted QR code images. The general representation of a perspective transformation [14] is
(1)[x′y′w′]=[uv1][a11a12a13a21a22a23a31a32a33],
where x=x′/w′ and y=y′/w′. In (1), each original coordinate (u, v) can be transformed to a new coordinate (x, y) by using the 3 by 3 matrix. Based on (1), x and y can be written as
(2)x=x′w′=a11u+a21v+a31a13u+a23v+a33,y=y′w′=a12u+a22v+a32a13u+a23v+a33.Without loss of generality, the 3 by 3 matrix can be normalized, so thata33=1. Equation (2) can be rewritten as
(3)x=a11u+a21v+a31-a13ux-a23vx,y=a12u+a22v+a32-a13uy-a23vy.Applying four pairs of correspondence points to (3), we can get a linear system as follows:
(4)[u0u1u2u30000v0v1v2v30000111100000000u0u1u2u30000v0v1v2v300001111-u0x0-u1x1-u2x2-u3x3-u0y0-u1y1-u2y2-u3y3-v0x0-v1x1-v2x2-v3x3-v0y0-v1y1-v2y2-v3y3]×[a11a21a31a12a22a32a13a23]=[x0x1x2x3y0y1y2y3].The value of unknown coefficients will be determined by solving the linear system in (4).


## 3.2. Reed-Solomon Error Correction

Reed-Solomon codes are nonbinary cyclic error-correcting codes [15]. In QR code decoding procedures, we might obtain some error information because of distorted images or inappropriate binarization. Reed-Solomon codes help us to correct the error information. The general decoding algorithm [16] of RS codes consists of computing the syndromes, determining an error locator polynomial, and solving the error values.For computing the syndromes, the received message is viewed as the coefficients of a polynomialS(x):
(5)S(x)=∑i=0n-1rixi,
where ri is the received message at position i. Therefore, the syndromes (S0,S1,…,S2t-1) are defined as
(6)S0=S(α0),S1=S(α1),…,S2t-1=S(α2t-1),
where 2t is equal to the number of codewords available for error correction and α is the primitive element on the Galois field. Syndrome polynomial is defined as(7)S(x)=∑i=02t-1Sixi.After computing syndrome polynomial, we use Euclidean algorithm to construct the error locator polynomial and error evaluator polynomial. Error locator polynomial can be used to find the error positions. Error evaluator polynomial is used to find the error values. The Euclidean algorithm is based on the key equation in(8)Ω(x)=S(x)Λ(x)(modx2t).Given onlyS(x) and t, we want to obtain the error locator polynomialΛ(x) and the error evaluator polynomial Ω(x). Equation (8) means that
(9)θ(x)x2t+S(x)Λ(x)=Ω(x)
for some polynomial θ(x). Finally, we can use Euclidean algorithm to generate the error locator polynomial and error evaluator polynomial.For solving the error values, Forney's algorithm is selected. The error values for a Reed-Solomon code are computed by(10)eik=-Ω(Xk-1)Λ′(Xk-1),
where eik is the corrected value at position ik; Xk-1 is the root ofΛ(x) at position k; and Λ′(x) is the formal derivative ofΛ(x). By (10), we obtain the corrected data of QR code images.


## 4. The Proposed Method

We design a QR code recognition procedure for decoding QR code accurately and rapidly. First, we propose a new local binarization method to overcome images with uneven light and nonuniform background problems. And then we use three finder patterns and an alignment pattern of QR code efficiently to locate the QR code position. After locating QR code position, we resample QR code image by perspective transformation. Finally, we get the corrected data by Reed-Solomon error correction algorithm. Figure1 illustrates the procedure.Figure 1
QR code decoding procedure.


### 4.1. Binarization

Binarization is an important process for accurately recognizing black-and-white module in QR code images. Therefore, we propose a new binarization method to improve the recognition of images with nonuniform background and uneven light. Our method is a local threshold algorithm based on Sauvola’s method [8]. We decompose each image into a series of blocks and then calculate a threshold T1 for each block using
(11)T1(x,y)=mean(x,y)×[1+(standarddeviation(x,y)R)].The defaultR is 1250. For each block, we convolve with the kernel in (12) to calculate a threshold T2. By using the threshold T2, we split each block into bright area and dark area. Figures 2 and 3 shows that our method can achieve the same performance with less computing cost, compared with modified Sauvola’s method [8]:
(12)C=110[111121111],(13)f(A,B,C)=(B·x-A·x)(C·y-A·y)-(B·y-A·y)(C·x-A·x).Figure 2
An uneven light image [17].Figure 3
Binary image using our method.


### 4.2. Estimating Version

QR code extraction is responsible for searching QR code area in images. QR code extraction consists of searching finder patterns, estimating version, and searching alignment pattern. We use the proportion of finder patterns to locate the QR code position. After searching three finder patterns, we use the distance between these patterns to estimate version. Finally, we develop a connected-component method to search alignment pattern accurately.


#### 4.2.1. Searching Finder Patterns

In searching finder patterns, we need to determine the upper left, lower left, and upper right finder patterns in the QR code. First, we scan the binary image horizontally to find all points matching the ratios 1 : 1 : 3 : 1 : 1. For each point matching the ratios, we check its vertical direction. Finally, we have collected all points in images matching the ratios 1 : 1 : 3 : 1 : 1 both horizontally and vertically.After collecting points, we merge points in the same finder pattern. If the number of finder patterns is more than three, we filter out some inappropriate points. First, we calculate the angle between three points.  If the maximum angle is greater than a thresholdT1 or the minimum angle is less than a threshold T2, the points will be filtered. And then we identify the direction of finder patterns. The maximum angle corresponding to the finder pattern is the upper left finder pattern. Finally, we use cross product in (13) to determine the lower left and upper right finder patterns, where A is the upper left finder pattern; B and C are the other finder patterns; and A·x and A·y represent the x and y coordinate of A. If f(A,B,C)<0, then B is upper right finder pattern, and C is lower left finder pattern.


#### 4.2.2. Estimating Version

After searching three finder patterns, we can estimate version using module size and the distance between two finder patterns. Module size can be calculated by(14)Module_size=Widthoffinderpattern7.
We calculate version by
(15)Version=((Euclidean_distance(f1,f2)/Module_size)-10)4,
where f1 is upper left finder pattern and f2 is upper right finder pattern. We can get rough version by (15), but (15) misjudges the version when QR code image is rotated. We overestimate the width of finder pattern in rotated image in Figure 4.Figure 4
Red line is the width of finder pattern, and blue line is the estimated width.As a result, we underestimate the version of QR code image. Therefore, we revise (15) to be(16)Version=(Euclidean_distance(f1,f2)/Module_size*cosθ-10)4,
where θ is the angle between blue line and red line in Figure 4. We estimate version more accurately by (16) and thus before perspective transformation.


### 4.3. Searching Alignment Pattern

Low resolution image or inappropriate binarization method will result in the deformation of alignment pattern. Therefore, we propose a new searching alignment method to overcome the problem. First, we roughly locate the alignment pattern using three finder patterns. Moreover, we extract subimage with a specified radius in Figure5. We calculate the connected component in the subimage, both black pixels and white pixels. After calculating the connected component, we get two images in Figures 6(b) and 6(c).Figure 5
We extract blue rectangle to find the alignment pattern (radius = 30 pixels).(a) Extracted image in Figure5; (b) found connected components of black pixels; (c) found connected components of white pixels.
(a)
(b)
(c)For each connected component of black pixelCi in Figure 6(b), we check its border pixels. If all border pixels are adjacent to the same connected component of white pixel Cj′ in Figure 6(c), then we check all border pixels in Cj′. Once all border pixels in Cj′ are adjacent to the same black pixel connected component Ck in Figure 6(b), these components possibly contain alignment pattern. Finally, we calculate the centroid of Ci as the centroid of alignment pattern.


### 4.4. Perspective Transformation

After estimating the version and locating the centroid of three finder patterns and alignment pattern, we resample QR code image through perspective transformation. The eight coordinates can be presented as shown in Table1.Table 1
Eight coordinates used for perspective transformation (D=17+4*version).
Function patternof QR code
Originalcoordinate
Normalizedcoordinate
Upper left finder pattern
(x0, y0)
(3.5, 3.5)
Upper right finder pattern
(x1, y1)
(D-3.5, 3.5)
Lower left finder pattern
(x2, y2)
(3.5,D-3.5)
Lower right alignment pattern
(x3, y3)
(D-6.5, D-6.5)To avoid the appearance of cracks and holes, we use inverse warping in perspective transformation. First, we calculate a transformationT from normalized coordinate to original coordinate. For each pixel in normalize image, we calculate its corresponding location in original image using the transformation T. Finally, we copy the pixel value of original image to the normalized image. Table 2 shows our resampling results.Table 2
Result of resampling.
Original image
Normalized image


## 4.1. Binarization

Binarization is an important process for accurately recognizing black-and-white module in QR code images. Therefore, we propose a new binarization method to improve the recognition of images with nonuniform background and uneven light. Our method is a local threshold algorithm based on Sauvola’s method [8]. We decompose each image into a series of blocks and then calculate a threshold T1 for each block using
(11)T1(x,y)=mean(x,y)×[1+(standarddeviation(x,y)R)].The defaultR is 1250. For each block, we convolve with the kernel in (12) to calculate a threshold T2. By using the threshold T2, we split each block into bright area and dark area. Figures 2 and 3 shows that our method can achieve the same performance with less computing cost, compared with modified Sauvola’s method [8]:
(12)C=110[111121111],(13)f(A,B,C)=(B·x-A·x)(C·y-A·y)-(B·y-A·y)(C·x-A·x).Figure 2
An uneven light image [17].Figure 3
Binary image using our method.


## 4.2. Estimating Version

QR code extraction is responsible for searching QR code area in images. QR code extraction consists of searching finder patterns, estimating version, and searching alignment pattern. We use the proportion of finder patterns to locate the QR code position. After searching three finder patterns, we use the distance between these patterns to estimate version. Finally, we develop a connected-component method to search alignment pattern accurately.


### 4.2.1. Searching Finder Patterns

In searching finder patterns, we need to determine the upper left, lower left, and upper right finder patterns in the QR code. First, we scan the binary image horizontally to find all points matching the ratios 1 : 1 : 3 : 1 : 1. For each point matching the ratios, we check its vertical direction. Finally, we have collected all points in images matching the ratios 1 : 1 : 3 : 1 : 1 both horizontally and vertically.After collecting points, we merge points in the same finder pattern. If the number of finder patterns is more than three, we filter out some inappropriate points. First, we calculate the angle between three points.  If the maximum angle is greater than a thresholdT1 or the minimum angle is less than a threshold T2, the points will be filtered. And then we identify the direction of finder patterns. The maximum angle corresponding to the finder pattern is the upper left finder pattern. Finally, we use cross product in (13) to determine the lower left and upper right finder patterns, where A is the upper left finder pattern; B and C are the other finder patterns; and A·x and A·y represent the x and y coordinate of A. If f(A,B,C)<0, then B is upper right finder pattern, and C is lower left finder pattern.


### 4.2.2. Estimating Version

After searching three finder patterns, we can estimate version using module size and the distance between two finder patterns. Module size can be calculated by(14)Module_size=Widthoffinderpattern7.
We calculate version by
(15)Version=((Euclidean_distance(f1,f2)/Module_size)-10)4,
where f1 is upper left finder pattern and f2 is upper right finder pattern. We can get rough version by (15), but (15) misjudges the version when QR code image is rotated. We overestimate the width of finder pattern in rotated image in Figure 4.Figure 4
Red line is the width of finder pattern, and blue line is the estimated width.As a result, we underestimate the version of QR code image. Therefore, we revise (15) to be(16)Version=(Euclidean_distance(f1,f2)/Module_size*cosθ-10)4,
where θ is the angle between blue line and red line in Figure 4. We estimate version more accurately by (16) and thus before perspective transformation.


## 4.2.1. Searching Finder Patterns

In searching finder patterns, we need to determine the upper left, lower left, and upper right finder patterns in the QR code. First, we scan the binary image horizontally to find all points matching the ratios 1 : 1 : 3 : 1 : 1. For each point matching the ratios, we check its vertical direction. Finally, we have collected all points in images matching the ratios 1 : 1 : 3 : 1 : 1 both horizontally and vertically.After collecting points, we merge points in the same finder pattern. If the number of finder patterns is more than three, we filter out some inappropriate points. First, we calculate the angle between three points.  If the maximum angle is greater than a thresholdT1 or the minimum angle is less than a threshold T2, the points will be filtered. And then we identify the direction of finder patterns. The maximum angle corresponding to the finder pattern is the upper left finder pattern. Finally, we use cross product in (13) to determine the lower left and upper right finder patterns, where A is the upper left finder pattern; B and C are the other finder patterns; and A·x and A·y represent the x and y coordinate of A. If f(A,B,C)<0, then B is upper right finder pattern, and C is lower left finder pattern.


## 4.2.2. Estimating Version

After searching three finder patterns, we can estimate version using module size and the distance between two finder patterns. Module size can be calculated by(14)Module_size=Widthoffinderpattern7.
We calculate version by
(15)Version=((Euclidean_distance(f1,f2)/Module_size)-10)4,
where f1 is upper left finder pattern and f2 is upper right finder pattern. We can get rough version by (15), but (15) misjudges the version when QR code image is rotated. We overestimate the width of finder pattern in rotated image in Figure 4.Figure 4
Red line is the width of finder pattern, and blue line is the estimated width.As a result, we underestimate the version of QR code image. Therefore, we revise (15) to be(16)Version=(Euclidean_distance(f1,f2)/Module_size*cosθ-10)4,
where θ is the angle between blue line and red line in Figure 4. We estimate version more accurately by (16) and thus before perspective transformation.


## 4.3. Searching Alignment Pattern

Low resolution image or inappropriate binarization method will result in the deformation of alignment pattern. Therefore, we propose a new searching alignment method to overcome the problem. First, we roughly locate the alignment pattern using three finder patterns. Moreover, we extract subimage with a specified radius in Figure5. We calculate the connected component in the subimage, both black pixels and white pixels. After calculating the connected component, we get two images in Figures 6(b) and 6(c).Figure 5
We extract blue rectangle to find the alignment pattern (radius = 30 pixels).(a) Extracted image in Figure5; (b) found connected components of black pixels; (c) found connected components of white pixels.
(a)
(b)
(c)For each connected component of black pixelCi in Figure 6(b), we check its border pixels. If all border pixels are adjacent to the same connected component of white pixel Cj′ in Figure 6(c), then we check all border pixels in Cj′. Once all border pixels in Cj′ are adjacent to the same black pixel connected component Ck in Figure 6(b), these components possibly contain alignment pattern. Finally, we calculate the centroid of Ci as the centroid of alignment pattern.


## 4.4. Perspective Transformation

After estimating the version and locating the centroid of three finder patterns and alignment pattern, we resample QR code image through perspective transformation. The eight coordinates can be presented as shown in Table1.Table 1
Eight coordinates used for perspective transformation (D=17+4*version).
Function patternof QR code
Originalcoordinate
Normalizedcoordinate
Upper left finder pattern
(x0, y0)
(3.5, 3.5)
Upper right finder pattern
(x1, y1)
(D-3.5, 3.5)
Lower left finder pattern
(x2, y2)
(3.5,D-3.5)
Lower right alignment pattern
(x3, y3)
(D-6.5, D-6.5)To avoid the appearance of cracks and holes, we use inverse warping in perspective transformation. First, we calculate a transformationT from normalized coordinate to original coordinate. For each pixel in normalize image, we calculate its corresponding location in original image using the transformation T. Finally, we copy the pixel value of original image to the normalized image. Table 2 shows our resampling results.Table 2
Result of resampling.
Original image
Normalized image


## 5. Experiment Result

Experimental environment:(1)
CPU: Intel core i5-3210M CPU 2.50 GHz,(2)
memory: 4 GB,(3)
OS: Windows 7,(4)
programming language: Java.In this section, we conduct several experiments to evaluate the performance. First, we compare the accuracy between our QR code decoding algorithm and 2D barcode image processing library (Zxing) [17]. The experiment result shows that our decoding algorithm has better accuracy than Zxing. And then we use different sizes of images to evaluate the decoding time. The experiment results show our method decoding images in real time. Moreover, we implement a QR code scanner on Android phone. We test the decoding ability of some defaced images. The experiment result shows that our QR code scanner successfully decodes these images.


### 5.1. Image Source

Our test images in Table3  are from Google open-source 1D/2D barcode image processing library Zxing-2.1 [17]. The images are classified into six data sets, a total of 178 images. The first data set contains low resolution QR code images. The second data set contains trademark QR code image. The skew QR code images are included in the third data set. The fourth data set contains distorted QR code images. Uneven light QR code images are included in the fifth data sets. The sixth data set contains rotated QR code images.Table 3
Test images.
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6


### 5.2. Accuracy Analysis

We compare the accuracy between our decoding algorithm and Google open-source 1D/2D barcode image processing library Zxing-2.1 [17]. Table 4 shows the results.Table 4
Comparison between our method and Zxing-2.1.
Our method
Zxing-2.1
Set 1
20
/
20
17
/
20
Set 2
32
/
34
30
/
34
Set 3
38
/
42
38
/
42
Set 4
36
/
48
36
/
48
Set 5
19
/
19
19
/
19
Set 6
15
/
15
15
/
15
Total
160
/
178
155
/
178In 178 test images, there are 8 images in Table5 that we successfully recognize and Zxing-2.1 fails. Moreover, there are 3 images in Table 6 that Zxing-2.1 successfully recognizes and our method fails.Table 5
Images we successfully recognize and Zxing-2.1 fails.Table 6
Images Zxing-2.1 successfully recognizes and our method fails.The accuracy of our method is about 90% and that of Zxing-2.1 is only 87%. Our method has better recognition rate in Sets 1 and 2. Zxing-2.1 cannot accurately locate the alignment pattern because of the low resolution or inappropriate binarization. Our method improves the problem, so that we have better result.


### 5.3. Efficiency Analysis

In this section, we show the execution time between our method and Zxing for decoding different sizes of QR code images. We use four different sizes of QR code images to calculate the execution time. Each size contains five images. Table7 shows the results.Table 7
The execution time between our method and Zxing for decoding different-size images.
Our method
Zxing
3
20
*
240
214 ms
139 ms
640
*
480
312 ms
190 ms
800
*
600
375 ms
237 ms
1024
*
768
448 ms
264 msOur method needs more decoding time than Zxing, but our method still can decode QR code images in real time. We only need 448 milliseconds for decoding resolution1024*768 pixel images.


### 5.4. Comparison of Different Barcode Applications

We implement a QR code scanner on Android phone. Moreover, we collect four popular barcode scanners from Google Play and iOS market. We compare the decoding ability of some defaced images. Table8 shows the result. Our application can successfully decode all test images. Our application has the best result of these applications in these images. The reason for our better results is that two steps of the binarization stage in our method will get a more appropriate threshold to split each block into bright area and dark area. Moreover compared with current applications, our new searching alignment method could handle a large deformation of alignment pattern as the result of inappropriate binarization and low resolution which can be observed in sample images.Table 8
Comparison of different barcode scanner applications.
Our
Zxing [17]
Quickmark [18]
Bakodo [19]
BarCodeScan [20]
O
O
X
X
X
O
X
X
X
X
O
X
O
O
O
O
X
O
O
O
O
O
O
O
X
O
O
O
O
X
O
X
O
O
O
O
X
O
O
O
O
X
X
X
X
O
X
X
X
X
Total
10/10
3/10
6/10
6/10
4/10


## 5.1. Image Source

Our test images in Table3  are from Google open-source 1D/2D barcode image processing library Zxing-2.1 [17]. The images are classified into six data sets, a total of 178 images. The first data set contains low resolution QR code images. The second data set contains trademark QR code image. The skew QR code images are included in the third data set. The fourth data set contains distorted QR code images. Uneven light QR code images are included in the fifth data sets. The sixth data set contains rotated QR code images.Table 3
Test images.
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6


## 5.2. Accuracy Analysis

We compare the accuracy between our decoding algorithm and Google open-source 1D/2D barcode image processing library Zxing-2.1 [17]. Table 4 shows the results.Table 4
Comparison between our method and Zxing-2.1.
Our method
Zxing-2.1
Set 1
20
/
20
17
/
20
Set 2
32
/
34
30
/
34
Set 3
38
/
42
38
/
42
Set 4
36
/
48
36
/
48
Set 5
19
/
19
19
/
19
Set 6
15
/
15
15
/
15
Total
160
/
178
155
/
178In 178 test images, there are 8 images in Table5 that we successfully recognize and Zxing-2.1 fails. Moreover, there are 3 images in Table 6 that Zxing-2.1 successfully recognizes and our method fails.Table 5
Images we successfully recognize and Zxing-2.1 fails.Table 6
Images Zxing-2.1 successfully recognizes and our method fails.The accuracy of our method is about 90% and that of Zxing-2.1 is only 87%. Our method has better recognition rate in Sets 1 and 2. Zxing-2.1 cannot accurately locate the alignment pattern because of the low resolution or inappropriate binarization. Our method improves the problem, so that we have better result.


## 5.3. Efficiency Analysis

In this section, we show the execution time between our method and Zxing for decoding different sizes of QR code images. We use four different sizes of QR code images to calculate the execution time. Each size contains five images. Table7 shows the results.Table 7
The execution time between our method and Zxing for decoding different-size images.
Our method
Zxing
3
20
*
240
214 ms
139 ms
640
*
480
312 ms
190 ms
800
*
600
375 ms
237 ms
1024
*
768
448 ms
264 msOur method needs more decoding time than Zxing, but our method still can decode QR code images in real time. We only need 448 milliseconds for decoding resolution1024*768 pixel images.


## 5.4. Comparison of Different Barcode Applications

We implement a QR code scanner on Android phone. Moreover, we collect four popular barcode scanners from Google Play and iOS market. We compare the decoding ability of some defaced images. Table8 shows the result. Our application can successfully decode all test images. Our application has the best result of these applications in these images. The reason for our better results is that two steps of the binarization stage in our method will get a more appropriate threshold to split each block into bright area and dark area. Moreover compared with current applications, our new searching alignment method could handle a large deformation of alignment pattern as the result of inappropriate binarization and low resolution which can be observed in sample images.Table 8
Comparison of different barcode scanner applications.
Our
Zxing [17]
Quickmark [18]
Bakodo [19]
BarCodeScan [20]
O
O
X
X
X
O
X
X
X
X
O
X
O
O
O
O
X
O
O
O
O
O
O
O
X
O
O
O
O
X
O
X
O
O
O
O
X
O
O
O
O
X
X
X
X
O
X
X
X
X
Total
10/10
3/10
6/10
6/10
4/10


## 6. Conclusion

In this paper, our carefully designed preprocessing methods improve the accuracy of the traditional decoding procedure. Although refined steps improve accuracy at the expense of increased decoding time [21], the QR code still can meet the real-time requirement. The decoding steps consist of image binarization, QR code extraction, perspective transformation, and error correction. We efficiently resolve the non-uniform background and uneven light problems by using a modified local threshold algorithm. In QR code extraction, we use the position detection patterns of QR code efficiently and accurately to locate the QR code position. After locating the QR code position, we restore a distorted image through perspective transformation and resampling. Finally, we get the corrected data by Reed-Solomon error correction algorithm.In the experiment, we compare the accuracy between our method and Zxing. The experiment result shows our method to have better accuracy than Zxing. Moreover, we use different-size images to calculate the execution time. The experiment shows that our method can efficiently decode images. All images can be decoded in less than one second.



---

*Source: 848276-2013-12-12.xml*