Blur Estimation for Barcode Recognition in Out-of-Focus Images (Image Analysis)

Abstract

Recently, with the popularity of hand-held devices with camera, many applications requiring barcode identification in images have appeared. There are several problems with these applications because of the limitation of camera capability. Among them, heavily blur problems are the most significant and popular. In this paper, we propose a novel approach to estimate blur for recognising barcodes in heavily blurred images. With this approach, we are able to extract correctly the barcode from heavily blurred images, which existing methods cannot.

Keywords: Blur estimation, Barcode identification, pattern recognition, heavily blurred images.

Introduction

Recently, with the popularity of mobile phones aimed with integrated camera, there is a need for recognising barcodes from images captured from these devices. However, due to the limitation of controlling focus lens, the captured images are often heavily distorted by the out of focus blur. Therefore, it is very hard to extract the barcode from these heavily distorted images with existing methods proposed for conventional barcode reader. There are several approaches reported in literature for solving the blur problem in barcode recognition, e.g. edge detection-based approach [3,5,6], inverse-problem-based approach [2] and statistical machine learning techniques[7]. These techniques cannot work well for heavily distorted signals [7] because it is difficult to extract features such as edges and peaks of the bars and spaces from these signals.


In this paper, we propose a novel approach to estimate blur for recognising barcodes in heavily blurred images. We first estimate the ranges of blur parameters, and then search through these ranges with sampled values to find the parameters that allow us to extract correctly the most number of barcode values along the scan lines of the barcode image. For each scan line, we generate candidate signals by utilising the structure of the barcode, blur them with blur parameters in process, and compare with the distorted signal of the scan line to find the best matched candidate signal. The checksum of the barcode is used to verify the candidate. With this approach, we are able to extract correctly the barcode from heavily blurred images, which existing methods cannot.

The paper is organised as follows. In Section 2, barcode representation is described in details. The emphasis of the paper is in Section 3 which presents related works. Subsequently, our proposed algorithm in Section 4 is followed by experiments and results in Section 5.

Barcode Signal Reconstruction

From a 2D image of the barcode, a unique 1D signal can be extracted by scanning a horizontal line through the barcode image. Therefore, the barcode can be represented as a series of 1D patterns representing 0s and 1s (see Fig. 1):

tmp1411-1595_thumb[2][2]

If the signal obtained from the image looks sharp and clear like in Fig. 1, the barcode can be recognised easily. However, as the captured barcode image is blurred and noised as in Fig. 2, the extracted 1D signal is heavily distorted (see Fig. 2). In this case, it is very hard to recognise the barcode precisely.

Clear barcode image and orginal signals

Fig. 1. Clear barcode image and orginal signals

Blurred barcode image and blurred signals

Fig. 2. Blurred barcode image and blurred signals

The sharpness of the captured signal depends on the reader device and its distance between the reader and the surface of barcode. The longer the distance between them, the more blurred the original signal is. The blurred signal f(x) is often modelled as the noise added convolution of the original signal u(x) with a Gaussian kernel of unknown amplitude a and standard deviation a [2]:

tmp1411-1598_thumb[2][2]

where n(x) is a noise function, a is a strictly positive constant, and

tmp1411-1599_thumb[2][2]

Related Works

In the approach based on edge detection, traditional barcode decoding techniques such as peak locations [3], selective sampling [5] and EM algorithm [6] have been employed. These approaches cannot work well if the phone cameras are designed with low quality [7] or the images are heavily distorted. In fact, with handheld cameras, noises and focusing errors may appear frequently. In other words, it is really difficult to extract features such as edges and peaks of the bars and spaces from the heavily distorted images. In another approach, barcode is extracted after the process of signal restoration through solving an inverse problem [2]. There are two serious problems with this approach. Firstly, restored signals usually have errors because the degrading process is often unknown and complex. Secondly, the cost of computation is considerably high because of the process of signal restoration. Finally, this approach is only suitable with simulated images. For real images, barcode cannot be recognised correctly. Besides two above approaches, statistical machine learning techniques [7] are also used to identify barcode. Based on the nature of the contaminated barcode symbols, the trained classifiers are able to discriminate different code patterns by extracting their statistical features [7]. However, the cost for maintaining the system is considerably high because collecting training data is often an absolutely great task. In addition, each type of barcode or a change of capturing device needs a particular recognition system.

Our Proposed Approach

To recognise barcode patterns in heavily distorted images, we propose an effective algorithm in both of accuracy and performance, in which the prior structural knowledge of barcode is used thoroughly.

Despite that images may be distorted, barcodes can be located quite easily because of several reasons: they contains black and white vertical lines and every barcode have less than four consecutive 1s or 0s; they are often printed in separated area; and they often have the ratio of 3:4 between the height and width. After locating the barcode in the distorted image, we estimate the blur parameters. This is done by comparing the size of the barcode in the distorted image with the actual size of a barcode and locating the position of two border guard bars by optimising the error function. Blurred signals of digits are pre-computed with the estimated blur parameters. This pre-computation is conducted in order to speed up our algorithm. We then go through each scan line of the barcode image to find the barcode value that that best matches the signal of scan line. This is done by first re-locating the guard bars, calculating position of each digit

Algorithm 1. Pseudo-code for barcode recognition algorithm

Algorithm 1. Pseudo-code for barcode recognition algorithm

in the barcode and comparing the signal of the scan line with blurred signals of digits. The first digit is implied by the patterns of six left digits. If the checksum of the detected value of the barcode is true, the barcode value is added as a vote. The barcode value with maximal number of vote is returned as result. The very detail of barcode recognition process is explained in Algorithm 1.

The Error Function

The error function that we use when finding the best matched candidate for each considered pattern is as follows:

tmp1411-1601_thumb[2][2]

where u(x) is the signal pattern of a generated candidate, f (x) is the signal pattern of the scan line at the calculated position.

Estimating the Blur Parameters

Parameters of image degradation can be auto-extracted based on image processing techniques [1,2,4]. However, the high computation needed by these techniques is a burden to real-time application. To avoid this computation, we apply the following process. Firstly, the fixed Gaussian size needs to be set large enough for heavily distorted images. Secondly, we can a assign 1 to , by which the range of value of each pixel is from minimum to maximum value appearing in the image instead of 0 to 255, because this parameter is related to the light intensity radiating over the region of interest. Finally, parameter a can be estimated by using the extracted position of border guard bars. By experiment, we found that the error function of border guard bar patterns has a convex parabolic curve when the parameter changes. Therefore, this parameter can be estimated approximately via a search technique.

Algorithm Complexity

The complexity of our algorithm istmp1411-1602_thumb[2][2] the number of pixels representing a bit) where O(size of image) is the complexity of locating barcodes. K is the number of horizontal scan lines. R is the number surrounding of positions of left border. 6, 20 and 10 are related to the number of digits in barcodes and the number of candidates for each digit. The number of pixels representing a bit is depended on the Gaussian size. The required memory does not exceed O(size of image).

Experiment and Result

We tested our algorithm on 50 blurred images with the various ranges of blur degree and the light intensity radiating over the region of barcode. The obtained results can be considerable and competitive. The correct identification rate is 46/50. For each barcode, it takes about 0.5 second to recognise in a Windows PC of the Pentium 4, 2.4 GHz, 1 GB RAM. Our algorithm can recognise correctly many barcodes in heavily blurred images, which it is difficult to recognise by previous algorithms [6] (see Fig. 3). However, there are still some distorted images with the appearance of geometric transform, so barcodes cannot be recognised (see Fig. 4). We have also carried the experiments by first deblurring the distorted signal using the extension of Lucy-Richardson maximum likelihood algorithm[2], and then decoding the barcode to compare with our approach. However, the deblurring did not improve the recognition on heavily distorted image.

Barcodes are recognized correctly

Fig. 3. Barcodes are recognized correctly

Barcodes are recognized incorrectly

Fig. 4. Barcodes are recognized incorrectly

Conclusion

In this paper, we have proposed an effective algorithm based on prior knowledge for barcode identification in heavily blurred images. The algorithm utilises prior knowledge of barcodes in order to first estimate the blur and then successfully decode the barcode in heavily blurred images. In addition, this approach can avoid expensive computation such as image restoration. We have performed experiments on real blurredly captured images to show the effectiveness of our algorithm.

Next post:

Previous post: