Field Notes
High-Capacity Color Bar Code
Gavin Jancke
We are all so familiar with bar codes that they often go unnoticed—they are almost ubiquitous in everyday life, appearing everywhere from food packaging to shipping labels. The original 1D bar codes that appeared in the retail industry in 1974 comprised vertical bars of variable widths and stored a 12-digit number. Bar codes evolved as computing power increased, and black-and-white 2D bar codes (matrix codes) were developed in the late '80s, marking increased data density from just a few digits to a few hundred bytes.
In 2003 I began working on a counterfeit-proof, biometric identification card as a project for Microsoft Research. I needed to store not only the cryptographic text, such as name and age, but also fingerprint or iris scan templates. In order to store all the necessary data, the existing black-and-white bar code would have been larger than that ID card itself, so clearly a new approach was needed.
I had to determine how to store more than one bit of information per symbol, which had been the standard for black-and-white 2D bar codes. By using colors rather than black and white, I could increase this to two or three bits of data using four and eight colors, respectively.
I also experimented with the symbol shapes to see if they could be packed together more tightly without compromising their registration when being scanned. Initially hexagons seemed like a good possibility, but the shapes melded together and the computer couldn't discern them clearly enough.
I eventually settled on triangles because they intersect neatly in a compressed space, yet retain their identity as distinct shapes. In using rows of triangles in multiple colors, I could increase the density capability into 3D.
There were a lot of variables with which to contend. One of the biggest challenges of working with color is variance in printing specs and in lighting conditions. Although color may be easily discernible to the human eye (at least for those who are not color blind), it is not as clearly discernible to a computer.
I used several different approaches to ensure that the software could read color accurately. I created a very small, nearly unnoticeable palette within the bar code that contained the reference colors that existed in the actual bar code. This provided a calibration mechanism that specified exactly what constitutes a particular red, for example. I also tried more advanced techniques such as customized and lightweight color-clustering algorithms that take advantage of color space theory to categorize the colors into sets. Both approaches work equally well and complement one another.
One of my goals for this project was to write a program that would enable cell phones to read the bar codes. With cell phones, one has to consider poor lighting and out-of-focus, fixed, focal-length lenses. A further challenge was to do all of this computer vision on integer-based, relatively slow cell phone CPUs, so the team needed to come up with some solid theory on how to detect the bar code in the image while touching as few pixels as possible. The scan needed to work within a range of read qualities, such as bright in-focus LCD panels to lower-light, out-of-focus physical print.
The final algorithm decodes bar code images on real-time camera video frames faster than the actual frame rate—about 10ms on a 200Mhz CPU. In an image, the smallest number of pixels a bar code can be for the smallest data payload and still be detected is about 45 pixels square.
Making all of this work under varying conditions took more than two years to refine. This technology has recently been licensed to third parties, and there will be some exciting applications of it later this year.
Gavin Jancke, Director of Engineering for Microsoft Research, runs the Advanced Development Group and Web Experience teams. Previously he worked as a Product Support Engineer, Software Engineer for SQL Server, and served on Bill Gates' executive technical advisory staff.