Local localization using fast image match

• US 20050147281A1
• Filed: 01/07/2004
• Published: 07/07/2005
• Est. Priority Date: 01/07/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,529,410 B2
• Time in Patent Office: Days
• US Class Current: 382/119
• 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
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/12 Details of acquisition arrangements; Constructional details thereof
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

An efficient technique is disclosed for determining a portion of a document corresponding to a captured image. When a user employs a pen to create a stroke in a document, images of the document are captured by a camera mounted on the pen. While the location of some of the images will be determined from, for example, an analysis of a pattern on the document that is captured by the image or a pixel-by-pixel comparison of the image with the document, the location of other images will be determined by segmenting the sequence of images into groups that correspond to the shape of the stroke. Information relating to located images in a segment can then be employed to determine the position of unlocated images in the segment. For example, a document search region for an unlocated image can be established based upon the position of a previous located image and a maximum velocity or acceleration of the pen. The rotation and scale of the unlocated image are estimated as the same of the located image, and the unlocated image is warped using the rotation and scale. A pixel-by-pixel comparison can then be made between the warped unlocated image and the document search region. Further, if the warped unlocated image is matched successfully, the transform parameters of the image can be further refined.

Claims

1. A method for determining positions of images of a stroke, comprising:

grouping a plurality of images of a stroke in a document into one or more segments, such that each segment has a first located image corresponding to a first known position in the document and a last located image corresponding to a second known position in the document;

determining if each segment is finished or unfinished, each finished segment including at least a third located image corresponding to a third known position in the document; and

finishing each unfinished segment.

2. The method recited in claim 1, further including determining that a segment is finished if the segment includes at least a third located image corresponding to a third known position in the document, wherein the third known position was known prior to grouping the plurality of images into one or more documents.

3. The method recited in claim 1, wherein finishing each unfinished segment includes identifying a position in the document corresponding to each image in at least one unfinished segment.

4. The method recited in claim 3, wherein identifying a position in the document corresponding to a current image includes

determining a search area in the document based upon movement of a pen employed to form the stroke and a position in the document corresponding to a previous image, and

comparing the current image to the search area in the document.

5. The method recited in claim 4, wherein the movement of the pen is a maximum velocity of the pen.

6. The method recited in claim 4, wherein the movement of the pen is an actual velocity of the pen determined from positions in the document corresponding to two or more previous images.

7. The method recited in claim 4, wherein the movement of the pen is a maximum acceleration of the pen.

8. The method recited in claim 1, wherein each segment corresponds to a relatively linear portion of the stroke.

9. The method recited in claim 1, further comprising

analyzing positions in the document corresponding to each of the plurality of images;

and

pruning one or more erroneous positions.

10. The method recited in claim 9, wherein analyzing positions in the document corresponding to each of the plurality of images includes designating that positions identified before the plurality of images are grouped into segments are not erroneous.