wiredfool

Barcode Recognition

Every so often, I get on to a kick where I start reading up on lisp, erlang and others that have functional, reliable, metaprogrammable, or other ‘able’ traits that indicate a more powerful language. In a way, this is partly responsible for my investigation of ruby on rails, as a metaprogramming language that has one dominant web framework that seems to do things right.

Some of this is because I see people using these tools to create software that is elegant, effective, and done with few resources. The most recent iteration is dabbledb. This is software that I wish that I’d written. I’m pretty sure that it’s written in smalltalk by a small team, who did the work between consulting jobs.

Some of this is because I want things to get easier. However, I’m reminded of Lance Armstrong: “It doesn’t get any easier, you just go faster.” The programming is still going be ‘hard’, but it better be solving bigger problems.

I’ve had a problem at work that I’ve thought about, on and off, for a year or so. We drive several check scanners, one of them with a barcode recognizer. Helpfully enough, that’s the lowest volume one — generally the scanner that one wants to upgrade from. But for people who need that barcode scanning to match a payment coupon to their database, it’s kind of an important feature. There are a few open source packages out there that do barcode recognition, some as part of an ocr engine, some as stand alone. Lots of payware activex stuff, com objects, or other closed source windows stuff. But nothing that gave a quick and easy overview that’s incorporatable or reimplementable. So I need a barcode recognizer from a black and white image. I don’t need to find the barcode, since it’s in the same place every time.

code 39
So, Code 39 barcode. There are a lot of barcode symbologies. This is a little different than the upc symbol, it’s an early attempt that’s had wide use, it’s not especially dense, but it’s easy to read.

Each ‘character’ has 9 bars, starting and ending with black, and a narrow white bar between character. 3 of those bars are wide, generally 3x wider than the narrow bars. This means that each character is a fixed width, probably about 16x the smallest unit (3×3 + 7×1). Also, there’s supposed to be a large white space at the beginning and end of the barcode, and start and stop characters at each end. So the total number of bars, white and black, including start/stop codes, but not the end buffer space, will be (chars)*10 + 19 bars.

So now, for some functional goodness. The essential trick here is to encode a string of bits from the image in run length encoding, here represented by tuples of (length, color) in an array. Once you have that, you can figure out if you have a reasonable number of bars (one per run length entry), characters, and from that, the barcode. Everything in the problem can be modeled as a list, and all (save one) of the operations can be a map or filter on the list.

I’m doing this in python, usng the itertools package and a curry implementation that gives me partial function application. (e.g. bar = curry(foo,a), bar(b) == foo(a,b)) Itertools gets me the groupby function, which returns lists of identical(ish) items. Curry, well, curry gets me partial function evaluation, which is really some syntatcic sugar to let me use map instead of an explicit for loop.

First up, we need a row of pixels. I’m assuming that we know where the bar code is in the image, and we just need to interpret it. Finding the barcode is a problem left for the reader. We’re using the python imaging library, so extracting a row is a quick function. Here I’m cropping the barcode region to a 1 pixel high area at a height v in the region, then getting the data from the image.

	def extract_row(self, img, v):
		(w,h) = img.size
		return img.crop((0,v,w,v+1)).getdata()

For a black and white image, this comes back as a list of integers, either 0 (black) or 255 (white).

Next, we need to take this pixel data and get something that approximates bars. Run length encoding does the trick here, since we would like color and width for each item on our scan line. This is the first use of the itertools.groupby function, which returns a value and an iterator of the items for each identical value. I’m grabbing the length of the value list and the value, mapping the value to a color, and returning it as a tuple, then chopping off the whitespace at each end.

	def to_rle(self, row):		
		mp = {0: 'b', 255: 'w'}
		return [(len(list(g)), mp[k]) for k,g in itertools.groupby(row)][1:-1]

This should return a list of [(len, ‘b’), (len, ‘w’), (len,’b’) …] where the first and last items are black. If they’re not, then we should just discard the line. It’s much easier to just discard lines that don’t make sense, either from a bad scan or missing barcode information than to try to tough it up. There are always more scanlines to try. (Until there aren’t, and then it may be worth some touchup).

Now, we have a list of white an black regions, we need to determine if they are wide or narrow bars, then split them into individual characters. Since there is a rough correspondence between the pixel width of the barcode and the number of narrow bar widths, I’ve set a threshold of 2x the narrow bar width as the divider for wide/narrow. We can calculate the narrow bar spacing by pxLen/(16*characters), and # chars = (len(rle)+1)/10. Or, in code:

	def threshold(self, rle):
		n = (len(rle)+1)/10
		pxlen = sum(map(lambda x: x[0], rle))		
		return 2*(pxlen / (16*n))

And apply it using:

	def to_bars(self, rle):
		return map(curry(lambda x,y: str(int(y[0] > x)), self.sym.threshold(rle)), rle)

In this case, I’m returning it as ‘1’, and ‘0’ for wide and narrow, respectively. I could return bits or booleans or strings, but I found the 1 and 0 easy enough for the character substitution. In the future, I’ll probably make them binary and try to specify the mappings as character set transformations. But not today.

The penultimate step is to chunk into characters, another use of the groupby function, this time with a little stored state. I want to pull off 10 bars at a time (9 + whitespace), so I’m using a helper that will give me a integer div 10 of the number of times that it’s been called.

	def _iterkey(self, val):
		self._iterstate +=1
		return (self._iterstate-1) / 10
	
	def chunk(self, bars):
		self._iterstate = 0
		return [''.join(list(g)[:9]) for k,g in itertools.groupby(bars, self._iterkey)]

Finally, we need to turn the chunks into characters. I’ve got a map of the 9 character chunks to the character that they represent, processed from the wikipedia and other documentation above. So it’s a simple matter of subbing into the map and dropping the start and stop characters:

	def to_chars(self, chunked):
		return ''.join(map(lambda x: self.sym.bkw[x], chunked)[1:-1])

Putting this all together with some error checking, retries on the next scan line, we get:

 	def recognize(self, img):
		(w,h) = img.size
		for scan in range(1,h-1):
			rle = self.to_rle(self.extract_row(img, scan))			
			if len(rle) < self.sym.min_length : continue			
			if not self.sym.check_len(rle): continue
			chunks = self.sym.chunk(self.to_bars(rle))
			if len(self.sym.invalid_chunks(chunks)) : continue
			try:
				ret = self.sym.extract(self.to_chars(chunks))
				if len(ret): return ret
			except:
				continue
		return None

On my linux (ubuntu 6.06, amd64, 3600?) box, this does about one barcode per .01 sec, where the barcodes are about 280x100px, extracted from about 1 megapixel images. On average, I'm trying about 40 scanlines before I hit on one that's error free. It's about 2.5x slower on the mac (macbook core duo) for reasons that I haven't figured out yet.

Link to the full source.
Link to an archive with the code, test code and a sample image.

2 comments

2 Comments so far

  1. greg August 11th, 2008 11:14 am

    This is really cool. I made it into an online utility here. Let me know what you think. I wonder how hard it would be to add UPC -A support?

  2. greg August 11th, 2008 12:28 pm

    That’s http://utilitymill.com/utility/barcode_recognizer (last link didn’t make it through.)

Leave a reply

You must be logged in to post a comment.