Fiducial mark patterns for graphical bar codes

• US 20020186884A1
• Filed: 06/07/2001
• Published: 12/12/2002
• Est. Priority Date: 06/07/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Yen, Jonathan, Shaked, Doron, Atkins, C. Brian, Saw, Chit Wei, Levy, Avraham
• Granted Patent: US 6,742,708 B2
• Time in Patent Office: Days
• US Class Current: 382/183
• CPC Class Codes: G06K 19/06037 multi-dimensional coding

Abstract

Fiducial mark patterns for graphical bar codes (i.e., images that contain inconspicuous graphical modulations that encode embedded information) that are characterized by high detection robustness and good local deformation tracking are described. In one bar coding method, a base image is modulated with a graphical encoding of a message to produce a graphical bar code, and a fiducial mark pattern comprising a plurality of dots arranged to track one or more reference locations and local deformation across the graphical bar code is generated. In another bar coding method, fiducial mark candidates are identified in a fiducial mark pattern, a fiducial mark path is computed based upon one or more of the identified fiducial mark candidates, and one or more reference locations are identified based upon the computed fiducial mark path.

Claims

1. A bar coding method, comprising:

modulating a base image with a graphical encoding of a message to produce a graphical bar code; and

generating a fiducial mark pattern comprising a plurality of dots arranged to track one or more reference locations and local deformation across the graphical bar code.

2. The method of claim 1, wherein the fiducial mark pattern surrounds the graphical bar code.

3. The method of claim 1, wherein the fiducial mark pattern comprises reference color dots and background color dots.

4. The method of claim 3, the reference color dots and the background color dots are arranged in a repeating pattern having a characteristic period and comprising one reference color dot and one or more background color dots.

5. The method of claim 4, wherein the reference color dots are arranged along a rectangular fiducial mark path surrounding the graphical bar code.

6. The method of claim 5, wherein the rectangular fiducial mark path has a height dimension of 1+H·

T and a width dimension of 1+W·

T, where H and W have integer values of 1 or greater and T is the characteristic fiducial mark pattern period.

7. The method of claim 6, wherein the graphical bar code has a height dimension of H·

T−

2·

Δ

−

1 and a width dimension of W·

T−

2·

T−

1, where Δ

is the dot spacing between the graphical bar code and the fiducial mark pattern.

8. The method of claim 1, further comprising rendering the graphical bar code and the fiducial mark pattern with dots of the same size.

9. The method of claim 1, wherein the fiducial mark pattern comprises at least one orientation mark.

10. The method of claim 9, wherein the orientation mark is located at a corner position of the fiducial mark pattern.

11. The method of claim 9, wherein the orientation mark is different from other marks of the fiducial mark pattern.

14. The method of claim 13, further comprising correcting global deformations in the graphical bar code based upon the one or more reference locations.

15. The method of claim 13, wherein identifying fiducial mark candidates comprises identifying centers of reference color dots in the fiducial mark pattern.

16. The method of claim 13, further comprising discarding identified fiducial mark candidates having dot sizes larger than a selected dot size.

17. The method of claim 13, further comprising discarding identified fiducial mark candidates spaced from the computed fiducial mark path by more than a selected distance.

18. The method of claim 13, wherein a fiducial mark candidate located within a selected range from one of the identified reference locations is identified as a valid fiducial mark and its location is identified as a reference location for a neighboring fiducial mark candidate.

19. The method of claim 18, further comprising discarding a fiducial mark candidate spaced outside of a selected range from an identified reference location is discarded.

20. The method of claim 13, further comprising identifying the orientation of the graphical bar code based upon an asymmetric fiducial mark candidate in the fiducial mark pattern.

12. A computer program residing on a computer-readable medium and comprising computer-readable instructions for causing a computer to:

modulate a base image with a graphical encoding of a message to produce a graphical bar code; and

generate a fiducial mark pattern comprising a plurality of dots arranged to track one or more reference locations and local deformation across the graphical bar code.

13. A bar coding method, comprising:

identifying fiducial mark candidates in a fiducial mark pattern;

computing a fiducial mark path based upon one or more of the identified fiducial mark candidates; and

identifying one or more reference locations based upon the computed fiducial mark path.

21. A computer program residing on a computer-readable medium and comprising computer-readable instructions for causing a computer to:

identify fiducial mark candidates in a fiducial mark pattern;

compute a fiducial mark path based upon one or more of the identified fiducial mark candidates; and

identify one or more reference locations based upon the computed boundary path.