METHOD OF IMAGING POSITION-CODING PATTERN HAVING TAG COORDINATES ENCODED BY BIT-SHIFTED SUBSEQUENCES OF CYCLIC POSITION CODE

• US 20100086209A1
• Filed: 08/11/2009
• Published: 04/08/2010
• Est. Priority Date: 10/02/2008
• Status: Abandoned Application

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Lapstun, Paul
• Application Number:
  US12/539,589
• Publication Number:
  US 20100086209A1
• Time in Patent Office: Days
• US Class Current: 382/182
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/10772 Moved readers, e.g. pen, wand
• CPC Class Codes: G06K 7/1417 2D bar codes

Abstract

A method of decoding a position-coding pattern disposed on a surface of a substrate. The method comprises the steps of: (a) operatively positioning an optical reader relative to the surface and capturing an image of a portion of the coding pattern; (b) sampling a windowed subsequence of a cyclic code sequence; (c) identifying a coordinate codeword using the windowed subsequence; and (d) determining a position of the optical reader from the coordinate codeword. The imaged portion has a diameter of more than one tag diameter and less than two tag diameters.

Claims

1. A method of decoding a position-coding pattern disposed on a surface of a substrate, said method comprising the steps of:

(a) operatively positioning an optical reader relative to said surface and capturing an image of a portion of said coding pattern, said coding pattern comprising;

a plurality of tags, each tag encoding a w-bit subsequence of a cyclic code sequence, said w-bit subsequence mapping to a corresponding coordinate codeword for said tag, wherein adjacent tags contain w-bit subsequences shifted by one bit relative to each other in the cyclic code sequence;

(b) sampling a windowed subsequence contained in said imaged portion;

(c) identifying a coordinate codeword using said windowed subsequence; and

(d) determining a position of the optical reader from said coordinate codeword

wherein said imaged portion has a diameter of more than one tag diameter and less than two tag diameters.

2. The method of claim 1, wherein said windowed subsequence contains a first subsequence from at least one first tag and a second subsequence from at least one second tag, said first and second tags being adjacent to each other, and wherein said method comprises the step of:

combining said first and second subsequences; and

using the combined first and second subsequences to identify said coordinate codeword.

3. The method of claim 1, wherein, if the combined first and second subsequences does not map to a valid coordinate codeword, said method comprises the step of:

determining a corresponding maximally likely coordinate from said combined first and second subsequences.

4. The method of claim 1, wherein said w-bit subsequence is represented by a set of coordinate data symbols in said tag, each of said coordinate data symbols containing at least one bit of the w-bit subsequence, each coordinate data symbol being represented by one or more data elements disposed on said surface.

5. The method of claim 1, wherein the cyclic code sequence is an m-sequence or a simplex code.

6. The method of claim 1, wherein said cyclic code sequence has a length n and a dimension k, and wherein:

n>

w>

k.

7. The method of claim 1, wherein a given tag contains a w-bit subsequence corresponding to offset i in the cyclic code sequence, and adjacent tags on either side of said given tag contain w-bit subsequences corresponding to offsets (i+1) and (i−

1) in the cyclic code sequence.

8. The method of claim 1, wherein said position-coding pattern comprises a plurality of target elements defining a target grid, said target grid comprising a plurality of cells, each cell defining a symbol group, wherein neighboring symbol groups share target elements.

9. The method of claim 8, wherein each tag is square and contains a plurality of symbol groups.

10. The method of claim 4, wherein each coordinate data symbol is a 1-bit symbol such that w coordinate data symbols represent said w-bit subsequence.

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

2 and spans across parts of at least first and second adjacent tags, said set of coordinate data symbols being arranged in each tag such that said windowed subsequence contained in said imaged portion is guaranteed to contain at least (w−

1) bits of a w-bit subsequence, said method further comprising the step of;

combining a first subsequence from at least one first tag with a second subsequence from at least one second tag to retrieve at least (w−

1) bits of the w-bit subsequence,

wherein l is a length of the tag and q is a length or a width of a coordinate data symbol.

12. The method of claim 11, wherein said windowed subsequence contains only (w−

1) bits of the w-bit subsequence, and said method further comprises the step of;

determining a maximally likely coordinate corresponding to said windowed subsequence.

13. The method of claim 4, wherein each tag contains an x-coordinate codeword mapped from a first cyclic code sequence and a y-coordinate codeword mapped from a second cyclic code sequence, said x-coordinate codeword being defined by a first set of x-coordinate data symbols, and said y-coordinate codeword being defined by a second set of y-coordinate data symbols.

14. The method of claim 13, wherein said first set is arranged in subsets of x-coordinate data symbols and said second set is arranged in subsets of y-coordinate data symbols.

15. The method of claim 14, wherein each subset of x-coordinate data symbols is configured as a column containing a plurality of said x-coordinate data symbols, and each subset of y-coordinate data symbols is configured as a row containing a plurality of said y-coordinate data symbols, wherein each of said rows and columns has a maximal width v.

16. The method of claim 15, wherein said imaged portion has a diameter of at least (l+v)√

2 and spans across parts of a plurality of adjacent tags, said columns of x-coordinate symbols and said rows of y-coordinate symbols being arranged such said windowed subsequence contained in said imaged portion is guaranteed to contain at least (w−

1) bits of a w-bit subsequence in said first cyclic code sequence and at least (w−

1) bits of a w-bit subsequence in said second cyclic code sequence, said method further comprising at least one step selected from the steps of;

combining subsequences from adjacent tags in at least one row of tags to retrieve at least (w−

1) bits of the w-bit subsequence in said first cyclic code sequence; and

combining subsequences from adjacent tags in at least one column of tags to retrieve at least (w−

1) bits of the w-bit subsequence in said second cyclic code sequence,

wherein l is a length of each tag.

17. The method of claim 4, wherein one or more of said coordinate data symbols is a merged data symbol, each merged data symbol being represented by said one or more data elements, and wherein each merged data symbol encodes at least one of said coordinate data symbols and at least one further data symbol which is different from said coordinate data symbol.

19. The optical reader of claim 1, wherein said imaged portion spans across parts of at least first and second adjacent tags such that said windowed subsequence contains a first subsequence from at least one first tag and a second subsequence from at least one second tag, wherein said processor is further configured for:

combining said first and second subsequences; and

using the combined first and second subsequences to identify said coordinate codeword.

18. An optical reader configured for decoding a position-coding pattern disposed on a surface of a substrate, said coding pattern comprising:

a plurality of tags, each tag encoding a w-bit subsequence of a cyclic code sequence, said w-bit subsequence mapping to a corresponding coordinate codeword for said tag, wherein adjacent tags contain a w-bit subsequence shifted by one bit relative to each other in the cyclic code sequence;

said optical reader comprising;

means for accessing said cyclic code sequence;

an image sensor for capturing an image of a portion of said position-coding pattern, said image sensor having a field-of-view of more than one tag diameter and less than two tag diameters; and

a processor configured for performing the steps of;

(i) sampling a windowed subsequence contained in said imaged portion;

(ii) accessing said cyclic code sequence and comparing said windowed subsequence with the accessed cyclic code sequence;

(iii) identifying a coordinate codeword using said windowed subsequence; and

(iv) determining a position of the optical reader from said coordinate codeword.

20. A system for decoding a position-coding pattern disposed on a surface of a substrate, said system comprising:

(A) said substrate, wherein said position-coding pattern comprises;

a plurality of tags, each tag encoding a w-bit subsequence of a cyclic code sequence, said w-bit subsequence mapping to a corresponding coordinate codeword for said tag, wherein adjacent tags contain a w-bit subsequence shifted by one bit relative to each other in the cyclic code sequence; and

(B) an optical reader comprising;

means for accessing said cyclic code sequence;

an image sensor for capturing an image of a portion of said position-coding pattern, said image sensor having a field-of-view of more than one tag diameter and less than two tag diameters; and

a processor configured for performing the steps of;

(i) sampling a windowed subsequence contained in said imaged portion;

(ii) accessing said cyclic code sequence and comparing said windowed subsequence with the accessed cyclic code sequence;

(iii) identifying a coordinate codeword using said windowed subsequence; and

(iv) determining a position of the optical reader from said coordinate codeword.