US4948955A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Barcode location determination
Assignee: Boeing Co
•
Filing: 1988-12-22
•
Granted: 1990-08-14
•
Expires: 2008-12-22
Abstract
Abstract A method of determining the location of a barcode block comprising the steps of reducing an input image, rejecting background clutter, detecting barcode regions, extracting barcode moment-based features, and determining four corner points of said barcode block. This method of determining the location of a barcode block can be implemented in a single PC card and achieve a throughput of more than 16 documents per second.
Inventors
- 👤 Shih-Jong J. Lee
- 👤 Robert C. Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 03:36
CPC Classifications
G; G06; G06K; G06K7/00; G06K7/10; G06K7/10544; G06K7/10821; G06K7/10851; G06K7/14
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
66 words
A method of determining the location of a barcode block comprising the steps of: reducing input image data into a down-sampled image; removing background clutter from said down-sampled image thereby creating a clutter-free, down-sampled image; detecting barcode regions from said clutter-free, down-sampled image; extracting connected, collinear components, along with their associated moment-based features, from said barcode regions; and grouping said connected, collinear components into barcode blocks.
Claim 2
Independent Claim
66 words
A method of determining the location of a barcode block comprising the steps of: reducing input image data into a down-sampled image; removing background clutter from said down-sampled image thereby creating a clutter-free, down-sampled image; detecting barcode regions from said clutter-free, down-sampled image; extracting connected, collinear components, along with their associated moment-based features, from said barcode regions; and grouping said connected, collinear components into barcode blocks.
Claim 3
Dependent Claim
31 words
A method for determining the location of a barcode block as recited in claim 1 wherein said reducing step includes a decimation which skips a predetermined number of pixels and lines.
Claim 4
Dependent Claim
34 words
A method for determining the location of a barcode block as recited in claim 2 wherein said reducing step averages selected pixels and then thresholds to convert said down-sampled image into binary bit-map form.
Claim 5
Dependent Claim
52 words
A method for determining the location of a barcode block as recited in claim 1 wherein said input image data is operated on by said reducing step to reduce said input image data by a ratio of 4 to 1 in each dimension, thus resulting in an overall 16 to 1 reduction.
Claim 6
Dependent Claim
40 words
A method of determining the location of a barcode block as recited in claim 1 wherein said step of removing background clutter comprises a first operation to remove large background clutter, and a second operation to remove small background clutter.
Claim 7
Dependent Claim
32 words
A method of determining the location of a barcode block as recited in claim 5 wherein said first operation consists of a morphological opening residue operation by a large symmetric structuring element.
Claim 8
Dependent Claim
31 words
A method of determining the location of a barcode block as recited in claim 6 wherein said large symmetric structuring element is a disc with a radius of six picture elements.
Claim 9
Dependent Claim
32 words
A method of determining the location of a barcode block as recited in claim 5 wherein said second operation consists of a morphological opening residue operation by a small symmetric structuring element.
Claim 10
Dependent Claim
31 words
A method of determining the location of a barcode block as recited in claim 8 wherein said small symmetric structuring element is a disc with a radius of two picture elements.
Claim 11
Dependent Claim
66 words
A method of determining the location of a barcode block as recited in claim 1 wherein said step of detecting barcode regions comprises the following sub-steps: performing a morphological dilation by a large structuring element to generate a barcode region-of-interest mask; eliminating image features outside said barcode region-of-interest mark; and performing a second morphological erosion by a small symmetric structuring element to detect said barcode regions.
Claim 12
Dependent Claim
32 words
A method of determining the location of a barcode block as recited in claim 10 wherein said large structuring element is a box having sides equal in length to fifteen picture elements.
Claim 13
Dependent Claim
31 words
A method of determining the location of a barcode block as recited in claim 10 wherein said small symmetric structuring element is a disk with a radius of one picture element.
Claim 14
Dependent Claim
53 words
A method of determining the location of a barcode block as recited in claim 10 wherein said sub-step of eliminating image features outside said barcode region-of-interest mask is performed by an AND gate having a first input supplied by said barcode region-of-interest mask, and a second input supplied by said clutter-free, down-sampled image.
Claim 15
Dependent Claim
31 words
A method of determining the location of a barcode block as recited in claim 1 wherein said associated moment-based features include centroid location, area, major axis length, and minor axis length.
Claim 16
Dependent Claim
27 words
A method of determining the location of a barcode block as recited in claim 1 wherein said grouping step comprises a unary test and a binary test.
Claim 17
Dependent Claim
53 words
A method of determining the location of a barcode block as recited in claim 15 wherein said unary test compares the heights of said connected, collinear components to a known height of a barcode and filters out those components which are either too large or too small as compared to said known height.
Claim 18
Dependent Claim
26 words
A method of determining the location of a barcode block as recited in claim 16 wherein said unary test determines the barcode axis of a component.
Claim 19
Dependent Claim
26 words
A method of determining the location of a barcode block as recited in claim 15 wherein said binary test determines the length of said barcode block.
Claim 20
Independent Claim
93 words
A method of accurately detecting barcode locations in order to permit accurate barcode reading comprising the steps of: receiving a digital image of a scanned document as an input; reducing said input thereby producing a down-sampled image; rejecting background clutter on said down-sampled image, thereby creating a clutter-free, down-sampled image; detecting barcode regions from said clutter-free, down-sampled image; applying a connected components feature extraction algorithm to detect connected components within said barcode regions; and applying a barcode clustering algorithm which utilizes said connected components as inputs, and groups collinear components into barcode blocks.
Claim 21
Independent Claim
93 words
A method of accurately detecting barcode locations in order to permit accurate barcode reading comprising the steps of: receiving a digital image of a scanned document as an input; reducing said input thereby producing a down-sampled image; rejecting background clutter on said down-sampled image, thereby creating a clutter-free, down-sampled image; detecting barcode regions from said clutter-free, down-sampled image; applying a connected components feature extraction algorithm to detect connected components within said barcode regions; and applying a barcode clustering algorithm which utilizes said connected components as inputs, and groups collinear components into barcode blocks.
Claim 22
Dependent Claim
20 words
A method of accurately detecting barcode locations as recited in claim 19 wherein said scanned document is a shipping label.
Claim 23
Dependent Claim
29 words
A method of accurately detecting barcode locations as recited in claim 19 wherein said accurate barcode reading is performed at a throughput of greater than 16 documents per second.
Claim 24
Independent Claim
28 words
A method of locating a barcode from an input stage comprising the step of: updating a hypothesized barcode block by merging connected components into said hypothesized barcode block.
Claim 25
Independent Claim
28 words
A method of locating a barcode from an input stage comprising the step of: updating a hypothesized barcode block by merging connected components into said hypothesized barcode block.
Claim 26
Dependent Claim
101 words
A method of locating a barcode from an input stage as recited in claim 22 wherein a component is merged into said hypothesized barcode block only if: (a) a difference between a barcode axis angle of said component and a barcode axis angle of a hypothesized barcode block is less than a first threshold value; (b) a shortest distance between said component and said hypothesized barcode block is less than a second threshold value; and (c) a perpendicular distance from a centroid of said component to a barcode axis of said hypothesized barcode block is less than a third threshold value.
Claim 27
Dependent Claim
25 words
A method of locating a barcode from an input stage as recited in claim 22 wherein the height of said hypothesized barcode block is predetermined.
Claim 28
Dependent Claim
30 words
A method of locating a barcode from an input stage as recited in claim 24 wherein the length of said hypothesized barcode block is updated to include all connected components.
Claim 29
Dependent Claim
29 words
A method of locating a barcode from an input stage as recited in claim 22 wherein the length of said hypothesized barcode block determines the length of said barcode.
Claim 30
Dependent Claim
44 words
A method of locating a barcode from an input stage as recited in claim 22 wherein when said updating step is completed, four corner points are determined for said hypothesized barcode block, and said four corner points represent a location boundary for said barcode.
References Cited (Backward Citations)
US4096992A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-08-13 | 1994-02-12 | 1994-08-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-08-13 | 1998-02-12 | 1998-08-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-08-13 | 2002-02-12 | 2002-08-14 | $7700.00 | Window Closed / Lapsed |