Image-based document indexing and retrieval

• US 7,475,061 B2
• Filed: 01/15/2004
• Issued: 01/06/2009
• Est. Priority Date: 01/15/2004
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Srivastava, Vivek, Simard, Patrice Y., Bargeron, David M.
• Primary Examiner(s): Corrielus; Jean M
• Assistant Examiner(s): COLAN, GIOVANNA B
• Application Number:
  US10/758,370
• Publication Number:
  US 20050165747A1
• Time in Patent Office: 1,818 Days
• Field of Search: 382/100, 382/176, 382/305, 382/23, 382/175, 713/187, 713/197, 707/1, 380/23
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system that facilitates document retrieval and/or indexing is provided. A component receives an image of a document, and a search component searches data store(s) for a match to the document image. The match is performed over word-level topological properties of images of documents stored in the data store(s).

Claims

1. A machine-implemented system for document retrieval and/or indexing comprising:

a processor;

a component that receives a captured image of at least a portion of a physical document;

a search component that locates a match to the physical document, the search is performed over word-level topological properties of generated images, the word-level topological properties comprise at least respective widths of words on the generated images, and the generated images being images of at least a portion of one or more electronic documents; and

a comparison component that iteratively compares a portion of a signature associated with the captured image based at least in part on word-level topological properties with corresponding portions of signatures respectively associated with the generated images based at least in part on word-level topological properties and excludes each generated image whose portion of the signature does not match the portion of the signature of the captured image to facilitate location of a match to the physical document,

the portion of the signature associated with the captured image and the portion of the signatures respectively associated with the generated images that are compared become progressively smaller with each iteration, where one or more iterations are performed until a predetermined threshold number of generated images remain,

wherein each portion of signature respectively associated with a generated image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the generated image is entered into a respective table location for each segment of the generated image, and

wherein the portion of the signature associated with the captured image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the captured image is entered into a respective table location for each segment of the captured image.

2. The system of claim 1, further comprising a component that generates signature(s) corresponding to one or more of the generated images and generates a signature corresponding to the captured image of the physical document, the signatures identify the word-layout of the generated images, and the search performed via comparing the signatures of the generated images with the signature of the captured image of the physical document.

3. The system of claim 2, the signatures being at least one of hash tables and or approximate hash tables, or a combination thereof.

4. The system of claim 3, the at least one of the hash tables and or approximate hash tables comprising a key that is associated with a location and width of a word within at least one of the generated images or the captured image of the physical document, or a combination thereof.

5. The system of claim 2, further comprising a scoring component that assigns confidence scores corresponding to a subset of the generated images that are searched against.

6. The system of claim 5, a generated image with the highest confidence score is selected as the match to the captured image of the physical document.

7. The system of claim 2, the signature(s) corresponding to the one or more generated images comprises a tolerance for error.

8. The system of claim 2, a portion of the signature(s) associated with the one or more generated images is compared to a corresponding portion of the signature of the captured image of the physical document.

9. The system of claim 8, the signature(s) corresponding to the one or more generated images that have a threshold number of matches to the corresponding portion of the signature of the captured image of the physical document are retained for further consideration.

10. The system of claim 9, further comprising a component that assigns confidence scores when a threshold number of signatures are being retained for further consideration.

11. The system of claim 2, the signatures corresponding to the one or more generated images and the signature of the captured image of the physical document are generated at least in part upon a location of at least a portion of each word in the generated images and the captured image of the physical document, respectively.

12. The system of claim 11, the signatures corresponding to the one or more generated images and the signature of the captured image of the physical document further generated at least in part upon a width of each word in the captured image and the generated images, respectively.

13. The system of claim 2, further comprising:

a component that generates at least one tree representation related to the generated images and the captured image of the physical document, the at least one tree representation being a hierarchical representation of the generated images and the captured image of the physical document, wherein the at least one tree representation conveys which segments of the generated images and which segments of the captured image of the physical document include a word; and

a comparison component that compares a tree representation related to the generated images with the tree representation related to the captured image of the physical document.

14. The system of claim 1, further comprising a component that reduces noise in the captured image of the physical document.

15. The system of claim 1, further comprising a component that generates a grayscale image of the captured image of the physical document.

16. The system of claim 1, farther comprising a connecting component that connects characters within a word of the generated images and the captured image without connecting words of the generated images and the captured image.

17. The system of claim 16, the generated images and the captured image being binary images, the connecting component performs a pixel dilation of the binary images.

18. The system of claim 17, the connecting component alters resolution of the captured image of the physical document to facilitate connecting characters within a word of the captured image of the physical document without connecting disparate words within the captured image of the physical document.

19. The system of claim 1, further comprising a caching component that automatically generates an image of an electronic document at a time such electronic document is printed.

20. The system of claim 19, further comprising an artificial intelligence component that infers which printed documents should have associated stored images.

21. The system of claim 1, further comprising an artificial intelligence component that excludes a subset of the generated images from the search based at least in part upon one of user state, user context, or user history.

22. The system of claim 1, at least one of the generated images is associated with an entry within a data store, the entry comprising one or more of an image of a page of an electronic document or a signature that identifies the image of the page, the signature based at least in part upon topological properties of words within the image of the page.

23. The system of claim 22, the one or more of the image of the page of the electronic document or the signature that identifies the image of the page associated with one or more of a URL that identifies a location of the electronic document, the electronic document, a hierarchical tree representation of the image of the page of the electronic document, OCR of the image of the page, data relating to a number of times the image of the page has been accessed, customer records, payment information, or workflow information, or a combination thereof.

41. A personal digital assistant comprising the system of claim 1.

24. A method that facilitates indexing and/or retrieval of a document, comprising:

generating a plurality of images of electronic documents, at least one of the images of electronic documents corresponding to a printed document;

capturing an image of a printed document after such document has been printed;

receiving a query requesting retrieval of an electronic document corresponding to the image of the printed document;

generating one or more signatures corresponding to at least a portion of one or more of the generated images, the signatures generated at least in part upon word-layout within the image(s), the one or more signatures is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the generated image is entered into a respective table location for each segment of the generated image;

generating a signature corresponding to at least a portion of the captured image, the signature is generated based at least in part upon word-layout within the captured image, the signature is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the captured image is entered into a respective table location for each segment of the captured image; and

comparing the one or more signatures corresponding to the one or more generated images to the signature corresponding to the captured image; and

identifying a generated image that has a highest number of table locations that have respective values that match values in corresponding table locations associated with the captured image.

25. A method that facilitates indexing and/or retrieval of a document, comprising:

receiving a captured image of at least a portion of a document; and

searching at least one data store for an electronic document corresponding to the captured image, the search performed via comparing topological word properties within the captured image with topological word properties of generated images corresponding to a plurality of electronic documents, the respective topological word properties comprising at least width of each word;

generating signatures corresponding to the generated images, each of the signatures is a hash table that contains a plurality of table locations where a respective value corresponding to a respective portion of a particular generated image is entered into a respective table location for each portion of the particular generated image;

generating a signature corresponding to the captured image of the document, the signature is a hash table that contains a plurality of table locations where a respective value corresponding to a respective portion of the captured image is entered into a respective table location for each portion of the captured image;

comparing a portion of the signatures corresponding to respective generated images to a portion of the signature corresponding to the captured image; and

identifying at least one generated image that has a highest number of table locations that have respective values that match values in corresponding table locations associated with the captured image.

26. The method of claim 25, further comprising:

comparing the signatures corresponding to the generated images with the signature corresponding to the captured image of the document, the signatures associated with the generated images are based at least in part upon location and width of each word within the generated images, and the signature associated with the captured image is based at least in part upon location and width of each word within the captured image.

27. The method of claim 25, further comprising:

partitioning the captured image of the document into a plurality of segments;

partitioning the generated images into segments corresponding to the segments of the captured image of the document; and

comparing the word layout of the captured image of the document with the word layout of the generated images only within corresponding segments of the captured image of the document and the images within the data store(s).

28. The method of claim 27, further comprising:

assigning confidence scores to the signatures corresponding to the generated images based at least in part upon a correspondence between the word layout of the captured image and the word layout of the generated images.

29. The method of claim 25, further comprising:

partitioning the captured image of the document to create a hierarchy of segments;

partitioning the generated images to create a hierarchy of segments corresponding to the hierarchy of segments related to the captured image of the document;

assigning the segments in the captured image of the documents and the segments in the generated images a first value when the segments comprise a word;

assigning the segments in the captured image of the documents and the segments in the generated images a second value when the segments do not comprise a word;

comparing the hierarchy of segments; and

removing one or more generated images from consideration when a segment associated with the one or more generated images assigned the second value and a corresponding segment associated with the captured image of the document is assigned the first value.

30. The method of claim 25, further comprising reducing noise in the captured image of the document prior to searching the data store(s).

31. The method of claim 30, wherein reducing noise comprises one or more of:

providing a filter that removes markings that have a width greater than a threshold width;

providing a filter that removes markings with a width less than a threshold width;

providing a filter that removes markings with a height greater than a threshold height; and

providing a filter that removes marking with a height less than a threshold height.

32. The method of claim 25, further comprising generating a grayscale image of the captured image of the document prior to searching the data store(s).

33. A machine-implemented system for indexing and/or retrieval of a document, comprising:

a processor;

means for generating an image of an electronic document when the electronic document is printed;

means for capturing an image of the document after the document has been printed;

means for generating a signature corresponding with the generated image;

means for generating a signature corresponding to the captured image;

means for storing the electronic document;

means for iteratively comparing location of respective words and width of respective words within a portion of a signature associated with the captured image to the location of respective words and width of respective words within respective portions of signatures associated with the generated images and excluding each generated image whose signature portion does not match the signature portion of the captured image,

the portion of the signature associated with the captured image and the corresponding portions of the signatures respectively associated with the generated images that are compared become progressively smaller with each iteration, where one or more iterations are performed until a predetermined threshold number of generated images remain,

wherein each portion of signature respectively associated with a generated image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the generated image is entered into a respective table location for each segment of the generated image, and

wherein the portion of the signature associated with the captured image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the captured image is entered into a respective table location for each segment of the captured image; and

means for retrieving the electronic document.

34. The system of claim 33, further comprising:

means for generating a signature that includes features that are highly specific to the generated image; and

means for generating a signature corresponding to the captured image, the signature includes features that are highly specific to the captured image.

35. The system of claim 34, further comprising means for comparing the signature corresponding to the generated image with the signature corresponding to the captured image.

36. The system of claim 34, further comprising means for accounting for error that occurs when capturing the image of the printed document.

37. The system of claim 33, further comprising:

means for partitioning the generated image into a plurality of segments;

means for partitioning the captured image into a plurality of segments where each segment corresponds to respective segments associated with the generated image; and

means for comparing a segment of the stored image with a corresponding segment of the captured image.

38. A machine-implemented system that facilitates indexing and/or retrieval of a document, comprising:

a processor;

a query component that receives an image of a printed document;

a caching component that generates and stores an image corresponding to the image of the printed document prior to the query component receiving the image of the printed document; and

a comparison component that determines and retrieves the stored image via comparing location of words and width of words within the stored image to location of words and width of words within the received image of the printed document,

the comparison component iteratively compares a portion of a signature associated with the received image with corresponding portions of signatures respectively associated with the stored images and excludes each stored image whose signature does not match the signature of the received image to facilitate identification of a match to the printed document,

the portion of the signature associated with the received image and the portion of the signatures respectively associated with the stored images that are compared become progressively smaller with each iteration, where one or more iterations are performed until a predetermined threshold number of signatures associated with stored images remain,

wherein location of words and width of words within at least a portion of a stored image is represented as a portion of a signature of the stored image, and location of words and width of words within at least a portion of the received image of the printed document is represented as a portion of a signature of the received image,

wherein each portion of signature respectively associated with a stored image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the stored image is entered into a respective table location for each segment of the stored image, and

wherein the portion of the signature associated with the received image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the received image is entered into a respective table location for each segment of the received image.

39. A computer storage medium having computer executable instructions stored thereon to facilitate document retrieval and/or indexing comprising:

return at least one stored image of an electronic document to a user based at least in part upon topological word properties of at least one captured image corresponding to the electronic document; and

an iterative comparison of a portion of a signature associated with the at least one captured image with corresponding portions of signatures respectively associated with the at least one stored image and excludes each stored image whose signature does not match the signature of the at least one captured image to facilitate identification of a match to the electronic document,

wherein the portion of the signature associated with the at least one captured image and the portion of the signatures respectively associated with the at least one stored image that are compared become progressively smaller with each iteration, where one or more iterations are performed until a predetermined threshold number of signatures associated with the at least one stored image remains, wherein the topological word properties comprise at least width of respective words,

wherein the portion of the signature associated with the at least one captured image is based at least in part on topological word properties of a corresponding portion of the at least one captured image, and the portion of signature associated with the at least one stored image is based at least in part on topological word properties of a corresponding portion of the at least one stored image,

wherein each portion of a signature respectively associated with a stored image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the stored image is entered into a respective table location for each segment of the stored image, and

wherein the portion of the signature associated with the captured image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the captured image is entered into a respective table location for each segment of the captured image.

40. A computer storage medium having a data structure thereon to facilitate document retrieval and/or indexing comprising, the data structure comprising:

a component that receives image(s) of at least a portion of a printed document; and

a search component that facilitates retrieval of an electronic document, the electronic document corresponding to the image(s) associated with the printed document, the retrieval based at least in part upon corresponding word-level topological properties when comparing the image(s) associated with the printed document and generated image(s) of the electronic document, the word-level topological properties comprise at least width of words; and

a comparison component that is associated with the search component and iteratively compares a portion of a signature associated with the received image associated with the printed document with corresponding portions of signatures respectively associated with the generated images and excludes each generated image whose signature does not match the signature of the received image to facilitate location of a match to the printed document,

wherein the portion of the signature associated with the received image and the portion of the signatures respectively associated with the generated images that are compared become progressively smaller with each iteration, where one or more iterations are performed until a predetermined threshold number of signatures associated with generated images remain,

wherein the portion of the signature associated with the received image is based at least in part on word-level topological properties of a corresponding portion of the received image, and portions of signature respectively associated with the generated images is based at least in part on word-level topological properties of corresponding portions of the generated images,

wherein each portion of a signature respectively associated with a generated image is a hash table that contains a plurality of table locations where respective value corresponding to a respective segment of the generated image is entered into a respective table location for each segment of the generated image, and

wherein the portion of the signature associated with the received image is a hash table that contains a plurality of table locations where a respective value corresponding to a respective segment of the received image is entered into a respective table location for each segment of the received image.