US6088482A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Techniques for reading two dimensional code, including maxicode
Assignee: Symbol Technologies LLC
•
Filing: 1998-10-22
•
Granted: 2000-07-11
•
Expires: 2018-10-22
Abstract
Abstract The disclosure relates to techniques for determining the presence, orientation and location of features in an image of a two dimensional optical code. The techniques are adapted for use in mapping data in an image pixel plane with grid locations in a grid-based two dimensional code to account for size, rotation, tilt, warping and distortion of the code symbol. Where such a code is a MaxiCode, techniques are disclosed for determining the presence and location of the MaxiCode bulls-eye, orientation modules, primary data modules and secondary data modules.
Inventors
- 👤 Duanfeng He
- 👤 Kevin Hunter
- 👤 Eugene Joseph
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 05:49
CPC Classifications
G; G06; G06K; G06K7/00; G06K7/10; G06K7/14; G06K7/1404; G06K7/1439; G06K7/1443; G06K7/1456
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
134 words
A method for determining the presence and location of a MaxiCode symbol bulls-eye and the orientation of the symbol in pixel data obtained by an optical code reader comprising the steps of: identifying a candidate center in a run of pixels having a color indicative of the center area of the bulls-eye; testing the candidate center to determine if adjacent pixel runs have a predetermined amount of mirror symmetry with respect to the candidate center; locating plural points located radially outward of the identified run which points correspond to an edge of a ring of the MaxiCode bulls-eye; fitting an ellipse to said located points; expanding the ellipse outwardly to estimate the location of orientation modules of the MaxiCode; and determining the orientation of the MaxiCode symbol from information read from the orientation modules.
Claim 2
Independent Claim
134 words
A method for determining the presence and location of a MaxiCode symbol bulls-eye and the orientation of the symbol in pixel data obtained by an optical code reader comprising the steps of: identifying a candidate center in a run of pixels having a color indicative of the center area of the bulls-eye; testing the candidate center to determine if adjacent pixel runs have a predetermined amount of mirror symmetry with respect to the candidate center; locating plural points located radially outward of the identified run which points correspond to an edge of a ring of the MaxiCode bulls-eye; fitting an ellipse to said located points; expanding the ellipse outwardly to estimate the location of orientation modules of the MaxiCode; and determining the orientation of the MaxiCode symbol from information read from the orientation modules.
Claim 3
Dependent Claim
20 words
The method of claim 1, wherein the ellipse has major and minor dimensions having a ratio of 2:1 or less.
Claim 4
Dependent Claim
27 words
The method of claim 1, wherein a least squares fit is employed to find the major and minor dimensions of the ellipse fitted to the located points.
Claim 5
Dependent Claim
23 words
The method of claim 3, wherein the ring edge located is the inner edge of the outermost black ring of the MaxiCode bulls-eye.
Claim 6
Dependent Claim
67 words
The method of claim 3, wherein 8 points on the edge of the ring of the MaxiCode bulls-eyes are located and an additional 16 points are identified on the edge, located at angularly adjacent locations on either side of each of the 8 located points and wherein all 24 points are used in the least square fit to find the major and minor dimensions of the ellipse.
Claim 7
Independent Claim
91 words
A method for associating pixel data in a pixel plane, obtained by an optical code reader from an image of a two dimensional grid-based symbol, with corresponding modules in the grid, comprising the steps of: identifying subsets of the pixel data having a known association with plural seed modules; determining the coefficients of an Euler transform through a least-squares best-fit method using the identified association between the pixel data subsets and the seed modules; and using the Euler transform to associate other locations in the pixel plane with additional symbol modules.
Claim 8
Independent Claim
91 words
A method for associating pixel data in a pixel plane, obtained by an optical code reader from an image of a two dimensional grid-based symbol, with corresponding modules in the grid, comprising the steps of: identifying subsets of the pixel data having a known association with plural seed modules; determining the coefficients of an Euler transform through a least-squares best-fit method using the identified association between the pixel data subsets and the seed modules; and using the Euler transform to associate other locations in the pixel plane with additional symbol modules.
Claim 9
Dependent Claim
13 words
The method of claim 6, wherein more than six seed modules are employed.
Claim 10
Dependent Claim
26 words
The method of claim 7, wherein the symbol is a MaxiCode symbol and the seed modules are the 18 orientation hexagon modules of the MaxiCode symbol.
Claim 11
Dependent Claim
30 words
The method of claim 6, wherein the grid-based symbol is located, at least in part, outside of any single plane perpendicular to the optical axis of the optical code reader.
Claim 12
Independent Claim
100 words
A method of decoding a MaxiCode symbol imaged by an optical code reader, the MaxiCode symbol having a central finder pattern and orientation modules, primary data modules and secondary data modules located on a hexagonal grid, comprising the steps of locating the central finder pattern; locating the orientation modules based on the location of the central finder pattern; locating primary data modules of the MaxiCode based on the determined location of the orientation modules; and sequentially locating the secondary data modules outwardly from the primary message modules toward the edge of the symbol using previously located positions of adjacent modules.
Claim 13
Independent Claim
100 words
A method of decoding a MaxiCode symbol imaged by an optical code reader, the MaxiCode symbol having a central finder pattern and orientation modules, primary data modules and secondary data modules located on a hexagonal grid, comprising the steps of locating the central finder pattern; locating the orientation modules based on the location of the central finder pattern; locating primary data modules of the MaxiCode based on the determined location of the orientation modules; and sequentially locating the secondary data modules outwardly from the primary message modules toward the edge of the symbol using previously located positions of adjacent modules.
Claim 14
Dependent Claim
25 words
The method of claim 10, wherein the location of secondary data modules are estimated using the positions of adjacent modules and just past adjacent modules.
Claim 15
Dependent Claim
41 words
The method of claim 10, further comprising the step of refining the location of a first set of secondary data modules by centering black/white transitions before locating a next set of secondary data modules further outward for the central finder pattern.
Claim 16
Dependent Claim
21 words
The method of claim 10, wherein the secondary data modules are located in a successive radial progression of rings of hexagons.
Claim 17
Dependent Claim
28 words
The method of claim 10, wherein deviations from a regular hexagonal grid are accumulated as the location of secondary data modules proceeds outwardly from the central finder pattern.
Claim 18
Independent Claim
132 words
A method of determining a candidate location of a MaxiCode symbol bulls-eye center comprising the steps of: (a) locating a first sequence of plural adjacent pixel runs along a horizontal axis, the runs in the sequence having alternating colors; (b) determining whether the lengths of the located horizontal pixel runs have a predetermined proportionate relationship; (c) locating a second sequence of plural, adjacent pixel runs having alternating colors along a second axis running through the center of the central horizontal run and not parallel with the horizontal axis; (d) determining whether the lengths of the pixel runs of the second sequence have a predetermined proportionate relationship with respect to a central run; and (e) identifying a candidate location of a MaxiCode symbol bulls-eye center based on a positive determination in step (d).
Claim 19
Independent Claim
132 words
A method of determining a candidate location of a MaxiCode symbol bulls-eye center comprising the steps of: (a) locating a first sequence of plural adjacent pixel runs along a horizontal axis, the runs in the sequence having alternating colors; (b) determining whether the lengths of the located horizontal pixel runs have a predetermined proportionate relationship; (c) locating a second sequence of plural, adjacent pixel runs having alternating colors along a second axis running through the center of the central horizontal run and not parallel with the horizontal axis; (d) determining whether the lengths of the pixel runs of the second sequence have a predetermined proportionate relationship with respect to a central run; and (e) identifying a candidate location of a MaxiCode symbol bulls-eye center based on a positive determination in step (d).
Claim 20
Dependent Claim
33 words
The method of claim 15, wherein the first sequence is selected so that it has nine runs, the runs in the sequence being alternating black and white runs, first of which is white.
Claim 21
Dependent Claim
41 words
The method of claim 15, further comprising the step of using the candidate location determined in step (e) to define new axes along which new sequences of pixel runs are evaluated to determine whether the runs have a predetermined proportionate relationship.
Claim 22
Dependent Claim
28 words
The method of claim 17, further comprising the step of determining whether the lengths of sequences of runs which run in different directions have a predetermined proportionate relationship.
Claim 23
Dependent Claim
41 words
The method of claim 15, wherein the predetermined proportionate relationship with respect to the central run is one in which pixel runs on both sides of the central run have lengths between one-half and twice the length of the central run.
References Cited (Backward Citations)
US5637849A
Cited
US5966463A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-11 | 2004-01-10 | 2004-07-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-11 | 2008-01-10 | 2008-07-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-11 | 2012-01-10 | 2012-07-11 | $7700.00 | Window Closed / Lapsed |