Image Processing for Barcode Recognition
From SoftwarePractice.org
Contents |
Image Processing Introduction
The challenge in this project is to be able to detect a barcode on an image and we have to account for the following situations: blurriness, slanted barcodes, light intensity of images, noise in images, more than one barcode in the image and upside down barcodes. There are many techniques that can be used in image processing and our group has invested in the Image Processing Toolbox in Matlab so that we will be able to use special functions to identify our barcodes.
Algorithm Development in Matlab for Barcode Recognition
The following flow chart outlines the image processing algorithm that our group has used in order to recognise a barcode in an image:
Figure 1: Flowchart Image Processing Algorithm
A few notes for the above flow chart; the [2000 2000] refers to the image size, the trapezoidal boxes are decision points, three of these are actually checkboxes in the GUI, the fourth is based on the size of the image. Eccentricity of a straight line is 1, hence the reason for lines > 0.98 eccentricity (0.02 variance). Median area should be the size of a bar, hence range 1/4*area <= area <= 4*area according to Code 39 standards.
As can be seen from the flow chart the highlevel processes are; converting the image into binary image, eliminating noise and cropping the output to show just the barcode and a single binary array. The rest of this page will go into further detail of the aforementioned processes and provide sample input and output images.
Image Classes in Matlab
At step 1 in the above process we need to convert the image into a "Grayscale Image" that represents the image as a matrix where every element has a value corresponding to how bright or dark the pixel is at the corresponding position. There are two classes in Matlab that can do this:
1. Double Class: assigns a floating number between 0 and 1 to each pixel.
The value for black is 0 and the value for white is 1.
2. UINT8 Class: assigns an integer between 0 and 255 to represent the brightness. The value for black is 0 and the value for white is 255. (There is also UNIT 16, UNIT32 and UNIT64 and with these have integer values in the range 2^k, where k is either 8, 16, 32 or 64.)
We convert our images in the first step into uint8 images and then from there into binary images using the matlab function im2bw. It is in this conversion when we use the Otsu's graythresh levelling function. Basically this uses Otsu's method to calculate the threshold between a white pixel and a black pixel. This is then inputted into the im2bw function. We need to work with binary functions because to be able to eliminate noise and also to be able to output a binary array we need to work with a binary image.
Please refer to this link to find out more about the types of images in Matlab[1]
Detecting and Rotating Slanted Image
This barcode detection algorithm can also detect if the barcode is slanted and readjust the barcode so that it is straight. Actually very simple maths is behind this part of the algorithm! Using the Bounding Box property of Regionprops this will output the upper-left x and y coordinates, the width and the height of each area found in the image (i.e. the bars in the barcode). From this if we take the x and y values of the first and last bar and calculate their gradient, if this is not zero then the barcode must be slanted. Since we have the gradient we can then calculate the degree to rotate the image, one trick is that we had to convert from radians to degrees! This part of the code happens right near the end of the algorithm since we want to make sure that we only have barcode bars in the image, otherwise this will distort the output. The only major disadvantage is that it will work for barcodes that are rotated -90 to 90 degrees, if the barcode is rotated more than this the resultant barcode will be upside down (i.e. the barcode will still be straightened but it will be upside down). Below shows this part of the algorithm in action!
Figure 2: Rotate Barcode Function
To account for the fact that it will only work for barcodes between -90 to 90 degrees we have put a rotate 180 degree checkbox into our GUI so that any images that have barcodes rotated greater than this can be turned "Upside down" and then rotated so that they are straight. Below is an example of this.
Figure 3: Image that needs to up turned "Upside down"
Figure 4: Successful rotation of image and hence able to read barcode
Advanced Noise Elimination Techniques
The basic algorithm will go through three elimination stages:
1. Clear any group/s of pixels that are touching the edge/border of the image
2. Clear any group/s of pixels less than 100 pixels^2 in area for image sizes > [300 300] or 50 pixels^2 for those smaller.
3. Clear any group/s of pixels that are not straight (since eccentricity of a straight line is 1).
What happens when there is noise in the image, for example letters such as I, L, T etc that make it through the first three elimination stages? This will cause the resulting output image to include other noise not just the barcode. Hence we need to use more of the Region Properties properties to eliminate this noise. There are several options to the do this.
1. Firstly you can use the property Centroids that outputs the x and y values of the centre of each area in the image. From this you can then calculate the distance between each centroid of a group of pixels in an image. The barcode will have a small distance between each bar of the graph, so the advantage here is that if a bit of noise was on the same x axis as the barcode so possibly make it through the above elimination technique, the distance would be too far away from the barcode, hence it would be eliminated. Disadvantage of this technique is that if there is noise scattered around the barcode it will calculate the distances from bars to the noise and thus bars will be eliminated, I have included a diagram to show this effect. The first image below shows an example where the noise is scattered around the barcode and the second shows the effects of using this option, i.e. bars are missing!!! Hence we have NOT implemented this method.
Figure 5: Distance Noise Elimination Function
Figure 6: Distance Noise Elimination Function Output
2. This option uses the property area, so it will output the area of each of the groups of pixels left in the image both barcode and noise. Generally by this stage there are just small groups of noise left that weren't eliminated by the 100 threshold or maybe a really large group. Hence it is possibly to calculate the median area and this would be of one of the bars (assuming mainly bars left in the image). From this you can set boundaries for the area so lower boundary median/4 and upper boundary median * 4. We have chosen 4 since the greatest ratio of narrow to wide is 1:3. Hence 4 times the median and 1/4 of the median should definitely include the bars of the barcode (we have tested this and it is a fact). Advantage of this option is that it does not matter if noise has made it through to this stage or not and it is easy to calculate ( a lot more efficient than calculating the distance!). Disadvantage if the area of the noise is the same size as the barcode it will still make it through!!! The image below shows the elimination of all the noise that only works with this option out of the three stated here (it is the same image as Figure 1). We have implemented this method into the normal find barcode function, as it does provide a useful noise elimination technique that is not too calculation exhaustive and will not affect images that just have a barcode in them.
Figure 7: Area Noise Elimination Function
3. Lastly you can use the property Centroids again this time though we will be doing something different with the x and y values. A barcode would generally be in the same region of the image, so you can use the median and standard deviation calculations to determine the region of the barcode (assuming that if there is any noise it will mainly be random outliers in the image.) Advantage of this technique is that it can identify the region of the image where the barcode is and eliminate any outlier noise. Disadvantage is that if all the noise is eliminated in the first three stages and if the barcode takes up the whole image you may loose bars of the barcode!!! Second disadvantage is if the barcode is on a 45 degree angle may loose outer bars of the barcode. Both are not good!!! That is why we decided to put in a checkbox in the GUI so that the user can decide to use this function if they input an image that is "noisy". Also we have made it so that the algorithm will only eliminate noise on the axis where the standard deviation is smaller. The reasoning behind this is because generally a barcode will be spread along one axis and since we don't want to loose the outer bars we look at the axis where the barcode values stays fairly constant and we know if that anything further away on this axis is not a bar. For example say the barcode is spread along the x-axis we will get a fairly large st deviation for x whereas y values will have a smaller st deviation. Hence any outliers in the y values will be eliminated. Similarily for a barcode spread along the y axis. Disadvantage will be for any noise that is on the same axis as the bar and also for any barcodes at 45 degrees. Below shows an example of eliminating the noise (the red parts are the "bars" of the barcode notice that stray lines have made it through the normal function, hence this special noise elimination is needed to identify the barcode).
Figure 8: Centroid Noise Elimination Function
Figure 9: Centroid Noise Elimination Function
Deblur an Image
One of the requirements we would like our program to have is the capability of being able to deblur an image and recognise if there is a barcode on the image and if possible read that barcode. To deblur an image is quite difficult and it all depends on how badly "blurred" the image is in the first place and it can actually be modeled by the following equation (based on help in Image Processing toolbox):
g = H*f + n
g = blurred image
H = distortion operator, also called Point Spread Function (PSF)
f = original image
n = additive noise
Now the PSF is important as it describes the degree to which an optical system blurs a point of light. In mathematical terms the PSF is the inverse Fourier Transform of the Optical Transfer function (OTF). The distortion operation when convolved with the image, creates the distortion. This means that to deblur the image the blurred image needs to be deconvolved with the PSF that exactly describes the distortion. The Image Processing Toolbox has four deblurring functions:
1. deconvwnr - implements deblurring using the Wiener filter
2. deconvreg - implements deblurring using a regularised filter
3. deconvluvy - implements deblurring using a Lucy-Richardson algorithm
4. deconvblind - implements deblurring using a blind deconvolution algorithm
The problem with our blurred images will be that we do not know the distortion operator, i.e. if the picture is blurred to begin with we don't know the exact PSF of it. This is why we have implemented the blind deconvolution algorithm because it will perform the deblurring without knowledge of the original PSF.
This function is also quite an exhaustive function so it is recommended to have pictures of pixel size less than 1000 by 1000.
Below is example of how our original deblur algorithm worked. So we have our original image:
Figure 10: Blurred image
We apply the deblur function that does five steps (this algorithm is based on the help file 'Deblurring Images Using the Blind Deconvolution Algorithm' see References);
1. Uses an initial PSF based on a gaussian distribution, now this was chosen because it best represents distortion of a camera lens being out of focus
2. The first iteration will use an array 4 pixels smaller than the PSF, i.e. UNDERPSF
3. The second iteration will use an array 4 pixels bigger than the PSF, i.e. OVERPSF
4. The third iteration will use a PSF of the same size, INITPSF
5. By using the edge function and changing threshold values we can get an array of "Weighted" values that will help with the final iteration of the blind deconvolution function
Figure 11: Original Deblur Function
This is quite an exhaustive function and to be practical in terms of performance time it was decided to only use the first iteration of UNDERPSF. Furthermore we found that with images that were only slightly blurred putting them through the above five iterations would make the image worse than before and generally the UNDERPSF did a pretty good job of deblurring these slightly blurred images. Hence we use only the one iteration of the blind deconvolution and as you can see below we were able to successfully deblur several images and thus read the barcodes. It must be noted that the blurring that occurs in the first place is RANDOM hence this is a very basic deblur function that will only work on images that happen to be blurred a special way.
Figure 12: Image to be deblurred
Figure 13: Successful deblur of image using modified Deblur Function
Future Enhancements to Image Processing Techniques
1. We would like to improve the functionality of the deblur function so make the user able to input different variables so that other blurred images can be read. At the moment the random gaussian PSF has fixed variables. This enhanced functionality would require user input fields in the GUI that would then be inputted into the deblur function. The user would also need to understand the types of variables that they should enter in so for this enhancement there would need to be a help page on suitable types of input variables.
2. We would like to improve the graythresh technique of converting the image from a uint8 to a binary (black and white) image. In the design process it details about the troubles with light intensity in photos if there is a lot of light some of the black parts in the image will be converted to white instead of black! A way to enhance this would be to look at a histogram of the light intensity of the images and if there is not a clear enough distinction between white and black do an image enhancement function that would attempt to lessen the light intensity in the image. This would require another checkbox function that the user could tick if they had an image that has been distorted by light intensity.
3. We would like to be able to identify two or more barcodes in an image as well. At the moment if there are two barcodes and you tick noise elimination one barcode will be outputted but the function doesn't know that there is another barcode in the image. This would have to do with the region properties function again and seeing the region of the barcodes as two distinct barcodes so output two arrays. This functionality would require changes to the GUI to be able to process two different outputs for different barcodes.
4. We would like to be able to identify 2D barcodes, these are not just made up of bars so our original find barcode function would not work. We would have to come up with another function altogether for finding 2D barcodes in an image.
click here to go to the next stage in the barcode reading process Image Processing to Barcode Reader
click here to return to the main page for Team B Bar code reading from image
