Method and apparatus for decoding bar code symbols using byte-based searching

• US 5,404,003 A
• Filed: 07/28/1994
• Issued: 04/04/1995
• Est. Priority Date: 02/01/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/282,164
• Time in Patent Office: 250 Days
• Field of Search: 235/462, 235/463, 235/494
• 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/1443 locating of the code in an image

Abstract

A bar code reader locates and decodes a bar code symbol in a pixel image by searching along a selected scan line for a candidate quiet zone and then counting the bright/dark transitions that correspond to candidate bars and spaces. The reader determines whether the candidate quiet zone and candidate bars and spaces correspond to a bar code symbol, and, if so, decodes the symbol. When processing binary pixel images, the reader searches for candidate quiet zones and counts bright/dark transitions by analyzing the image one byte of pixels at a time.

Claims

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

(a) selecting a first scan line in said image;

(b) byte-based quiet-zone searching along said first search line to identify a candidate quiet zone;

(c) byte-based transition searching along said first search line to identify a plurality of candidate bars and spaces;

(d) determining whether said candidate quiet zone and said candidate bars and spaces correspond to said symbol; and

(e) decoding said symbol in accordance with the determination of step (d), wherein step (c) comprises the steps of;

(1) selecting a byte of said image, wherein said byte corresponds to two or more consecutive pixels of said image along said first scan line;

(2) accessing a look-up table using the byte as an index to determine how many bright/dark transitions correspond to the byte; and

(3) determining whether said bright/dark transitions correspond to said plurality of candidate bars and spaces.

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

(1) selecting a byte of said image, wherein said byte comprises two or more pixels along said first search line; and

(2) determining whether said byte corresponds to said candidate quiet zone.

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

(1) selecting a first byte of said image, wherein said first byte comprises eight consecutive pixels along said first search line;

(2) selecting a second byte of said image, wherein said second byte comprises the eight consecutive pixels along said first search line that follow said first byte;

(3) if the last pixel of said first byte corresponds to a dark pixel, then determining how many bright/dark transitions correspond to said second byte by referring to a first look-up table;

(4) if the last pixel of said first byte corresponds to a bright pixel, then determining how many bright/dark transitions correspond to said second byte by referring to a second look-up table; and

(5) determining whether said bright/dark transitions correspond to said plurality of candidate bars and spaces.

4. The method of claim 1, wherein step (d) further comprises the step of verifying that the widths of said candidate bars are less than a specified threshold.

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

(f) selecting a second search line substantially parallel to said first search line; and

(g) repeating steps (b), (c), and (d) along said second search line to verify said symbol.

6. The method of claim 1, wherein step (e) further comprises the step of locating the four corners of said bar code symbol.

7. The method of claim 6, wherein step (e) further comprises the step of correcting the location of at least one of said four corners.

8. The method of claim 1, wherein step (e) further comprises the step of applying one or more geometry tests to verify said bar code symbol.

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

(a) selecting a first search line in said image;

(b) selecting a byte of said image, wherein said byte comprises two or more pixels along said first search line;

(c) determining whether said byte corresponds to said symbol; and

(d) decoding said symbol in accordance with the determination of step (c), wherein step (c) comprises the steps of;

(1) accessing a look-up table using the byte as an index to determine how many bright/dark transitions correspond to the byte; and

(2) determining whether said bright/dark transitions correspond to a plurality of candidate bars and spaces.

10. The method of claim 9, wherein step (c) further comprises the steps of:

(3) determining whether said byte corresponds to a candidate quiet zone; and

(4) determining whether said candidate quiet zone corresponds to said symbol.

11. The method of claim 9, wherein step (c) further comprises the step of:

(3) determining whether said candidate bars and spaces correspond to said symbol.

12. The method of claim 11, further comprising the step of quiet-zone searching along said first search line to identify a candidate quiet zone, wherein step (c)(3) further comprises the step of determining whether said candidate quiet zone corresponds to said symbol.

13. The method of claim 12, wherein said quiet-zone searching comprises byte-based quiet-zone searching.

14. 18. The method of claim 11, wherein step (b) comprises the steps of:

(1) selecting a first byte of said image, wherein said first byte comprises eight consecutive pixels along said first search line; and

(2) selecting a second byte of said image, wherein said second byte comprises the eight consecutive pixels along said first search line that follow said first byte; and

wherein step (c)(1) comprises the steps of;

(1) if the last pixel of said first byte corresponds to a dark pixel, then determining how many bright/dark transitions correspond to said second byte by referring to a first look-up table; and

(2) if the last pixel of said first byte corresponds to a bright pixel, then determining how many bright/dark transitions correspond to said second byte by referring to a second look-up table.

15. The method of claim 11, wherein step (c)(3) further comprises the step of verifying that the widths of said candidate bars are less than a specified threshold.

16. The method of claim 11, wherein step (b) comprises the steps of:

(1) selecting a first byte of said image, wherein said first byte comprises eight consecutive pixels along said first search line; and

(2) selecting a second byte of said image, wherein said second byte comprises the eight consecutive pixels along said first search line that follow said first byte; and

wherein step (c)(3) further comprises the steps of;

(i) if the last pixel of said first byte corresponds to a dark pixel, then determining the width of at least a portion of a bar of said candidate bars by referring to a first look-up table;

(ii) if the last pixel of said first byte corresponds to a bright pixel, then determining the width of said portion of said bar of said candidate bars by referring to a second look-up table; and

(iii) verifying that the width of said bar is less than a specified threshold.

17. The method of claim 9, further comprising the steps of:

(e) selecting a second search line substantially parallel to said first search line; and

(f) repeating steps (b) and (c) along said second search line to verify said symbol.

18. The method of claim 9, wherein step (d) further comprises the step of locating the four corners of said bar code symbol.

19. The method of claim 18, wherein step (d) further comprises the step of correcting the location of at least one of said four corners.

20. The method of claim 9, wherein step (d) further comprises the step of applying one or more geometry tests to verify said bar code symbol.

21. An apparatus for reading a bar code symbol in a binary image, comprising:

(a) means for selecting a first search line in said image;

(b) means for byte-based quiet-zone searching along said first search line to identify a candidate quiet zone;

(c) means for byte-based transition searching along said first search line to identify a plurality of candidate bars and spaces;

(d) means for determining whether said candidate quiet zone and said candidate bars and spaces correspond to said symbol; and

(e) means for decoding said symbol in accordance with the determination of means (d), wherein means (c) comprises;

(1) means for selecting a byte of said image, wherein said byte corresponds to eight consecutive pixels of said image along said first scan line;

(2) means for accessing a look-up table using the byte as an index to determine how many bright/dark transitions correspond to the byte; and

(3) means for determining whether said bright/dark transitions correspond to said plurality of candidate bars and spaces.

22. The apparatus of claim 21, wherein means (b) further comprises:

(1) means for selecting a byte of said image, wherein said byte comprises two or more pixels along said first search line; and

(2) means for determining whether said byte corresponds to said candidate quiet zone.

23. The apparatus of claim 21, wherein means (c) comprises:

(1) means for selecting a first byte of said image, wherein said first byte comprises eight consecutive pixels along said first search line;

(2) means for selecting a second byte of said image, wherein said second byte comprises the eight consecutive pixels along said first search line that follow said first byte;

(3) means for determining how many bright/dark transitions correspond to said second byte by referring to a first look-up table, if the last pixel of said first byte corresponds to a dark pixel;

(4) means for determining how many bright/dark transitions correspond to said second byte by referring to a second look-up table, if the last pixel of said first byte corresponds to a bright pixel; and

(5) means for determining whether said bright/dark transitions correspond to said plurality of candidate bars and spaces.

24. The apparatus of claim 21, wherein means (d) further comprises means for verifying that the widths of said candidate bars are less than a specified threshold.

25. The apparatus of claim 21, further comprising:

(f) means for selecting a second search line substantially parallel to said first search line; and

(g) means for verifying said symbol, comprising;

(1) means for byte-based quiet-zone searching along said second search line to verify the identity of said candidate quiet zone; and

(2) means for byte-based transition searching along said second search line to verify the identity of said plurality of candidate bars and spaces.

26. The apparatus of claim 21, wherein means (e) further comprises means for locating the four corners of said bar code symbol.

27. The apparatus of claim 26, wherein means (e) further comprises means for correcting the location of at least one of said four corners.

28. The apparatus of claim 21, wherein means (e) further comprises means for applying one or more geometry tests to verify said bar code symbol.

29. An apparatus for reading a bar code symbol in a binary image, comprising:

(a) means for selecting a first search line in said image;

(b) means for selecting a byte of said image, wherein said byte comprises two or more pixels along said first search line;

(c) means for determining whether said byte corresponds to said symbol; and

(d) means for decoding said symbol in accordance with the determination of means (c), wherein means (c) comprises;

(1) means for accessing a look-up table using the byte as an index to determine how many bright/dark transitions correspond to the byte; and

(2) means for determining whether said bright/dark transitions correspond to a plurality of candidate bars and spaces.

30. The apparatus of claim 29, wherein means (c) further comprises:

(3) means for determining whether said byte corresponds to a candidate quiet zone; and

(4) means for determining whether said candidate quiet zone corresponds to said symbol.

31. The apparatus of claim 29, wherein means (c) further comprises:

(3) means for determining whether said candidate bars and spaces correspond to said symbol.

32. The apparatus of claim 31, further comprising means for quiet-zone searching along said first search line to identify a candidate quiet zone, wherein means (c)(3) further comprises means for determining whether said candidate quiet zone corresponds to said symbol.

33. The apparatus of claim 32, wherein said means for quiet-zone searching comprises means for byte-based quiet-zone searching.

34. The apparatus of claim 31, wherein means (b) comprises:

(1) means for selecting a first byte of said image, wherein said first byte comprises eight consecutive pixels along said first search line; and

(2) means for selecting a second byte of said image, wherein said second byte comprises the eight consecutive pixels along said first search line that follow said first byte; and

wherein means (c)(1) comprises;

(1) means for determining how many bright/dark transitions correspond to said second byte by referring to a first look-up table, if the last pixel of said first byte corresponds to a dark pixel; and

(2) means for determining how many bright/dark transitions correspond to said second byte by referring to a second look-up table, if the last pixel of said first byte corresponds to a bright pixel.

35. The apparatus of claim 31, wherein means (c)(3) further comprises means for verifying that the widths of said candidate bars are less than a specified threshold.

36. The apparatus of claim 31, wherein means (b) comprises:

(1) means for selecting a first byte of said image, wherein said first byte comprises eight consecutive pixels along said first search line; and

(2) means for selecting a second byte of said image, wherein said second byte comprises the eight consecutive pixels along said first search line that follow said first byte; and

wherein means (c)(3) further comprises;

(i) means for determining the width of at least a portion of a bar of said candidate bars by referring to a first look-up table, if the last pixel of said first byte corresponds to a dark pixel;

(ii) means for determining the width of said portion of said bar of said candidate bars by referring to a second look-up table, if the last pixel of said first byte corresponds to a bright pixel; and

(iii) means for verifying that the width of said bar is less than a specified threshold.

37. The apparatus of claim 29, further comprising:

(e) means for selecting a second search line substantially parallel to said first search line; and

(f) means for verifying said symbol, comprising;

(1) means for selecting a second byte of said image, wherein said second byte comprises two or more pixels along said second search line; and

(2) means for determining whether said second byte corresponds to said symbol.

38. The apparatus of claim 29, wherein means (d) further comprises means for locating the four corners of said bar code symbol.

39. The apparatus of claim 38, wherein means (d) further comprises means for correcting the location of at least one of said four corners.

40. The apparatus of claim 29, wherein means (d) further comprises means for applying one or more geometry tests to verify said bar code symbol.