Robust barcode reader

• US 6,814,291 B1
• Filed: 12/15/2003
• Issued: 11/09/2004
• Est. Priority Date: 12/15/2003
• Status: Expired due to Fees

• Current Assignee: Pitney Bowes Incorporated (Böwe Systec AG), University of Connecticut (State of Connecticut)
• Original Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Inventors: Javidi, Bahram, Kirschner, Wallace, Cordery, Robert A.
• Primary Examiner(s): Fureman, Jared J.
• Assistant Examiner(s): TRAIL, ALLYSON NEEL
• Application Number:
  US10/736,036
• Time in Patent Office: 330 Days
• Field of Search: 235/462.25, 235/462.09, 235/462.1, 235/462.01, 235/462.08, 235/462.32, 235/494
• US Class Current: 235/462.25
• 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
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/247 by affine transforms, e.g. correction due to perspective effects; Quadrilaterals, e.g. trapezoids

Abstract

A method and system for reading a two-dimensional barcode symbol on a mailpiece. The barcode symbol may be distorted during the printing process or the image acquiring process, rendering it difficult to recognize by a conventional template matching method. Typically, a two-dimensional barcode symbol is composed on a two-dimensional array of visually contrasting blocks. Any group of four adjacent blocks sharing a common corner may form an identifiable pattern. These patterns can be used as internal landmarks. When the barcode symbol is distorted, the distances between the internal landmarks change accordingly. Using an Lp-norm algorithm to measure the distances in the transform domain, distortion can thus be determined and the global geometry of the barcode symbol restored based on the distance measurements.

Claims

1. A method for reconstructing global geometry of a two-dimensional barcode susceptible to geometrical distortion, said barcode having a two-dimensional pattern composed of a plurality of contrasting polygons and comprising a plurality of common corners located at different locations within the two-dimensional pattern, each common corner defined by a group of said contrasting polygons located adjacent to each other, said method comprising the steps of:

(a) acquiring an image of at least a part of the two-dimensional pattern;

(b) comparing at least a portion of the acquired image with at least one template pattern for finding a match therebetween, each of said at least one template pattern comprising a group of contrasting sections located adjacent to each other defining at least one further common corner;

(c) locating a number of common vertices within the two-dimensional pattern based on the further common corner;

(d) obtaining a plurality of distances between the located common corner; and

(e) determining linearity of at least a portion of the two-dimensional pattern based on the obtained distances in order to reconstruct global geometry of the barcode.

2. The method of claim 1, wherein the contrasting polygons are black and white.

3. The method of claim 1, wherein the contrasting polygons are rectangular and each common corner is defined by four adjacent contrasting polygons.

4. The method of claim 3, wherein each further common vertex is defined by four adjacent contrasting polygons.

5. The method of claim 1, wherein the template pattern is a pattern in a frequency domain, said method further comprising the step of:

transforming the portion of the acquired image into a transformed image in the frequency domain so as to carry out the comparing step in the frequency domain.

6. The method of claim 5, wherein the frequency domain has a plurality of frequencies in a frequency range, said comparing comprising the steps of:

(a) obtaining a difference between the template pattern and the transformed image at said plurality of frequencies in the frequency domain,

(b) summing the differences over the frequency domain for providing an error measurement, and

(c) determining whether the match is found based on the error measurement.

7. The method of claim 6, wherein the difference at each of said plurality of frequencies is raised to a power of N prior to said summing, wherein N is a number greater than 0.

8. A data processing system for use in conjunction with an imaging device for recognizing a two-dimensional barcode on an item, said barcode having a two-dimensional pattern composed of a plurality of contrasting polygons and comprising a plurality of common corners located at different locations within the two-dimensional pattern, each common corner defined by a group of said contrasting polygons located adjacent to each other, the imaging device disposed relative to the item for acquiring at least a part of the two-dimensional pattern for providing data indicative of the acquired pattern, said two-dimensional barcode susceptible to geometrical distortion, said system comprising:

(a) a data input device, operatively connected to the imaging device, for receiving data indicative of the acquired pattern;

(b) a software program, responsive to the received data, for carrying out a plurality of data processing steps, which comprises;

(c) comparing at least a portion of the acquired pattern with at least one template pattern for finding a match therebetween, each of said at least one template pattern comprising a group of contrasting sections located adjacent to each other defining at least one further common corner;

(d) locating a number of common vertices within the two-dimensional pattern based on the further common corner;

(e) obtaining a plurality of distances between the located common corner; and

(f) determining linearity of at least a portion of the two-dimensional pattern based on the obtained distances in order to reconstruct global geometry of the barcode.

9. The system of claim 8, wherein the template pattern is a pattern in a frequency domain, said data processing steps further comprise:

transforming the portion of the acquired image into a transformed image in the frequency domain so as to carry out the comparing step in the frequency domain.

10. The system of claim 9, wherein the frequency domain has a plurality of frequencies in a frequency range, said comparing comprising the steps of

(a) obtaining a difference between the template pattern and the transformed image at said plurality of frequencies in the frequency domain,

(b) summing the differences over the frequency domain for providing an error measurement, and

(c) determining whether the match is found based on the error measurement.