|
Barcodes and cellphones - Why doesn't it work?
Ever since the advent of cameras on cellphones, people have been trying
to build applications that read barcodes and link to something. Maybe a
price database or an inventory system. Major companies have expended millions
of dollars (and hundreds of millions of yen) on these efforts, with little
or no success. Part of the problem is the lack of the "killer app".
Part of it lies in the technology.
There are dozens of types of barcodes, but when you visualize a barcode
you probably see the almost universal EAN/UPC/JAN codes. That's because
they are predominant in the retail world. They are on most of the things
we buy. So let's look more closely at this barcode type. These common codes
all use the same font. Because the codes were intended to be mass-produced
cheaply, the codes have a great deal of redundancy built into them. This
makes it harder to misread them.
Here's what barcodes are made of:
Each number in a barcode is represented by "characters" consisting
for four bars: two black, two white. Each bar can have one of four thicknesses.
If you assign the values 0-3 to the four widths, every character adds up
to 7. It is critical for a scanning system to be able to read the width
of each bar as well as knowing if it is black or white.
The EAN barcode type (European Article Number, also called the International
Article Number) is the longest of the familiar barcodes; it will have 8,
13, 15 or 18 digits. UPC codes run 8, 12, 14 and 17. Since eighteen
digits is the worst case, we'll calculate what is required to read this
code. Eighteen digits means 72 bars just for the numbers. Plus bars for
marking the beginning, middle and end of the code. If the thinnest bar is
one pixel wide, then we need 11 pixels to read a single character. Eighteen
characters requires 198 pixels. "Start" and "stop" bars
plus extra characters for error checking add another 50 or so. That means
it takes about 250 pixels to represent the barcode.
Cellphone cameras have a much greater pixel-width than 250, so you'd think
they should be able to do the job. But to obtain an accurate reading, we
actually need multiples of 250 pixels.
Why can't 250 (or even 640) pixels of camera capture 250 pixels
of barcode?
First, 250 pixels assumes we are lined up perfectly, each pixel matching
the position of a bar (or part of a bar) exactly. If we are off by half
of a pixel, the smallest black bar is now two gray pixels. Off by 1/4 of
a pixel and it becomes one light gray, one dark. Even worse, each of those
gray pixels are imaging part of TWO bars.
Zooming in, we'll look at what this means for the number 5. 5 = 1-2-3-1.
A perfectly aligned scanner would see the following eleven pixels: BB www BBBB ww.
If it was 1/2 pixel off and the pixels can actually be gray, the string
would look like this: G B GwwG BBB Gw.
Not pretty and not readable. But, you say, my cellphone's camera has 640x480
resolution. With perfect alignment, we would see this pattern. BBBB wwwwww BBBBBBBB wwww.
Reading 1/2 pixel off, we'd get G BBB GwwwwwG BBBBBBB Gwww.
Can we do anything with this? Maybe. Let's drop the gray pixels. That leaves
us with a 3-5-7-3. Ok, divide by 2 and drop the extra: 1-2-3-1. Perfect,
just what we need.
Except there was a scratch on the second black bar and we really read:
G BBB GwwwwwG BB GwG BB Gwww.
If we drop the gray pixels, we end up with 3-5-2-2-3 -- pure garbage.
But wait! There are lots more rows of pixels, we just need to figure out
which one is right. Just to play it safe, we'll look until we have TEN identical
strings that all read exactly the same. At that point, surely we can trust
the results?
Maybe. If the camera is tilted slightly, none of the rows of pixels will
be lined up correctly and each one will give different results. We can adjust
for this, it's called de-skewing. We take rows of pixels and move them back
and forth until we can match up sections. This takes a fair amount of work,
but it can be done.
Focus on fewer pixels or fuzzy closeup?
Another problem greets us at this point. To make use of all the camera's
available pixels, the image of the barcode must more or less fill the screen.
That means getting very close; so close that the lens of the camera cannot
focus properly. That makes the image fuzzy. Shades of gray won't work, but
that's what the fuzzy image captures. If we take the picture of the barcode
from a long enough distance that the image is sharp it will be small; we
won't be using most of the camera's resolution. That makes de-skewing and
conversion more difficult. Get close where everything is grey, and the image
cannot be interpreted at all.
Two possible solutions?
Much higher resolution cameras (a low-end barcode scanner will have a 2048
pixel linear array) and/or a close-up lens for your cellphone would help
a lot. At least one company sells closeup lenses, but the requirements are
different for each camera. Plus, you have to take the close-up lens
off for normal use. Maybe one of these will happen, maybe not.
There are barcodes, called 2D matrixes, that can be read by a low-resolution
camera. They look like little boxes of square dots. All of the dots are
the same size, they are relatively large and easy to image. If you look
long enough, you'll find some.
They are "futureware" in the sense that people have hopes that
someone (besides delivery services) will eventually start using them for
something. But will the retail and manufacturing world decide that it needs
to throw out the system they've used for the last 30 years, in order to
accommodate cellphone users who might want to read their barcodes? Probably
not for a while.
|
