Method and apparatus for processing low resolution images of degraded bar code symbols

• US 5,276,315 A
• Filed: 05/14/1992
• Issued: 01/04/1994
• Est. Priority Date: 05/14/1992
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Surka, Stefan
• Primary Examiner(s): PITTS, HAROLD I
• Application Number:
  US07/883,004
• Time in Patent Office: 600 Days
• Field of Search: 235/462, 235/472, 235/384, 235/494
• US Class Current: 235/462.1
• CPC Class Codes: G06K 7/10 by electromagnetic radiation, e.g. optical sensing; by corpuscular radiation
• CPC Class Codes: G06K 7/1092 sensing by means of TV-scanning

Abstract

A system is disclosed for processing a two dimensional digital image representative of a bar code symbol. The bar code symbol is oriented in a bar direction. The system includes means for dividing the two dimensional image into a plurality of two dimensional sections perpendicular to the bar direction. Means for determining information representative of the intensity of a plurality of such sections is also provided. A one dimensional intensity projection signal is formed from the determined information. The system also includes means for calculating the areas of a plurality of regions described by the projection signal. The widths of a plurality of bars in the bar code symbol are determined from the calculated areas.

Claims

1. A method for decoding a bar code symbol oriented in a bar direction from a two dimensional digital input image representative of said bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said bar code symbol being comprised of a plurality of modules each of which has at least one bar and at least one space, wherein information is encoded in each of said modules in accordance with its width, comprising the steps of:

(A) dividing said two dimensional input image into a plurality of non-overlapping two dimensional sections, each of said two dimensional sections being bounded by first and second reference lines substantially parallel to said bar direction and third and fourth reference lines substantially perpendicular to said bar direction, wherein said third and fourth reference lines are spaced at least two pixels apart, and wherein said first, second, third and fourth reference lines are oriented omnidirectionally with respect to the rows and columns of pixels in said input image;

(B) determining a plurality of intensity information values representative of the intensities of corresponding sections of said plurality of sections by summing pixel values derived from said input image lying in each of said sections;

(C) forming a one dimensional intensity projection signal by arranging said plurality of intensity information values along an axis, said one dimensional intensity projection signal having a plurality of corresponding peaks;

(D) calculating the areas of a plurality of regions described by said one dimensional intensity projection signal, wherein each of said areas is bounded by a portion of said one dimensional intensity projection signal and said axis, said portion lying between corresponding peaks of said one dimensional projection signal; and

(E) determining the widths of a plurality of bars in said bar code symbol from said areas.

2. The method of claim 1, wherein step (C) further comprises the steps of:

(1) determining from said projection signal a minimum global scaling parameter and a maximum global scaling parameter; and

(2) globally scaling said projection signal in accordance with said minimum and maximum global scaling values.

3. The method of claim 2, wherein step (C)(1) comprises the steps of:

(a) determining a plurality of local minimum values from said projection signal;

(b) determining said minimum global scaling parameter from an average of said plurality of local minimum values;

(c) determining a plurality of local maximum values from said projection signal; and

(d) determining said maximum global scaling parameter from an average of said plurality of local maximum values.

4. The method of claim 3, wherein step (C) further comprises the step of:

(3) locally scaling said projection signal in accordance with said local minimum and local maximum values.

5. The method of claim 4, wherein step (C)(3) comprises the steps of:

(a) positioning a sliding window on said projection signal;

(b) calculating a contrast value for pixels in said window;

(c) comparing said contrast value to a predetermined threshold;

(d) if said contrast value exceeds said predetermined threshold then

locally scaling pixels in said window

otherwise marking pixels in said window as undefined;

(e) moving said sliding window a distance equal to one bin to the right;

(f) repeating steps (a)-(e) for the full length of said projection signal; and

(g) resolving by linear interpolation pixels marked undefined.

6. The method of claim 1, wherein said two dimensional digital image is representative of a corrupted bar code symbol.

13. The method of claim 1, wherein said plurality of intensity information values are determined in step (B) by summing only gray scale pixel values taken directly from said input image for each of said sections.

7. An apparatus for decoding a bar code symbol oriented in a bar direction from a two dimensional digital input image representative of said bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said bar code symbol being comprised of a plurality of modules each of which has at least one bar and at least one space, wherein information is encoded in each of said modules in accordance with its width, comprising the steps of:

(A) means for dividing said two dimensional input image into a plurality of non-overlapping two dimensional sections, each of said two dimensional sections being bounded by first and second reference lines substantially parallel to said bar direction and third and fourth reference lines substantially perpendicular to said bar direction, wherein said third and fourth reference lines are spaced at least two pixels apart, and wherein said first, second, third and fourth reference lines are oriented omnidirectionally with respect to the rows and columns of pixels in said input image;

(B) means for determining a plurality of intensity information values representative of the intensities of corresponding sections of said plurality of sections by summing pixel values derived from said input image lying in each of said sections;

(C) means for forming a one dimensional intensity projection signal by arranging said plurality of intensity information values along an axis, said one dimensional intensity projection signal having a plurality of corresponding peaks;

(D) means for calculating the areas of a plurality of regions described by said one dimensional intensity projection signal, wherein each of said areas is bounded by a portion of said one dimensional intensity projection signal and said axis, said portion lying between corresponding peaks of said one dimensional projection signal; and

(E) means for determining the widths of a plurality of bars in said bar code symbol from said areas.

8. The apparatus of claim 7, wherein said means for forming further comprises:

(1) means for determining from said projection signal a minimum global scaling parameter and a maximum global scaling parameter; and

(2) means for globally scaling said projection signal in accordance with said minimum and maximum global scaling values.

9. The apparatus of claim 8, wherein said means for selecting comprises:

(a) means for determining a plurality of local minimum values from said projection signal;

(b) means for determining said minimum global scaling parameter from an average of said plurality of local minimum values;

(c) means for determining a plurality of local maximum values from said projection signal; and

(d) means for determining said maximum global scaling parameter from an average of said plurality of local maximum values.

10. The apparatus of claim 9, wherein said means for forming further comprises:

(3) means for locally scaling said projection signal in accordance with said local minimum and local maximum values.

11. The apparatus of claim 10, wherein said means for locally scaling comprises:

(a) means for positioning a sliding window on said projection signal;

(b) means for calculating a contrast value for pixels in said window;

(c) means for comparing said contrast value to a predetermined threshold;

(d) means for locally scaling pixels in said window if said contrast value exceeds said predetermined threshold;

(e) means for marking pixels in said window as undefined if said contrast value does not exceed said predetermined threshold; and

(f) means for resolving by linear interpolation pixels marked undefined.

12. The apparatus of claim 7, wherein said two dimensional digital image is representative of a corrupted bar code symbol.

14. The apparatus of claim 7, wherein said means for determining a plurality of intensity information values sums only gray scale pixel values taken directly from said input image for each of said sections.