METHOD OF DECODING CODING PATTERN WITH VARIABLE NUMBER OF MISSING DATA SYMBOLS POSITIONED OUTSIDE IMAGING FIELD-OF-VIEW

• US 20110182521A1
• Filed: 01/27/2010
• Published: 07/28/2011
• Est. Priority Date: 01/27/2010
• Status: Abandoned Application

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Napper, Jonathon Leigh, Lapstun, Paul
• Application Number:
  US12/694,273
• Publication Number:
  US 20110182521A1
• Time in Patent Office: Days
• US Class Current: 382/195
• 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 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, the coding pattern comprising a plurality of tags, each tag comprising a plurality n₁ of local data symbols encoding a local (n₂, k) Reed-Solomon code for the tag, wherein n₁≧n₂; (c) sampling a plurality of the local data symbols within the imaged portion, the plurality of sampled local data symbols defining a sampled local codeword; (d) identifying n₃ missing data symbols in the sampled local codeword, the missing data symbols being positioned outside the imaged portion; and (e) decoding the sampled local codeword by treating the n₃ missing data symbols as erasures. The value of n₃ varies depending on an alignment of the imaged portion with a tag to be decoded.

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 tags, each tag comprising;

a plurality n₁ of local data symbols encoding a local (n₂, k) Reed-Solomon code for said tag, wherein n₁≧

n₂;

(c) sampling a plurality of said local data symbols within said imaged portion, said plurality of sampled local data symbols defining at least part of a sampled local codeword;

(d) identifying n₃ missing data symbols in said sampled local codeword, said missing data symbols being positioned at least partially outside said imaged portion; and

(e) decoding said sampled local codeword by treating said n₃ missing data symbols as erasures,

wherein n₃ varies depending on an alignment of said imaged portion with a tag to be decoded.

2. The method of claim 1, wherein only part of said tag to be decoded is contained within said imaged portion and n₃ is at least 1.

3. The method of claim 1, wherein 0, 1, 2, 3, 4 or 5 symbol errors are corrected during said decoding.

4. The method of claim 1, wherein n₁=n₂ and none of said local data symbols is replicated within each tag.

5. The method of claim 1, wherein said n₃ missing data symbols are identified using the alignment of the imaged portion with the tag to be decoded.

6. The method of claim 1, wherein n₃ varies between 0 and n_max, for all possible alignments, and wherein n_max is determined by a diameter of said imaged portion and an arrangement of said local data symbols in each tag.

7. The method of claim 6, wherein (n₂−

n_max)>

k.

8. The method of claim 6, wherein n_max is from 2 to 15.

9. The method of claim 6, wherein each tag is a square tag of length l comprising:

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

a plurality n₁ of local y-coordinate data symbols encoding a respective local (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.

10. The method of claim 9, wherein said imaged portion has a diameter of at least (l+q)√

2 and less than (2l)√

2 and is guaranteed to contain at least (n₁+z)/2 coordinate data symbols from each of said local Reed-Solomon codes.

11. The method of claim 10, wherein n_max=(n₁−

z)/2.

12. The method of claim 9, 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.

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

14. The method of claim 13, 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.

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

16. 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 cells, wherein neighboring cells share target elements and wherein each tag is defined by a plurality of contiguous cells.

17. The method of claim 16, wherein each cell defines a symbol group containing a plurality of said local data symbols.

18. The method of claim 17, 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 local data symbols.

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

(A) a substrate having the coding pattern disposed thereon or therein, said coding pattern comprising a plurality of tags, each tag comprising;

a plurality n₁ of local data symbols encoding a local (n₂, k) Reed-Solomon code for said tag, wherein n₁≧

n₂; and

(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 a plurality of said local data symbols within said imaged portion, said plurality of sampled local data symbols defining at least part of a sampled local codeword;

(ii) identifying n₃ missing data symbols in said sampled local codeword, said missing data symbols being positioned at least partially outside said imaged portion; and

(iii) decoding said sampled local codeword by treating said n₃ missing data symbols as erasures,

wherein n₃ varies depending on an alignment of said imaged portion with a tag to be decoded.

20. An optical reader for decoding a coding pattern disposed on or in a substrate, said coding pattern comprising a plurality of tags, each tag comprising:

a plurality n₁ of local data symbols encoding a local (n₂, k) Reed-Solomon code for said tag, wherein n₁≧

n₂;

said 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 a plurality of said local data symbols within said imaged portion, said plurality of sampled local data symbols defining at least part of a sampled local codeword;

(ii) identifying n₃ missing data symbols in said sampled local codeword, said missing data symbols being positioned at least partially outside said imaged portion; and

(iii) decoding said sampled local codeword by treating said n₃ missing data symbols as erasures,

wherein n₃ varies depending on an alignment of said imaged portion with a tag to be decoded.