Global localization by fast image matching

• US 7,463,774 B2
• Filed: 01/07/2004
• Issued: 12/09/2008
• Est. Priority Date: 01/07/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Qiang, Dang, Yingnong, Wang, Jian, Chen, Liyong, Ma, Xiaoxu
• Primary Examiner(s): Bali; Vikkram
• Assistant Examiner(s): Rashid; David P
• Application Number:
  US10/752,086
• Publication Number:
  US 20050147299A1
• Time in Patent Office: 1,798 Days
• Field of Search: 382/218
• US Class Current: 382/218
• 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

An efficient technique is provided for determining a portion of a document corresponding to a captured image. Areas of a document in which the pattern is at least partially obscured are identified. A reference pixel in the image is selected, and an offset between the pixel and the pattern is determined. A pixel-by-pixel comparison is then made of the image with the document such that the reference pixel is only compared with locations in the document that are both within the identified areas and have the determined offset from the pattern. The comparison with the highest correspondence between the image pixels and the electronic document then identifies the position of the reference pixel relative to the electronic document.

Claims

1. A method of determining a portion of a document corresponding to a captured image, comprising:

obtaining a captured image of a portion of a document, the document having a pattern that uniquely identifies different positions in the document;

determining obscured areas of the document in which the pattern is at least partially obscured;

designating a reference pixel in the captured image;

identifying locations in the obscured areas of the document that may correspond with the reference pixel;

comparing the captured image with different portions of the document, such that the reference pixel is compared with one or more of the identified locations; and

based upon the comparison, determining an identified location in the document that corresponds with the reference pixel,

wherein determining an identified location in the document that corresponds with the reference pixel further includes

warping the captured image so that the scale and rotation of the captured image match the scale and rotation of the document;

rotating the warped captured image at multiples of 90°

; and

determining a correlation value for each comparison of the image with a portion of a document.

2. The method recited in claim 1, wherein identifying locations in the other comparison correlation values by a obscured areas of the document that may correspond with the reference pixel includes:

determining an offset distance between the reference pixel and the representation of the pattern in the captured image; and

identifying locations in the obscured areas of the document that are offset from the pattern by the offset distance.

3. The method recited in claim 1, wherein determining an identified location in the document that corresponds with the reference pixel further includes identifying comparison values that have a correlation value of 0.5 or greater.

4. The method recited in claim 3, wherein determining an identified location in the document that corresponds with the reference pixel further includes

identifying a highest comparison correlation value that is higher than all other comparison correlation values by a threshold amount;

and

determining that the reference pixel corresponds to the document location employed in the comparison with the highest comparison correlation value.

5. The method recited in claim 4, wherein comparing the captured image with different portions of the document includes comparing each rotated warped captured image with the different portions of the document.

6. The method recited in claim 1, wherein the document is an electronic document.

7. The method recited in claim 1, wherein the threshold amount is 0.1.

8. The method recited in claim 1, wherein determining obscured areas of the document comprises determining, for a given pixel of the document, whether the amount of the pattern that is obscured in a portion of the document around the given pixel is more than a predetermined amount.

9. The method recited in claim 8, wherein the portion of the document around a given pixel is the same size as the captured image.

10. The method recited in claim 1, wherein the pattern is randomly or pseudorandomly generated.

11. A computer-readable medium storing a program which when executed causes a computer to perform:

receiving a captured image of a portion of a document, wherein the document has a pattern that uniquely identifies different positions in the document and wherein the portion of the pattern in the captured image is at least partially obscured;

determining obscured areas of the document in which the pattern is at least partially obscured;

determining a spatial relationship between a reference pixel in the captured image and the pattern within the captured image;

identifying locations in the obscured areas of the document exhibiting a similar spatial relationship to the pattern in the obscured areas;

warping the captured image so that the scale and orientation of the captured image matches the scale and orientation of the document;

rotating the warped captured image at multiples of 90°

;

comparing the captured image with determined obscured areas of the document by comparing the captured image with portions of the obscured areas of the document associated with the identified locations;

determining a correlation value for each comparison of the image with a portion of a document; and

identifying the position of the portion of the document corresponding to the captured image.

12. The computer-readable medium according to claim 11, wherein the determined spatial relationship is the shortest distance between the reference pixel and an unobscured portion of the pattern.

13. The computer-readable medium according to claim 12, wherein the distance is a pixel offset between the reference pixel and the unobscured portion of the pattern.

14. The computer-readable medium according to claim 11, the program further comprising:

repeating a comparison of the captured image with a particular portion of the document for each 90°

rotation of the captured image.

15. The computer-readable medium according to claim 11, the program further comprising:

identifying the position of the portion of the document corresponding to the captured image based on the comparisons which produce a correlation of 50% or greater.

16. The computer-readable medium according to claim 11, the program further comprising:

identifying the position captured image to be the portion of the document corresponding to the comparison which produces a correlation at least 10% higher than all other comparison correlation values.

17. The computer-readable medium according to claim 11, wherein determining obscured areas of the document comprises determining, for a given pixel of the document, whether the amount of the pattern that is obscured in a portion of the document around the given pixel is more than a predetermined amount.

18. The computer-readable medium according to claim 17, wherein the portion of the document around a given pixel is the same size as the captured image.

19. The computer-readable medium according to claim 17, wherein the predetermined amount represents an amount of obscuring of the pattern such that the pattern in that potion of the document does not uniquely identify the position of the portion within the document.

20. The computer-readable medium according to claim 11, wherein the pattern is randomly or pseudorandomly generated.

21. A method for determining a portion of a document corresponding to a captured image, comprising:

receiving a captured image of a portion of a document, wherein the document has a randomly- or pseudorandomly-generated pattern that uniquely identifies different positions in the document and wherein the portion of the pattern in the captured image is at least partially obscured;

warping the captured image so that the scale and orientation of the captured image matches the scale and orientation of the document;

determining obscured areas of the document by determining, for each of given pixels of the document, whether the amount of the pattern that is obscured in a portion of the document around each given pixel is sufficient to preclude unique identification of the position of the portion within the document;

determining a pixel offset between a reference pixel in the captured image and the pattern within the captured image, wherein the pixel offset represents the shortest distance between the reference pixel and an unobscured portion of the pattern;

identifying locations in the obscured areas of the document with a comparable pixel offset;

comparing the captured image with portions of the obscured areas of the document associated with the identified locations, repeating the comparison for each 90°

rotation of the captured image;

identifying the position of the portion of the document corresponding to the captured image as the position of the portion of the document associated with the comparison which produces a correlation at least 10% higher than the other comparisons.