Statistical model for global localization

• US 7,430,497 B2
• Filed: 10/31/2002
• Issued: 09/30/2008
• Est. Priority Date: 10/31/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dang, Yingnong, Chen, Zheng, Wu, Jiang, Wang, Jian, Chen, Liyong, Ma, Xiaoxu
• Primary Examiner(s): Shah; Kamini
• Assistant Examiner(s): Gebresilassie; Kibrom K
• Application Number:
  US10/284,421
• Publication Number:
  US 20040085302A1
• Time in Patent Office: 2,161 Days
• Field of Search: 709/223, 382/181, 382/253, 382/284, 382/232, 382/173, 382312-314, 382/177, 382/179, 382187-189, 382/316, 703/2
• US Class Current: 703/2
• 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: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A system and process for determining the location of a captured image from a larger image is described. Using a list of determined locations, the system is able to determine the best or most likely path of a pen tip.

Claims

1. A process for determining a path of a pen having a camera capturing information, which is used to determine candidates for said pen'"'"'s location with respect to a surface, comprising the steps of:

segmenting a surface into blocks;

analyzing the segmented surface to determine a relationship between the blocks of the segmented surface;

receiving a list of candidates, representative of locations of the pen with respect to the surface, for each image captured by said camera, the list of candidates being constrained by the determined relationship between the blocks of the segmented surface; and

determining a most likely path of said pen with respect to the surface based on a minimal movement from a previous image captured by said camera and at least one candidate of at least one received list of candidates,

wherein said process skips at least one candidate of a list of candidates for an image in determining said most likely path.

2. The process according to claim 1, wherein said determining step uses a bigram model.

3. The process according to claim 1, wherein said determining step uses a trigram model.

4. The process according to claim 1, wherein said list of candidates is related to active codes.

5. The process according to claim 1, wherein said list of candidates is related to passive codes.

6. A computer-readable medium having computer-implementable instructions stored thereon, said instructions when executed on a computer, cause the computer to perform the functions of:

determining a path of a pen having a camera capturing information, which is used to determine candidates for said pen'"'"'s location with respect to a surface, said instructions comprising the steps of;

segmenting a surface into blocks;

analyzing the segmented surface to determine a relationship between the blocks of the segmented surface;

receiving a list of candidates, representative of locations of the pen with respect to the surface, for each image captured by said camera, the list of candidates being constrained by the determined relationship between the blocks of the segmented surface; and

determining a most likely path of said pen with respect to the surface based on a minimal movement from a previous image captured by said camera and at least one candidate of at least one received list of candidates,

wherein said instructions further cause the computer to skip at least one candidate of a list of candidates for an image in determining said most likely path.

7. The computer-readable medium according to claim 6, wherein said determining step uses a bigram model.

8. The computer-readable medium according to claim 6, wherein said determining step uses a trigram model.

9. The computer-readable medium according to claim 6, wherein said list of candidates is related to active codes.

10. The computer-readable medium according to claim 6, wherein said list of candidates is related to passive codes.

11. A system for determining a path of a pen with respect to a surface comprising:

an input configured to receive information related to an image from a camera attached to said pen; and

a processor configured to;

segment a surface into blocks,

analyze the segmented surface to determine a relationship between the blocks of the segmented surface,

process said information to obtain a list of candidates, representative of locations of the pen with respect to the surface, for each image captured by said camera, the list of candidates being constrained by the determined relationship between the blocks of the segmented surface, and

determine a most likely path said pen with respect to the surface based on a minimal movement from a pervious image captured by said camera and at least one candidate of at least one processed list of candidates,

wherein said processor skips at least one candidate of the list of candidates for the image in determining said most likely path.

12. The system according to claim 11, wherein said processor bases a location of the pen at least in part on a location of at least one potential candidate from at least one previous image from said camera.

13. A system for determining a path of a pen with respect to an encoded medium comprising:

an encoded medium, said encoded medium including an encoded image;

a camera configured to capture said encoded image; and

a processor configured to;

segment the encoded medium into blocks,

analyze the segmented encoded medium to determine a relationship between the blocks of the segmented encoded medium,

process said encoded image to obtain a list of candidates, representative of locations of the pen with respect to the encoded medium, for each encoded image captured by said camera, the list of candidates being constrained by the determined relationship between the blocks of the segmented encoded medium, and

determine at least one possible location of said encoded image and provide a most likely path of the pen associated with said camera based on a minimal movement from a pervious portion of the encoded image captured by said camera and a number of potential candidates from said encoded medium,

wherein said processor skips at least one potential candidate of the number of potential candidates for the captured encoded image in providing said most likely path.

14. The system according to claim 13, wherein said encoded medium is a blank paper.

15. The system according to claim 13, wherein said encoded medium is paper with graphical content.

16. The system according to claim 13, wherein said encoded medium is a computer display showing an image combined with an encoded image.

17. The system according to claim 13, wherein said encoded medium is a computer display showing an image, wherein said computer display includes an encoded image associated with the computer display.

18. The system according to claim 17, wherein the encoded image is part of said computer display.

19. The system according to claim 17, wherein the encoded image is a transparent overlay placed over said computer display.