CODING PATTERN COMPRISING CONTROL SYMBOLS

• US 20110180615A1
• 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,276,827 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 therein or thereon. 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 control symbols, each control 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, each data symbol being encoded by a set of macrodots. Any contiguous tag-shaped array of c grid cells contains cnt control symbols, which encode r₁ registration symbols and r₂ second symbols. The r₁ registration symbols, taken in a defined sequence relative to a physical layout of the tag-shaped array, form a registration codeword of length r₁. The r₂ second symbols form one or more second codewords.

Claims

1. A substrate having a coding pattern disposed therein or thereon, 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 control symbols, each control 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 control symbols, said cnt control symbols encoding r₁ registration symbols and r₂ second symbols,

the r₁ registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, form a registration codeword of length r₁;

the r₂ second symbols form one or more second codewords;

there are ct 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; and

cnt≧

r₁ and r₂.

2. The substrate of claim 1, wherein n=1, each control symbol encodes a respective registration symbol and a respective second symbol, and r₁=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 the defined sequence is different for each of the ct possible registration codewords.

6. The substrate of claim 1, wherein a minimum distance (d_reg) between each of the ct possible 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 (d_reg−

1)/2 registration symbol errors.

7. The substrate of claim 1, wherein at least some of said r₂ second symbols form a format codeword of length m, said format codeword being one of a plurality of distinct format codewords, each distinct format codeword corresponding to a distinct format of said coding pattern.

8. The substrate of claim 7, wherein a minimum distance (d_format) between pairs of distinct format codewords is at least m/2.

9. The substrate of claim 7, wherein each distinct format identifies one or more of:

a presence or absence of reserved data in each tag; and

a number of macrodots in each set of macrodots used to encode a respective data symbol.

10. The substrate of claim 1, 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 at least one pair of distinct formats.

11. The substrate of claim 9, wherein said reserved data is selected from the group consisting of:

a digital signature; and

a distributed data fragment.

12. The substrate of claim 7, wherein:

at least some of the r₂ second symbols form a flag codeword of length f, said flag codeword indicating whether an active area flag is present or absent.

13. The substrate of claim 12, wherein r₂=m+f.

14. The substrate of claim 12, wherein a minimum distance (d_flag) between different flag codewords is at least f/2.

15. The substrate of claim 12, wherein:

a plurality of said nt control symbols in each grid cell encodes second symbols for said format codeword; and

one of said nt control symbols in each grid cell encodes a second symbol for said flag codeword.

16. The substrate of claim 1, wherein each registration symbol has three or more possible symbol values and each second symbol is a binary symbol.

17. The substrate of claim 1, wherein:

each registration codeword symbol is a ternary symbol;

n=1;

r₁=ct=36; and

said registration codeword is;

1201, 2011, 2121, 2002, 0111, 2222, 0002, 1011, 0002.

18. The substrate of claim 7, wherein:

each second symbol is a binary symbol;

m=27; and

said format codeword is selected from one of the following codewords;

19. A substrate having a coding pattern disposed therein or thereon, 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 control symbols, each control 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;

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 2 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;

(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 control symbols, said cnt control symbols encoding r₁ registration symbols and r₂ second symbols,

the r₁ registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, form a registration codeword of length r₁;

the r₂ second symbols form one or more second codewords;

there are 2 ct distinct registration codewords, each corresponding to a distinct one of the 2 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 2 or more; and

cnt≧

r₁ and r₂.

20. The substrate of claim 19, wherein said substrate is at least partially transparent such that said coding pattern is readable from either side of said substrate.