Retrieving Electronic Documents by Converting Them to Synthetic Text

• US 20090018990A1
• Filed: 07/12/2007
• Published: 01/15/2009
• Est. Priority Date: 07/12/2007
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Moraleda, Jorge
• Granted Patent: US 8,176,054 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. A number of electronic documents are first indexed by the indexing module and stored as a synthetic text library. The retrieval module then converts and 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. It should be noted that a plurality of matches and corresponding electronic documents may be retrieves ranked by order according the similarity of the synthetic text. In one or more embodiments, the present invention includes a method for indexing documents by converting them to synthetic text, and a method for retrieving documents by converting an image to synthetic text and comparing the synthetic text to documents that have been converted to synthetic text for a match.

Claims

1. A system for converting documents to synthetic text, the system comprising:

an indexing module for receiving an electronic document and generating a synthetic representation of the electronic document, the indexing module also producing an association between the electronic document and the synthetic representation; and

a data storage for storing the electronic document, the synthetic representation of the electronic document, and an association between the electronic document, a page of the electronic document and the synthetic representation

2. The system of claim 1 wherein the synthetic text is plain text.

3. The system of claim 1 wherein the indexing module provides a full true mapping of the electronic document to plain text.

4. The system of claim 1 wherein the synthetic text representation of the document alone is sufficient to perform retrieval of a corresponding electronic document.

5. The system of claim 1 wherein the synthetic text does not represent any natural language content of the electronic document.

6. The system of claim 1 wherein the synthetic text is in a one dimensional synthetic language encoded from the two-dimensional structures of the electronic document.

7. The system of claim 1 wherein the indexing module also associates the document, the page and a location within the page for the synthetic representation.

8. The system of claim 1 further comprising a retrieval module for retrieving one or more original electronic documents corresponding to a string of synthetic text, the retrieval module adapted for communication with the data storage and the indexing module.

9. The system of claim 8 wherein the retrieval module receives an image patch and generates the string of synthetic text from the image patch.

10. The system of claim 8 further comprising a retrieval engine for searching for the string of synthetic text in the data storage, the retrieval engine being a conventional search engine.

11. The system of claim 8, wherein the retrieval module retrieves and presents an ordered list of the electronic documents most likely to match the input image.

12. The system of claim 1, further comprising a graph encoder for converting an electronic document to synthetic text by converting scripts in the electronic document to a sequence of quantized feature vectors.

13. The system of claim 1, further comprising a quantization module to adjust and optimize the encoding by modifying the quantization parameters used in encoding.

14. The system of claim 1, further comprising a graph encoder for converting an electronic document to synthetic text by encoding a geometry of neighboring bounding boxes into a word of synthetic text that identifies a particular document and a location with the particular document.

15. The system of claim 1, further comprising a SIFT encoder for generating synthetic text from the Scale Invariant Feature Transformation features of the electronic document.

16. A method for generating synthetic text for an electronic document, the method comprising:

receiving an electronic document;

defining a two-dimensional structure for encoding;

identifying a plurality of two-dimensional structure in the electronic document; and

encoding at least one of the plurality of two-dimensional structures in the electronic document to create a one-dimensional structure.

17. The method of claim 16, wherein the two-dimensional structure is a bounding box for a word in the electronic document.

18. The method of claim 16, wherein the two-dimensional structure is a Scale Invariant Feature Transformation feature for the electronic document.

19. The method of claim 16, further comprising the step of storing the one-dimensional structure, the electronic document and an association between the one-dimensional structure and the electronic document in a database.

20. The method of claim 19, wherein the associate includes a document identification, a document page and a location within a page.

21. The method of claim 16, wherein the identifying and encoding are performed for every two-dimensional structure in the electronic document.

22. The method of claim 16, further comprising receiving a second electronic document and performing the steps of identifying and encoding for the second electronic document.

23. The method of claim 16, wherein encoding at least one of the plurality of two-dimensional structures includes performing graph encoding for each bounding box in the electronic document.

24. The method of claim 16, wherein encoding at least one of the plurality of two-dimensional structures includes performing SIFT encoding for each SIFT features in the electronic document.

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

receiving an image patch;

defining a two-dimensional structure in the image patch;

encoding at least one two-dimensional structure of the image patch into a one-dimensional structure;

searching for any one-dimensional structure similar to the one two-dimensional structure of the image patch; and

retrieving a electronic document corresponding to the one-dimensional structure similar to the one two-dimensional structure of the image patch.

26. The method of claim 25, further comprising identifying a plurality of two-dimensional structures in the image patch.

27. The method of claim 25, wherein the two-dimensional structures in the image patch is a bounding box for words.

28. The method of claim 25, wherein the two-dimensional structures in the image patch is a SIFT features in the image patch.

29. The method of claim 25, further comprising encoding a plurality of original documents to corresponding one-dimensional structures.

30. The method of claim 25, wherein the one-dimensional structure is text, and the searching is performed by a conventional search engine.

31. The method of claim 25, wherein retrieving includes retrieving a plurality of electronic documents and presenting the plurality of electronic documents in rank order according to a similarity between the one-dimensional structure for the electronic documents and the one two-dimensional structure of the image patch.

32. A method for obtaining features of text documents, the method comprising:

defining a plurality of bounding boxes around features of a text document;

creating a graph between the plurality of bounding boxes; and

generating a feature vector representing the bounding box.

33. The method of claim 32 wherein one feature vector is generated for each bounding box.

34. The method of claim 32 wherein the graph is one from the group of a spiral path and a snake path.

35. The method of claim 32 wherein generating the feature vector is performed by encoding a parameter of the graph.

36. The method of claim 35 wherein the parameter is one from the group of:

an angle between segments;

relative lengths of two words joined by a segment; and

an aspect ratio of bounding boxes.

37. The method of claim 32 wherein one graph is created for each of the plurality of bounding boxes.