Method for reading a two-dimensional barcode

• US 6,371,373 B1
• Filed: 05/25/1999
• Issued: 04/16/2002
• Est. Priority Date: 05/25/1999
• 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): FRANKLIN, JAMARA ALZAIDA
• Application Number:
  US09/318,462
• Time in Patent Office: 1,057 Days
• Field of Search: 235/462.09, 235/462.1, 235/462.11, 235/456, 235/454, 235/462.01, 235/462.07, 235/462.16, 235/462.18, 235/462.19, 235/462.25, 235/462.26, 235/462.27, 235/462.28
• 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/1452 detecting bar code edges

Abstract

Two embodiments of a method of decoding information stored in a two-dimensional barcode printed on a printed medium are introduced. Both embodiments provide an improved method of analyzing horizontal and vertical edge count arrays to identify the column and row centerlines therein to enable the subsequent reading of the binary data located at the intersection of each row centerline and column centerline. In the first embodiment, the centerlines are located by first locating each successive pair of peaks in the respective edge count array, where each peak must have 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. Preferably, each successive pair of peaks in the respective edge count array is separated by a third predetermined value. In addition, the first predetermined value is preferably reduced by a predetermined amount if a second peak within a pair of peaks in the respective edge count array is separated from a first peak by more than a fourth predetermined value, and the second peak is then re-identified using the reduced first predetermined value. The second embodiment alternately employs the method of the first embodiment or a prior art method to reduce the number of errors produced, using the prior art method first to locate the column centerlines and the method of the first embodiment first to locate the row centerlines.

Claims

1. A method of decoding information stored in a two-dimensional barcode printed on a printed medium, comprising the steps of:

scanning a two-dimensional barcode to create a two-dimensional pixel array representing said two-dimensional barcode;

determining the horizontal edge count in each row of pixels in said two-dimensional pixel array;

determining the vertical edge count in each column of pixels in said two-dimensional pixel array;

determining the column centerlines by locating each successive pair of peaks in said horizontal edge counts, and then locating a column centerline in a valley region between each successive pair of peaks;

determining the row centerlines by locating each successive pair of peaks in said vertical edge counts, and then locating a row centerline in a valley region between each successive pair of peaks; and

reading out binary data located at the intersection of each row centerline and column centerline to produce a signal representative of the encoded information in said two-dimensional barcode.

2. The method of claim 1, wherein each of said peaks in said horizontal edge counts has a magnitude greater than a predetermined peak threshold, and each of said peaks in said vertical edge counts has a magnitude greater than a predetermined peak threshold.

3. The method of claim 1, wherein each of said column centerlines has a magnitude less than a predetermined valley threshold, and each of said row centerlines has a magnitude less than a predetermined valley threshold.

4. The method of claim 1, wherein each of said successive pair of peaks in said horizontal edge counts is separated by at least a predetermined distance, and each of said successive pair of peaks in said vertical edge counts is separated by at least a predetermined distance.

5. The method of claim 2, wherein said step of determining the column centerlines includes a further step of reducing said predetermined peak threshold by a predetermined amount if a second peak within a pair of peaks in said horizontal edge counts is separated from a first peak by more than a predetermined distance, and then re-identifying said second peak using said reduced predetermined peak threshold, and said step of determining the row centerlines includes a further step of reducing said predetermined peak threshold by a predetermined amount if a second peak within a pair of peaks in said vertical edge counts is separated from a first peak by more than a predetermined distance, and then re-identifying said second peak using said reduced predetermined peak threshold.

6. A method of decoding information stored in a two-dimensional barcode printed on a printed medium, comprising the steps of:

scanning a two-dimensional barcode to create a two-dimensional pixel array representing said two-dimensional barcode;

determining the horizontal edge count in each row of pixels in said two-dimensional pixel array;

determining the vertical edge count in each column of pixels in said two-dimensional pixel array;

determining the column centerlines by locating each successive pair of peaks in said horizontal edge counts, each of said peaks having a magnitude greater than a predetermined peak threshold and each of said successive pair of peaks being separated by at least a predetermined distance, and then locating a column centerline in a valley region between each successive pair of peaks, each of said column centerlines having a magnitude less than a predetermined valley threshold;

determining the row centerlines by locating each successive pair of peaks in said vertical edge counts, each of said peaks having a magnitude greater than a predetermined peak threshold and each of said successive pair of peaks being separated by at least a predetermined distance, and then locating a row centerline in a valley region between each successive pair of peaks, each of said row centerlines having a magnitude less than a predetermined valley threshold; and

reading out binary data located at the intersection of each row centerline and column centerline to produce a signal representative of the encoded information in said two-dimensional barcode.

7. A method of decoding information stored in a two-dimensional barcode printed on a printed medium, comprising the steps of:

scanning a two-dimensional barcode to create a two-dimensional pixel array representing said two-dimensional barcode;

determining the horizontal edge count in each row of pixels in said two-dimensional pixel array;

determining the vertical edge count in each column of pixels in said two-dimensional pixel array;

determining the column centerlines by the steps of

locating the local minima representing the column centerlines in said horizontal edge counts, and comparing the number of column centerlines located to a predetermined number, or

alternately, locating, if the number of column centerlines located is not equal to the predetermined number, the column centerlines by locating each successive pair of peaks in said horizontal edge counts, and then locating a column centerline in a valley region between each successive pair of peaks;

determining the row centerlines by the steps of

locating each successive pair of peaks in said vertical edge counts, locating a row centerline in a valley region between each successive pair of peaks, and then comparing the number of row centerlines located to a predetermined number, or

alternately, locating, if the number of row centerlines located is not equal to the predetermined number, the row centerlines by locating the local minima representing the row centerlines in said vertical edge counts;

reading out binary data located at the intersection of each row centerline and column centerline to produce a signal representative of the encoded information in said two-dimensional barcode.

8. The method of claim 7, wherein said step of determining the row centerlines further includes, instead of said alternate locating step, a step of locating and deleting an extra centerline upon detection that the number of row centerlines first located is one greater than the predetermined number.

9. The method of claim 7, wherein said step of determining the row centerlines further includes, instead of said alternate locating step, a step of inserting an extra centerline upon detection that the number of row centerlines first located is one less than the predetermined number.

10. The method of claim 7, wherein each of said peaks in said horizontal edge counts has a magnitude greater than a predetermined peak threshold, and each of said peaks in said vertical edge counts has a magnitude greater than a predetermined peak threshold.

11. The method of claim 7, wherein each of said column centerlines has a magnitude less than a predetermined valley threshold, and each of said row centerlines has a magnitude less than a predetermined valley threshold.

12. A method of decoding information stored in a two-dimensional barcode printed on a printed medium, comprising the steps of:

scanning a two-dimensional barcode to create a two-dimensional pixel array representing said two-dimensional barcode;

determining the horizontal edge count in each row of pixels in said two-dimensional pixel array;

determining the vertical edge count in each column of pixels in said two-dimensional pixel array;

determining the row centerlines by the steps of

locating the local minima representing the row centerlines in said vertical edge counts, and comparing the number of row centerlines located to a predetermined number, or

alternately, locating, if the number of row centerlines located is not equal to the predetermined number, the row centerlines by locating each successive pair of peaks in said vertical edge counts, and then locating a row centerline in a valley region between each successive pair of peaks;

determining the column centerlines by the steps of

locating each successive pair of peaks in said horizontal edge counts, locating a column centerline in a valley region between each successive pair of peaks, and then comparing the number of column centerlines located to a predetermined number, or

alternately, locating, if the number of column centerlines located is not equal to the predetermined number, the column centerlines by locating the local minima representing the column centerlines in said horizontal edge counts;

reading out binary data located at the intersection of each row centerline and column centerline to produce a signal representative of the encoded information in said two-dimensional barcode.

13. The method of claim 12, wherein said step of determining the column centerlines further includes, instead of said alternate locating step, a step of locating and deleting an extra centerline upon detection that the number of column centerlines first located is one greater than the predetermined number.

14. The method of claim 12, wherein said step of determining the column centerlines further includes, instead of said alternate locating step, a step of inserting an extra centerline upon detection that the number of column centerlines first located is one less than the predetermined number.

15. The method of claim 12, wherein each of said peaks in said vertical edge counts has a magnitude greater than a predetermined peak threshold, and each of said peaks in said horizontal edge counts has a magnitude greater than a predetermined peak threshold.

16. The method of claim 12, wherein each of said row centerlines has a magnitude less than a predetermined valley threshold, and each of said column centerlines has a magnitude less than a predetermined valley threshold.