Enhanced approach of m-array decoding and error correction

• US 20050193292A1
• Filed: 01/06/2004
• Published: 09/01/2005
• Est. Priority Date: 01/06/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Qiang, Li, Yue, Wang, Jian, Ma, Xiaoxu, Lin, Zhouchen
• Granted Patent: US 7,583,842 B2
• Time in Patent Office: Days
• US Class Current: 714/718
• 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 process and apparatus for determining the location of a captured array 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 neighboring window of a given size. A portion of the array of the neighboring window may be captured and a subset of extracted bits corresponding to the captured array is decoded to identify error bits. The location of the captured array is determined within the non-repeating array by further processing the decoded bits.

Claims

1. A method for determining a location of a captured array, the method comprising:

(A) obtaining extracted bits that are associated with the captured array;

(B) determining position coordinates if there are no error bits; and

(C) if there are error bits, determining the position coordinates from a portion of the extracted bits by non-repetitive bit selections, wherein the position coordinates are consistent with a local constraint.

2. The method of claim 1, wherein (B) comprises:

(i) selecting a first subset from the extracted bits;

(ii) decoding the first subset; and

(iii) in response to (ii), if no error bits are detected, determining the position coordinates of the captured array.

3. The method of claim 2, wherein (ii) utilizes a first matrix equation {tilde over (b)}^t=r^t{tilde over (M)}, and wherein {overscore (M)} is a sub-matrix of M in order to determine a vector r.

4. The method of claim 3, wherein (ii) further utilizes a second matrix equation {circumflex over (b)}^t=r^tM in order to determine decoded bits.

5. The method of claim 2, wherein (iii) comprises:

(1) comparing decoded bits with the extracted bits.

6. The method of claim 1, wherein (C) comprises:

(i) if an error bit is detected, selecting a different subset from the extracted bits, wherein at least one bit of the different subset is from previous sets of error bits;

(ii) decoding with corresponding bits of the different subset;

(iii) in response to (ii), determining whether another decoding iteration shall be performed;

(iv) if another decoding iteration shall be performed, selecting another subset from the extracted bits and repeating (ii); and

(v) if another decoding iteration shall not be performed, determining the position coordinates of the captured array.

7. The method of claim 6, wherein calculated bits given by {circumflex over (b)}^t=r^tM are different from the extracted bits.

8. The method of claim 2, wherein (B) further comprises:

(iv) verifying that the position coordinates are within a destination area.

9. The method of claim 6, wherein (C) further comprises:

(vi) verifying that the position coordinates are within a destination area.

10. The method of claim 2, wherein (i) comprises:

(1) randomly choosing constituent bits of the first subset from the extracted bits.

11. The method of claim 6, wherein (i) comprises:

(1) choosing the corresponding bits of the different subset from the extracted bits in a manner as to whether decoded bits satisfy a matrix equation b^t=r^tM in a previous iteration of the method; and

(2) computing how many different bits there are between calculated bits given by {circumflex over (b)}^t=r^tM and the extracted bits.

12. The method of claim 6, wherein (v) comprises:

(1) selecting a determined vector r_i if the determined vector corresponds to a number of error bits that is less than a threshold; and

(2) in response to (1), ordering a plurality of determined vectors in an ascending order by a corresponding number of error bits.

13. The method of claim 12, wherein (v) further comprises:

(3) in response to (2), finding a first solution that corresponds to the position coordinates within a destination area.

14. The method of claim 13, wherein (v) further comprises:

(4) if no solutions are located within the destination area, indicating a failure of decoding.

15. The method of claim 6, wherein (iii) comprises:

(1) adjusting a required number of iterations of the method based on an expected error rate of error bits.

16. The method of claim 6, wherein (ii) comprises:

(1) determining a vector r by utilizing a first matrix equation {tilde over (b)}^t=r^t{tilde over (M)};

(2) calculating decoded bits by utilizing a second matrix equation {circumflex over (b)}^t=r^tM, wherein the vector is determined by (1); and

(3) comparing the decoded bits with the extracted bits to find a number of error bits.

17. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 1.

18. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 2.

19. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 6.

20. An apparatus that determines position coordinates of a captured array, comprising:

(a) a bit selection module that applies a smart strategy to choose a subset of bits that has at least one bit from previous sets of error bits, the subset being selected from extracted bits that correspond to the captured array;

(b) a decoding module that processes the subset of bits to determine error information regarding the extracted bits and that determines whether another iteration of decoding is necessary from the error information; and

(c) a position determination module that processes the error information to determine position coordinates of the captured array, wherein the position coordinates are within a destination area.

21. The apparatus of claim 20, further comprising:

an input interface that receives the extracted bits and presents the extracted bits to the bit selection module for processing.

22. The apparatus of claim 20, wherein the decoding module calculates a location matrix r_i for the i^th iteration and determines error bits by comparing decoded bits determined from {circumflex over (b)}^t=r^tM with the extracted bits.

23. The apparatus of claim 20, further comprising:

an output interface that provides the position coordinates of the captured array, wherein the position coordinates are determined by the position determination module.

24. A method for determining location coordinates of a captured array, the method comprising:

(A) receiving extracted bits that are associated with the captured array;

(B) selecting a first bit subset from the extracted bits;

(C) decoding the first bit subset;

(D) if no error bits are detected, determining the location coordinates of the captured array, the location coordinates being within a destination area;

(E) selecting a different subset from the extracted bits, wherein at least one bit of the different subset does not satisfy a matrix equation {circumflex over (b)}^t=r^tM;

(F) decoding selected bits of the different subset;

(G) adjusting a number of iterations for performing (F), the number being adjusted according to results from (F);

(H) if another decoding iteration shall be performed, repeating (E)-(G); and

(I) if another decoding iteration shall not be performed, determining the location coordinates of the captured array, wherein the location coordinates are within the destination area.