Decoding and error correction in 2-D arrays

• US 20040085287A1
• Filed: 10/31/2002
• Published: 05/06/2004
• Est. Priority Date: 10/31/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Yue, Wang, Jian, Lin, Zhou Chen
• Granted Patent: US 7,116,840 B2
• Time in Patent Office: Days
• US Class Current: 345/156
• 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

Abstract

A system and process for determining the location of a captured image from a larger image is described. A non-repeating sequence may be folded into a non-repeating array in which the array is unique for every sub window of a given size. The image of the sub window may be captured and its location determined within the non-repeating array.

Claims

1. A process for creating a wrapped non-repeating sequence into an array comprising the steps of:

creating a non-repeating sequence;

wrapping said non-repeating sequence into an array,

wherein each sub window having at least n elements is unique in said array, where the size of said array is less than or equal to 2ⁿ−

1.

2. The process according to claim 1, wherein said wrapping step wraps said non-repeating sequence along a diagonal of said array.

3. The process according to claim 2, wherein said wrapping step includes representing each element b_kl the array (m₁, m₂) is represented by an element of said sequence a_i where:

k=i mod(m₁), l=i mod(m₂), i=0, . . . , L−

1 and L=2ⁿ−

1.

4. A process for determining the location of a captured array comprising the steps of:

extracting columns from said captured array;

sorting extracted code from said columns by distance;

constructing a matrix from said columns and determining a vector from said code to code in a larger array;

determining the position of extracted code.

5. The process according to claim 4, further comprising the steps of:

constructing at least another matrix from said columns and determining at least a second vector.

6. The process according to claim 4, further comprising the step of:

performing error correction on said code.

7. A computer-readable medium having a program stored thereon for creating a wrapped non-repeating sequence into an array, said program comprising the steps of:

creating a non-repeating sequence;

wrapping said non-repeating sequence into an array,

wherein each sub window having at least n elements is unique in said array, where the size of said array is less than or equal to 2ⁿ−

1.

8. The computer-readable medium according to claim 7, wherein said wrapping step wraps said non-repeating sequence along a diagonal of said array.

9. The computer-readable medium according to claim 8, wherein said wrapping step includes representing each element b_kl the array (m₁, m₂) is represented by an element of said sequence a_i where:

k=i mod(m₁), l=i mod(m_2), i=0, . . . , L−

1 and L=2ⁿ−

1.

10. A computer-readable medium having a program stored thereon for determining the location of a captured array comprising the steps of:

extracting columns from said captured array;

sorting extracted code from said columns by distance;

constructing a matrix from said columns and determining a vector from said code to code in a larger array;

determining the position of extracted code.

11. The computer-readable medium according to claim 10, further comprising the steps of:

constructing at least another matrix from said columns and determining at least a second vector.

12. The computer-readable medium according to claim 10, further comprising the step of:

performing error correction on said code.

13. A system for determining the location of a captured array in a larger array comprising:

a storage storing information regarding said larger array;

an input receiving said captured array;

a processor for determining a distance between said captured array and said larger array by determining the shift of a sequential version of said captured array from said larger array.

14. The system according to claim 13, wherein the vector providing the location of said captured array in said larger array is given by:

r^t={tilde over (b)}^t{tilde over (M)}<sup>−

1</sup>.

15. A method for decoding captured image information comprising the steps of:

capturing image information;

decoding said image information;

error correcting said image information; and

determining locations associated with said captured image information.

16. The method according to claim 15, wherein said decoding step occurs in a processing device locally associated with a camera that captures said image information.

17. The method according to claim 15, wherein said decoding step occurs remote from a camera that captures said image information.

18. The method according to claim 15, wherein said error correcting occurs in a processing device locally associated with a camera that captures said image information.

19. The method according to claim 15, wherein said error correcting step occurs remote from a camera that captures said image information.