METHOD OF DECODING CODING PATTERN COMPRISING CONTROL SYMBOLS

• US 20110182464A1
• 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,828 B2
• Time in Patent Office: Days
• US Class Current: 382/100
• CPC Class Codes: G06F 3/0321 by optically sensing the absolute position with respect to a regularly patterned surface forming a passive digitiser, e.g. pen optically detecting position indicative tags printed on a paper sheet constructional details of pen-shaped pointing devices G06F3/03545, G06F3/03542, G06F3/037
• CPC Class Codes: G06F 3/03545 Pens or stylus
• CPC Class Codes: G06V 10/12 Details of acquisition arrangements; Constructional details thereof
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/142 using hand-held instruments; Constructional details of the instruments
• CPC Class Codes: G06V 30/1426 by sensing position defining codes on a support
• CPC Class Codes: G06V 30/1448 based on markings or identifiers characterising the document or the area

Abstract

A method of decoding a coding pattern disposed on or in a substrate. The method comprises the steps of: (a) operatively positioning an optical reader relative to a surface of the substrate; (b) capturing an image of a portion of the coding pattern; (c) sampling and decoding control symbols contained in the imaged portion to provide r₁ registration symbols and r₂ second symbols; (d) constructing an imaged registration codeword of length r₁ using the registration symbols ordered in a defined sequence; (e) identifying a distinct registration codeword corresponding to the imaged registration codeword; (f) determining a registration corresponding to the identified registration codeword; (g) constructing an imaged format codeword of length m using the determined registration and some of the r₂ second symbols; (h) identifying a distinct format codeword corresponding to the imaged format codeword; (i) determining a distinct format corresponding to the identified format codeword; and (j) using the determined registration and the determined format to decode data symbols sampled from the imaged portion.

Claims

1. A method of decoding a coding pattern disposed on or in a substrate, said method comprising the steps of:

(a) operatively positioning an optical reader relative to a surface of said substrate;

(b) capturing an image of a portion of said coding pattern, 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 translational symmetry with the tag as its unit cell, but no rotational symmetry;

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 the 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 cm control symbols, said cm 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₂;

(c) sampling and decoding at least cnt control symbols contained in said imaged portion to provide r₁ registration symbols and r₂ second symbols;

(d) constructing an imaged registration codeword of length r₁ using said registration symbols ordered in a defined sequence, said defined sequence being determined by positions of control symbols relative to target elements in the imaged portion;

(e) identifying one of ct distinct registration codewords corresponding to said imaged registration codeword;

(f) determining a registration corresponding to said identified registration codeword, said registration identifying a registration between a tag-shaped array of c grid cells at least partially contained in said imaged portion and the logical layout of the coding pattern;

(g) constructing an imaged format codeword of length m using said determined registration and at least some of said r₂ second symbols, wherein r₂≧

m;

(h) identifying one of a plurality of distinct format codewords corresponding to said imaged format codeword;

(i) determining a distinct format corresponding to said identified format codeword; and

(j) using said determined registration and said determined format to decode data symbols sampled from said imaged portion.

2. The method 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 method 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 method of claim 1, wherein a field of view of the optical reader has a diameter of between l and 1.2l, where l is defined as the diameter of one tag.

5. The method of claim 1, wherein the identified registration codeword in step (e) is selected from the ct possible registration codewords on the basis of having a smallest distance from the imaged registration codeword.

6. The method of claim 1, wherein a minimum distance (d_reg) between the ct possible registration codewords is at least r₁/2, and said method determines said registration in the presence of up to (r₁/2−

1)/2 registration symbol errors.

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

8. The method of claim 7, wherein the identified format codeword in step (h) is selected from the plurality of possible format codewords on the basis of having a smallest distance from the imaged format codeword.

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

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

a digital signature; and

a distributed data fragment.

12. The method of claim 1, wherein at least some of said r₂ second symbols form a flag codeword of length f, said flag codeword indicating whether an active area flag is present or absent, said method comprising the step of:

constructing an imaged flag codeword of length f using said determined registration and at least some of said r₂ second symbols;

identifying one of a plurality of possible flag codewords corresponding to said imaged flag codeword; and

determining whether an active area flag is present or absent using said identified flag codeword.

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

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

15. The method of claim 14, 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 method 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 local data symbols, and wherein said method comprises the step of:

decoding local data symbols contained within the imaged portion to determine a coordinate location of said optical reader relative to the surface.

17. The method of claim 1, wherein each tag comprises one or more common codewords identifying an identity, each common codeword being common to a plurality of contiguous tags, each common codeword comprising a respective set of common data symbols, and wherein said method comprises the step of:

decoding common data symbols contained within the imaged portion to determine said one or more common codewords; and

determining said identity using said one or more common codewords.

18. The method of claim 17, wherein said identity identifies at least one of:

said substrate;

a region;

a page;

a product;

a visual layout; and

an interactivity layout.

19. A system for decoding a coding pattern, said system comprising:

(A) 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 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 translational symmetry with the tag as its unit cell, but no rotational symmetry;

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 the 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 cm control symbols, said cm 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₂;

(B) an optical reader comprising;

an image sensor for capturing an image of a portion of said coding pattern; and

a processor configured for performing the steps of;

(i) sampling and decoding at least cm control symbols contained in said imaged portion to provide r₁ registration symbols and r₂ second symbols;

(ii) constructing an imaged registration codeword of length r₁ using said registration symbols ordered in a defined sequence, said defined sequence being determined by positions of control symbols relative to target elements in the imaged portion;

(iii) identifying one of ct distinct registration codewords corresponding to said imaged registration codeword;

(iv) determining a registration corresponding to said identified registration codeword, said registration identifying a registration between a tag-shaped array of c grid cells at least partially contained in said imaged portion and the logical layout of the coding pattern;

(v) constructing an imaged format codeword of length m using said determined registration and at least some of said r₂ second symbols, wherein r₂≧

m;

(vi) identifying one of a plurality of distinct format codewords corresponding to said imaged format codeword;

(vii) determining a distinct format corresponding to said identified format codeword; and

(viii) using said determined registration and said determined format to decode data symbols sampled from said imaged portion.

20. A method of decoding a coding pattern disposed on or in an at least partially transparent substrate, said method comprising the steps of:

(a) operatively positioning an optical reader relative to either side of said substrate;

(b) capturing an image of a portion of said coding pattern, 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 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 translational symmetry with the tag as its unit cell, but no rotational symmetry and no reflection axes;

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 cm control symbols, said cm 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₂;

(c) sampling and decoding at least cnt control symbols contained in said imaged portion to provide r₁ registration symbols and r₂ second symbols;

(d) constructing an imaged registration codeword of length r₁ using said registration symbols ordered in a defined sequence, said defined sequence being determined by positions of control symbols relative to target elements in the imaged portion;

(e) identifying one of 2ct distinct registration codewords corresponding to said imaged registration codeword;

(f) determining a registration corresponding to said identified registration codeword;

(g) constructing an imaged format codeword of length m using said determined registration and at least some of said r₂ second symbols;

(h) identifying one of a plurality of distinct format codewords corresponding to said imaged format codeword;

(i) determining a distinct format corresponding to said identified format codeword; and

(j) using said determined registration and said determined format to decode data symbols sampled from said imaged portion.