METHOD OF DECODING A PATTERN-ENCODED COORDINATE

• US 20110185266A1
• 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,413,027 B2
• Time in Patent Office: Days
• US Class Current: 714/784
• 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: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence

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, the coding pattern comprising a plurality of square tags of length/identifying two-dimensional location coordinates; and (c) sampling and decoding x-coordinate data symbols within the imaged portion and y-coordinate data symbols within the imaged portion. The imaged portion has a predetermined diameter and is guaranteed to contain sufficient data symbols from each of the Reed-Solomon codes so that symbol errors are correctable in each of the codes during the decoding.

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 plurality of square tags of length/identifying two-dimensional location coordinates, each tag comprising;

a plurality n₁ of x-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for an x-coordinate;

a plurality n₁ of y-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for a y-coordinate;

a number z of said x-coordinate data symbols positioned in a central column of width q in each tag with a remaining (n₁−

z) x-coordinate data symbols distributed evenly on either side of said central column; and

a number z of said y-coordinate data symbols positioned in a central row of said tag of width q with a remaining (n₁−

z) y-coordinate data symbols distributed evenly above and below said central row, wherein n₁≧

n₂ and z≧

1;

(c) sampling and decoding at least one of;

x-coordinate data symbols within said imaged portion; and

y-coordinate data symbols within said imaged portion,

wherein said imaged portion has a diameter of at least (l+q)√

2 and less than (2 l)√

2 and is guaranteed to contain at least (n₁+z)/2 data symbols from each of said Reed-Solomon codes, and wherein one or more symbol errors are correctable in each of said codes during said decoding.

2. The method of claim 1, wherein n₁=n₂ and none of said x-coordinate or y-coordinate data symbols is replicated within each tag.

3. The method of claim 1, wherein n₂>

2 k and z≧

k.

4. The method of claim 1, wherein:

z is from 1 to 253;

k is from 1 to 253;

n₁ is from 3 to 255; and

n₂ is from 3 to 255.

5. The method of claim 4, wherein up to 126 symbol errors are corrected during said decoding.

6. The method of claim 1, wherein said sampled x-coordinate data symbols and y-coordinate data symbols within said imaged portion define respective sampled x-coordinate and y-coordinate codewords, and wherein any missing coordinate data symbols from respective (n₂, k) Reed-Solomon codes are treated as erasures in said sampled codewords.

7. The method of claim 6, wherein a number of said missing coordinate data symbols from respective (n₂, k) Reed-Solomon codes varies from 0 to (n₁−

z)/2 depending on an alignment of said imaged portion with a tag to be decoded.

8. The method of claim 1, wherein each data symbol is encoded using multi-pulse position modulation.

9. The method of claim 8, 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, wherein p>

d.

10. The method of claim 9, wherein d is an integer value of 2 to 6 and p is an integer value of 4 to 12.

11. The method of claim 9, wherein each data symbol provides i possible symbol values, and wherein any unused symbol values are treated as erasures.

12. The method of claim 9, wherein q=2 s, 3 s, 4 s or 5 s, and s is defined as a spacing between adjacent macrodots.

13. The method of claim 1, wherein said coding pattern comprises a plurality of target elements defining a target grid, said target grid comprising a plurality of grid cells, wherein neighboring grid cells share target elements and wherein each tag is defined by a plurality of contiguous grid cells.

14. The method of claim 13, wherein each grid cell defines a symbol group containing a plurality of data symbols, wherein each symbol group comprises at least one of said x-coordinate symbols or at least one of said y-coordinate symbols.

15. The method of claim 14, wherein each tag comprises one or more common Reed-Solomon codewords identifying a region identity associated with said surface, each common codeword being common to a plurality of contiguous tags and each common codeword comprising a respective set of common data symbols, wherein said method comprises the further steps of:

sampling and decoding common data symbols within said imaged portion; and

determining a region identity using said decoded common data symbols

16. The method of claim 14, wherein each symbol group comprises one or more registration symbols, said registration symbols identifying one or more of:

a tag encoding format;

a translation of a symbol group relative to a tag containing said symbol group;

an orientation of a layout of said data symbols with respect to said target grid; and

a flag,

wherein said method comprises the further step of;

sampling and decoding registration symbols within the imaged portion; and

using the decoded registration symbols to decode the x-coordinate data symbols and y-coordinate data symbols

17. The method of claim 16, wherein said method comprises the further step of:

using the decoded registration symbols to determine a tag encoding format for said coding pattern, said tag encoding format identifying a number of macrodots contained in each of said data symbols.

18. The method of claim 16, wherein said method comprises the further step of:

using the decoded registration symbols to determine whether at least one tag within said imaged portion is flagged or unflagged; and

providing feedback to a user in the event that the tag is flagged.

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 plurality of square tags of length/identifying two-dimensional location coordinates, each tag comprising;

a plurality n₁ of x-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for an x-coordinate;

a plurality n₁ of y-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for a y-coordinate;

a number z of said x-coordinate data symbols positioned in a central column of width q in each tag with a remaining (n₁−

z) x-coordinate data symbols distributed evenly on either side of said central column; and

a number z of said y-coordinate data symbols positioned in a central row of said tag of width q with a remaining (n₁−

z) y-coordinate data symbols distributed evenly above and below said central row, wherein n₁≧

n₂ and z≧

k; and

(B) an optical reader comprising;

an image sensor for capturing an image of a portion of said coding pattern, said image sensor having a field of view with a diameter of at least (l+q)√

2 and less than (2 l)√

2; and

a processor configured for performing the steps of;

(i) sampling at least (n₁+z)/2 data symbols from at least one of said Reed-Solomon codes; and

(ii) decoding at least one of;

said x-coordinate data symbols within said imaged

portion; and

said y-coordinate data symbols within said imaged portion, wherein said processor is configured to correct one or more symbol errors in each of said codes when decoding said x-coordinate and y-coordinate data symbols.

20. An optical reader for decoding a coding pattern disposed on or in a substrate, said coding pattern comprising a plurality of square tags of length/identifying two-dimensional location coordinates, each tag comprising:

a plurality n₁ of x-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for an x-coordinate;

a plurality n₁ of y-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for a y-coordinate;

a number z of said x-coordinate data symbols positioned in a central column of width q in each tag with a remaining (n₁−

z) x-coordinate data symbols distributed evenly on either side of said central column; and

a number z of said y-coordinate data symbols positioned in a central row of said tag of width q with a remaining (n₁−

z) y-coordinate data symbols distributed evenly above and below said central row, wherein n₁≧

n₂ and z≧

k;

said optical reader comprising;

an image sensor for capturing an image of a portion of said coding pattern, said image sensor having a field of view with a diameter of at least (l+q)√

2 and less than (2 l)√

2; and

a processor configured for performing the steps of;

(i) sampling at least (n₁+z)/2 data symbols from at least one of said Reed-Solomon codes; and

(ii) decoding at least one of;

said x-coordinate data symbols within said imaged

portion; and

said y-coordinate data symbols within said imaged portion, wherein said processor is configured to correct one or more symbol errors in each of said codes when decoding said x-coordinate and y-coordinate data symbols.