US 6,082,619 A · Method for locating and reading a two-dimensional barcode

Abstract

Two-dimensional barcodes surrounded by a quiet zone of white space which may or may not include a border, each barcode having encoded digital information in a bitmap representing preferably randomized encoded data bits, are printed onto a printed medium. To extract the encoded digital information from the printed medium, the printed medium is scanned, then the bitmap is located within the printed medium by moving a window, in stepwise fashion in a predetermined pattern across the printed medium. At each step the portion of the printed medium which is encompassed by the window is tested to determine whether it conforms to one or more characteristics of the bitmap. The skew of the bitmap, if any, is determined, by using a finite-state recognizer in combination with a Hough Transform calculation. In one embodiment, the candidate region is divided into a plurality of horizontal regions, preliminary skew angles are calculated for each region, and the actual skew angle is selected using a voting scheme. Once the skew angle is calculated, the bitmap is deskewed if necessary, cropped, and the randomized digital information is read from the bitmap. Finally, 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.

Claims21

Dependent claims

A method of decoding randomized information printed on a human readable 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 bitmap having a predetermined size and surrounded by an outer region of pixels of predetermined substantially uniform color, comprising the steps of:

scanning said human readable medium to digitize said bitmap;
formatting said bitmap to a pixel based grayscale representation;
converting said pixel based grayscale representation to a pixel based binary representation by setting a threshold intensity level based on said grayscale representation and converting pixels to a first level or to a second level dependent on their relationship to said threshold;
locating the row and column boundaries of a candidate region for said digitized bitmap by moving a window across said pixel based binary representation in stepwise fashion in a predetermined pattern, at each step testing a portion of said representation which is encompassed by said window to determine whether said portion conforms to one or more characteristics of said bitmap, and setting the boundaries of said candidate region as the boundaries of said window if said portion does conform to said one or more characteristics of said bitmap;
determining the skew angle of said digitized bitmap within said candidate region;
deskewing said digitized bitmap so that the skew angle is reduced to substantially zero;
reading out binary data from said digitized bitmap 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.

7 more elements

A method of decoding randomized information printed on a human readable 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 bitmap having a predetermined size and surrounded by a outer region of pixels of predetermined substantially uniform color, comprising the steps of:

scanning said human readable medium to digitize said bitmap;
formatting said bitmap to a pixel based grayscale representation;
converting said pixel based grayscale representation to a pixel based binary representation by setting a threshold intensity level based on said grayscale representation and converting pixels greater than or equal to said threshold to a first level and pixels less than said threshold to a second level;
locating the row and column boundaries of a candidate region for said digitized bitmap;
determining the skew angle of said digitized bitmap within said candidate region by locating horizontal or vertical edges within said bitmap using a finite-state recognizer, calculating the coordinates of a horizontal or vertical line within said bitmap representing said horizontal or vertical edges using the Hough Transform, and calculating said skew angle as the angle between the coordinates of said horizontal or vertical line within said bitmap and a horizontal line representing a row of pixels within said candidate region or a vertical line representing a column of pixels within said candidate region;
deskewing said digitized bitmap so that the skew angle is reduced to substantially zero;
reading out binary data from said digitized bitmap 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.

7 more elements

Dependencies are inferred from the claim text.

Method for locating and reading a two-dimensional barcode

Life of this patent

Method for locating and reading a two-dimensional barcode

Life of this patent

Abstract

Claims21