wiredfool

View Album

Went to the mass ascension of hot air balloons on Saturday, part of the Balloon Classic in Indianola IA. There were 100 or more balloons all going up into hot (100 degree), hazy skies in the space of 20 minutes or so. I was shooting a 100mm lens, but it looked like the pros were using the Canon 70-200 f2.8L lens. Always keeping an eye on the equipment, but there’s no way that I’ll be able to afford one of those anytime soon.

I wasn’t too happy wiht the colors, I was hoping that the sky would be more consistently blue, but it was hazy, hot, humid, and later, dusty from chasing the pack on gravel roads.

The mist here is all dust, not fog.

Local skyline

View Album

Looks kinda like I’m shooting through algae.

A little late for the 4th, but I only noticed these today. These are the flowers from the croton plant in the kitchen, something that barely survives as a houseplant in this climate but is tree sized in Cozumel. Each burst is about 1/4″ across.

Along with the salmonberries that I’ve pictured here before, we’ve got huckleberries. I think these have a more complex flavor, if not a bit tart. We’ve got at least 4 bushes, one of them is a good 10 feet tall and loaded with fruit. This particular one, Vaccinium parvifolium is a relative of the blueberry, native to the pacific northwest, and historically used by the Native tribes. I’m thinking of a huckleberry/chocolate ganache, but I may just be tempted to just lightly crush them and sprinkle over ice cream.

And a 4th of July roundup, we didn’t actually stick around for the fireworks due to a stiff, cold, onshore breeze but we did stay long enough for Ben to have a few turns in the firetruck.

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.

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.

Rose and I just um… consumed Poppy Z. Brite’s Liquor (a novel) in one quite enjoyable 24 hour period. This is not heavy literature, rather the perfect sort of book to accompany one to a hammock on a warm summer’s day. Preferably with a cold drink at your side.

Two guys, longtime partners and chef material, get fired from a kitchen job for drinking on the job. In a funk, one hits on the idea for a resturant where every dish has liquor in it. The perfect New Orleans resturant hook. The kitchen scenes seemed accurate enough, the fight scenes satisfying, and the list of resturant concept failures was laugh out loud hillarious.