📄 readbarc.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>How it works</title>
</head>
<body>
<h1>How it works
</h1>
<p>By Jon A. Webb, Ph.D.</p>
<h2>Overview
</h2>
<p>The biggest problem with reading barcodes on a cellphone is that the barcode is too small and too out of focus to distinguish the individual lines in the barcode. In fact, an image of a barcode on a cellphone (if taken close enough so that the barcode extends across more than one hundred pixels, as is necessary to read a UPC barcode of 95 individual bars) will be blurred enough that the light and dark lines for a digit blur into the lines for the digits on the left and right. As a result, the image of the lines for "0" in the sequence "03" (say) will look different from "0" in the sequence "07". This means that no conventional image processing technique, such as thresholding or edge detection, has a chance of working. Image sharpening techniques do not work, either. The image is not just corrupted or noisy-it's in the wrong place.
</p>
<p>What does work is synthetic image analysis. The basic idea is to form an image of what the barcode should look like, taking into account the blur from defocusing, and then compare this synthetic image with the actual image. If the match is better for "030400" than for "070400" (say), then the barcode is probably "030400", not "070400".
</p>
<p>In order for synthetic image analysis to work, a great deal must be known about the image, starting with the exact position of each sequence of barcode stripes for a digit. Fortunately, barcodes are designed to make it relatively easy to extract this information. There is a "quiet" area surrounding the barcode, so the barcode can be isolated and rectified it into a standard layout. The number of position of the digit codes is known (at least for UPC and EAN barcodes).
</p>
<p>Finally, we have to consider how to search the space of possible barcodes to determine what synthetic images to compare with the real one. After all, a UPC barcode consists of 12 digits, so there are a trillion different possible barcodes (actually, one of the digits is a check digit, so there are really only 100 billion, but still). We do not have time to generate synthetic images of them all and compare. The trick here is to consider the barcode digits two at a time, from left to right, using the last digit from the last pair as the first digit in the next pair. So we only have to examine ten different possibilities for each digit.
</p>
<p>At the highest level the barcode decoder works as follows:</p>
</p>
<ol>
<li>Isolate the barcode from the image.
</li>
<li>Stretch and normalize the barcode so it is in a standard layout. Also compensate for lighting and contrast variation.
</li>
<li>For each possible pair of digits - 00, 01, 02, etc., form the synthetic image consisting of the pattern at the left side of the barcode, followed by the pattern for the two digits, appropriately blurred. Find the pair that matches the best. Take the first digit of the pair to be the first digit of the barcode.
</li>
<li>For the next digit, take the digit just found, say 3, and synthesize the blurred images of the digit pairs-30, 31, etc.. Compare them with the barcode; choosing the best match. This gives the next digit in the barcode. Repeat this step until all six digits (for a UPC barcode) are found.
</li>
</ol>
<p>
In this way we work across the barcode, comparing the synthetic image with the actual image two digits at a time. When we reach the middle of the barcode we start over, since there's a gap between the left and right halves..
</p>
<p>After all this is done, we have, for each row in the barcode, a sequence of digits for the left and right side. But different rows are going to give different sequences, and we need a way to determine which sequence is correct. In order to do this, we form the vertical average of the barcode image (to eliminate as much noise as possible) and compare it with each left and right side to determine how well they match. We then consider the top few possible left and right sides and see whether or not they pass the check digit test. The best match that passes the check digit test is our result.
</p>
<p>Finally, we have a test to see if our best guess at the barcode matches well enough overall to be considered a correct match. If it passes, we report the result back. If not, we draw a big red X over the image to indicate we could not find a barcode.
</p>
<h2>How it works: In more detail
</h2>
The processing in <code>CReadBarcode::DoItL</code> is broken down into four steps:
<ol>
<li>Finding the edges of the barcode.
</li>
<li>Rectifying the barcode into a rectangular layout.
</li>
<li>Finding the precise edges of the barcode and normalizing the rectangular barcode image.
</li>
<li>Decoding.
</li>
</ol>
<h3>Finding the edges of the barcode</h3>
<p>We begin by converting the image from the color image captured by the camera phone sensor to gray.
This is done using an image processing pipeline constructed with JSIL (Jon's Symbian Imaging Library)
in the <code>CReadBarcode::CropAndDetectEdgesL</code> member function.
</p>
<p>The first stage of the pipeline uses the <code>CRgbSelectBand</code> class to select the green band of the
image. The green band is used because inexpensive color sensors capture color images using a
pixel layout called a "Bayer mosaic" which makes half the pixels green, one quarter red, and
one quarter blue, because of human eye sensitivity to the color green. Green is therefore the
highest resolution band. Selecting it gives the highest resolution gray image.
</p>
<p>The next stage in the pipeline <code>CCrop</code>, crops the image to the rectangle from the
original user interface. This cropped image is saved for later using <code>IReplicate</code>, a helper class that copies the bitmap.
</p>
<p>Next we apply a Canny edge detector horizontally (using the <code>CCannyHoriz</code> class) to
detect edges in the barcode. The resolution of the edge detector is set high enough so that any
significant edges in the barcode, particularly those at the ends, will be detected.
</p>
<p>Switching now to the <code>CReadBarcode::FindBarcodeEdgesL</code> function, we find the zero-crossings
in the edge image, using <code>CZeroCrossingHoriz</code>. Zero-crossings give us the precise horizontal
position of each edge. We then take, in each row of the image, the first zero crossing, and
fit a line to the positions using the Hough transform <code>CLineFitHough</code>. This gives
a line at the boundary of the left side of the barcode. We repeat this process with the last
zero crossing in each row, getting a line at the right side of the barcode. These two lines thus bound the barcode.
</p>
<h3>Rectifying the barcode into a rectangular layout.
</h3>
<p>Once the left and right edges of the barcode are found, we form the trapezoid consisting
of the left and right edges and the first and last row of the barcode, and stretch the image
so its width is equal to the greater of the widths of the first and the last rows, using
<code>CTrapezoidWarp</code> in the <code>CReadBarcode::RectifyBarcodeL</code> member function.
</p>
<h3>Finding the precise edges of the barcode and normalizing the rectangular barcode image
</h3>
<p>Now that the barcode has been warped into a rectangle, we can do a better job of finding its
left and right edges. All we have to do is to sum the barcode vertically and look for a large
change in brightness. The quiet area on either side of the barcode will be light colored, and a
(suitably blurred) barcode will be darker. So by looking for a transition from light to dark on
the left side of the barcode and from dark to light on the right side, we will obtain the extent of the barcode.
</p>
<p>This processing is done in <code>CReadBarcode::FindPreciseBarcodeLimitsL</code>. The vertical average of the
barcode image is taken using <code>CVerticalAverage</code>. The result of this is a one-dimensional array. We
form sums of this array over wide and narrow windows using <code>FormShortAndLongSumsL</code>. Then, on the
left side, we look for the point in the left third of the image where there is the largest
positive difference between the narrow sum and the wide sum. We do this because we want the
narrow sum to lie in the light quiet area, and the wide sum to lie in the dark barcode. This
point is the left edge of the barcode. A similar test is used on the right side.
</p>
<p>The left and right barcode edges allow us to prepare the image for decoding. In order for
decoding to work without bias towards or against any of the digits in any of the positions,
we stretch the image using <code>CRectStretch</code> so that its width is an exact multiple
of the barcode width - i.e., for a UPC barcode, one of 95, 190, 285, etc. pixels. As part of the
same pipeline we reduce the image height by averaging using CReduce in order to speed up processing
while decoding and also histogram equalize the image using <code>CHistEq</code>. All this is done in
<code>CReadBarcode::CropAndStretchImageL</code>.
</p>
<h3>Decoding
</h3>
<p>The barcode is decoded using the <code>CBars2SymUpc</code> class. (Eventually, other barcode
decoders, such as an EAN decoder, will be implemented, but right now only UPC is recognized.) The
<code>CBars2SymUpc::DecodeL</code> function does the actual decoding. There are several steps in <code>DecodeL</code>:
</p>
<ol>
<li>Make guesses at the left and right barcodes for each row.
</li>
<li>For each reasonably popular guess at the left barcode, form a mask based on its
digits and convolve it with a vertically average of the barcode image, storing the convolution result.
</li>
<li>Repeat this with each reasonably popular guess at the right barcode.
</li>
<li>For each pair of guesses at the left and right barcodes, check to see if the pair
passes the check digit test. If it does, take its combined convolution result, and
compare it with the best convolution result so far. If it is better, this pair is the new best guess at the barcode.
</li>
</ol>
<p>The point of the test in steps b and c is that the program that generates the barcode
guesses in step a does not use an exact test. As we form the barcode guesses in step a,
we generate the next digit by testing all pairs combined with the previous digit. This
forms the best guess at a digit by taking into account the blurring that results from
the digit to the left, but ignores the blurring that results from the digit to the right.
So we need a way to weed out those guesses where the inaccuracy of considering just pairs
of digits from left to right results in a bad result. When we form the complete digit mask
in steps b and c we blur both to the left and right, so that the match estimate is more exact.
Also, by convolving with a vertically averaged barcode image, we eliminate as much noise as possible.
</p>
<p>The guesses at the left and right barcodes are made in <code>CBars2SymUpc::EstimateCodeLeftL</code>
and<code> CBars2SymUpc::EstimateCodeRightL</code>. Prior to <code>CBars2SymUpc::EstimateCodeLeftL</code>,
<code>CBars2SymUpc::BuildLeftSideMaskL</code> has built one hundred masks, one for each of the digit
pairs 00, 01, ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -