Passive embedded interaction code

• US 7,133,563 B2
• Filed: 10/31/2002
• Issued: 11/07/2006
• 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, Wu, Jiang, Wang, Jian, Ma, Xiaoxu
• Primary Examiner(s): Dang, Duy M.
• Application Number:
  US10/284,451
• Publication Number:
  US 20040086191A1
• Time in Patent Office: 1,468 Days
• Field of Search: 382187-188, 382/232, 382/251, 382/253, 382/312, 382/240, 345/179
• US Class Current: 382/240
• CPC Class Codes: G06F 3/03545 Pens or stylus
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A system and method for encoding a document image and finding a location based on that image are described. A document page is encoded into codes associated with various locations of the document page. The codes are assembled into a code book. Captured images may then be similarly encoded and searched against the codes in the codebook. One or more codes and associated locations may be returned, thereby providing one or more possible locations for the captured images.

Claims

1. A system for encoding an image of a document comprising:

an input that receives said image of said document;

a parser that parses said image into sub-images;

a encoder that encodes said sub-images into a code;

a storage that stores said code associated with a location of said sub-images in relation to said image,

wherein said storage includes a codebook;

wherein said storage stores said codes into a binary tree,

wherein said binary tree separates said codes based on their distance from a centroid of said codebook.

2. The system for encoding according to claim 1, wherein said encoder encodes based on sections of said sub-images.

3. The system for encoding according to claim 1, wherein said encoder encodes based on radial analysis of said sub-images.

4. A system for creating a codebook comprising:

an input that receives codes associated with sub-images of an image;

a processor that organizes said codes into said codebook, said codes being associated with a location of said sub-images in relation to said image; and

a storage that stores said code book,

wherein said processor organizes said codes into a binary tree,

wherein said binary tree separates said codes based on their distance from a centroid of said codebook.

5. The system for creating a codebook according to claim 4, wherein said processor organizes said codes into a linear list of said codes.

6. The system for creating a codebook according to claim 4, wherein said binary tree further separates said codes based on their distance from centroids of subsections of said codebook.

7. A system for searching a codebook comprising:

a first input that receives a codebook having codes associated with sub-images of an image and information relating to the location of the sub-images in said image;

a second input that receives an image from camera attached to a pen;

an encoder that encodes said image from said camera and output a code associated with said camera image;

a processor that searches said codebook for one or more code candidates that are similar to said code associated with said camera image;

an output that outputs one or more locations associated with said one or code candidates,

wherein said processor organizes said codes in the codebook into a binary tree,

wherein said binary tree separates said codes in the codebook based on their distance from a centroid of said codebook.

8. A method for creating a codebook comprising the steps of:

receiving encoded information regarding a sub-image;

receiving location information regarding where said sub-image is located in a larger image;

associating said encoded information with said location information;

storing said associated information as said codebook;

finding a centroid of said encoded information;

finding a first code of said encoded information farthest from said cetroid;

finding a second code of said encoded information farthest from said first code; and

separating said encoded information to two datasets, with one closer to said first code and the other closer to said second code.

9. The method according to claim 8, wherein said storing step further comprises storing said codebook as a linear list.

10. The method according to claim 8, wherein said storing step further comprises storing said codebook as a binary tree.

11. The method according to claim 10, further comprising the step of reducing the size of said encoded information for storage in said binary tree.

12. The method according to claim 8, wherein repeating the steps of finding a centroid through separating said encoded information until a binary is realized.