Recognizing barcodes with AI

Question

As a pet project/learning experience (no this is not homework) I'm working on software to recognize barcodes from a photograph. I'm not looking for software or a library that does it - instead I'm using this as a learning exercise that I'm blogging about and will post up on Codeplex.

I have code that successfully recognizes EAN13 barcodes and UPC version A/E should follow shortly. I have two areas that I'm concerned about, though. First is in decoding barcodes that are in a picture that is bit blurry or with poor contrast, etc. Second is in simply finding the actual barcode in a larger picture (right now you have to give me a photo of just the barcode).

I have the gut feeling that some form of AI is going to help me out here. I played a bit in the past with genetic algorithms and I took a course ages ago on AI so it's not totally foreign to me, but I'm not quite sure where to start.

What type of algorithm is best suited to this type of problem? Any recommended reading or code for the AI grunt work? Yes, I want to understand what's happening, but I don't necessarily want to go down to the level of coding the sorts, etc myself.

Answer 1

I would suggest to search for properties that a barcode has. Some that I have in mind are:

1. Histogram of colors shows two distinct colors in about even distribution
2. Doing a hough transformation finds many parallel lines
3. The thickness of the lines have two distinct dimensions.

Some other?

Having this I would split the image into pieces and do a classification with these features then cobine the results to calculate a liklyhood if the piece contains an barcode or not.

For your second problem (blurry image) I would suggest to calculate the 1st order derivative of the grayvalues and then detect the edges of the lines in this space. The maximum of the derivative is lower if the image is blurred but it should be detectable to a certain blurring factor.

Does this help you?

Answer 2

You don't need any specific AI or softcomputing technique. You need to apply image processing technique to improve the quality of the image or to isolate the barcode from a larger image. You could use Matlab for prototyping and learnig more about image processing.

Answer 3

As mp already noted you don't necessary need any real AI technique for it. Have a look at chapter 12 of Real World Haskell. It implements an almost complete barcode recognizer. Sample code is in Haskell, but there is plenty of explanation, so you can probably understand the ideas and tricks even without Haskell experience.

If you want to solve it with AI then the best bet is probably using ANNs. For the given problem I would recommend to use a quite advanced technique called HyperNEAT. See my explanation (and links) as the first answer to the SO question Neural Network Size...

I would probably use two or three different networks,

• The first one to find the barcode on the bigger picture. One output neuron per pixel/set of pixels, output value is the confidence if that pixel seems to be a part of a barcode. Based on the result I would use some image transformation to convert it to a "standard" format (x*y rectangle)
• If you have difficulties with finding the location of the barcode use a second one. Feed the result of the first one, and ask it to give the coordinates of two corners. However, I'm not quite sure that it will be very easy to evolve this one.
• Last one would work on the standardized format, output neurons for each line (or square, if you work with a possibly 2D barcode), saying if the given area should be considered black or white.

Probably it would also help to do some pre-processing of the image, e.g. those that are described in RWH.