CODING PATTERN COMPRISING REGISTRATION CODEWORD HAVING VARIANTS CORRESPONDING TO POSSIBLE REGISTRATIONS

• US 20110180613A1
• Filed: 01/27/2010
• Published: 07/28/2011
• Est. Priority Date: 01/27/2010
• Status: Active Grant

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Napper, Jonathon Leigh, Lapstun, Paul
• Granted Patent: US 8,292,190 B2
• Time in Patent Office: Days
• US Class Current: 235/494
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence

Abstract

A substrate having a coding pattern disposed thereon or therein. The coding pattern comprises a tiling of contiguous grid cells, each grid cell being demarcated by t target elements and having t-fold rotational symmetry, each grid cell containing nt registration symbols, each registration symbol being encoded by a set of macrodots; and a tiling of contiguous tags, each tag consisting of an array of c grid cells, each tag containing a plurality of data symbols. There are ct possible registrations between a physical layout of the coding pattern and a logical layout of the coding pattern and any contiguous tag-shaped array of c grid cells contains cnt registration symbols. The registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, form a registration codeword of length r. There are v distinct registration codewords, each corresponding to a distinct one of the ct possible registrations.

Claims

1. A substrate having a coding pattern disposed thereon or therein, said coding pattern comprising:

a tiling of contiguous grid cells, each grid cell being demarcated by t target elements and having t-fold rotational symmetry, each grid cell containing nt registration symbols, each registration symbol being encoded by a set of macrodots; and

a tiling of contiguous tags, each tag consisting of an array of c grid cells, each tag containing a plurality of data symbols and having an identical layout of data symbols, each data symbol being encoded by a set of macrodots;

wherein;

the coding pattern has a physical layout defined by its tiling of contiguous grid cells, said physical layout belonging to a plane symmetry group that has t-fold rotational symmetry and translational symmetry with the grid cell as its unit cell;

the coding pattern has a logical layout defined by its tiling of contiguous tags, said logical layout belonging to a plane symmetry group that has no rotational symmetry but has translational symmetry with the tag as its unit cell;

there are ct possible registrations between the physical layout of the coding pattern and the logical layout of the coding pattern, each registration corresponding to a distinct combination of one of the t possible rotations of the physical layout of coding pattern relative to the logical layout of the coding pattern and one of the c possible translations of the physical layout of the coding pattern relative to the logical layout of the coding pattern;

any contiguous tag-shaped array of c grid cells contains cnt registration symbols, said registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, forming a registration codeword of length r;

there are v distinct registration codewords, each corresponding to a distinct one of the ct possible registrations;

the registration codeword of each contiguous tag-shaped array of c grid cells thereby uniquely identifies a registration between said tag-shaped array and the logical layout of the coding pattern;

t=is an integer value of 2 or more;

c=is an integer value of 2 or more;

n is an integer value of 1 or more;

cnt≧

r; and

v≧

ct.

2. The substrate of claim 1, wherein n=1 and r=ct.

3. The substrate of claim 1, wherein:

t is 2, 3, 4 or 6;

c is 2, 3, 4, 9, 16, 25 or 36; and

n is 1, 2, 3 or 4.

4. The substrate of claim 1, wherein the registration codeword of each tag-shaped array facilitates identification of at least one of the data symbols of a tag that shares at least one grid cell with said tag-shaped array.

5. The substrate of claim 1, wherein v=ct.

6. The substrate of claim 5, wherein a minimum distance between each of the ct distinct registration codewords is at least r/2, thereby allowing the registration between said tag-shaped array and the logical layout of the coding pattern to be determined in the presence of up to (r/2−

1)/2 registration symbol errors.

7. The substrate of claim 1, wherein v>

ct, such that each of the ct possible registrations has a plurality of corresponding registration codewords.

8. The substrate of claim 7, wherein a minimum distance between pairs of distinct registration codewords encoding different registrations is at least r/2.

9. The substrate of claim 8, wherein each of the ct possible registrations has first and second corresponding registration codewords, said first registration codewords identifying a first encoding format of said coding pattern and said second registration codewords identifying a second encoding format of said coding pattern.

10. The substrate of claim 7, wherein a minimum distance (d_format) between each pair of first and second registration codewords encoding the same registration is at least r/2.

11. The substrate of claim 9, wherein each data symbol is represented by d₁ macrodots, each of said d₁ macrodots occupying a respective position from a plurality of predetermined possible positions p₁, the respective positions of said d₁ macrodots representing one of a plurality of possible data values, and wherein d₁ has different values in said first and second encoding formats.

12. The substrate of claim 9, wherein each of the ct possible registrations has a corresponding flagged first registration codeword, a corresponding unflagged first registration codeword, a corresponding flagged second registration codeword and a corresponding unflagged second registration codeword, said flagged registration codewords identifying the presence of an active area flag and said unflagged registration codewords identifying the absence of said active area flag.

13. The substrate of claim 11, wherein:

at least some tag-shaped arrays in said coding pattern having the first encoding format contain a mixture of registration symbols from said flagged first registration codeword and registration symbols from said unflagged first registration codeword to form a mixed first registration codeword of length r; and

at least some tag-shaped arrays in said coding pattern having the second format contain a mixture of registration symbols from said flagged second registration codeword and registration symbols from said unflagged second registration codeword to form a mixed second registration codeword of length r.

14. The substrate of claim 13, wherein a minimum distance (d_flag) between each pair of flagged and unflagged registration codewords encoding the same registration and the same format is less than r/2, thereby enabling correction of registration symbol errors in said mixed first and second registration codewords.

15. The substrate of claim 14, wherein each tag contains a registration codeword selected from one of the codewords defined as:

16. The substrate of claim 1, wherein each registration symbol is represented by d₂ macrodots, each of said d₂ macrodots occupying a respective position from a plurality of predetermined possible positions p₂, the respective positions of said d₂ macrodots representing one of a plurality of possible registration symbol values.

17. The substrate of claim 1, wherein each tag comprises at least one local codeword identifying a location of a respective tag, said local codeword comprising a respective set of said data symbols.

18. The substrate of claim 17, wherein each tag comprises one or more common codewords, each common codeword being common to a plurality of contiguous tags, each common codeword comprising a respective set of said data symbols.

19. The substrate of claim 18, wherein each common codeword, or a set of common codewords, identifies a region identity, a page identity or a substrate identity.

20. A substrate having a coding pattern disposed on or in a surface thereof, said coding pattern comprising:

a tiling of contiguous grid cells, each grid cell being demarcated by t target elements and having t-fold rotational symmetry, each grid cell containing nt registration symbols, each registration symbol being encoded by a set of macrodots; and

a tiling of contiguous tags, each tag consisting of an array of c grid cells, each tag containing a plurality of data symbols and having an identical layout of data symbols, each data symbol being encoded by a set of macrodots;

wherein;

the coding pattern has a physical layout defined by its tiling of contiguous grid cells, said physical layout belonging to a plane symmetry group that has at least one reflection axis, t-fold rotational symmetry and translational symmetry with the grid cell as its unit cell;

the coding pattern has a logical layout defined by its tiling of contiguous tags, said logical layout belonging to a plane symmetry group that has no reflection axis and no rotational symmetry, but has translational symmetry with the tag as its unit cell;

there are 2ct possible registrations between the physical layout of the coding pattern and the logical layout of the coding pattern, each registration corresponding to a distinct combination of;

(1) whether or not the physical layout of the coding pattern is reflected relative to the logical layout of the coding pattern;

(2) one of t possible rotations of the physical layout of coding pattern relative to the logical layout of the coding pattern; and

(3) one of c possible translations of the physical layout of the coding pattern relative to the logical layout of the coding pattern;

any contiguous tag-shaped array of c grid cells contains cnt registration symbols, said registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, forming a registration codeword of length r;

there are v distinct registration codewords, each corresponding to a distinct one of the 2ct possible registrations;

the registration codeword of each contiguous tag-shaped array of c grid cells thereby uniquely identifies a registration between said tag-shaped array and the logical layout of the coding pattern;

t=is an integer value of 2 or more;

c=is an integer value of 2 or more;

n is an integer value of 1 or more;

cnt≧

r; and

v≧

2ct.