Retrieving electronic documents by converting them to synthetic text

• US 8,478,761 B2
• Filed: 03/08/2012
• Issued: 07/02/2013
• Est. Priority Date: 07/12/2007
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Moraleda, Jorge
• Primary Examiner(s): TRAN, ANHTAI V
• Application Number:
  US13/415,228
• Publication Number:
  US 20120173504A1
• Time in Patent Office: 481 Days
• Field of Search: None
• US Class Current: 707/743
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18171 Syntactic representation, e.g. using a grammatical approach
• 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: G06V 30/418 Document matching, e.g. of document images

Abstract

The present invention relies on the two-dimensional information in documents and encodes two-dimensional structures into a one-dimensional synthetic language such that two-dimensional documents can be searched at text search speed. The system comprises: an indexing module, a retrieval module, an encoder, a quantization module, a retrieval engine and a control module coupled by a bus. Electronic documents are first indexed by the indexing module and stored as a synthetic text library. The retrieval module then converts an input image to synthetic text and searches for matches to the synthetic text in the synthetic text library. The matches can be in turn used to retrieve the corresponding electronic documents. In one or more embodiments, the present invention includes a method for comparing the synthetic text to documents that have been converted to synthetic text for a match.

Claims

1. A method for retrieving an electronic document in response to receipt of an image patch, the method comprising:

receiving the image patch;

identifying a first two-dimensional structure in the image patch;

identifying a second two-dimensional structure in the image patch;

identifying a third two-dimensional structure in the image patch;

generating a first text string that encodes the first two-dimensional structure into a first one-dimensional structure by specifying a location of the first two-dimensional structure, a first quantized angle measured between a line originating from the first two-dimensional structure and a path joining a center of the first two-dimensional structure to a center of the second two-dimensional structure and a second quantized angle defining a path joining a center of the second two-dimensional structure to a center of the third two-dimensional structure;

searching, from a library, for a second one-dimensional structure that is similar to the first one-dimensional structure of the image patch; and

retrieving the electronic document corresponding to the second one-dimensional structure similar to the first one-dimensional structure of the image patch from a document storage.

2. The method of claim 1, further comprising determining the first and the second quantized angles using a plurality of quantization levels.

3. The method of claim 1, wherein the first, the second and the third two-dimensional structures in the image patch each include a bounding box for words.

4. The method of claim 1, wherein the first, the second and the third two-dimensional structures in the image patch include a Scale Invariant Feature Transform (SIFT) feature in the image patch.

5. The method of claim 1, further comprising:

encoding a plurality of electronic documents to corresponding one-dimensional structures; and

storing the plurality of electronic documents, the one-dimensional structures and associations between the plurality of electronic documents and the corresponding one-dimensional structures in the document storage.

6. The method of claim 1, wherein the first and the second one-dimensional structures include text, and the searching is performed by a conventional search engine.

7. The method of claim 1, wherein retrieving further comprises:

retrieving a plurality of electronic documents from the document storage;

determining a rank order based at least in part on a similarity between the second one-dimensional structure in each of the plurality of electronic documents and the first one-dimensional structure of the image patch; and

presenting the plurality of electronic documents in the rank order.

8. A system for retrieving an electronic document in response to receipt of an image patch, the system comprising:

a processor;

an indexing module stored on a memory and executable by the processor, the indexing module receiving the image patch, identifying a first two-dimensional structure in the image patch, identifying a second two-dimensional structure in the image patch and identifying a third two-dimensional structure in the image patch;

an encoder coupled to the indexing module, the encoder generating a first text string that encodes the first two-dimensional structure into a first one-dimensional structure by specifying a location of the first two-dimensional structure, a first quantized angle measured between a line originating from the first two-dimensional structure and a path joining a center of the first two-dimensional structure to a center of the second two-dimensional structure and a second quantized angle defining a path joining a center of the second two-dimensional structure to a center of the third two-dimensional structure;

a retrieval engine coupled to the indexing module, the retrieval engine searching, from a library, for a second one-dimensional structure that is similar to the first one-dimensional structure of the image patch; and

a retrieval module coupled to the indexing module, the retrieval module retrieving the electronic document corresponding to the second one-dimensional structure similar to the first one-dimensional structure of the image patch from a document storage.

9. The system of claim 8, further comprising a quantization module coupled to the encoder, the quantization module determining the first and the second quantized angles using a plurality of quantization levels.

10. The system of claim 8, wherein the first, the second and the third two-dimensional structures in the image patch each include a bounding box for words.

11. The system of claim 8, wherein the first, the second and the third two-dimensional structures in the image patch include a Scale Invariant Feature Transform (SIFT) feature in the image patch.

12. The system of claim 8, further comprising the indexing module:

encoding a plurality of electronic documents to corresponding one-dimensional structures; and

storing the plurality of electronic documents, the one-dimensional structures and associations between the plurality of electronic documents and the corresponding one-dimensional structures in the document storage.

13. The system of claim 8, wherein the first and the second one-dimensional structures include text, and the searching is performed by a conventional search engine.

14. The system of claim 8, wherein the retrieval module retrieving the electronic document further comprises:

retrieving a plurality of electronic documents from the document storage;

determining a rank order based at least in part on a similarity between the second one-dimensional structure in each of the plurality of electronic documents and the first one-dimensional structure of the image patch; and

presenting the plurality of electronic documents in the rank order.

15. A computer program product for retrieving an electronic document in response to receipt of an image patch comprising a non-transitory computer usable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

receive the image patch;

identify a first two-dimensional structure in the image patch;

identify a second two-dimensional structure in the image patch;

identify a third two-dimensional structure in the image patch;

generate a first text string that encodes the first two-dimensional structure into a first one-dimensional structure by specifying a location of the first two-dimensional structure, a first quantized angle measured between a line originating from the first two-dimensional structure and a path joining a center of the first two-dimensional structure to a center of the second two-dimensional structure and a second quantized angle defining a path joining a center of the second two-dimensional structure to a center of the third two-dimensional structure;

search, from a library, for a second one-dimensional structure that is similar to the first one-dimensional structure of the image patch; and

retrieve the electronic document corresponding to the second one-dimensional structure similar to the first one-dimensional structure of the image patch from a document storage.

16. The computer program product of claim 15, wherein the computer readable program when executed on the computer further causes the computer to determine the first and the second quantized angles using a plurality of quantization levels.

17. The computer program product of claim 15, wherein the first, the second and the third two-dimensional structures in the image patch each include a bounding box for words.

18. The computer program product of claim 15, wherein the first, the second and the third two-dimensional structures in the image patch include a Scale Invariant Feature Transform (SIFT) feature in the image patch.

19. The computer program product of claim 15, wherein the computer readable program when executed on the computer further causes the computer to:

encode a plurality of electronic documents to corresponding one-dimensional structures; and

store the plurality of electronic documents, the one-dimensional structures and associations between the plurality of electronic documents and the corresponding one-dimensional structures in the document storage.

20. The computer program product of claim 15, wherein the computer readable program when executed on the computer further causes the computer to retrieve the electronic document by:

retrieving a plurality of electronic documents from the document storage;

determining a rank order based at least in part on a similarity between the second one-dimensional structure in each of the plurality of electronic documents and the first one-dimensional structure of the image patch; and

presenting the plurality of electronic documents in the rank order.