Registers – Coded record sensors – Particular sensor structure
Reexamination Certificate
1999-05-25
2002-04-16
Lee, Michael G. (Department: 2876)
Registers
Coded record sensors
Particular sensor structure
C235S462010, C235S462090, C235S462250, C235S456000
Reexamination Certificate
active
06371373
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to an improved method for reading two-dimensional barcodes printed within an image. In particular, the method of reading two-dimensional barcodes of the present invention provides improved performance when reading documents which have been previously transmitted by facsimile, or which contain noise similar to that caused by facsimile machines.
BACKGROUND OF THE INVENTION
A common technique for reading raw bits (i.e., logical bits representing either a “1” or a “0”) in a one-dimensional barcode is to move a horizontal scan line across the barcode and detect transitions from white to black and from black to white. However, this technique cannot be directly applied to a two-dimensional barcode which consists of an array of N rows and M columns of logical bits, because a single scan line can not determine which of the N rows or which of the M columns it is reading.
Various techniques have been used to read the logical bits from a two-dimensional barcode which involve the addition of alignment marks and/or clock bits that are used to specifically identify the separate rows and columns.
A method of reading a two-dimensional barcode which does not require clock bits or alignment marks to identify rows or columns of logical bits is described in U.S. Pat. No. 5,862,270 (“the '270 Patent”), entitled “A Clock-Free Two-Dimensional Barcode and Method for Printing and Reading the Same” and assigned to the same assignee as the present invention. The contents of the '270 Patent are explicitly incorporated by reference herein. As described in further detail in the '270 Patent, the method for reading the logical bits within a two-dimensional barcode described therein operates on the bit array resulting from the scanning process. All of the horizontal “edges” for each column of the pixel array, and all of the vertical “edges” for each row are identified and then counted, and then horizontal and vertical histograms (actually one-dimensional arrays) are created of the edge count for each column and row, respectively. Each array is then examined to determine the local minimas, which represent the center lines for each column and row, since there are much fewer edges in the center of a column or row than at the periphery. Since the system has a priori knowledge of how many logical bits are in a column and in a row (and thus how far apart the column and row centerlines should be), the processing of these one-dimensional arrays is improved by only looking within particular regions for the local minimas.
However, the method of the '270 Patent may encounter difficulties in reading a two-dimensional barcode which has been transmitted by facsimile, due to distortion of the barcode caused by horizontal line drop and horizontal line repeat during the facsimile transmission of the document, or a two-dimensional barcode which contains drawn line noise in either the horizontal or vertical directions. A horizontal line drop, when it occurs at the point on the document being transmitted where the barcode is positioned, causes the height of a row of logical bits to be smaller than the height of the rest of the rows within the two-dimensional barcode. Of course, as one reasonably skilled in the art will recognize, if the horizontal line drop is so large that an entire row of logical bits is deleted, no amount of processing can read the deleted logical bits, although, as discussed in the '270 Patent, error correction techniques may be used to recover the lost data. On the other hand, a horizontal line repeat, when it occurs at the point on the document being transmitted where the barcode is positioned, causes the height of one row of logical bits to be larger than the height of the rest of the rows and the height of another row of logical bits to be smaller than the height of the rest of the rows within the two-dimensional barcode. Drawn line noise is caused by actual marking of the document by, e.g., a pencil, and can cause a single row or column of logical bits to appear as two separate rows or columns of logical bits having a height or width, respectively, smaller than the rest of the rows or columns.
The method of '270 Patent may miss a row centerline, add a row centerline, or both, due to line repeat or line drop distortion, since both types of distortion cause the center line for the row distorted to have an unanticipated row to row spacing. In
FIG. 1
, a barcode
10
which has suffered a line drop of four lines is shown alongside the resulting vertical edge histogram
20
(histograms are used herein to graphically display the horizontal (or column) and vertical (or row) edge count arrays which are processed to locate the column and row centerlines, respectively). The row centerlines
30
through
60
and
80
have been determined by the method of the '270 Patent. While row centerlines
30
,
40
,
50
and
80
have been correctly determined, centerline
60
was incorrectly determined due to the extra local minima caused by the line drop and is thus too close to centerline
50
. In addition, local minima
70
, representing the proper centerline for that row, was missed since it was not within the region examined for a local minima.
It is therefore an object of the present invention to provide an improved method of reading a clock free two-dimensional barcode printed on a printed medium.
It is an additional object of this invention to provide a method of reading a clock free two-dimensional barcode which includes distortion caused by the transmission by facsimile of the document on which the barcode is printed.
It is yet another object of this invention to provide a method of reading a clock free two-dimensional barcode which includes distortion caused by lines drawn on the face of the document on which the barcode is printed.
Various other objects, advantages and features of the present invention will become readily apparent from the ensuing detailed description and the novel features will be particularly pointed out in the appended claims.
SUMMARY
The present invention is directed to a method of decoding information stored in a two-dimensional barcode printed on a printed medium which provides improved performance when the barcode to be read includes line drop or line repeat distortion caused by transmission by facsimile. Two embodiments of the present invention are disclosed. In both embodiments, the two-dimensional barcode is first scanned to create a two-dimensional pixel array representing the two-dimensional barcode. Then the number of horizontal edges in each column of pixels in the two-dimensional pixel array are determined and stored in an horizontal edge count array, and, likewise, the number of vertical edges in each row of pixels in the two-dimensional pixel array are determined and stored in a vertical edge count array. Each array is then processed to locate the centerlines therein, where the intersection of each column and row centerline represents the position of a binary bit of data stored in the two-dimensional barcode. The centerlines are then used to extract the binary data from the scanned two-dimensional barcode, to produce a signal representative of the encoded information stored therein.
In the first embodiment, the horizontal and vertical edge count arrays are processed in the same manner to extract the column and row centerlines, respectively. In particular, each of the two edge count arrays is separately scanned to determine the centerlines therein by locating each successive pair of peaks in the edge counts, each of the peaks having a magnitude greater than a first predetermined value, and then locating a centerline in a valley region between each successive pair of peaks, each of the centerlines having a magnitude less than a second predetermined value. Once both edge count arrays have been processed, the binary data located at the intersection of each row centerline and column centerline is read to produce a signal representative of the encoded information in the two-dimensional barcode. Pr
Kanai Junichi
Ma Yue
Amster Rothstein & Ebenstein
Franklin Jamara A
Lee Michael G.
Matsushita Electric - Industrial Co., Ltd.
LandOfFree
Method for reading a two-dimensional barcode does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for reading a two-dimensional barcode, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for reading a two-dimensional barcode will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925684