Method and apparatus for decoding angular orientation of lattice codes

• US 6,678,425 B1
• Filed: 12/06/1999
• Issued: 01/13/2004
• Est. Priority Date: 12/06/1999
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Hecht, David L., Flores, L. Noah, Gorbet, Matthew G.
• Primary Examiner(s): Wu, Jingge
• Assistant Examiner(s): Hesseltine, Ryan J.
• Application Number:
  US09/455,304
• Time in Patent Office: 1,499 Days
• Field of Search: 382/289, 382/100, 382/287, 382/288, 382/294, 382/317, 382/284, 235/456, 235/462.09, 235/494, 235/454, 235/470, 358/488
• US Class Current: 382/289
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/17 using hand-held instruments
• CPC Class Codes: G06V 10/19 by sensing codes defining pattern positions
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

An angular orientation of a lattice image pattern is found by forming a composite image of superimposed portions of a lattice image by aligning centroids of a lattice element in each portion, and determining a lattice axis from a line fit through centroids of lattice elements in the composite image. The composite image is formed by selecting a seed pixel, finding a local minimum near the seed pixel and then finding a centroid based on the local minimum. From the centroid, it is determined whether the glyph centroid has sufficient contrast to be included in the composite image. The composite image is formed by superimposing subsamples of the lattice image based on glyph centroids. The composite image is then analyzed to determine a lattice axis through centroids in the composite image, and determining a quadrant image based on the lattice axis.

Claims

1. A method for determining an angular orientation of a lattice image pattern of glyphs, comprising:

forming a composite image of superimposed portions of the lattice image pattern of glyphs including;

finding a plurality of glyph centroids;

for each glyph centroid, determining a subsample of the lattice image pattern of glyphs based on the glyph centroid; and

adding the subsample to the composite image; and

determining a lattice axis from a single line fit through centroids of some of the glyphs in the composite image.

2. The method according to claim 1, wherein the step of finding a plurality of glyph centroids includes, for each glyph centroid:

selecting a seed pixel;

finding a local minimum near the seed pixel, wherein the local minimum indicates that a glyph is present;

finding the glyph centroid based on the local minimum; and

determining whether the glyph centroid has sufficient contrast.

3. The method according to claim 1, wherein the step of determining a lattice axis includes:

finding a darkest pixel along an arc; and

finding the centroid of the shape including the darkest pixel.

4. The method according to claim 1, further including:

determining a quadrant angle based on the lattice axis.

5. An apparatus for determining an angular orientation of a lattice image pattern of glyphs, comprising:

means for forming a composite image of superimposed portions of the lattice image pattern of glyphs, the forming means including

means for finding a plurality of glyph centroids;

means for determining, for each glyph centroid, a subsample of the lattice image pattern of glyphs based on the glyph centroid; and

means for adding the subsample to the composite image; and

means for determining a lattice axis from a single line fit through centroids of some of the glyphs in the composite image.

6. The apparatus according to claim 5, wherein the means for finding a plurality of glyph centroids includes, for each glyph centroid:

means for selecting a seed pixel;

means for finding a local minimum near the seed pixel, wherein the local minimum indicates that a glyph is present;

means for finding the glyph centroid based on the local minimum; and

means for determining whether the glyph centroid has sufficient contrast.

7. The apparatus according to claim 5, wherein the means for determining a lattice axis includes:

means for finding a darkest pixel along an arc; and

means for finding the centroid of the shape including the darkest pixel.

8. The apparatus according to claim 5, further comprising:

means for determining a quadrant angle based on the lattice axis.

9. A method for determining an angular orientation of a lattice image pattern of glyphs, comprising:

forming a composite image having a plurality of composite glyphs including

finding a plurality of glyph centroids; and

for each glyph centroid, adding a subsample of said lattice image pattern of glyphs to said composite image; and

determining a lattice axis for said lattice image pattern of glyphs from a line fit through centroids of some of said plurality of composite glyphs.

10. The method of claim 9, wherein the step of finding a plurality of glyph centroids comprises, for each glyph centroid:

selecting a seed pixel;

finding said glyph near said seed pixel; and

finding the glyph centroid for said glyph.

11. An apparatus for determining an angular orientation of a lattice image pattern of glyphs, comprising:

a determination mechanism configured to determine a glyph centroid for each of a plurality of glyphs in the lattice image pattern of glyphs;

a compositing mechanism, responsive to said determination mechanism, configured to composite a subsample of said lattice image pattern of glyphs to a composite image; and

a lattice-axis determination mechanism configured to determine a lattice axis for said lattice image pattern of glyphs from a line fit through centroids of some of said plurality of glyphs in the composite image formed by the compositing mechanism.

12. The apparatus of claim 11, wherein the compositing mechanism further comprises:

a seed selection mechanism configured to select a seed pixel from within said lattice image pattern of glyphs;

a glyph recognition mechanism configured to find said glyph near said seed pixel; and

a determination mechanism configured to determine a glyph centroid for said glyph recognized by the glyph recognition mechanism.

13. A computer program product including computer usable media having computer-readable code embodied therein for causing a computer to determine an angular orientation of a lattice image pattern of glyphs, the computer program product comprising:

computer readable program code configured to cause said computer to effect a determination mechanism configured to determine a glyph centroid for each of a plurality of glyphs in the lattice image pattern of glyphs;

computer readable program code configured to cause said computer to effect a compositing mechanism, responsive to said determination mechanism, configured to composite a subsample of said lattice image pattern of glyphs to a composite image; and

computer readable program code configured to cause said computer to effect a lattice-axis determination mechanism configured to determine a lattice axis for said lattice image pattern of glyphs from a line fit through centroids of some of said plurality of glyphs in the composite image formed by the compositing mechanism.