Method and apparatus for locating and decoding machine-readable symbols

• US 5,777,309 A
• Filed: 10/30/1995
• Issued: 07/07/1998
• Est. Priority Date: 10/30/1995
• Status: Expired due to Term

• Current Assignee: Intermec Technologies Corporation (Honeywell International Inc.)
• Original Assignee: Intermec Corporation (Honeywell International Inc.)
• Inventors: Ackley, H. Sprague, Maltsev, Pavel A.
• Primary Examiner(s): PITTS, HAROLD I
• Application Number:
  US08/549,916
• Time in Patent Office: 981 Days
• Field of Search: 235/462, 235/463, 235/454, 235/494
• US Class Current: 235/462.09
• 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 method and apparatus for locating and decoding machine-readable symbols is provided. In a preferred embodiment, an image of the symbol is stored and a sampling path through the stored image is selected. The sampling path represents a reflectance signal profile formed through the symbol. Characteristic or critical points are selected along the profile, including minimum and maximum points of peaks and valleys in the profile. Distances between the centers of peaks and valleys are determined. The present invention locates a defined portion of the symbol, such as a finder pattern, by locating a predetermined series of measured distances, such as a series of adjacent, substantially equal distances. After having located the finder pattern, the present invention determines the location of the symbol within the stored image, and thereafter decodes the symbol.

Claims

1. A method of locating within a two-dimensional stored image and decoding a machine-readable symbol representing encoded information in two-dimensions, the symbol including a plurality of selectively spaced two-dimensional geometric shapes, the shapes and spaces between the shapes having at least a first width in at least one dimension, the symbol having a predetermined location pattern of shapes and spaces identifying the symbol, the method comprising the steps of:

producing a reflectance signal from the two-dimensional stored image based on light reflected from the symbol, the reflectance signal having valleys and peaks that represent the reflectance of the shapes and spaces, respectively, comprising the symbol, the signal including a regular series of peaks and valleys corresponding to the predetermined location pattern;

identifying a plurality of portions in the reflectance signal that correspond to the valleys and peaks of the shapes and spaces;

measuring distances between the plurality of portions in the reflectance signal, including an approximately regular series of measured distances corresponding to the regular series of peaks and valleys;

identifying the predetermined location pattern based on the approximately regular series of measured distances in the reflectance signal;

determining a location orientation of the symbol based on the identified predetermined location pattern; and

decoding the information encoded in the symbol based on the location of the symbol.

2. The method of claim 1 wherein the step of producing a reflectance signal includes the step of producing the reflectance signal as a multiple level digital signal.

3. The method of claim 1 wherein the step of identifying a plurality of portions in the reflectance signal includes the steps of finding minimum and maximum points in the reflectance signal that correspond to the valleys and peaks, respectively.

4. The method of claim 1 wherein the shapes in the symbol represent low reflectivity, while the spaces in the symbol represent high reflectivity relative to the shapes, and

wherein the step of identifying a plurality of portions in the reflectance signal includes the steps of finding points in the reflectance signal where the reflectance signal indicates that reflectivity increases, where the reflectance signal indicates that reflectivity decreases, where the reflectance signal indicates a portion of substantially constant high reflectivity, and where the reflectance signal indicates a portion of substantially constant low reflectivity.

5. The method of claim 1 wherein the step of measuring distances with respect to the plurality of portions in the reflectance signal measures distances between centers of the valleys and peaks in the reflectance signal.

6. The method of claim 1 wherein the step of measuring distances includes the steps of:

identifying a center for each of the plurality of portions;

selecting a first portion and an adjacent second portion from the plurality of portions;

measuring a distance between the centers of the first and second portions; and

,

repeating the steps of selecting and measuring until all distances between the plurality of portions have been measured.

7. The method of claim 1 wherein the step of determining the location of the symbol includes the steps of:

identifying at least one predetermined set of shapes and spaces; and

determining an orientation of the symbol based on a position of the predetermined set of shapes and spaces with respect to the predetermined location pattern.

8. The method of claim 1 wherein the predetermined location pattern is a plurality of concentric shapes and spaces, and wherein the step of identifying the predetermined location pattern includes the step of locating a selected pattern of substantially equal measured distances.

9. The method of claim 1 wherein the symbol is a bar code symbol, wherein the predetermined location pattern is one of a start and stop code for the bar code symbol, and wherein the step of identifying the predetermined location pattern includes the step of locating a large measured distance corresponding to a quiet zone, and locating a smaller measured distance, relative to the large measured distance, corresponding to a shape in the symbol adjacent to the quiet zone.

10. The method of claim 1 wherein the step identifying the predetermined location pattern includes the step of locating a selected pattern of measured distances.

11. The method of claim 1 wherein the step of measuring distances with respect to the plurality of portions in the reflectance signal measures distances between centers of the valleys and peaks in the reflectance signal to produce a series of center distances based on the reflectance signal, and

wherein the step identifying the predetermined location pattern includes the step of locating a repeating pattern of approximately similar center distances within the series of center distances.

12. The method of claim 1, further comprising the step of producing a stored image of the symbol;

and

wherein the step of producing a reflectance signal produces a sampling path through the stored image.

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

determining that the predetermined location pattern has not been identified in the reflectance signal;

producing another reflectance signal based on light reflected from a portion of the symbol that differs from a portion of the symbol that previously produced the reflectance signal; and

repeating the steps of producing another reflectance signal, identifying a plurality of portions, measuring, and identifying the predetermined location pattern until the predetermined location pattern is identified in the symbol.

14. A method of locating a data collection symbol representing encoded information, the symbol including a plurality of spaced two-dimensional shapes and having a selected pattern of shapes and spaces between the shapes, the method comprising the steps of:

receiving a signal based on light reflected from the symbol, the signal representing a reflectance of at least some of the shapes and spaces of the symbol, wherein the shapes and spaces of the symbol represent information encoded in two dimensions;

identifying a plurality of portions in the signal that correspond to at least portions of the shapes and spaces represented in the signal;

measuring distances between the plurality of portions in the signal including a selected pattern of measurements;

identifying the selected pattern based on the measured selected pattern of measurements in the signal; and

determining a location of the symbol based on the identified selected pattern.

15. The method of claim 14 of wherein the step of identifying a plurality of portions in the signal includes the step of finding minimum and maximum points in the signal that correspond to peaks and valleys in the signal.

16. The method of claim 14 wherein the step of measuring distances between the plurality of portions in the signal measures distances between centers of peaks and valleys in the signal.

17. The method of claim 14 wherein the step of identifying the selected pattern includes the step of locating a series of substantially equal measured distances.

18. The method of claim 14 wherein the step of identifying a plurality of portions in the signal includes the step of filtering noise from the signal.

19. An apparatus for locating a machine-readable symbol representing encoded information in two-dimensions, the machine-readable symbol including a plurality of selectively spaced two-dimensional shapes, and having a selected pattern of shapes and spaces between the shapes, the apparatus comprising:

a sensor that receives light that is reflected from the machine-readable symbol and produces an output signal therefrom that represents the reflectance of the shapes and spaces comprising the symbol;

a receiver that receives the output signal and produces a reflectance signal indicative of at least some of the shapes and spaces; and

a processor for processing the reflectance signal and producing a signal indicative of the information encoded in the symbol, the processor (i) identifying a plurality of portions in the reflectance signal that correspond to at least portions of the shapes and spaces, (ii) measuring distances between the plurality of portions in the reflectance signal, including an approximately regular series of measured distances, (iii) identifying the selected pattern based on the regular series of measured distances in the reflectance signal, and (iv) determining a location of the symbol based on the identified selected pattern.

20. The apparatus of claim 19 wherein the processor measures distances by identifying a center for each of the plurality of portions in the reflectance signal and measuring distances between the centers of the plurality of portions.

21. The apparatus of claim 19 wherein the processor defines at least one threshold with respect to the plurality of portions in, the reflectance signal identifies a center for each of the plurality of portions at the threshold and measures a distance between the center of each of the plurality of portions.

22. The apparatus of claim 19 wherein the processor identifies the plurality of portions in the reflectance signal by, in part, finding minimum and maximum points that correspond to valleys and peaks, respectively, the reflectance signal.

23. The apparatus of claim 19 wherein the processor identifies the selected pattern by identifying a predetermined number of substantially equal measured distances.

24. An apparatus for locating and decoding a machine-readable symbol representing encoded information in two-dimensions, the machine-readable symbol including a plurality of selectively spaced two-dimensional shapes, and having a selected pattern of shapes and spaces between the shapes, the apparatus comprising:

a sensor that receives light that is reflected from the machine-readable symbol and produces an output signal therefrom that represents the reflectance of the shapes and spaces comprising the symbol;

a receiver that receives the output signal and produces a reflectance signal indicative of at least some of the shapes and spaces;

a detection circuit that identifies a plurality of portions in the reflection signal that correspond to portions of at least some of the shapes and spaces, including an approximately regular series of measured distances;

a measuring circuit that generates a distance signal indicating distances between the plurality of portions in the reflectance signal; and

a decoding circuit that identifies a location of the selected pattern in the machine-readable symbol based on the distance signal, including the regular series of measured distances, and therefrom produces a signal indicative of the information encoded in the machine-readable symbol.