Strokes localization by m-array decoding and fast image matching

• US 7,263,224 B2
• Filed: 01/16/2004
• Issued: 08/28/2007
• Est. Priority Date: 01/16/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): Wu; Jingge
• Assistant Examiner(s): TSAI, TSUNG YIN
• Application Number:
  US10/759,357
• Publication Number:
  US 20050201621A1
• Time in Patent Office: 1,320 Days
• Field of Search: 382/188, 382/294, 382/181, 382/100, 382/291, 382/187, 382/313, 382/314, 705/3, 701/207, 716/7, 380/54, 345/179
• US Class Current: 382/188
• 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

Systems and methods that determine a path of a pen tip as the pen tip is moved across a document are described. The document is watermarked with a maze pattern from which encoded position information is determined. A sequence of images is captured by a camera that is located in a pen. The path of the pen tip is determined by decoding the associated maze pattern and by matching the captured images with document images. If the position coordinates of any frame that is associated with a stroke cannot be determined from m-array decoding, the frames are transformed and then matched with an area of a document image. Once the position coordinates of at least one frame is determined, the position coordinates of other frames are determined by matching the frames in a neighboring area.

Claims

1. A method for determining a path of a pen tip within a document, the method comprising:

(A) decoding extracted bits associated with a captured image to determine location coordinates of the captured image, by;

(A)(i) obtaining the extracted bits that are associated with a captured array;

(A)(ii) processing the extracted bits to determine whether the extracted bits contain at least one error bit and to determine the location coordinates if no error bits are detected; and

(A)(iii) if the at least one error bit is detected, further processing the extracted bits to determine the location coordinates from a portion of the extracted bits, by;

(A)(iii)(1) if an error bit is detected, selecting a different subset from the extracted bits, wherein at least one bit of the different subset is not one of previously correctly decoded bits;

(A)(iii)(2) decoding associated bits of the different subset;

(A)(iii)(3) in response to (2), determining whether another decoding iteration shall be performed;

(A)(iii)(4) if another decoding iteration shall be performed, selecting another subset from the extracted bits wherein at least one bit of the other subset is selected from a set of wrongly decoded bits of each previous iteration and repeating (2); and

(A)(iii)(5) if another decoding iteration shall not be performed, determining the location coordinates of the captured array, wherein the location coordinates are consistent with a local constraint;

(B) in response to (A), if the location coordinates of the captured image cannot be determined by decoding, matching the captured image with image information of the document; and

(C) mapping the path of the pen tip from the location coordinates of the captured image to the location coordinates of the tip of the pen.

2. The method of claim 1, wherein the image information is selected from watermarked document image information or image information of a neighboring area of a decoded position corresponding to the captured image.

3. The method of claim 1, further comprising:

(D) analyzing a maze pattern to extract bits from the captured image, wherein the maze pattern corresponds to an m-array.

4. The method of claim 3, further comprising:

(B) segmenting the maze pattern from an obstruction component of the captured image, wherein the obstruction component occludes the maze pattern.

5. The method of claim 4, wherein (E) comprises:

(E)(i) normalizing the captured image to compensate for non-uniform illumination.

6. The method of claim 1, wherein (B) comprises:

(B)(i) matching the captured image with an area of an image of the document, wherein the area is estimated by analyzing the image of the document or a corresponding location of a neighbor image frame, and wherein the corresponding location is determined by m-array decoding or global localization.

7. The method of claim 6 wherein (B) further comprises:

(B)(ii) in response to (i), if the location coordinates cannot be determined, warping the captured image; and

(B)(iii) matching the captured image with an area of the document, wherein an x-y position cannot be uniquely determined by m-array decoding.

8. The method of claim 7, wherein (B) further comprises:

(B)(iv) in response to (iii), repeating (i).

9. The method of claim 7, further comprising:

(D) determining the area of the document, wherein the area is occluded by content of the document, and wherein the document is watermarked.

10. The method of claim 1, further comprising:

(D) calibrating the pen tip to obtain a calibration parameter, wherein (C) comprises using the calibration parameter and a perspective transform obtained from local localization.

11. The method of claim 10, wherein (D) comprises:

(D)(i) fixing the pen tip at a contact point on the document;

(D)(ii) changing a position of a pen camera center; and

(D)(iii) mapping the position of the pen camera center to the contact point.

12. The method of claim 10, wherein the calibration parameter is indicative of a virtual pen tip position.

13. The method of claim 3, wherein (D) comprises:

(D)(i) calculating a pattern parameter, the pattern parameter characterizing grid lines of the maze pattern.

14. The method of claim 7, wherein (ii) comprises:

(B)(ii)(1) scaling and rotating a captured image by applying an affine transform obtained from maze pattern analysis; and

(B)(ii)(2) aligning the captured maze pattern to a select point of a search region.

15. The method of claim 9, wherein (D) comprises:

(D)(i) obtaining a document image, wherein the document image is watermarked.

16. A method for determining a path of a pen tip within a document, the method comprising:

(A) decoding extracted bits associated with a captured image to determine location coordinates of the captured image;

(B) in response to (A), if the location coordinates of the captured image cannot be determined by decoding, matching the captured image with image information of the document, by;

(B)(i) matching the captured image with an area of an image of the document, wherein the area is estimated by analyzing the image of the document or a corresponding location of a neighbor image frame, and wherein the corresponding location is determined by m-array decoding or global localization;

(B)(ii) in response to (i), if the location coordinates cannot be determined, warping the captured image, by;

(B)(ii)(

     1) scaling and rotating a captured image by applying an affine transform obtained from maze pattern analysis;

(B)(ii)(2) aligning the captured maze pattern to a select point of a search region; and

(B)(ii)(3) matching the warped frame with a document image, wherein the warped frame corresponds to a largest cross-correlation value; and

(B)(iii) matching the captured image with an area of the document, wherein an x-y position cannot be uniquely determined by m-array decoding; and

(C) mapping the path of the pen tip from the location coordinates of the captured image to the location coordinates of the tip of the pen.

17. The method of claim 16, wherein the image information is selected from watermarked document image information or image information of a neighboring area of a decoded position corresponding to the captured image.

18. The method of claim 16, further comprising:

(D) analyzing a maze pattern to extract bits from the captured image, wherein the maze pattern corresponds to an m-array.

19. The method of claim 18, further comprising:

(E) segmenting the maze pattern from an obstruction component of the captured image, wherein the obstruction component occludes the maze pattern.

20. The method of claim 19, wherein (B) comprises:

(E)(i) normalizing the captured image to compensate for non-uniform illumination.

21. The method of claim 16, further comprising:

(D) calibrating the pen tip to obtain a calibration parameter, wherein (C) comprises using the calibration parameter and a perspective transform obtained from local localization.

22. The method of claim 21, wherein (D) comprises:

(D)(i) fixing the pen tip at a contact point on the document;

(D)(ii) changing a position of a pen camera center; and

(D)(iii) mapping the position of the pen camera center to the contact point.

23. The method of claim 21, wherein the calibration parameter is indicative of a virtual pen tip position.

24. The method of claim 16, wherein (A) comprises:

(A)(i) obtaining the extracted bits that are associated with a captured array;

(A)(ii) processing the extracted bits to determine whether the extracted bits contain at least one error bit and to determine the location coordinates if no error bits are detected; and

(A)(iii) if the at least one error bit is detected, further processing the extracted bits to determine the location coordinates from a portion of the extracted bits,

wherein the location coordinates are consistent with a local constraint.

25. The method of claim 24, wherein (ii) comprises:

(A)(ii)(

     1) selecting a first subset from the extracted bits;

(A)(ii)(2) decoding the first subset; and

(A)(ii)(3) in response to (A)(ii)(2), if no error bits are detected, determining the location coordinates of the captured array.

26. The method of claim 18, wherein (D) comprises:

(D)(i) calculating a pattern parameter, the pattern parameter characterizing grid lines of the maze pattern.

27. The method of claim 16, wherein (C) comprises:

(C)(i) calculating pen tip location coordinates from virtual pen tip coordinates utilizing a perspective transform.

28. A method for determining a path of a pen tip within a document, the method comprising:

(A) decoding extracted bits associated with a captured image to determine location coordinates of the captured image;

(B) in response to (A), if the location coordinates of the captured image cannot be determined by decoding, matching the captured image with image information of the document, by;

(B)(i) matching the captured image with an area of an image of the document, wherein the area is estimated by analyzing the image of the document or a corresponding location of a neighbor image frame, and wherein the corresponding location is determined by m-array decoding or global localization;

(B)(ii) in response to (i), if the location coordinates cannot be determined, warping the captured image; and

(B)(iii) matching the captured image with an area of the document, wherein an x-y position cannot be uniquely determined by m-array decoding;

(C) mapping the path of the pen tip from the location coordinates of the captured image to the location coordinates of the tip of the pen; and

(D) determining the area of the document, wherein the area is occluded by content of the document, and wherein the document is watermarked, by;

(D)(i) obtaining a document image, wherein the document image is watermarked;

(D)(ii) determining whether a neighboring window of a pixel only contains maze pattern cells, wherein the document image is represented by a plurality of sub-windows; and

(D)(iii) if the sub-window does not contain only the maze pattern, differentiating a measure of visible maze pattern cells.

29. The method of claim 28, wherein (iii) comprises:

(1) partitioning the document image into a plurality of blocks having substantially a same size as maze pattern cells;

(2) if corresponding small blocks are occluded by document content, counting a number of completely visible blocks in a neighboring window with a pixel as the center of the window; and

(3) labeling the pixel with an indicator that is indicative of the number of visible blocks.

30. The method of claim 28, wherein the image information is selected from watermarked document image information or image information of a neighboring area of a decoded position corresponding to the captured image.

31. The method of claim 28, wherein (A) comprises:

(A)(i) obtaining the extracted bits that are associated with a captured array;

(A)(ii) processing the extracted bits to determine whether the extracted bits contain at least one error bit and to determine the location coordinates if no error bits are detected; and

(A)(iii) if the at least one error bit is detected, further processing the extracted bits to determine the location coordinates from a portion of the extracted bits,

wherein the location coordinates are consistent with a local constraint.

32. The method of claim 31, wherein (ii) comprises:

(A)(ii)(1) selecting a first subset from the extracted bits;

(A)(ii)(2) decoding the first subset; and

(A)(ii)(3) in response to (2), if no error bits are detected, determining the location coordinates of the captured array.

33. The method of claim 28, wherein (C) comprises:

(C)(i) calculating pen tip location coordinates from virtual pen tip coordinates utilizing a perspective transform.