Method and apparatus for locating and decoding machine-readable symbols

• US 5,786,583 A
• Filed: 02/16/1996
• Issued: 07/28/1998
• Est. Priority Date: 02/16/1996
• Status: Expired due to Term

• Current Assignee: Intermec Corporatiom
• Original Assignee: Intermec Corporation (Honeywell International Inc.)
• Inventors: Maltsev, Pavel A.
• Primary Examiner(s): Hajec, Donald T.
• Assistant Examiner(s): Le, Thien Minh
• Application Number:
  US08/602,624
• Time in Patent Office: 893 Days
• Field of Search: 235/464, 235/494, 235/462, 235/472, 235/436, 235/432, 235/486
• US Class Current: 235/462.15
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 2019/06243 concentric-code
• CPC Class Codes: G06K 2019/06262 with target- or other orientation-indicating feature
• 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
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes

Abstract

A method and apparatus for locating and decoding machine-readable symbols is provided. The present invention stores an image of the symbol and locates all Jordan curves having an angular length less than π within the image of the symbol. The present invention finds and selects all convex Jordan curves from the set of all Jordan curves found within the stored image. The present invention determines equations of a pair of tangent lines from end points of each convex Jordan curve and determines an equation of a center line for each pair of tangent lines. The present invention determines a point of intersection of the center lines, and based on the point of intersection, locates a center point of a finder pattern of the symbol. The present invention confirms that the located center point is indeed the center of the finder pattern, and thereafter decodes the symbol.

Claims

1. A method of locating and decoding a machine-readable symbol representing encoded information, 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 orientation pattern of convexly curved shapes and spaces between the convexly curved shapes, the convexly curved shapes at least partially surrounding a predetermined point of the symbol, the method comprising the steps of:

storing an image of the symbol;

locating all curved shapes within the stored image of the symbol, including the convexly curved shapes of the predetermined orientation pattern;

determining a pair of tangent lines from endpoints of each located curved shape;

defining a line between each pair of tangent lines;

determining at least one point of intersection of the defined lines;

locating the predetermined point of the symbol based on the at least one point of intersection of the defined lines; and

decoding the information encoded in the symbol based on the located predetermined point of the symbol.

2. The method of claim 1 wherein the step of storing an image of the symbol stores an image of a MaxiCode symbol and wherein the convexly curved shapes are a plurality of concentric rings surrounding the predetermined point.

3. The method of claim 1 wherein the step of locating all curved shapes within the stored image of the symbol includes the steps of:

locating an edge point of a curved shape;

analyzing an area proximate the edge point;

determining a dominant direction of the located curved shape based on the analyzed area; and

applying a vertical searching template for locating a position of the curved shape if the dominant direction is horizontal, and applying a horizontal searching template for locating a position of the curved shape if the dominant direction is vertical.

4. The method of claim 1 wherein the step of locating all curved shapes in the symbol locates all curved edges between curved shapes and adjacent spaces, and locates curved edges having an angular length less than π

.

5. The method of claim 1 wherein the step of locating all curved shapes in the symbol locates all convex Jordan curves.

6. The method of claim 1 wherein the step of locating all curved shapes within the stored image of the symbol includes the steps of:

determining an area under each of the located curved shapes;

comparing each determined area to maximum and minimum values corresponding to maximum and minimum error deviations from an ideal area under a circular curve having a same chord length and height substantially equal to a length of a chord extending between endpoints of the curve and a height of the curve, respectively; and

ignoring any curve whose determined area is greater than the maximum value or less than the minimum value.

7. The method of claim 1 wherein the step of locating all curved shapes within the stored image of the symbol includes the steps of:

determining an area under a located curved shape by determining an area of a plurality of rectangular regions under the located curved shape and summing the areas of the plurality of rectangular regions;

comparing the determined area to a selected value; and

ignoring the curve if the determined area bears a predetermined relationship to the selected value.

8. The method of claim 1 wherein the step of locating all curved shapes within the stored image of the symbol includes the steps of:

determining an area under each of the located curved shapes;

comparing each determined area to a selected value; and

ignoring any curve whose determined area bears a predetermined relationship to the selected value.

9. The method of claim 1 wherein the step of determining a pair of tangent lines includes the step of determining an intersection point of each pair of tangent lines, and

wherein the step of defining a line between each pair of tangent lines defines a centerline by determining a midpoint of a chord formed between the endpoints of each located curved shape, and defining the centerline as a line extending through the intersection point of each pair of tangent lines and the respective midpoint.

10. The method of claim 1 wherein the step of determining at least one point of intersection of the defined lines ignores any point of intersection between two defined lines where an angle of intersection between the defined lines is less than about 10 degrees and greater than about 90 degrees.

11. The method of claim 1 wherein the predetermined point is a central point of the predetermined orientation pattern, and wherein the step of locating the predetermined point of the symbol includes the steps of:

from the at least one point of intersection of the defined lines, analyzing the stored image to locate an edge of one of the convexly curved shapes of the predetermined orientation pattern;

determining an orientation of a concavity of the one located convexly curved shape;

analyzing the stored image along the determined orientation of concavity to locate another edge of the convexly curved shapes;

repeating the steps of determining an orientation and analyzing the stored image along the determined orientation for a preselected number of iterations;

defining an interior line extending away from the another edge;

determining a midpoint of the interior line and defining a line perpendicular to the interior line from the midpoint; and

defining the central point as a midpoint of the perpendicular line.

12. The method of claim 1 wherein the predetermined point is a central point of the predetermined orientation pattern, and wherein the method further comprises the steps of:

measuring distances to the convexly curved shapes in opposite directions from the central point; and

confirming that the central point is an approximate center point of the symbol if the measured distances in opposite directions are approximately similar.

13. The method of claim 1 wherein the predetermined point is an approximately central point of the symbol, and wherein the method further comprises the step of confirming that the predetermined point is a center point of the symbol.

14. In a computer system having a processor and a data storage device, a computer implemented method of locating a predetermined pattern of convexly curved shapes and spaces between the convexly curved shapes within an image stored in the data storage device, the convexly curved shapes at least partially surrounding a preselected point, the method comprising the steps of:

locating all curved shapes within the stored image, including the convexly curved shapes of the predetermined pattern;

determining a pair of tangent lines from endpoints of each located curved shape;

defining a line between each pair of tangent lines;

determining at least one point of intersection of the defined lines; and

locating the preselected point based on the at least one point of intersection of the defined lines.

15. The method of claim 14 wherein the step of locating all curved shapes in the symbol locates all edges between curved shapes and adjacent spaces, and locates curved shapes having an angular length less than π

.

16. The method of claim 14 wherein the step of locating all curved shapes within the stored image includes the steps of:

determining an area under each of the located curved shapes;

comparing each determined area to a selected value; and

ignoring any curve whose determined area bears a predetermined relationship to the selected value.

17. The method of claim 14 wherein the step of determining a pair of tangent lines includes the step of determining an intersection point of each pair of tangent lines, and

wherein the step of defining a line between each pair of tangent lines defines a centerline by determining a midpoint of a chord formed between the endpoints of each located curved shape, and defining the centerline as a line extending through the intersection point of each pair of tangent lines and the respective midpoint.

18. The method of claim 14 wherein the preselected point is an approximately central point of the predetermined pattern, and wherein the method further comprises the step of confirming that the preselected point is a center point of the predetermined pattern.

19. An apparatus for decoding a machine-readable symbol representing encoded information, the machine-readable symbol including a plurality of spaced two-dimensional shapes, the symbol having a predetermined orientation pattern of convexly curved shapes and spaces between the convexly curved shapes, the convexly curved shapes at least partially surrounding a predetermined point of the symbol, the apparatus comprising:

a sensor that receives light that is reflected from the 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 digital signal representing an image of the shapes and spaces of the symbol;

a storage device for storing the digital signal; and

a processor for processing the digital signal and producing a signal indicative of the information encoded in the symbol, the processor (a) locating all curved shapes within the stored digital signal, (b) determining a pair of tangent lines from endpoints of each located curved shape, (c) defining a line between each pair of tangent lines, (d) determining at least one point of intersection of the defined lines, (e) locating the predetermined point based on the at least one point of intersection of the defined lines, and (f) decoding the symbol and producing a signal indicative of the information encoded in the symbol based on the located predetermined point of the symbol.

20. The apparatus of claim 19 wherein the processor locates all edges between curved shapes and adjacent spaces, and locates curved shapes having an angular length less than π

.

21. The apparatus of claim 19 wherein the processor locates the curved shapes by (i) determining an area under each of the located curved shapes, (ii) comparing each determined area to a selected value, and (iii) ignoring any curve whose determined area bears a predetermined relationship to the selected value.

22. The apparatus of claim 19 wherein the processor determines a pair of tangent lines by determining an intersection point of each pair of tangent lines, and defines a line between each pair of tangent lines by defining a centerline based on a midpoint of a chord formed between the endpoints of each located curved shape and the intersection point of each pair of tangent lines.

23. The apparatus of claim 19 wherein the predetermined point is an approximately central point of the symbol, and wherein the processor confirms that the located predetermined point is a center point of the symbol.