Decoding and error correction in 2-D arrays

• US 7,639,885 B2
• Filed: 06/02/2008
• Issued: 12/29/2009
• 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:
  US12/131,810
• Publication Number:
  US 20090110308A1
• Time in Patent Office: 575 Days
• Field of Search: 382/100, 382232-233, 382274-275, 382/289, 382291-297, 382/182, 345/649, 235/454
• US Class Current: 382/233
• 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 performed by a computer having a memory and a processor, the method comprising:

with a processor,

capturing image information, wherein the image information includes a predefined grid orientation comprising a plurality of pixels representing a plurality of corners,

determining a first angle to rotate the captured image information for decoding based on the predefined grid orientation,

rotating the captured image information by the determined first angle to provide a first rotated image,

determining a corner of the plurality of corners that is missing from the first rotated,

determining a second angle to rotate the first rotated image based upon the determined missing corner,

rotating the first rotated image by the determined second angle to provide a second rotated image,

decoding said second rotated image,

error correcting the decoded image, and

determining locations associated with the error corrected image,

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

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

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

5. 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.

6. A computer-readable medium containing instructions that when executed by a computer perform a method for decoding captured image information, the method comprising:

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

determining a pattern of the plurality of patterns that is missing from the captured image information;

determining a first angle to rotate the captured image information for decoding based on the predefined grid orientation;

rotating the captured image information by the determined first angle to provide first rotated image information;

determining a second angle to rotate the first rotated image information for decoding based upon the determined missing pattern;

rotating the first rotated image information by the determined second angle to provide second rotated imate information; and

decoding the second rotated image information.

7. The computer-readable medium according to claim 6 wherein each pattern represents a corner in the image information.

8. The computer-readable medium according to claim 6, further comprising:

determining locations associated with the captured image information.

9. The computer-readable medium according to claim 6, further comprising:

determining metadata associated with the captured image information.

10. A system for decoding captured image information comprising:

a component for capturing image information, the image information including a predefined grid orientation, wherein the predefined grid orientation comprises a plurality of pixels representing a plurality of corners;

a component for determining a first angle to rotate the image information for decoding based on the predefined grid orientation;

a component for rotating the image information by the determined first angle to provide a first rotated image;

a component for determining a corner of the plurality of corners that is missing from the first rotated image;

a component for determining a second angle to rotate the first rotated image for decoding based upon the determined missing corner;

a component for rotating the first rotated image by the determined second angle to provide a second rotated image;

a component for decoding the second rotated image;

a component for error correcting the decoded image;

a component for determining locations associated with the error corrected image; and

a component for determining metadata associated with the error corrected image.