Team C: Barcode recognition

From SoftwarePractice.org

• Asakura, Ken 00050500
• Chen, Tony 10188631
• Foo, Trevor 01041553
• Lam, Kevin 10451704

Contents 1 Project Scope 2 Code 39 3 Design Issues 3.1 Image Rotation 3.2 Noise 3.3 Blurriness Of The Image 3.4 Unknown Size 3.5 Affine Distortion 3.6 Designing The Interface 4 Data Conversion 5 Samples 5.1 Sample Code 39 Bar Codes 5.2 Output 6 GUI 6.1 Directions of use 6.2 Problems Encountered 6.3 Limitations 7 Literature Review, research and discussion 7.1 Relavant Literatures 7.2 Research 7.2.1 Fourier Transform list 7.3 Discrete Fourier Transform (DFT) 7.3.1 Inverse Discrete Fourier Transform (IDFT) 7.3.2 DFT with time window 7.4 Fast Fourier Transform (FFT) 8 Systems & Development Perspective 9 References

Project Scope

The ultimate goal of this project shall be to extract the alphanumeric information contained in a certain barcode. The final delivery of the project shall be;

• A program which shall scan the barcode and display the contained information in a form which a human being can comprehend.
• A documentation which explains clearly the concepts used in the program. The documentation shall examine the total performance of the code, as well as potential alternatives to the code. This shall also contain and clarify the theory and methodology undertaken to deliver the nature and structure of the program.

The selection of the bar code standards is unrestricted. Hence it is part of the project to select the standard wisely, to make the implementation as simple as possible, with focus on the image processing and conversion.

There are several numbers of key factors which shall be significant to be considered. These factors are considered and be dealt with using relevant signal processing methods.

These issues are; noise distortion, image rotation, affine distortions and blurriness. They are key barcode scanner issues which are dealt with in real life situations. Professional engineers deal with these issues using known signal process methods. This documentation shall mainly explore how we dealt with these issues using Matlab.

Code 39

• Available characters under Code 39 include:
  • Uppercase letters (A through Z)
  • Digits (0 through 9)
  • Limited number of special characters.
• There is no specific method of error detection.
• The ratio between narrow and wide bars is 1:2-1:3.
• The asterisk(*) character is not an encodable character. It is used as a start and stop character.
• Each character code is separated by a narrow white bar, which appear every ten(10) bars.
• A complete table of code translations can be found at: Wikipedia

Design Issues

Image Rotation

Problem: The barcode is rotated with respect to the camera.
Solution: For design purposes, the barcode will initially be a perfect image which will further be rotated at a random angle. The reader will read the image as a whole and determine the angle of which it was rotated and correctly align the barcode.

By observation, you could keep the image in its current form and locate the extremities and determine the angle. Locate the top left and right points on the bar code. With the co-ordinates calculate the arc-tangent of the right-angled triangle formed.

Observing the barcode directly.

By taking this method one step further, we take the Fourier transform of the image. By taking the logarithm of the Fourier transform we see variations in the frequencies, with more concentration inline with the barcode. Then to convert the Fourier transform into a form which we can work from, threshold the Fourier transform to expose the maximum values. Here the extreme values on either side represent the whole barcode as a whole, rather than just specific corners, as seen in the previous method. After locating the points, again calculating the arc-tangent and thus finding the degree of change from the 0 axis we are able to rotate the image appropriately. Due to the nature of this subject, we have made use of the function imrotate() in the Image Processing Toolbox to rotate the image, as image rotation itself has minimal relation to this course.

The logarithmic magnitude of its Fourier transform

Exposing the maxima points (Threshold)

Matlab Implementation

angle = imageAngle('code+rotate.gif');
angle: Degrees(Int)
code+rotate.gif: X x Y x Unit(8).

This function of the program will call the function whilst feeding the function an image array. For simplicity, the code has been designed around the gray scale colour map. The function will take the 2D Fourier transform of the image, shift the transform so that all the frequency values are centered. It will then thresh hold the resulting Fourier transformed image leaving a handful of ones which will be aligned in the direction of the code angle. The extremities will then be located, from the co-ordinates the inverse tangent will be calculated thus returning an angle, which the function will return to the user calling the function. This angle will then be fed into the built-in functions in Matlab to rotate the image to its correct alignment.

Advantages & Limitations

This method was chosen to overcome some of the possible irregularities in some images and issues with locating the corners of bar codes. The quality of some of the bar code images would cause issues, where as taking the Fourier transform of the code, allows bases of detection on the frequencies rather then actual values of the image.

One issue when implementing this into Matlab was, images of unequal dimensions (in the X and Y axis) were returning angles which were lower than the actual angle required for complete restoration. No actual code was implemented into the program to pad the arrays with additional zero's so that the 2D Fourier transforms came out correctly. In order to by-pass this issue, sample images were copied to image canvases of square dimensions.

When thresholding the image, there were issues on what would determine the point in which you would threshold the image. Since no logical solution could be devised, values of 65% - 85% were used as threshold values. The inaccuracy of these values would sometime cause the rotation to be off by a couple of percent.

imrotate(); We did not explore all the arguments used in this function, which may result in a more refined image.

This code is limited by the fact that it can only detect angle rotations in certain quadrants. If the image is rotated too much, there are no sections which check whether the code is currently reversed and requires to be mirrored along the horizontal axis.

Intermediate Results

The inital coding for this subsection consisted of the code locating the corner points of given image. This method did work, though we were seeking possible solutions which used some of the signal theory and filtering in the freqency domain.

Noise

Problem: Poor signal to noise ratio, bad lighting conditions, image taken through glass, and so on.
Solution: By observing the image directly, it is possible to manipulate each section by using floating averages. A combination of thresholding and vertical averaging would be sufficient for bar code cleaning.

While researching on this topic, we were looking for solutions where by we put the image's Fourier transform through a filter of some sort, to retain some of the image's original structure and alignment. There were numerous algorithms which filtered out noise in the frequency domain, though a lot of these methods relied on the function to know what noise was used in the image. A typical noise reduction method is similar to that of a debluring filter which will smoothen out some of the random pixels in the image.

Matlab Implementation

denoise = pixelaverage('noise.jpg'); denoise: Array ( X x Y x Unit (8) ) noise.jpg: Array ( X x Y x Unit (8) )

The image will be passed into the function as a X x Y x Unit (8) array, and the function will return a 'relatively' denoised image in the same form. An ideal barcode should only contain black and white pixels, the code applys the quantisation method in order to change the pixel into black (0) or white (255). During this stage, the low level noise should be eliminated due to the adding of original pixel value (ie 0) and the noise value (ie 101) does not exceed the half way value (128) and will be quantitised to the closer end (ie 0).

However, the higher level noise (ie 209) would change the pixel value in great scale and the predefined functions would automatically assume it as another colour (black (0) + noise (209) = 209, and through quantisation it will turn out to be 255 which is a white pixel).

To overcome this problem, each pixel is compared with 2 consecutive pixels next to it vertically (the information we need is the vertically alligned bars) and take the average value of those pixels, and repeat the process with the 2 pixels vertically next to it. The outcome image would be an overall denoised image but also eliminated some details of the image.

Advantages & Limitations

Due to the insufficient information about the noise as there are many sources of noise input, and no specific rule on the structure of the image, this method hardly apply any signal processing methods to remove the noise. It was experimented to implement a noise removal function by using a LPF and eliminate additional signals below the threshold; however, the function cannot apply in this situation because it does not distinguish the difference between noise and information. For example, the 4 pixels which consists of values 3 254 2 3, ideally, this should present the pixels white black white white; when noise has been added in, say 30 23 50 150, then the new values would be 33 277 52 153, and through quantisation, the output is 0 255 0 255.

The average/comparing function was eventually implemented. The function is based on comparing the neighbouring pixels; so details that stands out from neighbouring information would be considered as noise. If the noise level is high and continue for few pixels, the function may consider it as information as it does not stand out from neighbouring pixels. Also the function only works on images that presents only black and white pixels. Other colours would be considered as either white or black.

Blurriness Of The Image

Problem: The camera is out of focus.
Solution: Aimed to sharpen the barcode to reduce amount the grayish areas. Manipulating the image directly and attempt to threshold the image, to either black or white (e.g. darkish colours are converted directly to black, and lighter colours directly to white). This method is effective due to the format of this certain image, but may be ineffective for other images.

It is aimed to maintain the clarity of the image, and thus look into the frequency domain for solutions. It is attempted to amplify the stronger frequencies forming a more vivid image reproduction. To achieve this result, the image is Fourier transformed through a high pass filter. The high pass filter will pass high frequencies through but will attenuate lower frequencies. Lower frequencies are determined by a specified cut-off frequency when designing the high pass filter.

Gaussian high pass filter

For our barcodes we used a Gaussian high pass filter.

Matlab Implementation

filteredImage = imageDeblur('code+blur.gif');
filteredImage: Array ( X x Y x Unit (8) )
code+blur.gif: Array ( X x Y x Unit (8) )

The image will be passed into the function as a X x Y x Unit (8) array, and the function will return a filtered image in the same form. The array will be passed through the fft2(); function, which finds the 2D Fourier transform of the image. The signal is then passed through a 2D high pass filter, which can be seen above. The high pass filter will allow all frequencies above the cutoff frequency to be passed through, resulting in a more defined image. The 2D high pass filter consists of a an array of ones with a circle of zeros in the middle. This when multiplied with the image's Fourier transform, will keep all the frequency components except those in the middle of the image. The image's Fourier transform will also be passed through fftshift2(); so that the frequencies are centralised in the center of the image.

Input Image f(x, y) => Pre-processing => Fourier Transform = > F(u, v) => Filter Function H(u, v) => H(u, v) F(u, v) =>Inverse Fourier Transform => Posy-processing => Enhanced Image g(x, y)

Following convolution theory, multiply the filter array and the image's Fourier transform. The filter will zero out the lower centralised frequencies from the image. Perform the ifftshift2(); and ifft2(); to return the image to its original state. Resulting in a sharpened image.

Advantages & Limitations

There is no specific way of determining the cutoff frequency of the program, and it could be easily altered to; filteredImage = imageDeblur('code+blur.gif', freq); allowing for a user defined cutoff frequency for the high pass filter. This value could effectively be sourced from the UI implementation. Other than a user-defined value, there is no absolute value or method of determining the optimum value for filtering. It basically comes down to what value appeals most to the eye of the viewer.

Unknown Size

Problem: The object with the bar code on it is an unknown distance away from the camera taking the image.

Solution: Re-sampling the image to the correct dimensions may be a more convenient procedure. Methods to re-size the image to the correct dimensions seem redundant with code detection not specifically looking for specific bar widths. Rather code detection has been designed to compensate for variations in bar code widths. To code detection has been designed to detect thin bars and thick bars, which are more than twice the thin bars width.

Advantages & Limitations

Actually re-sampling the images may cause more issues than scanning the original image. When re-sampling the image, you are limiting the dimensions of the image window and you are also implying that each bar is to be a specific width. Re-sizing of the image maybe required if we were to use the UPC bar code standard, which is initially why we chose to use Code 39.

Affine Distortion

Problem: The object with the bar code on it is not perpendicular to and on-axis with the camera.
Solution: When attempting to correct this flaw, it will be difficult to determine where each of the binary digits end, especially for standards which rely upon static bar lengths. Affine distortion may result in a varying widths for each binary digit representation. Based on this issue, Code 39 is a better standard to use. Code 39 digit detection could compensate for this flaw by using detection methods which detect widths relative to adjacent digits. Some of the image processing for this aspect may not be enough alone, and some leeway in the translation code maybe required to compensate for varying bar lengths.

Building from this idea, code detection with affine distortion can be simplified by maintaining a floating minimum/maximum bar width. The reader is designed to compare each bar to the floating minimum and updating the minimum size upon each thin bar detection.

An alternative solution would be to attempt to restore the bar code widths by calculating the bars of either sides and multiplying the ratio over.

Matlab Implementation

codeAffine = imageAffine('code+affine.gif');
codeAffine: Array ( X x Y x Unit (8) )
code+affine.gif: X x Y x Unit (8)

From the output codes compared to the original code, it can be seen the the multiplier method results in more accurate results. The problem with the floating average is that once there is an inconsistency found in the code, the remainder of the code would be detected incorrectly. Where as the multiplier method will attempt to normalise the whole bar code as a while, and then detection will proceed as usual and any errors in detection will not affect the remaining bars.

For this method, Matlab has two basic functions available to make use of; min() - finds the smallest value, max() - locates the larges value. In an array storing the widths of each bar, we can determine the widest and the narrowest bars in the given code. From these values, based upon the 1:2-1:3 ratios of narrow:wide we can determine the ratio of min(barWidth) x 2 : max(barWidth). With this ratio, we can inverse the value and create an array in the opposing direction of the array and multiply it through.

Designing The Interface

The planned Graphical User Interface (GUI) will support all image formats. The layout will consist of windows, buttons and text-boxes; windows to display the original and reconstructed bar codes, buttons to initiate each of the desired functions/filters and text-boxes to assign arguements to be used in each of the filters. The resulting output should consist of an alphanumeric string of characters translated from the bar code. 'Guide' command will be used in programming the user interface.

Data Conversion

• Import the image using imread() in Matlab.
• Determine the dimensions of the image.
• Compress the barcode into a linear array by taking the vertical sum of each column.
• Count the amount of pixels in each bar, before the next colour tranission.
• Locate the narrow white separators, every ten (10) bars and mark them.
• Locate the thinnest bar, for comparison usage.
• Compare each bar to the thinnest bar:
  • Thin bars < twice the thinnest
  • Wide bars > twice the thinnest
• Compile all the data collected, and form BbWw string.
• Translate the BbWw string into alphanumerics.

Samples

Sample Code 39 Bar Codes

Perfect barcode

Blurred barcode

Affine distorted barcode

Rotated barcode

Noisy barcode

Output

Original code result
bWbwBwBwb BwBwbWbwb BwbwBwbWb bwbwBWbwB BwbwBWbwb bWBwbwBwb BwBWbwbwb bwBWbwBwb bWbwBwBw

Affine code result (method #1)
bWbWBwBwb BWBwbWbWb BwbWBwbWb BwbwBWbWB BwbwBWbwb BWBwbwBwB BwBWbWBwb bWBWbWBWB BWBWBWBW

Affine code result (method #2)
bWbWBwBwb BWBwbWbWb BwbWBwbWb BwbwBWbWB BwbwBWbwb BWBwbwBwB BwBWbwBwb bWBWbwBwB bWbwBWBw

Deblur code result
bWbwBwBwb BwBwbWbwb BwbwBwbWb bwbwBWbwB BwbwBWbwb bWBwbwBwb BwBWbwbwb bwBWbwBwb bWbwBwBw

GUI

Directions of use

1. Type in the file name (e.g. barcode.jpg) in the box labelled “Enter Barcode Name” located in top left hand corner. The file must exist in the same folder as the code and it must be in the format of jpg or gif.
   
2. Click on the button below labelled “Load Barcode”, the original image will display in left hand side of the program.
   
3. Once it is loaded, press one of the four buttons which perform signal process and result will display in the right hand side of the program. The four function are De-blur, Rotate, Affine and De-noise. Note that four of the function cannot be combined and used. The program can be exited anytime by pressing the close button located in right hand corner.

Problems Encountered

There was two main problem encountered in creating the GUI and implemented with the design.

1. The code could not program in the way of calling function for most of the image processing functions. When the variables are passed along to another m-file, it started creating errors.
Solution: Since it is difficult to pass the arguments to another m-file, all of the code are combined in to the same file. Some of the variable changed name so it doesn’t collide.
2. Image function in the GUI cannot be combined. For example, when the barcode is blurred and rotated at the same time, the image processing can only handle de-blur or rotate it back to normal in once.
Solution: There was no solution programmed in this problem. The coding is difficult and tried number of times. At the end, the program can only run one function each time and it has to be closed to minimise the chance of being error.

Limitations

• As mentioned above in the GUI section, it cannot combine all functions and use it at same time. Therefore it has to run functions separately.

• For the rotating section, it locates the rotating angle. However, it relies on image toolbox in rotating the barcode. Therefore, the rotating function will only work on the machines that has image toolbox installed on.

Literature Review, research and discussion

Relavant Literatures

McCellan, Schafer, Yoder; Signal Process First, Prentice Hall 2002

Lynn, Paul, Fuerst, Wolfgang; Introductory Digital Signal Processing with Computer Applications, 2nd Edition, Wiley 1998

Stearns; Digital Signal Processing with Examples in Matlab, CRC Press 2002

Stein; Digital Signal Processing, A Computer Science Perspective, Wiley 2000

Research

Fourier Transform is a signal process tool which is used to analyse signals by representing it with components of sine and cosine waves. It produces a frequency domain signal from an input of time domain.

There are a variety of form of fourier transform, each are used depending on what the input signal and the desired output.

Fourier Transform list

The following table illustrates what Fourier transform is used in what circumstances.

_______________________________Discrete – Time________________Continuous – Time

Discrete Frequency_______________DFT, X[K]________________________Fourier Series, {ak}

Continuous Frequency__________DTFT, X(ejw)______________________CTFT, Xc(jw)

In general, Fourier transform is a process of computing the spectrum of a recorded signal. This is done to gain better understanding of the signal.

Discrete Fourier Transform (DFT)

• A method of describing the spectrum of a signal. Used when both time and frequency of the signal are discrete.

• A method which has been derived from the Continuous-Time Fourier Transform (CTFT) which is only used when the signal is continuous in both time and frequency. DFT was derived in conjunction to Riemann integral, which states that a simple approximation can be obtained by replacing the integral by sum if samples.

DFT: X[k] = ∑ x [n] e ^[–j(2π/N)kn]

Inverse Discrete Fourier Transform (IDFT)

Essentially IDFT summation is similar to DFT summation. The two only differences are the minus sign for the power of e and the factor of 1/N at the front. This is because DFT has been intoduced the result of computing the DTFT of finite length sequence at finite frequencies.

IDFT: x[n] = 1/N ∑ X[k] e ^[j(2π/N)kn]

DFT with time window

• Time windows are added to make the signal finite in the time domain. This allows us to analyse finite number of samples in our Fourier analysis. This is usually done by multiplying with a window, which can be defined as:

w[n] = 1 for 0 ≤ n ≤ L-1 = 0 otherwise

The above shall give us L samples.

• w[n] is simply multiplied to the DFT equation.

DFT and IDFT (Inverse Discrete Fourier Transform) can be summed up as methods for taking N numbers of sample in one domain and taking it to another domain.

Fast Fourier Transform (FFT)

• Fast Fourier Transform (FFT) is one of Fourier Transform methods. It is a very attractive method since it runs significantly faster than other methods. It is the most well studied algorithm and computer program for doing spectral analysis.

• FFT is the algorithms for implementing the efficient computation of the DFT.

• It is used when length N is a power of two. Hence when the number of operations proportional to N log2 N, rather than N2. This is particularly useful when N is a large number.

• One negative for FFT is that it may misinterpret the signal.

Systems & Development Perspective

References

1. Code 39 - Wikipedia, the free encyclopedia
2. Bar Code Reading From Image
3. Universal Product Code - Wikipedia, the free encyclopedia
4. Code 39 Specification Page
5. 2D Bar Codes Reading: Solutions for Camera Phones
6. Matlab GUI Tutorial
7. Image Transforms - Fourier Transforms
8. McCellan, Schafer, Yoder; Signal Process First, Prentice Hall 2002
9. Lynn, Paul, Fuerst, Wolfgang; Introductory Digital Signal Processing with Computer Applications, 2nd Edition, Wiley 1998
10. Stearns; Digital Signal Processing with Examples in Matlab, CRC Press 2002
11. Stein; Digital Signal Processing, A Computer Science Perspective, Wiley 2000