Strokes localization by m-array decoding and fast image matching

• US 20050201621A1
• Filed: 01/16/2004
• Published: 09/15/2005
• Est. Priority Date: 01/16/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Qiang, Dang, Yingnong, Wang, Jian, Chen, Liyong, Ma, Xiaoxu
• Granted Patent: US 7,263,224 B2
• Time in Patent Office: Days
• 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;

(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:

(E) 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:

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

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

(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:

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

(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:

(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:

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

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

(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 1, wherein (A) comprises:

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

(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

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

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

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

(2) decoding the first subset; and

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

15. The method of claim 13, wherein (iii) comprises:

(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;

(2) decoding associated bits of the different subset;

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

(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

(5) if another decoding iteration shall not be performed, determining the location coordinates of the captured array.

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

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

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

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

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

18. The method of claim 17, wherein (ii) further comprises:

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

19. The method of claim 1, wherein (C) comprises:

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

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

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

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

(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

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

22. The method of claim 21, 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.

23. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 1.

24. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 3.

25. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 6.

26. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 9.

27. A computer-readable medium having computer-executable instructions for performing the method as recited in claim 10.

28. An apparatus that determines a path of a pen tip within a document, comprising:

a decoding module that decodes extracted bits associated with a captured image;

a matching module that matches the captured image with image information of the document if location coordinates of the captured image cannot be determined by the decoding module; and

a mapping module that maps the path of the pen tip from the location coordinates of the captured image and that provides path information.

29. The apparatus of claim 28, further comprising:

a calibration module that determines a calibration parameter from movement information of a pen in relation to the pen tip, wherein the mapping module utilizes a transform and the calibration parameter in conjunction with the location coordinates of the captured image to map the path of the pen tip.

30. The apparatus of claim 28, further comprising:

a watermarked document analyzer that determines an area of a document and that provides the image information regarding the area, wherein the area is occluded by content of the document, and wherein the document is watermarked.

31. The apparatus of claim 28, further comprising:

a maze pattern analyzer that extracts the extracted bits associated with a maze pattern of the captured image and that provides the extracted bits to the decoding module.

32. The apparatus of claim 31, further comprising:

an image segmentation module that segments the maze pattern from an obstruction component of the captured image, wherein the obstruction component comprises document content that occludes the maze pattern.

33. 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 a 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 location coordinates of the captured image cannot be determined, matching the captured image with image information, comprising;

(i) warping the captured 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 location 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 location coordinates of a previously decoded image; 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 location coordinates.