Barcode Recognition

From SoftwarePractice.org

[1]

Team G :Anthony Chandra , Vineetha Menon , Deepa Pai and Nidhi Singh

Contents 1 Barcodes – An Overview 2 Project Aim : 3 Project Requirements : 4 Project Plan : 5 Codabar - A Barcode Reading Standard 6 Assumptions: 7 Design Process Breakdown: 8 Implementation of Graphical User Interface (GUI): 9 Image Processing Techniques 10 Advantages and Limitations 11 Problems and Solutions 12 Conclusion 13 References

Barcodes – An Overview

A Barcode is a visual depiction of information in the form of bars and spaces on a surface. The bars and spaces can be of different widths and consist of numbers, characters and symbols such as dot, colon etc.Different combinations of these alphanumeric characters are used to depict information. There are various types of barcodes in use today. These include Code 128, Code 39, EAN etc. (Brain,2000) [2]

The successfull barcode technology has been constantly improving in order to accommodate more information in the least possible space. Today barcodes are widely used on books and at retail stores in order to keep track of the products available and easy checkout of the products. The barcodes are read using scanners using laser beams or cameras. (Seideman,1993)[3]

Project Aim :

The main aim of this project is to implement a GUI based barcode reader program in MATLAB.This project requires us to use MATLAB's 'Image Processing Tool Box' and other tools to perform this task.

Project Requirements :

The project is based on the following requirements -

1. A specific bar code standard must be choosen. Based on the choosen standard, the program must be created.

2. The bar code reader should accept any barcode image as an input.

3. The extracted code should be displayed as output.

4. The bar code reader should also account for distortions and rotated and unclear images.

Project Plan :

Please click on the link - Team G Project Plan , to read information related to the project milestones and project progress.

Codabar - A Barcode Reading Standard

We have decieded to use the Codabar standard as the barcode reading standard for our project.

Codabar developed by Pitney Bowes Corporation in 1972 is an old standard now used in libraries, old blood banks and air parcel express applications. This standard uses 0s and 1s for spaces and bars respectively.

A Codabar image is shown below

A brief explanation of this standard has been described below.

For a detailed description of Codabar, Please click on the link -Codabar Explanation

BASIC RULES followed by the standard :

Every barcode image that follows the codabar standard has the following basic structure -

• A start character (A, B, C or D)

• An narrow inter character space

• Code using the barcode encoding technique

• A stop character (A, B, C or D)

• Each number in the barcode is separated by a narrow space represented by a 0

(Ashford, 2006)[4]

Assumptions:

1. The barcode supplied will be of codabar standard

2. The minimum size that our code can read will be 40 pixels per character

3. The barcode will be assumed to be upright (but can be rotated positively and negatively; up to +90 degrees)

4. The barcode images are expected to be on a contrasting background in relation to the barcode itself

5. If letters or additional characters are added in the image, they are assumed not to be located on top of the barcode.

6. Whilst blurred images are supported, there is expected to be a significant contrast between the barcode and the background.

Design Process Breakdown:

The steps listed below, explain the design techniques used to meet the specified requirements of this project. Click on each of the following links to view a detailed description :

Step 1 : Extraction of Data from the Image and Filtering

Step 2 : Locating the Barcode in the data and rotate if necessary and filter

Step 3 : Cropping the Image

Step 4 : Image Interpretation and Barcode Extraction using the 'Name' function

The various functions used in in steps listed above have been explained briefly in this section.To gain a more detailed understanding, please refer to the following section(Image Processing Tools and Techniques).

Implementation of Graphical User Interface (GUI):

In this section, the technique and tools used to implement GUI has been described.

Please follow the link - GUI

Image Processing Techniques

This section of the documentation describes our research and understanding of the the different image processing techniques and tools used in this project. Image Processing was a completely new concept to the entire team and hence we had to conduct a lot of research in oder to attempt and complete steps described in the previous section.

To access this section , please click on the following link : Image Processing Tools and Techniques

Advantages and Limitations

Advantages

1.The codabar standard does not require checksums to be calculated at the end as Codabar is a self checking standard. This saves additional calculation required, as only a lookup table needs to be implemented to find the equivalent character for a given binary code.

2.There are 4 start/stop characters in the codabar standard. One character represents the beginning of a barcode and another represents the stop of that barcode. Additionally, no start/stop character reads as the same binary code forward as another does backwards, this allows immediate detection of a backwards barcode.

3.Codabar always begins with a single bar. This helped in locating the barcode in the image. This image processing technique used to decode barcode searches for a black bar to identify the beginning of a barcode. This also established the size of a single bar, which can be used throughout the reading process to detect repeated '0's and '1's which have double the single bar width.

4.Codabar has a space between every character and this is helpful in the separation of different characters. Since every character starts with a bar, the separation helps in the identification of the start of a new character. It should be noted that the code detects when a new character occurs, when it encounters the sequence 101 in the barcode.

Limitations

The code submitted for this project does not meet the project requirements to a 100%. It has its share of limitations and shortcommings which have been listed in this section.

Many of these were due to a shortage of time to test and debug the final code. Given more time (by having less commitments to other university subjects and work), our code could have included functionality by doing the following:

1. Extended the name function to read barcodes backwards. This would have included loops to recognise when the beginning character was read backwards. None of the codabar standard letters (that begin and end each barcode) have the same binary code forwards as another letter's binary code backwards.

2. Accounted for barcodes rotated by a negative angle. This would have been implemented by code that read the barcode from the opposite side (from left to right), and from that scan supply an equivalent obtuse angle to imrotate. This code was developed, however, never fully debugged and as a result was omitted from the final program. Combining the code to work out if the barcode was negatively rotated would have allowed us to deal with the case of when barcodes were vertical. The data acquired would also have helped increase the accuracy of imcrop; when the image was fully cropped on either side to isolate just the barcode.

Problems and Solutions

Problem 1: In reading barcodes of different sizes, the code could only account for a single size of barcode.

Solution1: To overcome this problem we constructed code to adjust the barcode reading code. This code located the first bar and scanned it to find its width. This width became the baseline width that was used to scan the remainder of the barcode.

Problem2: We had grey pixels in the barcode as bars transitioned from white and black bars. This caused inconsistent bar sizes which disrupted the whole scanning process of the barcode.

Solution2: We countered this by using filtering and then scaling the barcode. The unsharp filter was used to sharpen the image, and a threshold value (the average value of the minimum and maximum value in the image vector) was set. Each value was then scaled according to this threshold value, and set as either 255 or 0.

Problem3: The grey pixels also caused problems in locating the barcode and in the filtering process. Our code would detect the first top left hand corner pixel that was not white and use that as the location of the barcode. Moreover, the edge function was picking up the stray pixels and detecting them as small edges.

Solution3: To overcome this problem, the image was filtered using the unsharp filter, and then using the edge function on the filtered image. After locating the corner of the barcode, our code scanned around that position to make sure that the pixel was connected to the rest of the barcode and not just a random pixel in the image.

Problem4: After locating the top corner of the barcode, we needed to find out what orientation it was in. This was done by scanning down the first bar (horizontally and vertically). The gradient angle was worked out from these differences. One problem was deciding whether the barcode was rotated positively or negatively.

Solution4: This problem was solved for a positively rotated barcode by having two different orientation tests (described in Step 2 of Task breakdown). Time constraints meant that full debugging of negatively orientated barcodes was not completed properly.

Problem5: The gradient angle that was calculated was incorrect, often resulting in the wrong orientation outcome. This problem was due to the small area that our code was scanning; the rise over run was not accurate.

Solution5: This was fixed by scanning the bottom corner and the top corner of the barcode image and calculating the gradient from this information.

Problem6: The image was even more blurred after rotation.

Solution6: This was corrected by using the motion filter. However, this was insufficient (there were stray pixels resulting from the rotation that complicated further analysis) and as a result, the image was passed through the unsharp filter again.

Problem7: After rotation, the barcode needed to be relocated so function imCrop could be called on it to isolate the barcode, so it could be read by our decoder. After rotation, the original image was creating a diamond shaped inlay on the figure; this created problems when trying to develop loops to pass from dark colour to light colour, back to dark colour. Additionally, as the diamond inlay didn’t exactly touch the corner of the new image on all four sides, the loops became very large. Our initial solution was to use the information of the rotation angle and using trigonometric equations to locate the approximate position of the new corner. This proved to be a very inconsistent solution that only worked for some rotated barcodes.

Solution7: This problem was finally solved by using the edge function; this simplified the loops that we needed to use as only colour transitions were highlighted in white.

Problem8: Issues with Debugging

Solution8: The angle of rotation was often coming up as incorrect. This was due to variation in the barcode edge image analysis. The code was modified to work with the most common type of barcodes supplied. Debugging on negative rotation has not been completed.

These were the major problems and set backs encountered with this project. Whilst other functionality had been allowed for, time constraints meant proper debugging (and hence problems) were not met.

Conclusion

With better time management on our behalf, our code could have included superior functionality and satisfied all the requirements of the project specification.

As a result, some tradeoffs in the quality of the code were made, and in certain functionality; such as rotation over 90 degress and in a negative direction. Whilst the matlab code was developed, the implementation proved harder and more time consuming than originaly planned. Debugging was not given sufficient time and in the interest of having a functioning program for submission (that produced predictable results) we chose to omitt these sections of code.

On a whole, whilst some functionalities in the project specification were oversimplified in our assignment, our program provides a solid foundation on which these functionalities can easily be integrated (given more time to debug).

[5]

References

[1]. Cartoon Stock, ‘Barcode Cartoons’, URL: http://www.cartoonstock.com/directory/B/Barcode.asp, last viewed 7th November 2006.

[2]. Brain M., 2000 ‘How UPC Barcodes Work?’, http://electronics.howstuffworks.com/upc.htm, last viewed 7th November 2006.

[3]. Seideman T., 1993, ‘Barcodes Sweep the World’, Vol. 8 Issue 4, http://www.americanheritage.com/articles/magazine/it/1993/4/1993_4_56.shtml, last viewed 7th November 2006.

[4]. Ashford T.L., ‘Barcode Software’, http://www.tlashford.com/frames/home_frameset/home_frameset.htm, last viewed 15th October 2006

[5]. Albrechts Y., 1996, ‘Kapreles’, URL: http://lambiek.net/artists/a/albrechts_y.htm, last viewed 7th November 2006.

[6]. The MathWorks Inc.,'Matlab Help', 1994-2006, <Inc.http://www.mathworks.com/access/helpdesk/help/techdoc/matlab.shtml>, last viewed 7th November 2006.