Mixed media reality indexing and retrieval for repeated content

• US 8,385,660 B2
• Filed: 06/24/2009
• Issued: 02/26/2013
• Est. Priority Date: 06/24/2009
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Moraleda, Jorge, Hull, Jonathan J., Piersol, Kurt W.
• Primary Examiner(s): STREGE, JOHN B
• Application Number:
  US12/491,018
• Publication Number:
  US 20100329574A1
• Time in Patent Office: 1,343 Days
• Field of Search: 382/209, 382/218, 382/224, 382/226
• US Class Current: 382/224
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

A system and method for indexing and retrieval of document images in an MMR system having repeated content is described. The system provides one or more hierarchical shared content indices that produce faster and/or more accurate search results. The system is also advantageous because the number and configuration of the hierarchical shared content indices is automated, scalable and efficient for processing documents with partially repeated content. In particular, the MMR matching unit includes a hierarchical shared content index (HSCI) and associated methods of use for processing images where the MMR system includes repeated content. The present invention also includes a number of novel methods including a method for adding an image to a hierarchical shared content index; a method for deleting an image from the hierarchical shared content index, and a method for using the hierarchical shared content index for image recognition, as well as a method for combining multiple MMR indexes into a hierarchical MMR index.

Claims

1. An apparatus for use in recognizing documents from an image patch, the apparatus comprising:

an image recognition unit having an input and an output, the input of the image recognition unit coupled to receive the image patch, the image recognition unit extracting features from the image patch;

a hierarchical mixed media reality (MMR) index coupled to and communicating with the image recognition unit, the hierarchical MMR index being a tree with a first set of nodes, wherein each node is a flat MMR index, the hierarchical MMR index used to determine document corresponding to the extracted features from a database of documents; and

a hierarchical shared content index coupled to the image recognition unit, the hierarchical shared content index having a hierarchical description of document pages, the hierarchical shared content index used to produce matching documents from the database of documents by traversing the hierarchical shared content index.

2. The apparatus of claim 1, wherein the hierarchical description of document pages includes at least one document page having a first part that is shared among a plurality of document pages and a second part that is unique to the at least one document page.

3. The apparatus of claim 2, wherein the at least one document page in the hierarchical description of document pages contains no shared parts.

4. The apparatus of claim 1, wherein the hierarchical shared content index is a part of a master index table.

5. The apparatus of claim 1, wherein the hierarchical shared content index comprises:

a hierarchical index having a second set of nodes associated by a plurality of edges; and

one or more entire document pages.

6. The apparatus of claim 5, wherein each of the second set of nodes includes a representation of shared content and the plurality of edges include positional information of a parent shared content in a child image.

7. The apparatus of claim 1, wherein the hierarchical shared content index is a directed acyclic graph in which leaf nodes represent actual pages that are indexed while internal nodes represent shared content.

8. A computer implemented method for recognizing documents from an image patch, the method comprising:

receiving, with one or more processors, the image patch;

determining, with the one or more processors, one or more features of the image patch;

determining, with the one or more processors, the document from a database of documents corresponding to the one or more features;

determining, with the one or more processors, an internal node in a hierarchical index corresponding to the document, the hierarchical index being a directed acyclic graph in which leaf nodes represent actual document pages that are indexed while internal nodes represent shared content among the actual document pages; and

producing, with the one or more processors, one or more matching documents from the database of documents by traversing the hierarchical index.

9. The method of claim 8 wherein the hierarchical index is one from the group of a hierarchical shared content index and a hierarchical mixed media reality (MMR) index.

10. The method of claim 8 wherein determining the document further comprises determining the document using a hierarchical mixed media reality (MMR) index, the hierarchical MMR index being a tree with a plurality of nodes, wherein each node is a flat MMR index.

11. The method of claim 8 further comprising receiving a fraction of the one or more features of the image patch, and using the the fraction of the one or more features of the image patch in producing the one or more matching documents.

12. The method of claim 8 further comprising determining a best match document from the one or more matching documents.

13. The method of claim 8 further comprising comparing the one or more features of the image patch to the hierarchical index and using the comparison in determining the internal node.

14. A computer program product comprising a computer usable medium including a non-transitory computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

receive an image patch;

determine one or more features of the image patch;

determine a document from a database of documents corresponding to the one or more features;

determine an internal node in a hierarchical index corresponding to the document, the hierarchical index being a directed acyclic graph in which leaf nodes represent actual document pages that are indexed while internal nodes represent shared content among the actual document pages; and

produce one or more matching documents from the database of documents by traversing the hierarchical index.

15. The computer program product of claim 14 wherein the hierarchical index is one from the group of a hierarchical shared content index and a hierarchical mixed media reality (MMR) index.

16. The computer program product of claim 14 wherein determining the document further comprises determining the document using a hierarchical mixed media reality (MMR) index, the hierarchical MMR index being a tree with a plurality of nodes, wherein each node is a flat MMR index.

17. The computer program product of claim 14 wherein the computer readable program when executed on the computer further causes the computer to compare the one or more features of the image patch to the hierarchical index and use the comparison in determining the internal node.

18. The computer program product of claim 14 wherein the computer readable program when executed on the computer further causes the computer to receive a fraction of the one or more features of the image patch and use the fraction of the one or more features of the image patch in producing the one or more matching documents.

19. The computer program product of claim 14 wherein the computer readable program when executed on the computer further causes the computer to determine a best match document from the one or more matching documents.

20. The computer program product of claim 14 wherein producing the one or more matching documents further comprises determining a set of internal nodes in the hierarchical index such that descendants of the set of internal nodes match the image patch.