Method and apparatus for decoding bar code symbols using gradient signals

• US 5,412,197 A
• Filed: 07/26/1994
• Issued: 05/02/1995
• Est. Priority Date: 01/29/1993
• 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: Smith, Christopher E.
• Primary Examiner(s): PITTS, HAROLD I
• Application Number:
  US08/280,576
• Time in Patent Office: 280 Days
• Field of Search: 235/462, 235/463
• US Class Current: 235/462.1
• CPC Class Codes: G06K 7/1093 sensing, after transfer of the image of the data-field to an intermediate store, e.g. storage with cathode ray tube
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1465 using several successive scans of the optical code

Abstract

A bar code reader decodes a bar code symbol in a pixel image by transforming the data corresponding to the symbol along a first scan line, where the transformation comprises rotation and stretching. The reader generates a whitening gradient vector, a blackening gradient vector, and a count vector from the transformed data. The reader then transforms (by rotating and stretching) another set of data corresponding to the symbol along a second scan line. The reader updates the whitening and blackening gradient vectors and the count vector using the second set of transformed data. The reader then generates whitening and blackening gradient signals from the whitening and blackening gradient vectors and the count vector. The reader segments the whitening and blackening gradient signals and generates a single one-dimensional reconstructed signal based on the weighted centroids of the two segmented gradient signals. The reader then decodes the symbol by decoding the reconstructed signal.

Claims

1. A method for reading a bar code symbol in a pixel image, comprising the steps of:

(a) selecting a first scan line crossing at least a first portion of said symbol;

(b) generating a first gradient signal representative of the dark-to-bright transitions in said first portion of said symbol;

(c) generating a second gradient signal representative of the bright-to-dark transitions in said first portion of said symbol, wherein the first gradient signal is distinct from the second gradient signal;

(d) selecting a second scan line crossing at least a second portion of said symbol;

(e) generating an updated first gradient signal in accordance with the dark-to-bright transitions in said second portion and the first gradient signal;

(f) generating an updated second gradient signal in accordance with the bright-to-dark transitions in said second portion and the second gradient signal; and

(g) decoding said symbol in accordance with said updated first and second .gradient signals.

2. The method of claim 1, wherein said first gradient signal is a whitening gradient signal and said second gradient signal is a blackening gradient signal.

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

(1) segmenting said Updated first gradient signal into at least one first segment;

(2) selecting a first location in said first segment corresponding to a dark-to-bright transition;

(3) segmenting said updated second gradient signal into at least one second segment;

(4) selecting a second location in said second segment corresponding to a bright-to-dark transition; and

(5) decoding said symbol in accordance with said first and second locations.

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

(i) generating a reconstructed signal in accordance with said first and second locations; and

(ii) decoding said reconstructed signal.

5. The method of claim 3, wherein said first location corresponds to a peak of said first segment.

6. The method of claim 3, wherein said first location corresponds to a weighted centroid of said first segment.

7. The method of claim 3, wherein said first segment comprises a local maximum in said updated first gradient signal.

8. The method of claim 3, wherein step (g)(1) further comprises the steps of:

(i) determining the mass of said first segment; and

(ii) if said mass is greater than a first mass threshold, then continuing to step (g)(2);

otherwise, rejecting said first segment.

9. The method of claim 1, wherein step (g) further comprises the step of smoothing said updated first gradient signal and said updated second gradient signal.

19. The method of claim 1, wherein:

step (a) further comprises the step of transforming said first portion, wherein said transforming comprises the steps of rotating said first portion to an angle substantially parallel to either a row or column of pixels in said image and stretching said first portion;

step (b) comprises the step of generating said first gradient signal in accordance with said transformed first portion;

step (c) comprises the step of generating said second gradient signal in accordance with said transformed first portion;

step (d) further comprises the step of transforming said second portion, wherein said transforming comprises the steps of rotating said second portion to an angle substantially parallel to either a row or column of pixels in said image and stretching said second portion;

step (e) comprises the step of generating said updated first gradient signal in accordance with said transformed second portion and the first gradient signal; and

step (f) comprises the step of generating said updated second gradient signal in accordance with said transformed second portion and the second gradient signal.

20. The method of claim 19, wherein:

step (e) comprises the step of generating an element of said updated first gradient signal by adding a value corresponding to said transformed first portion and a value corresponding to said transformed second portion; and

step (f) comprises the step of generating an element of said updated second gradient signal by adding a value corresponding to said transformed first portion and a value corresponding to said transformed second portion.

21. The method of claim 19, further comprising the steps of:

(h) generating a count vector in accordance with said transformed first portion; and

(i) incrementing said count vector in accordance with said transformed second portion, wherein;

step (g) comprises the step of decoding said symbol in accordance with said updated first and second gradient signals and said count vector.

22. The method of claim 21, wherein step (g) comprises the steps of:

(1) normalizing said updated first gradient signal by dividing an element of said updated first gradient signal by a corresponding element of said count vector; and

(2) normalizing said updated second gradient signal by dividing an element of said updated second gradient signal by a corresponding element of said count vector.

23. The method of claim 1, wherein:

step (e) comprises the step of generating an element of said updated first gradient signal by adding a value corresponding to said first portion and a value corresponding to said second portion; and

step (f) comprises the step of generating an element of said updated second gradient signal by adding a value corresponding to said first portion and a value corresponding to said second portion.

24. The method of claim 1, further comprising the steps of:

(h) generating a count vector in accordance with said first portion; and

(i) incrementing said count vector in accordance with said second portion, wherein;

step (g) comprises the step of decoding said symbol in accordance with said updated first and second gradient signals and said count vector.

25. The method of claim 24, wherein step (g) comprises the steps of:

(1) normalizing said updated first gradient signal by dividing an element of said updated first gradient signal by a corresponding element of said count vector; and

(2) normalizing said updated second gradient signal by dividing an element of said updated second gradient signal by a corresponding element of said count vector.

26. The method of claim 1, wherein said pixel image is a gray-scale image.

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

(h) transforming said symbol, wherein said transforming comprises the steps of rotating said symbol to an angle substantially parallel to either a row or column of pixels in said image and stretching said symbol, wherein;

step (a) comprises the step of selecting said first scan line crossing said transformed symbol;

step (b) comprises the step of generating said first gradient signal in accordance with the dark-to-bright transitions along said first scan line;

step (c) comprises the step of generating said second gradient signal in accordance with the bright-to-dark transitions along said first scan line;

step (d) comprises the step of selecting said second scan line crossing said transformed symbol;

step (e) comprises the step of generating said updated first gradient signal in accordance with the dark-to-bright transitions along said second scan line and the first gradient signal; and

step (f) comprises the step of generating said updated second gradient signal in accordance with the bright-to-dark transitions along said second scan line and the second gradient signal.

10. An apparatus for reading a bar code symbol in a pixel image, comprising:

(a) means for selecting a first scan line crossing at least a first portion of said symbol;

(b) means for generating a first gradient signal representative of the dark-to-bright transitions in said first portion of said symbol;

(c) means for generating a second gradient signal representative of the bright-to-dark transitions in said first portion of said symbol, wherein the first gradient signal is distinct from the second gradient signal;

(d) means for selecting a second scan line crossing at least a second portion of said symbol;

(e) means for generating an updated first gradient signal in accordance with the dark-to-bright transitions in said second portion and the first gradient signal;

(f) means for generating an updated second gradient signal in accordance with the bright-to-dark transitions in said second portion and the second gradient signal; and

(g) means for decoding said symbol in accordance with said updated first and second gradient signals.

11. The apparatus of claim 10, wherein said first gradient signal is a whitening gradient signal and said second gradient signal is a blackening gradient signal.

12. The apparatus of claim 10, wherein means (g) comprises:

(1) means for segmenting said updated first gradient signal into at least one first segment;

(2) means for selecting a first location in said first segment corresponding to a dark-to-bright transition;

(3) means for segmenting said updated second gradient signal into at least one second segment;

(4) means for selecting a second location in said second segment corresponding to a bright-to-dark transition; and

(5) means for decoding said symbol in accordance with said first and second locations.

13. The apparatus of claim 12, wherein means (g)(5) comprises:

(i) means for generating a reconstructed signal in accordance with said first and second locations; and

(ii) means for decoding said reconstructed signal.

14. The apparatus of claim 12, wherein said first location corresponds to a peak of said first segment.

15. The apparatus of claim 12, wherein said first location corresponds to a weighted centroid of said first segment.

16. The apparatus of claim 12, wherein said first segment comprises a local maximum in said updated first gradient signal.

17. The apparatus of claim 12, wherein means (g)(1) further comprises:

(i) means for determining the mass of said first segment; and

(ii) means for determining whether said mass is greater than a first mass threshold and for directing processing according to said determination.

18. The apparatus of claim 10, wherein means (g) further comprises means for smoothing said updated first gradient signal and said updated second gradient signal.

28. The apparatus of claim 10, wherein:

means (a) further comprises means for transforming said first portion, wherein said transforming means comprises means for rotating said first portion to an angle substantially parallel to either a row or column of pixels in said image and stretching said first portion;

means (b) comprises means for generating said first gradient signal in accordance with said transformed first portion;

means (c) comprises means for generating said second gradient signal in accordance with said transformed first portion;

means (d) further comprises means for transforming said second portion, wherein said transforming means comprises means for rotating said second portion to an angle substantially parallel to either a row or column of pixels in said image and stretching said second portion;

means (e) comprises means for generating said updated first gradient signal in accordance with said transformed second portion and the first gradient signal; and

means (f) comprises means for generating said updated second gradient signal in accordance with said transformed second portion and the second gradient signal.

29. The apparatus of claim 28, wherein:

means (e) comprises means for generating an element of said updated first gradient signal by adding a value corresponding to said transformed first portion and a value corresponding to said transformed second portion; and

means (f) comprises means for generating an element of said updated second gradient signal by adding a value corresponding to said transformed first portion and a value corresponding to said transformed second portion.

30. The apparatus of claim 28, further comprising:

(h) means for generating a count vector in accordance with said transformed first portion; and

(i) means for incrementing said count vector in accordance with said transformed second portion, wherein;

means (g) comprises means for decoding said symbol in accordance with said updated first and second gradient signals and said count vector.

31. The apparatus of claim 30, wherein means (g) comprises:

(1) means for normalizing said updated first gradient signal by dividing an element of said updated first gradient signal by a corresponding element of said count vector; and

(2) means for normalizing said updated second gradient signal by dividing an element of said updated second gradient signal by a corresponding element of said count vector.

32. The apparatus of claim 10, wherein:

means (e) comprises means for generating an element of said updated first gradient signal by adding a value corresponding to said first portion and a value corresponding to said second portion; and

means (f) comprises means for generating an element of said updated second gradient signal by adding a value corresponding to said first-portion and a value corresponding to said second portion.

33. The apparatus of claim 10, further comprising:

(h) means for generating a count vector in accordance with said first portion; and

(i) means for incrementing said count vector in accordance with said second portion, wherein;

means (g) comprises means for decoding said symbol in accordance with said updated first and second gradient signals and said count vector.

34. The apparatus of claim 33, wherein means (g) comprises:

(1) means for normalizing said updated first gradient signal by dividing an element of said updated first gradient signal by a corresponding element of said count vector; and

(2) means for normalizing said updated second gradient signal by dividing an element of said updated second gradient signal by a corresponding element of said count vector.

35. The apparatus of claim 10, wherein said pixel image is a gray-scale image.

36. The apparatus of claim 10, further comprising:

(h) means for transforming said symbol, wherein said transforming means comprises means for rotating said symbol to an angle substantially parallel to either a row or column of pixels in said image and stretching said symbol, wherein;

means (a) comprises means for selecting said first scan line crossing said transformed symbol;

means (b) comprises means for generating said first gradient signal in accordance with the dark-to-bright transitions along said first scan line;

means (c) comprises means for generating said second gradient signal in accordance with the bright-to-dark transitions along said first scan line;

means (d) comprises means for selecting said second scan line crossing said transformed symbol;

means (e) comprises means for generating said updated first gradient signal in accordance with the dark-to-bright transitions along said second scan line and the first gradient signal; and

means (f) comprises means for generating said updated second gradient signal in accordance with the bright-to-dark transitions along said second scan line and the second gradient signal.