Maze pattern analysis with image matching

• US 20060215913A1
• Filed: 03/24/2005
• Published: 09/28/2006
• Est. Priority Date: 03/24/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dang, Yingnong, Wang, Jian, Chen, Liyong
• Application Number:
  US11/089,189
• Publication Number:
  US 20060215913A1
• Time in Patent Office: Days
• US Class Current: 382/232
• CPC Class Codes: G06F 3/03545 Pens or stylus
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06V 10/19 by sensing codes defining pattern positions
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

Processes and apparatuses analyze an image of a maze pattern in order to extract bits encoded in the maze pattern by iteratively obtaining a perspective transform from the captured image plane to the paper plane. The embedded interactive data is recognized by obtaining a perspective transform between the captured image plane and paper plane based on an obtained affine transform. The perspective transform typically models the relationship between two planes more precisely than the affine transform. The number of error bits in the extracted bit matrix is typically reduced, thus enabling decoding of position information to be more efficient and robust.

Claims

1. A computer-readable medium for analyzing a captured image of a document, wherein the document contains an embedded interaction code (EIC) pattern, and having computer-executable instructions to perform the steps comprising:

(A) determining an affine transform and affine grid lines associated with the affine transform;

(B) extracting an initial bit matrix (B₀) from a pre-processed image using the affine grid lines;

(C) generating a first generated pattern image (I₁) from the initial bit matrix;

(D) obtaining a first perspective transform (T₁) by matching the pre-processed image and the first generated pattern image and obtaining first perspective grid lines associated with the first perspective transform; and

(E) extracting a first bit matrix (B₁) from the pre-processed image using the first perspective grid lines.

2. The computer-readable medium of claim 1, having computer-executable instructions to perform:

(F) for i>

1, generating an i^th generated pattern image (I_i) from an (i-1)^th bit matrix (B<sub>i−

1</sub>);

(G) obtaining an i^th perspective transform (T_i) by matching the pre-processed image and the i^th generated pattern image and obtaining i^th perspective grid lines associated with the i^th perspective transform; and

(H) determining an i^th bit matrix (B_i) from the pre-processed image using the i^th perspective grid lines.

3. The computer-readable medium of claim 2 having computer-executable instructions to perform:

(I) comparing the i^th bit matrix with an (i−

1)^th bit matrix (B<sub>i−

1</sub>).

4. The computer-readable medium of claim 3 having computer-executable instructions to perform:

(J) if the i^th bit matrix equals the (i−

1)^th bit matrix, setting final extracted bits to the i^th bit matrix.

5. The computer-readable medium of claim 4 having computer-executable instructions to further perform:

(K) decoding the final extracted bits.

6. The computer-readable medium of claim 3 having computer-executable instructions to perform:

(J) if the i^th bit matrix does not equal the (i−

1)^th bit matrix, repeating (F)-(I).

7. The computer-readable medium of claim 2 having computer-executable instructions to perform:

(I) determining the i^th perspective grid lines in an image sensor plane from a paper document plane with an inverse of the i^th perspective transform (T_i<sup>−

1</sup>).

8. The computer-readable medium of claim 1 having computer-executable instructions to perform:

(F) pre-processing the captured image to obtain the pre-processed image.

9. The computer-readable medium of claim 8 having computer-executable instructions to perform:

(G) normalizing the captured image for non-uniform illumination.

10. The computer-readable medium of claim 2, wherein (F) utilizes a priori knowledge of embedded interaction code (EIC) fonts.

11. The computer-readable medium of claim 3 having computer-executable instructions to perform:

(J) if the i^th bit matrix does not equal the (i−

1)^th bit matrix and a number of iterations exceeds a predetermined threshold, performing error correction on the i^th bit matrix.

12. The computer-readable medium of claim 3 having computer-executable instructions to perform:

(J) if a number of matching bits between the i^th bit matrix and the (i−

1)th bit matrix increases with consecutive iterations, repeating (F)-(I).

13. The computer-readable medium of claim 3 having computer-executable instructions to perform:

(J) if a number of iterations exceeds a predetermined threshold, setting final extracted bits to the i^th bit matrix.

14. The computer-readable medium of claim 13 having computer-executable instructions to perform:

(K) decoding the final extracted bits.

15. An apparatus for analyzing a captured image of a document that contains an embedded interaction code (EIC) pattern, comprising:

an affine transform analyzer that determines an affine transform corresponding to a pre-processed image and that determines an initial bit matrix from affine grid lines that are associated with the affine transform; and

a perspective transform analyzer that iteratively determines an i^th bit matrix (B_i) by utilizing an i^th perspective transform (T_i) and the pre-processed image.

16. The apparatus of claim 15, wherein, if an i^th bit matrix is equal to the (i−

1)^th bit matrix, the perspective transform analyzer terminates iteratively determining the i^th bit matrix and sets a final bit matrix to the i^th bit matrix.

17. The apparatus of claim 15, wherein the perspective transform analyzer determines the i^th perspective transform by matching the pre-processed image with an i^th generated image (I_i).

18. The apparatus of claim 17, wherein the perspective transform analyzer determines the i^th generated image based on an (i-1)^th bit matrix.

19. The apparatus of claim 15, further comprising:

a pre-processor that normalizes the captured image for illumination to obtain the pre-processed image.

20. A method for analyzing a captured image of a document, the document containing an embedded interaction code (EIC) pattern, the method comprising:

(A) normalizing the captured image for non-uniform illumination to obtain a pre-processed image;

(B) determining an affine transform and affine grid lines associated with the affine transform;

(C) extracting an initial bit matrix (B₀) from the pre-processed image using the affine grid lines;

(D) obtaining an i^th perspective transform (T_i) by matching the pre-processed image and the i^th generated pattern image (I_i) and obtaining i^th perspective grid lines associated with the i^th perspective transform;

(E) determining an i^th bit matrix (B_i) from the pre-processed image using the i^th perspective grid lines;

(F) comparing the i^th bit matrix with an (i−

1)^th bit matrix (B<sub>i−

1</sub>);

(G) if the i^th bit matrix equals the (i−

1)^th bit matrix, setting final extracted bits to the i^th bit matrix; and

(H) if the i^th bit matrix does not equal the (i−

1)^th bit matrix, repeating (D)-(G).