Comprehensive Analysis of Barcode Localization Methods

Comprehensive Analysis of Barcode Localization Methods

Savreet Kaur1, Dr. Raman Maini2

1Student, Master of Technology, Department of Computer Engineering, Punjabi University, Patiala

2Professor, Department of Computer Engineering, Punjabi University, Patiala

Abstract- Barcode Localization is an extremely useful in many application areas like banks, supermarkets, trade etc. Different types of barcode types such as UPC, EAN- 13 etc along with speed and accuracy requirements makes the task of barcode localization a challenging process. In this paper, we will be analyzing two existing barcode localization methods: one of which is based on dilation and erosion while the other is based on bottom- hat filtering. These two methods are implemented in MATLAB and are compared with each other for different type of barcodes like skewed, blurry barcodes along with multiple barcodes in an image. It is observed that the first method based

Fig. 1: Different types of Barcodes

EAN- 13

on dilation and erosion is faster whereas the second based on bottom- hat filtering is more accurate and provides orientation details. Results of first method are also better for blurry as well as skewed image whereas none of the two methods provides accurate results for complex images.

Keywords: Barcode Localization, Morphology, Bottom- Hat Filter, Directional Image Opening.

1. INTRODUCTION

   Barcodes are 1- dimensional group of parallel lines that carry alphanumeric information which can be read using computers, smart phones etc [7]. The main principle behind barcodes is to encode information in bars and spaces of varying widths along with redundant information for error correction. In this paper, we have mainly dealt with UPC, Code- 128 and EAN- 13 type of barcodes as shown in Fig. 1, but both the methods discussed can also be extended to other types of codes.

   UPC

   Code- 128

   Barcodes are a cheap, convenient and an efficient method to represent information and can be of big help in present day world where the amount of information is increasing exponentially. But barcodes cannot be read by humans and devices required for localizing and reading them are not adopted for personal use. This prevents us from using barcodes in many real life applications.

   This problem can be solved by using cameras available on portable devices like mobile phones, laptops etc. and Image Processing which can be used to localize barcodes. Barcodes can be captured using cameras and the image captured can then be processed using morphological operations to localize barcodes.

   This paper is organized as follows: In Section- 2 we have discussed basics of Barcode Localization along with its objectives and challenges. Section- 3 discusses the methods to be analyzed, one of which is based on dilation and erosion while the other is based on bottom- hat filtering. Section- 4 covers results of implementation of two methods as well as their comparison on the basis of different parameters (speed and accuracy) and different image types (skewed, blurred etc.).

2. BARCODE LOCALIZATION

   Barcode Localization means locating or finding barcodes in simple or complex images. It is mainly based on two main properties of barcodes. First property of barcode is that it contains black bars against a white background. Second property of barcodes states that it has a strong directional continuity. It means that barcodes have very strong continuity

   at one particular orientation and very low in all other orientations [4].

   Barcode localization methods have two main objectives, speed and accuracy [1]. For some applications, speed is more important while for others accuracy is more important. For example, in places like banks, accuracy is more important since a wrong code interpretation may produce information about a wrong/ unintended account. Processing speed is secondary desired feature in such applications. However, in mobile phone applications accuracy is not so critical since barcode can be scanned again if any problem arises. But here high processing speed is desirable.

   Localizing barcodes within an image presents many challenges. Barcode in an image can be rotated, skewed, distorted or there can be multiple barcodes in an image. Performance of methods discussed varies for these situations and we will analyze the performance of these methods for these conditions.

3. METHODS

   In this paper, we have discussed two techniques of localizing barcodes: the first one uses Tuinstras Algorithm which is based on Basic Morphological Operations such as Dilation and Erosion [2] and the second one uses Juett and Qis Algorithm which is based on Bottom- Hat Filtering [4].

   1. Method based on Basic Morphological Operations

      This method basically relies on basic morphological operations for separating out barcodes from image that may contain textual information apart from other sub- images. It uses the most basic feature of barcodes that they contain strong spatial frequency content in one direction and not in the other. Thus, there is presence of strong gradient in one direction.

      Fig. 2: Original Image from which barcodes are to be localized [7]

      In this method, initially pre- processing is done using quantization, where the input image is converted into binary as shown in Fig. 3. Next, gradient of image is calculated using

      Sobel kernels in horizontal and vertical direction as shown in Fig. 4. [2]

      Fig. 3: Image after conversion to binary

      Fig. 4: Image after applying Sobel kernels in horizontal and vertical

      directions

      Fig.5: Image after applying Dilation

      After this resultant image is dilated using square structuring element so as to merge nearby objects to form a region as shown in Fig. 5. Next step is to perform morphological erosion to remove thin lines from the image as shown in Fig. 6. After that all the small area objects are removed so that resultant image contains only barcodes as shown in Fig. 7. [2]

      Fig. 6: Image after applying erosion

      Fig. 7: Image after removing small objects

      After removing small area objects, dilation is performed again so as to highlight the area containing barcodes as shown in Fig. 8 followed by subtracting the resultant from the original image to obtain the true shape of barcodes.

      Fig.8: Image highlighting barcode area

      Fig. 9: Image showing actual shape of barcodes

   2. Method based on Bottom- Hat Filtering

   This method uses bottom hat filtering to localize barcodes, which utilizes dark on light pattern and directional continuity of barcodes. In this initially the image is converted to gray scale followed by contrast stretching which highlights the difference between light and dark areas of image.

   Fig. 10: Original Image [4]

   Fig. 11: Image after conversion to gray scale and Contrast Stretching

   After this bottom hat filtering of image is performed by taking close of the image, which expands white areas of image but does not affect areas which are originally white and then

   the resultant image is subtracted from the original image. This highlights the bars and textual information in the image.

   Fig.12: Image after applying Bottom- Hat filtering

   Fig.13: Image after conversion to binary

   After this the image is skeletonised by subtracting erosion of image from itself. This reduces large areas in the image to their outlines.

   Fig. 14: Image after skeletonising

   Next step is to find out orientation of barcodes. In order to find out orientation, directional image openng is performed at 16 different orientations on the same image.

   Fig. 15: Image showing orientation of the barcodes

4. RESULTS AND DISCUSSION

   In this section, we have compared the discussed methods effectiveness and features.

   1. Test suite, Test Environment and Implementation

      Experiments were conducted on test images having dimensions as 720 x 480 or 640 x 480 and which are in PNG format taken from [1] and [4]. Test images included images having multiple barcodes, skewed barcodes, images with complex background and images having noise.

      We implemented the algorithms given in previous section using MATLAB with the help of the Image Processing Toolbox. Evaluation was performed on a computer with Intel

      ® Core i3 2.40 GHz CPU, 3 GB RAM and Windows 7 (64- bit) operating system.

   2. Results

   In this section, we have compared the results of the two algorithms with each other with respect to various characteristics such as speed, accuracy, blurredness, noise, skewness etc.

   1. Speed: Both the algorithms were implemented over the same image and their running time was found out using a timer so as to compare their speeds. While Tuinstras method ran with an average running time of 1.618 seconds whereas Juett and Qi s method ran with an average running time of 3.81 seconds. This clearly shows that Tuinstras method runs faster than Juett and Qis method. This is because it searches for barcodes in an image in 16 different orientations. Also, Tuinstras method is based on edge detection which is faster than bottom- hat filtering.

   2. Accuracy: Bottom- hat filtering highlights barcodes by expanding white areas in the image and not affecting the areas which are originally white, which more truly preserve the shape of the barcodes as compared to Tuinstras method [4].

   3. Orientation: Juett and Qis algorithm can also be stated as better than Tuinstras algorithm since it also gives information about the orientation of barcodes, which is not given by Tuinstras algorithm as shown in Fig. 15.

   4. Skewed Image: Both the algorithms were applied on an image having skewed barcodes, whose results are shown in Fig. 16. As seen from the figures, results of Tuinstras method are slightly better than that of Juett and Qis method.

      Result using Juett and Qis Method Result using Tuinstras Method Fig. 16: Results of algorithms on images having skewed barcodes

   5. Multiple barcodes in an image: Both the algorithms were applied on images having more than one barcodes. While Tuinstras method was able to locate all the barcodes, but Juett and Qis method was not able to locate very small barcodes.

      Result using Juett and Qis Method Result using Tuinstras Method Fig. 17: Results of algorithms on image having multiple barcodes

   6. Blurred Image: Edge detection using Sobel operator fares better on blurry images as compared to bottom- hat filtering which uses opening and closing. So, as a result Tuinstras method localizes barcodes much better on a blurry image as compared to Juett and Qis method. But, when blurring is highly severe, localizing barcodes does not help because it is very difficult to decode them correctly, even if localized accurately.

   7. Complex Image: Both the algorithms are applied to barcodes in complex backgrounds. Although both the algorithms could localize the barcodes, but none of them

   could retain the actual shape of the barcodes as shown in Fig. 18.

   Result using Juett and Qis Method Result using Tuinstras Method Fig. 18: Results of algorithms on barcodes in complex background

5. SUMMARY

In this paper, we have analyzed two methods for localizing barcodes and compared their performance in terms of speed, accuracy as well as for different types of images (skewed, blurry and complex and when there are multiple barcodes in an image). We have created a test suite of different types of images like blurry, complex etc. and implemented these algorithms in MATLAB so as to analyze their performance and have concluded that none of the two specializes for all the situations. The method which suits a particular application depends upon its nature, input image etc. The first method based on dilation and erosion is faster than the second method while the second method is more accurate and also provides orientation details. For blurry and skewed images, the first method is more suitable whereas none of the two methods is effective for complex images.

ACKNOWLEDGEMENT

The authors would like to acknowledge the staff and laboratory attendants of University College of Engineering, Punjabi University Patiala, for the useful inputs, discussion and feedback while writing this paper.

REFERENCES

1. Melinda Katona and Laszlo G. Nyul, A novel method for accurate and efficient barcode detection with morphological operations, Eighth International Conference on Signal Image Technology and Internet based Systems, pp. 307-314, 2012

2. T. R. Tuinstra, Reading barcodes from digital imagery, Ph.D. Dissertation, Cedarville University, 2006.

3. E. Tekin and J. M. Coughlan, An algorithm enabling blind users to find and read barcodes, in Applications of Computer Vision (WACV), Proc IEEE Workshop Appl Comput Vis, 2009, pp. 18.

4. X. Q. James Juett, Barcode localization using bottom-hat filter, NSF Research Experience for Undergraduates, 2005.

5. Chunhui Zhang, Jian Wang, Shi Han, Mo Yi and Zhengyou Zhang, Automatic Barcode Localization in Complex Scenes, IEEE international conference on Image Processing, pp. 497- 500, 2006

6. N. Otsu, A Threshold Selection Method from Gray Level Histograms,

   Automatica, vol 11, pp.- 285- 296, 1975

7. Peter Bodnar and Laszlo G. Nyul, Improving Barcode Detection with combination of Simple Detectors, Eighth International Conference on Signal Image Technology and Internet based Systems, pp. 300-306, 2012

8. Aliasgar Kutiyanawala, Xiaojun Qi and Jiandong Tian, A Simple and Efficient Approach to Barcode Localization, 2009.