Patent US3066674A successfully refreshed from Google Patents.
US5487115A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for determining the fine angular orientation of bar code symbols in two-dimensional CCD images
Assignee: United Parcel Service of America Inc
•
Filing: 1993-08-17
•
Granted: 1996-01-23
•
Expires: 2013-08-17
Abstract
Abstract A system for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image. A window is selected from the two-dimensional image for processing. Edge magnitude information and edge direction information are determined for a plurality of pixels in the selected window. For each pixel in the plurality of pixels, the edge magnitude and the edge direction of each pixel is associated with at least one of a plurality of directional ranges if the edge magnitude associated with the pixel exceeds a threshold. For each directional range in the plurality of directional ranges, a density value associated with each directional range is determined in accordance with the number of pixels associated with the directional range, an angular mean value is determined in accordance with the edge directions associated with the directional range, and a noise value is determined in accordance with the edge directions associated with the directional range. At least one candidate directional range is selected in accordance with the associated density values. The fine angular orientation of a bar code symbol is determined in accordance with the edge directions associated with the candidate directional range.
Inventors
- 👤 Stefan Surka
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 22:18
CPC Classifications
G; G06; G06K; G06K7/00; G06K7/10; G06K7/14; G06K7/1404; G06K7/1439; G06K7/1452; G06K7/1443; G06K7/1456; G06V; G06V10/00; G06V10/20; G06V10/24; G06V10/25; G06V30/00; G06V30/10; G06V30/14; G06V30/146; G06V30/1475; G06V30/1478
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
193 words
A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of: (A) selecting a window from said two-dimensional image for processing; (B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window; (C) selecting a pixel from said plurality of pixels; (D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges; (E) repeating steps (C)-(D) for each pixel in said plurality of pixels; (F) selecting one directional range from said plurality of directional ranges; (G) determining a density value associated with said selected directional range in accordance with the number of pixels associated with said selected directional range; (H) repeating steps (F)-(G) for each of said plurality of directional ranges; (I) selecting at least one candidate directional range in accordance with said associated density values; and (J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 2
Independent Claim
193 words
A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of: (A) selecting a window from said two-dimensional image for processing; (B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window; (C) selecting a pixel from said plurality of pixels; (D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges; (E) repeating steps (C)-(D) for each pixel in said plurality of pixels; (F) selecting one directional range from said plurality of directional ranges; (G) determining a density value associated with said selected directional range in accordance with the number of pixels associated with said selected directional range; (H) repeating steps (F)-(G) for each of said plurality of directional ranges; (I) selecting at least one candidate directional range in accordance with said associated density values; and (J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 3
Dependent Claim
58 words
The method of claim 1, wherein step (G) further comprises the step of determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said at least one candidate directional range is selected in step (I) in accordance with said associated deviation and density values.
Claim 4
Dependent Claim
30 words
The method of claim 2, wherein said deviation value in step (G) is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.
Claim 5
Dependent Claim
58 words
The method of claim 3, wherein step (G) further comprises the step of determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and step (I) comprises selecting at least one candidate directional range in accordance with said associated deviation, density and angular mean values.
Claim 6
Dependent Claim
29 words
The method of claim 4, wherein said angular mean in step (G) is determined in accordance with the mean of said edge directions associated with said selected directional range.
Claim 7
Dependent Claim
194 words
The method of claim 4, wherein step (I) comprises the steps of: i. selecting one directional range from said plurality of directional ranges; ii. determining said selected directional range to be a candidate directional range if said density value associated with said selected directional range exceeds a second predetermined threshold, said deviation value associated with said selected directional range is less than a third predetermined threshold, and said angular mean value associated with said selected directional range differs from the angular center of said selected directional range by less than a fourth predetermined threshold; iii. repeating steps i.-ii. for each of said plurality of directional ranges; and step (J) comprises the steps of: i. if a plurality of candidate directional ranges were selected in step (I)ii., then selecting from said plurality of candidate directional ranges the directional range associated with the smallest deviation value and determining said fine angular orientation to be the angular mean value associated with said selected candidate directional range; ii. if a single candidate directional range was selected in step (I)ii., then determining said fine angular orientation to be the angular mean value associated with said single candidate directional range.
Claim 8
Dependent Claim
49 words
The method of claim 6, wherein step (A) comprises the steps of: i. selecting an object region from said two-dimensional pixel image; ii. determining the spatial coordinates of the center of mass associated with said selected object region; iii. selecting a window of pixels centered about said spatial coordinates.
Claim 9
Dependent Claim
41 words
The method of claim 7, wherein if no candidate directional range was selected in step (I)ii., then sequentially translating said window about said spatial coordinates and repeating steps (B)-(I) until at least one candidate directional range is selected in step (I)ii.
Claim 10
Independent Claim
192 words
A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of: (A) selecting a window from said two-dimensional image for processing; (B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window; (C) selecting a pixel from said plurality of pixels; (D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges; (E) repeating steps (C)-(D) for each pixel in said plurality of pixels; (F) selecting one directional range from said plurality of directional ranges; (G) determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range; (H) repeating steps (F)-(G) for each of said plurality of directional ranges; (I) selecting at least one candidate directional range in accordance with said associated deviation values; and (J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 11
Independent Claim
192 words
A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of: (A) selecting a window from said two-dimensional image for processing; (B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window; (C) selecting a pixel from said plurality of pixels; (D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges; (E) repeating steps (C)-(D) for each pixel in said plurality of pixels; (F) selecting one directional range from said plurality of directional ranges; (G) determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range; (H) repeating steps (F)-(G) for each of said plurality of directional ranges; (I) selecting at least one candidate directional range in accordance with said associated deviation values; and (J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 12
Dependent Claim
30 words
The method of claim 9, wherein said deviation value in step (G) is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.
Claim 13
Dependent Claim
57 words
The method of claim 9, wherein step (G) further comprises the step of determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and step (I) comprises selecting at least one candidate directional range in accordance with said associated deviation and angular mean values.
Claim 14
Dependent Claim
29 words
The method of claim 11, wherein said angular mean in step (G) is determined in accordance with the mean of said edge directions associated with said selected directional range.
Claim 15
Dependent Claim
49 words
The method of claim 9, wherein step (A) comprises the steps of: i. selecting an object region from said two-dimensional pixel image; ii. determining the spatial coordinates of the center of mass associated with said selected object region; iii. selecting a window of pixels centered about said spatial coordinates.
Claim 16
Independent Claim
194 words
A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of: (A) selecting a window from said two-dimensional image for processing; (B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window; (C) selecting a pixel from said plurality of pixels; (D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges; (E) repeating steps (C)-(D) for each pixel in said plurality of pixels; (F) selecting one directional range from said plurality of directional ranges; (G) determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range; (H) repeating steps (F)-(G) for each of said plurality of directional ranges; (I) selecting at least one candidate directional range in accordance with said associated angular mean values; and (J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 17
Independent Claim
194 words
A method for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising the steps of: (A) selecting a window from said two-dimensional image for processing; (B) determining an edge magnitude and an edge direction for a plurality of pixels in said selected window; (C) selecting a pixel from said plurality of pixels; (D) if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold, then associating said edge magnitude and said edge direction of said selected pixel with at least one of a plurality of directional ranges; (E) repeating steps (C)-(D) for each pixel in said plurality of pixels; (F) selecting one directional range from said plurality of directional ranges; (G) determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range; (H) repeating steps (F)-(G) for each of said plurality of directional ranges; (I) selecting at least one candidate directional range in accordance with said associated angular mean values; and (J) determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 18
Dependent Claim
59 words
The method of claim 14, wherein step (G) further comprises the step of determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said at least one candidate directional range is selected in step (I) in accordance with said associated deviation and angular mean values.
Claim 19
Dependent Claim
30 words
The method of claim 15, wherein said deviation value in step (G) is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.
Claim 20
Dependent Claim
49 words
The method of claim 14, wherein step (A) comprises the steps of: i. selecting an object region from said two-dimensional pixel image; ii. determining the spatial coordinates of the center of mass associated with said selected object region; iii. selecting a window of pixels centered about said spatial coordinates.
Claim 21
Independent Claim
194 words
An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising: (A) a window selector for selecting a window from said two-dimensional image for processing; (B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window; (C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold; (D) means for applying said classifier to each of said plurality of pixels; (E) a calculator for determining a density value associated with a selected directional range in accordance with the number of pixels associated with said selected directional range; (F) means for applying said calculator to each of said plurality of directional ranges; (G) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated density values; and (H) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 22
Independent Claim
194 words
An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising: (A) a window selector for selecting a window from said two-dimensional image for processing; (B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window; (C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold; (D) means for applying said classifier to each of said plurality of pixels; (E) a calculator for determining a density value associated with a selected directional range in accordance with the number of pixels associated with said selected directional range; (F) means for applying said calculator to each of said plurality of directional ranges; (G) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated density values; and (H) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 23
Dependent Claim
61 words
The apparatus of claim 18, wherein said calculator further comprises means for determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said candidate directional range selector comprises means for selecting said at least one candidate directional range in accordance with said associated deviation and density values.
Claim 24
Dependent Claim
27 words
The apparatus of claim 19, wherein said deviation value is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.
Claim 25
Dependent Claim
62 words
The apparatus of claim 19, wherein said calculator further comprises means for determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and said candidate directional range selector comprises means for selecting at least one candidate directional range in accordance with said associated deviation, density and angular mean values.
Claim 26
Dependent Claim
26 words
The apparatus of claim 21, wherein said angular mean is determined in accordance with the mean of said edge directions associated with said selected directional range.
Claim 27
Dependent Claim
98 words
The apparatus of claim 21, wherein said candidate directional ranges selector comprises: i. means for selecting one directional range from said plurality of directional ranges; ii. means for determining said selected directional range to be a candidate directional range if said density value associated with said selected directional range exceeds a second predetermined threshold, said deviation value associated with said selected directional range is less than a third predetermined threshold, and said angular mean value associated with said selected directional range differs from the angular center of said selected directional range by less than a fourth predetermined threshold.
Claim 28
Dependent Claim
56 words
The apparatus of claim 18, wherein said window selector comprises: i. an object region selector for selecting an object region from said two-dimensional pixel image; ii. means for determining the spatial coordinates of the center of mass associated with said selected object region; iii. means for selecting a window of pixels centered about said spatial coordinates.
Claim 29
Dependent Claim
26 words
The apparatus of claim 24, further comprising means for sequentially translating said window about said spatial coordinates until at least one candidate directional range is selected.
Claim 30
Independent Claim
193 words
An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising: (A) a window selector for selecting a window from said two-dimensional image for processing; (B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window; (C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold; (D) means for applying said classifier to each of said plurality of pixels; (E) a calculator for determining a deviation value associated with a selected directional range in accordance with said edge directions associated with said selected directional range; (F) means for applying said calculator to each of said plurality of directional ranges; (H) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated deviation values; and (I) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 31
Independent Claim
193 words
An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising: (A) a window selector for selecting a window from said two-dimensional image for processing; (B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window; (C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold; (D) means for applying said classifier to each of said plurality of pixels; (E) a calculator for determining a deviation value associated with a selected directional range in accordance with said edge directions associated with said selected directional range; (F) means for applying said calculator to each of said plurality of directional ranges; (H) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated deviation values; and (I) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 32
Dependent Claim
27 words
The apparatus of claim 26, wherein said deviation value is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.
Claim 33
Dependent Claim
61 words
The apparatus of claim 26, wherein said calculator further comprises means for determining an angular mean value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and said candidate directional range selector comprises means for selecting at least one candidate directional range in accordance with said associated deviation and angular mean values.
Claim 34
Dependent Claim
26 words
The apparatus of claim 28, wherein said angular mean is determined in accordance with the mean of said edge directions associated with said selected directional range.
Claim 35
Dependent Claim
56 words
The apparatus of claim 26, wherein said window selector comprises: i. an object region selector for selecting an object region from said two-dimensional pixel image; ii. means for determining the spatial coordinates of the center of mass associated with said selected object region; iii. means for selecting a window of pixels centered about said spatial coordinates.
Claim 36
Independent Claim
195 words
An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising: (A) a window selector for selecting a window from said two-dimensional image for processing; (B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window; (C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold; (D) means for applying said classifier to each of said plurality of pixels; (E) a calculator for determining an angular mean value associated with a selected directional range in accordance with said edge directions associated with said selected directional range; (F) means for applying said calculator to each of said plurality of directional ranges; (G) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated angular mean values; and (H) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 37
Independent Claim
195 words
An apparatus for determining the fine angular orientation of a bar code symbol in a two-dimensional pixel image comprising: (A) a window selector for selecting a window from said two-dimensional image for processing; (B) means for determining an edge magnitude and an edge direction for each of a plurality of pixels in said selected window; (C) a classifier for associating said edge magnitude and said edge direction of a selected pixel with at least one of a plurality of directional ranges if said edge magnitude associated with said selected pixel exceeds a first predetermined threshold; (D) means for applying said classifier to each of said plurality of pixels; (E) a calculator for determining an angular mean value associated with a selected directional range in accordance with said edge directions associated with said selected directional range; (F) means for applying said calculator to each of said plurality of directional ranges; (G) a candidate directional range selector for selecting at least one candidate directional range in accordance with said associated angular mean values; and (H) means for determining said fine angular orientation in accordance with said edge directions associated with said at least one candidate directional range.
Claim 38
Dependent Claim
62 words
The apparatus of claim 31, wherein said calculator further comprises means for determining a deviation value associated with said selected directional range in accordance with said edge directions associated with said selected directional range, and wherein said candidate directional range selector comprises means for selecting said at least one candidate directional range in accordance with said associated deviation and angular mean values.
Claim 39
Dependent Claim
27 words
The apparatus of claim 32, wherein said deviation value is determined in accordance with the standard deviation of said edge directions associated with said selected directional range.
Claim 40
Dependent Claim
56 words
The apparatus of claim 31 wherein said window selector comprises: i. an object region selector for selecting an object region from said two-dimensional pixel image; ii. means for determining the spatial coordinates of the center of mass associated with said selected object region; iii. means for selecting a window of pixels centered about said spatial coordinates.
References Cited (Backward Citations)
US3410991A
Cited
US3833882A
Cited
JPS5326623A
Cited
US4473746A
Cited
US4648120A
Cited
JPS6152779A
Cited
JPS62162181A
Cited
US4797943A
Cited
JPS63123179A
Cited
US4910787A
Cited
US4749879A
Cited
US5045677A
Cited
US4982342A
Cited
US5155344A
Cited
US5001766A
Cited
US5036182A
Cited
US4988852A
Cited
US4873426A
Cited
US4973829A
Cited
US4975977A
Cited
US4958064A
Cited
US5073954A
Cited
US5081689A
Cited
US5073958A
Cited
US5063604A
Cited
EP0449634A2
Cited
EP0450878A1
Cited
EP0449645A1
Cited
US5155343A
Cited
US4992650A
Cited
US5120940A
Cited
US5142592A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-22 | 1999-07-24 | 2000-01-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-22 | 2003-07-24 | 2004-01-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-22 | 2007-07-24 | 2008-01-23 | $7700.00 | Window Closed / Lapsed |