Strokes localization by m-array decoding and fast image matching

• US 7,570,813 B2
• Filed: 08/27/2007
• Issued: 08/04/2009
• 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): Ahmed; Samir A.
• Assistant Examiner(s): TSAI, TSUNG YIN
• Application Number:
  US11/845,584
• Publication Number:
  US 20080025612A1
• Time in Patent Office: 708 Days
• Field of Search: 382/188
• 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 of a pen within a document, the method comprising:

(A) calibrating the pen in order to obtain a calibration parameter;

(B) analyzing a watermarked document image in order to determine areas where x-y positions cannot be uniquely determined by m-array decoding;

(C) segmenting a maze pattern from an obstruction component of a captured image, wherein the obstruction component comprises document content that occludes the maze pattern;

(D) analyzing the maze pattern to extract bits from the maze pattern of the captured image;

(E) in response to (D), determining a transform that transforms image position coordinates to actual position coordinates, wherein the actual position coordinates identify a location of the pen tip in relation to the document;

(F) decoding the extracted bits associated with the captured image;

(G) in response to (F), if the image position coordinates of the captured image cannot be determined, matching the captured image with image information, comprising;

(i) warping the captured image to create a warped image; and

(ii) matching the warped image with an area of the document, where a corresponding x-y position cannot be uniquely determined by m-array decoding;

(H) determining image position coordinates of other image frames that are associated with a pen stroke, comprising;

(i) matching a corresponding captured image with a neighboring area of the image position coordinates of an image whose image position coordinates have been determined previously; and

(ii) repeating (i) until all image frames of the pen stroke are processed; and

(I) mapping the path of the pen tip from the transform, the calibration parameter, and the image position coordinates.

2. The method of claim 1, wherein the transform is a perspective transform obtained from local localization.

3. The method of claim 1, wherein calibrating the pen tip comprises:

fixing the pen tip at a contact point on the document;

changing a position of a pen camera center; and

mapping the position of the pen camera center to the contact point.

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

5. The method of claim 1, further comprising,

processing the extracted bits to determine whether the extracted bits contain at least one error bit.

6. The method of claim 1, wherein the document is a paper document.

7. The method of claim 1, wherein the document is an electronic document.

8. A computer-readable storage medium having computer-executable instructions for performing a method for determining a path of a pen tip of a pen within a document, the method comprising:

calibrating the pen in order to obtain a calibration parameter;

analyzing a watermarked document image in order to determine areas where x-y positions cannot be uniquely determined by m-array decoding;

segmenting a maze pattern from an obstruction component of a captured image,

wherein the obstruction component comprises document content that occludes the maze pattern;

analyzing the maze pattern to extract bits from the maze pattern of the captured image;

in response to analyzing the maze pattern, determining a transform that transforms image position coordinates to actual position coordinates, wherein the actual position coordinates identify a location of the pen tip in relation to the document;

decoding the extracted bits associated with the captured image;

in response to decoding the extracted bits, if the image position coordinates of the captured image cannot be determined, matching the captured image with image information, comprising;

warping the captured image to create a warped image; and

matching the warped image with an area of the document, where a corresponding x-y position cannot be uniquely determined by m-array decoding;

determining image position coordinates of other image frames that are associated with a pen stroke, comprising;

matching a corresponding captured image with a neighboring area of the image position coordinates of an image whose image position coordinates have been determined previously; and

repeating the matching of the corresponding captured image with neighboring areas until all image frames of the pen stroke are processed; and

mapping the path of the pen tip from the transform, the calibration parameter, and the image position coordinates.

9. The computer-readable storage medium of claim 8, wherein the transform is a perspective transform obtained from local localization.

10. The computer-readable storage medium of claim 8, wherein calibrating the pen tip comprises:

fixing the pen tip at a contact point on the document;

changing a position of a pen camera center; and

mapping the position of the pen camera center to the contact point.

11. The computer-readable storage medium of claim 8, wherein the calibration parameter is indicative of a virtual pen tip position.

12. The computer-readable storage medium of claim 8, further comprising,

processing the extracted bits to determine whether the extracted bits contain at least one error bit.

13. The computer-readable storage medium of claim 8, wherein the document is a paper document.

14. The computer-readable storage medium of claim 8, wherein the document is an electronic document.