US5515447A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for locating an acquisition target in two-dimensional images by detecting symmetry in two different directions
Assignee: United Parcel Service of America Inc
•
Filing: 1994-06-07
•
Granted: 1996-05-07
•
Expires: 2014-06-07
Abstract
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.
Inventors
- 👤 Joe Zheng
- 👤 Ming Lei
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 11:20
CPC Classifications
G; G06; G06K; G06K7/00; G06K7/10; G06K7/10544; G06K7/10821; G06K7/1093; G06K7/14; G06K7/1404; G06K7/1408; G06K7/1417; G06K7/1439; G06K7/1456
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
94 words
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.
Claim 2
Independent Claim
94 words
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.
Claim 3
Dependent Claim
126 words
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.
Claim 4
Dependent Claim
56 words
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.
Claim 5
Dependent Claim
154 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Independent Claim
147 words
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.
Claim 8
Independent Claim
147 words
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.
Claim 9
Dependent Claim
128 words
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.
Claim 10
Dependent Claim
45 words
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.
Claim 11
Dependent Claim
139 words
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.
Claim 12
Dependent Claim
38 words
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.
Claim 13
Dependent Claim
39 words
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.
Claim 14
Independent Claim
107 words
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.
Claim 15
Independent Claim
107 words
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.
Claim 16
Dependent Claim
42 words
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.
Claim 17
Dependent Claim
20 words
The method of claim 12, wherein said symbology comprises a plurality of polygonal information encoding elements arranged in a matrix.
Claim 18
Independent Claim
140 words
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.
Claim 19
Independent Claim
140 words
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.
Claim 20
Dependent Claim
20 words
The system of claim 15, wherein said symbology comprises a plurality of polygonal information encoding elements arranged in a matrix.
Claim 21
Independent Claim
127 words
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.
Claim 22
Independent Claim
127 words
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.
Claim 23
Dependent Claim
25 words
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.
Claim 24
Independent Claim
165 words
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.
Claim 25
Independent Claim
165 words
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.
Claim 26
Dependent Claim
27 words
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.
Claim 27
Independent Claim
108 words
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.
Claim 28
Independent Claim
108 words
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.
Claim 29
Independent Claim
151 words
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.
Claim 30
Independent Claim
151 words
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.
Claim 31
Independent Claim
120 words
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.
Claim 32
Independent Claim
120 words
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.
Claim 33
Dependent Claim
31 words
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.
Claim 34
Dependent Claim
28 words
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.
Claim 35
Dependent Claim
131 words
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.
Claim 36
Dependent Claim
25 words
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.
Claim 37
Dependent Claim
59 words
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.
Claim 38
Dependent Claim
154 words
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.
References Cited (Backward Citations)
US3632995A
Cited
US3801775A
Cited
US4424588A
Cited
US4947383A
Cited
US4695991A
Cited
US4696049A
Cited
WO1986005906A1
Cited
US4745269A
Cited
US4776464A
Cited
US4718103A
Cited
US4736109A
Cited
US4955062A
Cited
US4933865A
Cited
US4924078A
Cited
US4896029A
Cited
US4874936A
Cited
US5229591A
Cited
US5153928A
Cited
US5189711A
Cited
US5103489A
Cited
US5155343A
Cited
US5191621A
Cited
US5241166A
Cited
US5189292A
Cited
US5153418A
Cited
US5291564A
Cited
US5276315A
Cited
US5327171A
Cited
US5329105A
Cited
WO1994020925A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-07 | 1999-11-06 | 2000-05-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-07 | 2003-11-06 | 2004-05-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-07 | 2007-11-06 | 2008-05-07 | $7700.00 | Window Closed / Lapsed |