# US 8,276,828 B2 · Method of decoding coding pattern comprising control symbols

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,276,828 B2
- Document ID: US8276828B2
- Status: Granted
- Kind: B2
- Application number: 12/694,275
- Filed: 2010-01-27
- Published: 2011-07-28
- Granted: 2012-10-02
- Earliest claimed: 2010-01-27
- Assignees: Silverbrook Research Pty Ltd
- Inventors: Paul Lapstun; Jonathon Leigh Napper
- Web page: https://patentgrep.com/patent/US8276828B2

## CPC

- 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)}
- G06F 3/03545: {Pens or stylus}
- G06V 10/12: Details of acquisition arrangements; Constructional details thereof
- G06V 30/142: using hand-held instruments; Constructional details of the instruments
- G06V 30/1448: {based on markings or identifiers characterising the document or the area}
- G06V 30/10: Character recognition
- G06V 30/1426: {by sensing position defining codes on a support}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## 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 r1 registration symbols and r2 second symbols; (d) constructing an imaged registration codeword of length r1 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 r2 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

### Claim 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 r1 registration symbols and r2 second symbols;
the r1 registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, form a registration codeword of length r1;
the r2 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≧r1 and r2;
(c) sampling and decoding at least cnt control symbols contained in said imaged portion to provide r1 registration symbols and r2 second symbols;
(d) constructing an imaged registration codeword of length r1 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 r2 second symbols, wherein r2≧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.

### Claim 2 (depends on 1)

The method of claim 1, wherein n=1, each control symbol encodes a respective registration symbol and a respective second symbol, and r1=r2=ct.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 9)

The method of claim 9, wherein each data symbol is represented by d1 macrodots, each of said d1 macrodots occupying a respective position from a plurality of predetermined possible positions p2, the respective positions of said d1 macrodots representing one of a plurality of possible data values, and wherein d1 has different values in at least one pair of distinct formats.

### Claim 11 (depends on 9)

The method of claim 9, wherein said reserved data is selected from the group consisting of:
a digital signature; and
a distributed data fragment.

### Claim 12 (depends on 1)

The method of claim 1, wherein at least some of said r2 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 r2 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.

### Claim 13 (depends on 12)

The method of claim 12, wherein r2=m+f.

### Claim 14 (depends on 12)

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

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 1)

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.

### Claim 17 (depends on 1)

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.

### Claim 18 (depends on 17)

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.

### Claim 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 r1 registration symbols and r2 second symbols;
the r1 registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, form a registration codeword of length r1;
the r2 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≧r1 and r2;
(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 r1 registration symbols and r2 second symbols;
(ii) constructing an imaged registration codeword of length r1 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 r2 second symbols, wherein r2≧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.

### Claim 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 r1 registration symbols and r2 second symbols;
the r1 registration symbols, taken in a defined sequence relative to the physical layout of the tag-shaped array, form a registration codeword of length r1;
the r2 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≧r1 and r2;
(c) sampling and decoding at least cnt control symbols contained in said imaged portion to provide r1 registration symbols and r2 second symbols;
(d) constructing an imaged registration codeword of length r1 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 r2 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.
