Method and apparatus for locating an acquisition target in two-dimensional images by detecting symmetry in two different directions

• US 5,515,447 A
• Filed: 06/07/1994
• Issued: 05/07/1996
• Est. Priority Date: 06/07/1994
• 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: Zheng, Joe, Lei, Ming
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/254,976
• Time in Patent Office: 700 Days
• Field of Search: 382/1, 382/22, 382/25, 382/26, 382/48, 382/100, 382/101, 382/103, 382/199, 382/203, 382/204, 382/287, 382/291, 348/94, 209/583, 209/584, 235/461, 235/464, 235/470, 235/494
• US Class Current: 382/100
• 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/1456 determining the orientation of the optical code with respect to the reader and correcting therefore

Abstract

A system and method are disclosed for locating an acquisition target consisting of a plurality of concentric rings of alternating levels of reflectivity (bull'"'"'s-eye pattern) in two-dimensional images such as optically encoded symbologies. Such targets may be found even if they vary in size and tilt angle with respect to an imaging camera. Symmetry characteristics of the targets are used to locate the targets independent of the threshold level selected for determining transitions between rings of different reflectivity.

Claims

1. A method of locating an optically readable, two-dimensional acquisition target in a stored image, said target being of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising the steps of:

scanning said stored image along a scanning direction and detecting a candidate bounded element and associated border area demonstrating symmetry along said scanning direction; and

determining whether said candidate bounded element and associated border area are symmetric along a second direction.

2. The method of claim 1, wherein said key border area comprises a plurality of symmetric rings of alternating first and second reflectivity surrounding said key element;

and further comprising the steps of;

finding a center point of said candidate bounded element;

determining whether said candidate bounded element and said associated border area are symmetric along at least one of a pair of diagonal directions passing through said center point;

determining whether said candidate bounded element and said associated border area are symmetric along a vertical direction normal to said scanning direction;

determining diameters of said candidate bounded element and said associated border area in each of said directions in which they exhibit symmetry; and

determining whether said diameters are within a predetermined tolerance of each other.

3. The method of claim 2, wherein said steps of determining whether said candidate bounded element and said associated border area are symmetric comprise determining whether the width of said bounded element is at least as long as the widths of each of said border area rings of alternating reflectivity on both sides of said bounded element.

4. The method of claim 3, wherein said steps of determining whether said candidate bounded element and said associated border area are symmetric further comprise the steps of:

determining whether the absolute value of the difference between a first average width of the rings of the first reflectivity on both sides of said bounded element and a second average width of the rings of the second reflectivity on both sides of said bounded element is less than a preset tolerance;

determining whether the difference between the first average width of the rings of the first reflectivity on both sides of said bounded element and the individual components of said first average is less than said preset tolerance; and

determining whether the difference between the second average width of the rings of the second reflectivity on both sides of said bounded element and the individual components of said second average is less than said preset tolerance.

5. The method of claim 4, further comprising the steps of finding a pair of longest orthogonal cords within said bounded element and assigning a center point of said bounded element at the intersection of said cords.

6. A system for locating an optically readable, two-dimensional acquisition target in a stored image of a symbology in which alphanumeric data is encoded, said target being of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising:

a light source;

a detector comprising an array of pixels positioned to receive light from said light source reflected by said target;

a read-out circuit connected to obtain data signals from said pixels and to form in a memory device an image including said target; and

a processor configured to locate said key element by;

scanning said stored image along a scanning direction to detect a candidate bounded element demonstrating symmetry along said scanning direction; and

determining whether said candidate bounded element is symmetric along a second direction.

7. The system of claim 6, wherein said key border area comprises a plurality of symmetric rings of alternating first and second reflectivity surrounding said key element;

and wherein said processor is further configured to;

find a center point of said candidate bounded element;

determine whether said candidate bounded element and said associated border area are symmetric along at least one of a pair of diagonal directions passing through said center point;

determine whether said candidate bounded element and said associated border area are symmetric along a vertical direction normal to said scanning direction;

determine diameters of said candidate bounded element and said associated border area in each of said directions in which they exhibit symmetry; and

determine whether said diameters are within a predetermined tolerance of each other.

8. The system of claim 7, wherein said processor is further configured to determine whether the width of said bounded element is at least as long as the widths of each of said border area rings of alternating reflectivity on both sides of said bounded element.

9. The system of claim 8, wherein said processor is further configured to:

determine whether the absolute value of the difference between a first average width of the rings of the first reflectivity on both sides of said bounded element and a second average width of the rings of the second reflectivity on both sides of said bounded element is less than a preset tolerance;

determine whether the difference between the first average width of the rings of the first reflectivity on both sides of said bounded element and the individual components of said first average is less than said preset tolerance; and

determine whether the difference between the second average width of the rings of the second reflectivity on both sides of said bounded element and the individual components of said second average is less than said preset tolerance.

10. The system of claim 9, wherein said processor is further configured to find a pair of longest orthogonal cords within said bounded element and assign a center point of said bounded element at the intersection of said cords.

11. The system of claim 6, wherein said processor is configured to scan said stored image along a scanning direction for non-character information, and to detect a candidate bounded element demonstrating symmetry along said scanning direction using said non-character information.

12. A method of locating an optically readable, two-dimensional symbology of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising the steps of:

deriving a multiple-row image including said symbology from a pixel matrix and storing said image; and

locating said key element by;

scanning said stored image along a scanning direction and detecting a candidate bounded element and associated border area demonstrating symmetry along said scanning direction; and

determining whether said candidate bounded element and associated border area are symmetric along a second direction.

13. The method of claim 12, wherein said step of detecting a candidate bounded element and associated border area demonstrating symmetry along said scanning direction comprises run-length coding the rows of said image for the first reflectivity, and examining said runs for symmetry.

14. The method of claim 12, wherein said symbology comprises a plurality of polygonal information encoding elements arranged in a matrix.

15. A system for locating an optically readable, two dimensional symbology of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity completely surrounded by a geometrically symmetric key border area of a second reflectivity, comprising:

a light source;

a detector comprising an array of pixels positioned to receive light from said light source reflected by said symbology;

a read-out circuit connected to obtain data signals from said pixels and to form in a memory device an image including said symbology; and

a processor configured to locate said key element by;

scanning said stored image along a scanning direction to detect a candidate bounded element and associated border area demonstrating symmetry along said scanning direction; and

determining whether said candidate bounded element and associated border area are symmetric along a second direction.

16. The system of claim 15, wherein said symbology comprises a plurality of polygonal information encoding elements arranged in a matrix.

17. A method of locating an optically readable, two-dimensional acquisition target in a stored image, said target being of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising the steps of:

scanning said stored image along a scanning direction and detecting a candidate bounded element and associated border area demonstrating symmetry along said scanning direction;

determining whether said candidate bounded element and said associated border area are symmetric along a second direction;

determining diameters of said candidate bounded element and said associated border area in said scanning direction and said second direction; and

determining whether said diameters are within a predetermined tolerance of each other.

18. The method of claim 17, further comprising the steps of averaging said diameters and determining the size of said target based on said average diameter.

19. A system for locating an optically readable, two-dimensional acquisition target in a stored image, said target being of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising:

a light source;

a detector comprising an array of pixels positioned to receive light from said light source reflected by said target;

a read-out circuit connected to obtain data signals from said pixels and to form in a memory device an image including said target; and

a processor configured to locate said key element by;

scanning said stored image along a scanning direction to detect a candidate bounded element demonstrating symmetry along said scanning direction;

determining whether said candidate bounded element is symmetric along a second direction;

determining diameters of said candidate bounded element in said scanning direction and said second direction; and

determining whether said diameters are within a predetermined tolerance of each other.

20. The system of claim 19, wherein said processor is further configured to average said diameters and determine the size of said target based on said average diameter.

21. A method of locating an optically readable, two-dimensional acquisition target in a stored image, said target being of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising the steps of:

scanning said stored image along a scanning direction;

run-length coding said image in said scanning direction;

detecting a candidate bounded element and associated border area demonstrating symmetry along said scanning direction by examining said runs for symmetry; and

determining whether said candidate bounded element and said associated border area are symmetric along a second direction.

22. A system for locating an optically readable, two-dimensional acquisition target in a stored image, said target being of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising:

a light source;

a detector comprising an array of pixels positioned to receive light from said light source reflected by said target;

a read-out circuit connected to obtain data signals from said pixels and to form in a memory device an image including said target; and

a processor configured to locate said key element by;

scanning said stored image along a scanning direction;

run-length coding said image in said scanning direction;

detecting a candidate bounded element demonstrating symmetry along said scanning direction by examining said runs for symmetry; and

determining whether said candidate bounded element is symmetric along a second direction.

23. A method of locating an optically readable, two-dimensional symbology of the type having a key element, said key element being a geometrically symmetric, bounded element of a first reflectivity surrounded by a geometrically symmetric key border area of a second reflectivity, comprising the steps of:

deriving an image including said symbology from a pixel matrix and storing said image; and

locating said key element by;

scanning said stored image along a scanning direction;

run-length coding said image in said scanning direction;

detecting a candidate bounded element and associated border area demonstrating symmetry along said scanning direction by examining said runs for symmetry; and

determining whether said candidate bounded element and said associated border area are symmetric along a second direction.

24. The method of claim 23, further comprising the step of determining whether said candidate bounded element and associated border area are symmetric along a third direction normal to said scanning direction.

25. The method of claim 23, further comprising the strip of finding a pair of longest orthogonal cords within said bounded element to locate a center of said element.

26. The method of claim 23, wherein said key border area comprises a plurality of symmetric rings of alternating first and second reflectivity surrounding said key element;

and wherein said step of locating said key element further comprises;

finding a center point of said candidate bounded element;

determining whether said candidate bounded element and said associated border area are symmetric along at least one of a pair of diagonal directions passing through said center point;

determining whether said candidate bounded element and said associated border area are symmetric along a vertical direction normal to said scanning direction;

determining diameters of said candidate bounded element and said associated border area in each of said directions in which they exhibit symmetry; and

determining whether said diameters are within a predetermined tolerance of each other.

27. The method of claim 26, further comprising the steps of averaging said diameters and determining the size of said symbology based on said average diameter.

28. The method of claim 26, wherein said steps of determining whether said candidate bounded element and said associated border area are symmetric comprises the step of determining whether the width of said bounded element is at least as long as the widths of each of said border area rings of alternating reflectivity on both sides of said bounded element.

29. The method of claim 28, wherein said steps of determining whether said candidate bounded element and said associated border area are symmetric further comprises the steps of:

determining whether the absolute value of the difference between a first average width of the rings of the first reflectivity on both sides of said bounded element and a second average width of the rings of the second reflectivity on both sides of said bounded element is less than a preset tolerance;

determining whether the difference between the first average width of the rings of the first reflectivity on both sides of said bounded element and the individual components of said first average is less than said preset tolerance; and

determining whether the difference between the second average width of the rings of the second reflectivity on both sides of said bounded element and the individual components of said second average is less than said preset tolerance.