Decoding and error correction in 2-D arrays

• US 7,386,191 B2
• Filed: 09/06/2006
• Issued: 06/10/2008
• Est. Priority Date: 10/31/2002
• Status: Expired due to Fees

• 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:
  US11/470,338
• Publication Number:
  US 20070003169A1
• Time in Patent Office: 643 Days
• Field of Search: 382/100, 382/233, 382274-275, 382/312, 382/289, 382291-297, 345/649
• US Class Current: 382/296
• 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 decoding captured image information comprising:

capturing image information, the image information including a predefined grid orientation comprising a plurality of pixels representing a plurality of corners;

determining a corner of the plurality of corners that is missing from the captured image information;

determining an angle to rotate the image information for decoding based upon the determined missing corner;

rotating the image information by the determined angle;

decoding said rotated image information;

error correcting said rotated image information; and

determining locations associated with said captured image information.

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

3. The method according to claim 1, wherein said decoding occurs remote from a camera that captures said image information.

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

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

6. The method according to claim 1, wherein decoding said rotated image information includes reading out code from the rotated image information to generate a recovered bit stream and correlating the recovered bit stream with an original bit stream used to generate the predefined grid orientation.

7. The method according to claim 6, wherein correlating the recovered bit stream includes comparing the recovered bit stream against all bit stream fragments within the original bit stream.

8. The method according to claim 6, wherein correlating the recovered bit stream includes using a hamming distance between the recovered bit stream and the original bit stream.

9. The method according to claim 1, wherein the predefined grid orientation is based upon a 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 the two-dimensional array is a wrapped non-repeating one-dimensional sequence of numbers.