Border-less clock free two-dimensional barcode and method for printing and reading the same

• US 6,201,901 B1
• Filed: 06/01/1998
• Issued: 03/13/2001
• Est. Priority Date: 06/01/1998
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Tomkins, Andrew, Zhou, Jiangying, Lopresti, Daniel P.
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/088,189
• Time in Patent Office: 1,016 Days
• Field of Search: 382/190, 382/195, 382/294, 382/296, 382/306, 382/318, 382/100, 382/232, 382/193, 382/289, 382/182, 382/183, 382/312, 382/309, 382/203, 382/164, 382/165, 235/456, 235/437, 235/462.09, 235/462.1, 235/470, 235/494, 235/454, 235/462.23, 235/462.36, 358/433, 358/445, 358/447, 358/448, 250/236, 250/568, 283/70
• US Class Current: 382/306
• CPC Class Codes: G06K 19/06028 using bar codes
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence

Abstract

Inventive two-dimensional barcodes, each having encoded digital information in a bitmap representing preferably randomized encoded data bits, are printed onto a printed medium. Preferably, error correction codes are added to the digital information to ensure that the decoding process accurately reproduce the digital information. In one embodiment, the bitmap may further include “anchor” bits in each corner, which are used as part of the skew estimation and deskewing processes during decoding. In a second embodiment, no “anchor” bits are required. The encoded digital information is mapped into the two-dimensional barcode in such a way as to minimize the errors caused by damage to particular rows and/or columns, for example, row damage caused by faxing the printed barcode. To extract the encoded digital information from the printed medium, the printed medium is scanned, then the bitmap is located within the printed medium. The skew of the bitmap, if any, is determined, and the bitmap is deskewed if necessary. The bitmap is then cropped, and the randomized digital information is read from the bitmap. The digital information is derandomized and any error correction codes are removed, in the process correcting and/or recording any errors discovered, thereby reproducing the original encoded digital information.

Claims

1. A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each of said data pixels being either a first or second color, said printed medium further having other printed information thereon, comprising the steps of:

scanning said printed medium to digitize said bitmap and said other information;

formatting said bitmap and said other information to a pixel based grayscale representation;

setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color;

determining the row and column boundaries by determining the number of first color pixels in each row and each column of the scanned printed medium, and sequentially comparing the number of first pixels in each row and column, respectively, to a predetermined threshold;

determining the skew angle of said digitized bitmap;

deskewing said digitized bitmap so that said skew angle is reduced to substantially zero;

cropping said digitized bitmap;

reading out binary data from said digitized bitmap in a predetermined pattern to produce a one-dimensional array of digital data;

derandomizing said one-dimensional array of digital data; and

error-correcting the derandomized one-dimensional array of digital data to produce a substantially error-free digital representation of the encoded information.

6. The method as in claim 1, 3, 4 or 5, wherein said skew angle determining step uses either a template matching procedure or a Hough-transform procedure.

7. The method as in claims 1, 2, 4 or 5, wherein said deskewing step uses either a shear rotation procedure or a trigonometric procedure.

8. The method as in claims 1, 2 or 3, wherein said reading step reads said binary data in each of four alternative directions creating four alternative one-dimensional arrays of digital data, and said error correcting step selects the one-dimensional array of digital data with the least number of errors for output.

9. The method as in claims 1, 2 or 3, wherein said derandomizing step repeatedly derandomizes said one-dimensional array of digital data by alternative designated keys until the errors detected by said error correcting step fall below a preset threshold.

10. The method as in claims 1, 2, 3, 4 or 5, wherein said reading step comprises the steps of:

determining the number of horizontal and vertical edges in each respective row and column of said bitmap;

determining the row center lines from the local minima in the horizontal edge counts;

determining the column center lines from the local minima in the vertical edge counts; and

reading out binary data located at the intersection of each row center line and column center line in a predetermined pattern to produce a one-dimensional digital representation of said digitized bitmap.

2. A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each of said data pixels being either a first or second color, comprising the steps of:

scanning said printed medium to digitize said bitmap;

formatting said bitmap to a pixel based grayscale representation;

setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color;

determining the skew angle of said digitized bitmap by either a template matching procedure or a Hough-transform procedure;

deskewing said digitized bitmap so that said skew angle is reduced to substantially zero;

cropping said digitized bitmap;

reading out binary data from said digitized bitmap in a predetermined pattern to produce a one-dimensional array of digital data;

derandomizing said one-dimensional array of digital data; and

error-correcting the derandomized one-dimensional array of digital data to produce a substantially error-free digital representation of the encoded information.

3. A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each of said data pixels being either a first or second color, comprising the steps of:

scanning said printed medium to digitize said bitmap;

formatting said bitmap to a pixel based grayscale representation;

setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color;

determining the skew angle of said digitized bitmap;

deskewing said digitized bitmap so that said skew angle is reduced to substantially zero by either a shear rotation procedure or a trigonometric procedure;

cropping said digitized bitmap;

reading out binary data from said digitized bitmap in a predetermined pattern to produce a one-dimensional array of digital data;

derandomizing said one-dimensional array of digital data; and

error-correcting the derandomized one-dimensional array of digital data to produce a substantially error-free digital representation of the encoded information.

4. A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each of said data pixels being either a first or second color, comprising the steps of:

scanning said printed medium to digitize said bitmap;

formatting said bitmap to a pixel based grayscale representation;

setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color;

determining the skew angle of said digitized bitmap;

deskewing said digitized bitmap so that said skew angle is reduced to substantially zero;

cropping said digitized bitmap;

reading out binary data from said digitized bitmap in a predetermined pattern in each of four alternative directions to produce four alternative one-dimensional arrays of digital data;

derandomizing said four one-dimensional arrays of digital data; and

error-correcting said four derandomized one-dimensional arrays of digital data and selecting the one-dimensional array of digital data with the least number of errors for output of the decoded information.

5. A method of decoding randomized information printed on a printed medium in the form of a bitmap of rows and columns of data pixels representing encoded data bits, each of said data pixels being either a first or second color, comprising the steps of:

scanning said printed medium to digitize said bitmap;

formatting said bitmap to a pixel based grayscale representation;

setting the threshold intensity level based on said grayscale representation such that pixels above said threshold correspond to said first color and pixels below said threshold correspond to said second color;

determining the skew angle of said digitized bitmap;

deskewing said digitized bitmap so that said skew angle is reduced to substantially zero;

cropping said digitized bitmap;

reading out binary data from said digitized bitmap in a predetermined pattern to produce a one-dimensional array of digital data; and

derandomizing and error-correcting said a one-dimensional array of digital data by alternative designated keys until the errors determined fall below a predetermined level.