Method for locating and reading a two-dimensional barcode

• US 6,082,619 A
• Filed: 12/16/1998
• Issued: 07/04/2000
• Est. Priority Date: 12/16/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: Ma, Yue, Kanai, Junichi
• Primary Examiner(s): Lee, Michael G
• Assistant Examiner(s): Lee, Diane
• Application Number:
  US09/212,243
• Time in Patent Office: 566 Days
• Field of Search: 235/456, 235/460, 235/494, 235/462.1, 235/462.08, 235/462.11, 235/437, 235/438, 382/237, 382/270, 382/281, 382/289
• US Class Current: 235/462.1
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore

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.

Claims

1. 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.

2. The method of claim 1, whereby said window of said locating step comprises a core region corresponding to said predetermined size of said bitmap and a quiet region corresponding to said outer region, and wherein said testing comprises separately testing portions of said representation encompassed by said core region and said quiet region to determine whether said portions conform to one or more characteristics of said bitmap and said outer region, respectively, and wherein the boundaries of said candidate region are set to the boundaries of said core region.

3. The method of claim 2, wherein said testing of said core region comprises determining if the density of pixels of said first color or said second color within said portion of said representation encompassed by said core region is within a predetermined range.

4. The method of claim 2, wherein said testing of said quiet region comprises determining if the density of pixels of said first color or said second color within said portion of said representation encompassed by said quiet region is within a predetermined range.

5. The method of claim 1, wherein said locating step further comprises an additional testing step in which said candidate region is cropped and the dimensions of said cropped candidate region are compared to said predetermined size of said bitmap.

6. The method of claim 1, whereby said printed human readable medium further comprises other information, and wherein said scanning step, said formatting step and said converting step operate on said bitmap and said other information.

7. The method of claim 1, wherein said skew angle determining step comprises:

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.

8. The method of claim 7, whereby said candidate region is divided into a plurality of horizontal and/or vertical regions, preliminary skew angles are calculated for each of said plurality of horizontal and/or vertical regions, and said skew angle is selected by a voting scheme from said preliminary skew angles.

9. The method of claim 8, whereby said voting scheme selects the median value of said preliminary skew angles.

10. The method of claim 8, whereby said voting scheme selects the mean value of said preliminary skew angles.

11. The method of claim 1, further comprising the step of:

reducing the resolution of said pixel based binary representation by a predetermined factor prior to said locating step; and

wherein said locating step extracts said candidate region at the original resolution of said pixel based binary representation.

12. The method of claim 1, wherein said locating step moves said window in a predetermined pattern across at least one predetermined portion of said converted representation.

13. The method of claim 12, whereby said predetermined pattern moves along rows, starting at a center row of said converted representation, and then moving repeatedly one row upwards and then one row downwards, respectively, until the first row and last row of said converted representation is reached.

14. The method of claim 12, whereby said at least one predetermined portion consists of at least one corner of said converted representation.

15. The method of claim 1, further comprising the step of cropping said digitized bitmap after said deskewing step.

16. 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.

17. The method of claim 16, wherein said locating step comprises 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.

18. The method of claim 16, further comprising the step of:

reducing the resolution of said pixel based binary representation by a predetermined factor prior to said locating step; and

wherein said locating step extracts said candidate region at the original resolution of said pixel based binary representation.

19. The method of claim 16, further comprising the step of cropping said digitized bitmap after said deskewing step.

20. A method of locating a two-dimensional barcode within a scanned binary image comprising:

moving a window across said image in stepwise fashion in a predetermined pattern;

testing at each step a portion of said image which is encompassed by said window to determine whether said portion conforms to one or more characteristics of said two-dimensional barcode; and

setting the boundaries of said digitized bitmap as the boundaries of said window if said portion does conform to said one or more characteristics of said two-dimensional barcode.

21. A method of determining the skew angle of a two-dimensional barcode within a candidate region of a scanned binary image, comprising the steps of:

locating horizontal or vertical edges within said two-dimensional barcode using a finite-state recognizer;

calculating the coordinates of a horizontal or vertical line within said two-dimensional barcode 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 two-dimensional barcode 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.