/barCode

comment(s) 

EAN / UPC BarCode Image Recognition

http://www.brains-N-brawn.com/barCode 2/20/04 casey chesnut

was trying to come up with something different to code when Scoble posted a link to this: Camera Phones Help Buyers Beware. thought that was pretty cool, and wanted to give it a shot. since i have a book fetish, involving naked women reading, decided to target ISBN numbers. the concept is that you would take a picture of the ISBN barcode of a book, it would recognize that ISBN #, then use a web service to search for the best price. had never mucked around with barcodes, so needed to get up to speed with that 1st. barcodes are just plain fun. the whole mark of the beast stuff is a blast. if i were ever to get a tattoo, it would definitely be a barcode. probably my social security number on the back of my neck, universal soldier style. the key though, is that it would have to scan. but i dont think tattoo technology has advanced to that level. will probably be implanting RFID in my skull before then.

Creating BarCodes

little jogging around the internet turned up some sample code for generating barcodes from scratch. you just feed it the ISBN number and it will generate the image for you. the best one i found for EAN / UPS symbols was from Paulo S. Silvia Jr. it was lame ass VB.NET (sorry Paulo) so i first converted it to C#. that code, along with the information at barcodeisland.com gave me a good understanding of what the vertical black lines meant. then tweaked the barcode generation app so that it would create barcodes of different sizes, as well as different scales, to have more test cases to go against when trying to read them later on. the image below was generated with lines having a width of one pixel, so its pretty small and comparable in size to what you see on most consumer products. the moral of the story is that its quite easy to find code for creating barcodes from scratch, as well as their specifications. on the other hand, i found absolutely no information on how to read a barcode image. and i dont mean manually scanning the barcode with hardware, this has to be automated with image recognition software.

Image Recognition

took the brute first approach to start off with. just read a horizontal line of pixels across the image. identified by the red line through the image above. the process was to read each pixel one by one and record the length of pixels in a row that were black and white. reading across also gives you the size of the barcode. with those values, you can then use a proportion to dissect the black lines, and end up with a binary string representing the encoded barcode value (seen below). 1 represents a black line, and 0 represents white. we can easily see the left and right guards (101) represented in the string below, as well as the image above. also you can see the middle guard (01010). where you see multiple 1's in a row (111), then you will see thick black lines above. also note that the binary string is 95 characters long.

10101100010100111001100101001110111101011001101010100001011001101100110100001011100101110100101

with the binary string, you can then use the encoding rules to get the EAN / UPC number.

Pass 2 - The Wild

that is all fine when im generating the barcodes with line widths of 1 and 2 pixels. so when scanning across the image, i was always getting 95 lines back. the next level of difficulty was to search the internet and find barcode images that had been generated by other programs. about half of them worked, but the others would fail. the problem was that their scale was just a little bit different. so when doing the pixel-scan, instead of being all pure black or white, there were grey squares as well. some of them were exactly grey too, which really mucked up my logic. my 1st reaction was to target the grey squares explicitly. so that if the square was exactly grey, it would be tested twice; once as black and once as white. then it would generate the binary strings above. if the string length was not 95, it threw those out immediately. this let the program read a couple more of the barcodes from the wild, including the one below. not great, but decided to push on. NOTE, also tried the manual technique of just re-scanning by adjusting the height where it scans across horizontally. this was not useful here, but it might be for images later on.

Pass 3 - Scanned

the next level of difficulty was to introduce barcode images scanned from actual physical books. took some of my books to kinkos and started scanning them. after chasing off the employee whom wanted to teach me all about copyrights, i got back to work. tried reading them with my program, and only a couple worked. damnit. the problem was that the books introduced more shades of grey because the scanned lines were not exactly vertical. i bailed at this part, and started reading some Artificial Intelligence books. my thought was that the program needed a better way to handle uncertainty. in pass 2, it makes a yes / no decision, and the actual grey value is not taken into consideration from that point on. then it finally hit me that i needed to flatten the data. could take the color value of each pixel, and plot it along a graph. so it would create a wave representing the black and white barcode lines. by changing the representation of the data, the program would be able to read at a lower level of granularity (with more surface area) and get better results. the result of this flattening can be seen below.

so it turns the barcode into a wave format. then this intermediary image can be scanned multiple times. so i take one scan of the barcode, and then do multiple horizontal scans of this image. using the exact same logic i had earlier. of course, i ripped out the grey handling logic i had put in place earlier, because grey'ness is now represented by the image above. the peaks that dont reach the top of the image are some level of grey. doing a horizontal scan at a different height of the image will then return a different binary string representing the barcode. if a resulting string ends up being 95 characters long, then you know it should be tested further. also, EAN has a checksum, so you can check the resulting value to get rid of the uncertainty that was introduced. with this method, the program was able to read all of the scanned barcode images. excellent!

Pass 4 - Camera

continuing on, i introduced barcode images taken with a camera. my camera phone is too low quality, so none of those worked. took some more pictures with a digital camera, and only a couple of those were read successfully! all of the others failed though. applied some more AI techniques to test more decision paths, but that did not help. have not come up with any more ideas, like in part 3, that would make the results remarkably better. a pic of the application can be seen below.

Web Interface

on the off chance that you want to test it yourself, then you can upload a picture or image of a barcode to see if it can recognize it. NOTE this only has a chance of working with EAN / UPC barcodes, such as from most products and ISBN numbers. NOTE you'll have to scroll back down to see the result

 

Conclusion

with a little bit of effort, i was able to write a program to read a number of barcodes generated from different programs and of varying quality. with additional effort this could be expanded to better support lower quality images, particularly from camera phones. this would offer some interesting end user scenarios.

Updates

10/4/2004 had to do some more image processing and tweak the recognition logic, but finally got it working on my PocketPC using the HP Photosmart Mobile Camera

the screen caps below show the program in action. pic on the left shows the captured image with minimal preprocessing. pic on the right shows the transformed image used for recognition and the final result is displayed in a MessageBox. NOTE that it matches the numbers displayed at the bottom of the captured barcode image on the left! the scenario is that you would use this with a Smartphone while you were at a bookstore. you would take a picture of a books barcode, it would recognize the ISBN, and then check to see what price Amazon.com had for the same book using their Web Service

 

might revisit this when i get a get my hands on a newer Smartphone with camera. could also update this to support other barcode formats such as 3of9.

Future

still waiting on more RAM for my computer to make the jump to Whidbey. found out a couple of days ago that i'll be presenting at Microsoft Mobile DevCon next month, so i need to get to work on putting together a tricked up presentation