Decoding and error correction in 2-D arrays

• US 7,116,840 B2
• Filed: 10/31/2002
• Issued: 10/03/2006
• 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
• Primary Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US10/284,422
• Publication Number:
  US 20040085287A1
• Time in Patent Office: 1,433 Days
• Field of Search: 382/188, 382/201, 382/100, 382/205, 382/291, 382/233, 345/181, 345/156, 345/179, 345/182, 181/295
• 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 method for generating an image for identifying a position of an object with respect to the image, the method comprising steps of:

creating a non-repeating one-dimensional sequence of numbers;

wrapping the non-repeating one-dimensional sequence into a two-dimensional array; and

generating an image based upon the two-dimensional array;

wherein each sub window of the two-dimensional array having at least n elements is unique in the array and the size of the array is less than or equal to 2ⁿ−

1,

wherein a portion of the generated image is captured by a camera for decoding a position of an object with respect to the generated image.

2. The method of claim 1, wherein the step of wrapping includes wrapping the non-repeating one-dimensional sequence along a diagonal of the two-dimensional array.

3. The method of claim 2,

wherein the step of wrapping includes representing each bit b_kl of the two-dimensional array of size m₁ by m₂ by a number of the one-dimensional sequence,

wherein each bit b_kl of the two-dimensional array is calculated based upon k=i mod(m₁) and l=i mod(m₂),

wherein i=0, . . . , L−

1,

wherein L=m1×

m2.

4. The method of claim 1, wherein the two-dimensional array is a binary array.

5. The method of claim 1, wherein the one-dimensional sequence of numbers includes only ones and zeroes.

6. The method of claim 1, wherein the step of generating includes placing the image in a displayed form.

7. The method of claim 6, wherein the displayed form includes a physical medium.

8. The method of claim 7, wherein the physical medium includes a watermark on printed paper.

9. The method of claim 6, wherein the displayed form includes a projected image.

10. One or more computer readable media storing executable instructions for performing a method of generating an image for identifying a position of an object with respect to the image, the method comprising steps of:

creating a non-repeating one-dimensional sequence of numbers;

wrapping the non-repeating one-dimensional sequence into a two-dimensional array; and

generating an image based upon the two-dimensional array,

wherein each sub window of the two-dimensional array having at least n elements is unique in the array and the size of the array is less than or equal to 2ⁿ−

1,

wherein a portion of the generated image is captured by a camera for decoding a position of an object with respect to the generated image.

11. The computer readable media of claim 10, wherein the step of wrapping includes wrapping the non-repeating one-dimensional sequence along a diagonal of the two-dimensional array.

12. The computer readable media of claim 11,

wherein the step of wrapping includes representing each bit b_kl of the two-dimensional array of size m₁ by m₂ by a number of the one-dimensional sequence,

wherein each bit b_kl of the two-dimensional array is calculated based upon k=i mod(m₁) and l=i mod(m₂),

wherein i=0, . . . , L−

1,

wherein L=m1×

m2.

13. The computer readable media of claim 10, wherein the two-dimensional array is a binary array.

14. The computer readable media of claim 10, wherein the one-dimensional sequence of numbers includes only ones and zeroes.

15. The computer readable media of claim 10, wherein the step of generating includes placing the image in a displayed form.

16. The computer readable media of claim 15, wherein the displayed form includes a physical medium.

17. The computer readable medium of claim 15, wherein the physical medium includes a watermark on printed paper.

18. The computer readable media of claim 15, wherein the displayed form includes a projected image.

19. One or more computer readable media storing executable instructions for performing a method of displaying an image for identifying a position of an object with respect to the image, the method comprising steps of:

creating a non-repeating one-dimensional sequence of numbers;

wrapping the non-repeating one-dimensional sequence into a two-dimensional array; and

displaying an image based upon the two-dimensional array on a display of a computer,

wherein each sub window of the two-dimensional array having at least n elements is unique in the array and the size of the array is less than or equal to 2ⁿ−

1.