Decoding and Error Correction In 2-D Arrays

• US 20070025641A1
• Filed: 09/06/2006
• Published: 02/01/2007
• Est. Priority Date: 10/31/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Zhou, Li, Yue, Wang, Jian
• Granted Patent: US 7,330,605 B2
• Time in Patent Office: Days
• US Class Current: 382/291
• 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 determining the location of a captured array comprising:

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; and

determining the position of extracted code.

2. The process according to claim 1, further comprising:

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

3. The process according to claim 1, further comprising:

performing error correction on said code.

4. A computer-readable medium having a program stored thereon for determining the location of a captured array that, when executed by a computer causes the computer to:

extract columns from said captured array;

sort extracted code from said columns by distance;

construct a matrix from said columns and determine a vector from said code to code in a larger array; and

determine the position of extracted code.

5. The computer-readable medium according to claim 4, further causing the computer to:

construct at least another matrix from said columns and determine at least a second vector.

6. The computer-readable medium according to claim 4, further causing the computer to:

perform error correction on said code.

7. 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; and

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.

8. The system according to claim 7, 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>.