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

Abstract

Recently, with the popularity of hand-held deviceswith camera, many applications requiring barcode identification inimages have appeared. There are several problems with these applicationsbecause of the limitation of camera capability. Among them, heavilyblur problems are the most significant and popular. In this paper, wepropose a novel approach to estimate blur for recognising barcodes inheavily blurred images. With this approach, we are able to extractcorrectly the barcode from heavily blurred images, which existingmethods cannot.

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

Introduction

Recently, with the popularity of mobile phones aimedwith integrated camera, there is a need for recognising barcodes fromimages captured from these devices. However, due to the limitation ofcontrolling focus lens, the captured images are often heavily distortedby the out of focus blur. Therefore, it is very hard to extract thebarcode from these heavily distorted images with existing methodsproposed for conventional barcode reader. There are several approachesreported in literature for solving the blur problem in barcoderecognition, e.g. edge detection-based approach [3,5,6],inverse-problem-based approach [2] and statistical machine learningtechniques[7]. These techniques cannot work well for heavily distortedsignals [7] because it is difficult to extract features such as edgesand peaks of the bars and spaces from these signals.

In this paper, we propose a novel approach toestimate blur for recognising barcodes in heavily blurred images. Wefirst estimate the ranges of blur parameters, and then search throughthese ranges with sampled values to find the parameters that allow us toextract correctly the most number of barcode values along the scanlines of the barcode image. For each scan line, we generate candidatesignals by utilising the structure of the barcode, blur them with blurparameters in process, and compare with the distorted signal of the scanline to find the best matched candidate signal. The checksum of thebarcode is used to verify the candidate. With this approach, we are ableto extract correctly the barcode from heavily blurred images, whichexisting methods cannot.

The paper is organised as follows. In Section 2, barcoderepresentation is described in details. The emphasis of the paper is inSection 3 which presents related works. Subsequently, our proposedalgorithm in Section 4 is followed by experiments and results in Section5.

Barcode Signal Reconstruction

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

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

Fig. 1. Clear barcode image and orginal signals

Fig. 2. Blurred barcode image and blurred signals

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

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

Related Works

In the approach based on edge detection, traditionalbarcode decoding techniques such as peak locations [3], selectivesampling [5] and EM algorithm [6] have been employed. These approachescannot 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 isreally difficult to extract features such as edges and peaks of the barsand spaces from the heavily distorted images. In another approach,barcode is extracted after the process of signal restoration throughsolving an inverse problem [2]. There are two serious problems with thisapproach. Firstly, restored signals usually have errors because thedegrading process is often unknown and complex. Secondly, the cost ofcomputation is considerably high because of the process of signalrestoration. Finally, this approach is only suitable with simulatedimages. For real images, barcode cannot be recognised correctly. Besidestwo above approaches, statistical machine learning techniques [7] arealso used to identify barcode. Based on the nature of the contaminatedbarcode symbols, the trained classifiers are able to discriminatedifferent code patterns by extracting their statistical features [7].However, the cost for maintaining the system is considerably highbecause collecting training data is often an absolutely great task. Inaddition, each type of barcode or a change of capturing device needs aparticular recognition system.

Our Proposed Approach

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

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

Algorithm 1. Pseudo-code for barcode recognition algorithm

in the barcode and comparing the signal of the scan line with blurredsignals of digits. The first digit is implied by the patterns of sixleft digits. If the checksum of the detected value of the barcode istrue, the barcode value is added as a vote. The barcode value withmaximal number of vote is returned as result. The very detail of barcoderecognition 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:

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

Estimating the Blur Parameters

Parameters of image degradation can be auto-extractedbased on image processing techniques [1,2,4]. However, the highcomputation needed by these techniques is a burden to real-timeapplication. To avoid this computation, we apply the following process.Firstly, the fixed Gaussian size needs to be set large enough forheavily distorted images. Secondly, we can a assign 1 to , by which therange of value of each pixel is from minimum to maximum value appearingin the image instead of 0 to 255, because this parameter is related tothe light intensity radiating over the region of interest. Finally,parameter a can be estimated by using the extracted position of borderguard bars. By experiment, we found that the error function of borderguard bar patterns has a convex parabolic curve when the parameterchanges. Therefore, this parameter can be estimated approximately via asearch technique.

Algorithm Complexity

The complexity of our algorithm isthe number of pixels representing a bit) where O(size of image) is thecomplexity of locating barcodes. K is the number of horizontal scanlines. R is the number surrounding of positions of left border. 6, 20and 10 are related to the number of digits in barcodes and the number ofcandidates for each digit. The number of pixels representing a bit isdepended on the Gaussian size. The required memory does not exceedO(size of image).

Experiment and Result

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

Fig. 3. Barcodes are recognized correctly

Fig. 4. Barcodes are recognized incorrectly

Conclusion

In this paper, we have proposed an effectivealgorithm based on prior knowledge for barcode identification in heavilyblurred images. The algorithm utilises prior knowledge of barcodes inorder to first estimate the blur and then successfully decode thebarcode in heavily blurred images. In addition, this approach can avoidexpensive computation such as image restoration. We have performedexperiments on real blurredly captured images to show the effectivenessof our algorithm.