Database for mixed media document system

• US 9,405,751 B2
• Filed: 07/31/2006
• Issued: 08/02/2016
• Est. Priority Date: 08/23/2005
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Hull, Jonathan J., Lee, Dar-Shyang, Piersol, Kurt W.
• Primary Examiner(s): PENG, HUAWEN A
• Application Number:
  US11/461,164
• Publication Number:
  US 20070050411A1
• Time in Patent Office: 3,655 Days
• Field of Search: 707 1- 10, 707/101, 707/705, 707/708, 382/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user

Abstract

A Mixed Media Reality (MMR) system and associated techniques are disclosed. The MMR system provides mechanisms for forming a mixed media document that includes media of at least two types (e.g., printed paper as a first medium and digital content and/or web link as a second medium). In one particular embodiment, the MMR system includes a content-based retrieval database configured with an index table to represent two-dimensional geometric relationships between objects extracted from a printed document in a way that allows look-up using a text-based index. A ranked set of document, page and location hypotheses can be computed given data from the index table. The techniques effectively transform features detected in an image patch into textual terms (or other searchable features) that represent both the features themselves and the geometric relationship between them. A storage facility can be used to store additional characteristics about each document image patch.

Claims

1. A database system for providing mixed media documents, comprising:

one or more processors;

an index table, stored on a memory and accessible by the one or more processors, that stores electronic descriptions of features extracted from paper documents, wherein the features include word bounding boxes, feature location information for the features, and association information for each of the paper documents and locations with a mixed media document that combines printed and digital media;

a feature extraction module, stored on the memory and executable by the one or more processors to;

receive an image patch;

determine word bounding boxes from the image patch by aligning the image patch with a horizontal axis, detecting text lines in the image patch based on the aligned image patch, locating an area within each text line that is above a threshold as a word, and identifying the bounding boxes for words within the text lines;

generate a query from the image patch, at least one query term of the query comprising a two-dimensional geometric relationship between the word bounding boxes determined from the image patch, the two-dimensional geometric relationship specifying one or more of a direction, an angle, a distance between the word bounding boxes determined from the image patch, and geometric shape and contour of the word bounding boxes; and

an accumulator module, stored on the memory and executable by the one or more processors to;

locate at least one mixed media document that contains the word bounding boxes determined from the image patch; and

determine that the at least one mixed media document is a potential match to the query based on determining a two-dimensional geometric relationship between the features stored in the index table, comparing the two-dimensional geometric relationship between the word bounding boxes determined from the image patch with the two-dimensional geometric relationship between the features stored in the index table, computing a matching score for the at least one mixed media document, and returning the at least one mixed media document as a match to the query if the matching score is above a threshold.

2. The system of claim 1 further comprising:

a storage facility for storing additional characteristics associated with the image patch.

3. The system of claim 2 wherein the storage facility is a relational database.

4. The system of claim 2 wherein the additional characteristics include one or more actions including at least one of retrieval of textual information, retrieval of graphical information, executing a process, executing a command, placing an order, retrieving a video, retrieving a sound, storing information, creating a new document, printing a document, and displaying a document.

5. The system of claim 1 wherein the index table is capable of receiving the electronic descriptions of features extracted from the paper documents.

6. The system of claim 1 wherein each of the paper documents includes multiple pages, and the index table is further configured for associating the paper documents, the multiple pages, and x-y feature locations within the multiple pages with one or more mixed media documents.

7. The system of claim 1 wherein locating the at least one mixed media document and determining that the at least one mixed media document is a potential match to the query carried out by the accumulator module include computing a ranked set of the mixed media documents, pages, and location hypotheses based on data from the index table.

8. The system of claim 1 wherein the at least one query term of the query further comprises one or more word pairs associated with word separators, and wherein the word separators indicate that a word pair is horizontally adjacent using a dash and vertically adjacent using a plus sign.

9. The system of claim 1 wherein the index table comprises:

an inverted term index table, where each unique term in the inverted term index table points to a list of records, and each record identifies a candidate region on a page within the mixed media document.

10. The system of claim 9 wherein to locate the at least one mixed media document and determine that the at least one mixed media document is a potential match to the query, the accumulator module examines every record indexed by a key corresponding to terms of the query, and identifies a region that is most consistent with all the terms of the query.

11. The system of claim 10 wherein the two-dimensional geometric relationship includes a geometric shape and contour of a bounding box.

12. The system of claim 9 wherein the index table further comprises:

a document index table that includes relevant information for each mixed media document, the relevant information including at least one of a print resolution, a print date, a paper size, a shadow file name, and a page image location.

13. The system of claim 1 wherein the electronic descriptions are computed by the feature extraction module that associates the extracted features with inner-document location data of the features.

14. The system of claim 10 wherein the key is an output of a hash function of the terms in the query.

15. A computer-implemented method for providing mixed media documents, comprising:

storing, with one or more processors, at an index table, electronic descriptions of features extracted from paper documents and feature location information for the features, wherein the features include word bounding boxes, the index table associating each of the paper documents and locations with a mixed media document that combines printed and digital media;

receiving an image patch;

determining word bounding boxes from the image patch by aligning the image patch with a horizontal axis, detecting text lines in the image patch based on the aligned image patch, locating an area within each text line that is above a threshold as a word, and identifying the bounding boxes for words within the text lines;

generating, with the one or more processors, a query from the image patch, at least one query term of the query comprising a two-dimensional geometric relationship between the word bounding boxes determined from the image patch, the two-dimensional geometric relationship specifying one or more of a direction, an angle, a distance between the word bounding boxes determined from the image patch, and geometric shape and contour of the word bounding boxes;

locating, with the one or more processors, at least one mixed media document that contains the word bounding boxes determined from the image patch; and

determining that the at least one mixed media document is a potential match to the query based on determining a two-dimensional geometric relationship between the features stored in the index table, comparing the two-dimensional geometric relationship between the word bounding boxes determined from the image patch with the two-dimensional geometric relationship between the features stored in the index table, computing a matching score for the at least one mixed media document, and returning the at least one mixed media document as a match to the query if the matching score is above a threshold.

16. The method of claim 15 further comprising:

storing additional characteristics associated with the image patch.

17. The method of claim 16 wherein the additional characteristics include one or more actions including at least one of retrieval of textual information, retrieval of graphical information, executing a process, executing a command, placing an order, retrieving a video, retrieving a sound, storing information, creating a new document, printing a document, and displaying a document.

18. The method of claim 15 wherein storing, at the index table, the electronic descriptions of features extracted from the paper documents, includes:

receiving the electronic descriptions of features extracted from the paper documents.

19. The method of claim 15 wherein locating the at least one mixed media document and determining that the at least one mixed media document is a potential match to the query include:

computing a ranked set of the mixed media documents, pages, and location hypotheses based on data from the index table.

20. The method of claim 15 wherein the at least one query term of the query further comprises one or more word pairs associated with word separators, and wherein the word separators indicate that a word pair is horizontally adjacent using a dash and vertically adjacent using a plus sign.

21. The method of claim 15 wherein the index table comprises an inverted term index table, where each unique term in the inverted term index table points to a list of records, and each record identifies a candidate region on a page within the mixed media document, and wherein locating the at least one mixed media document and determining that the at least one mixed media document is a potential match to the query include:

examining every record indexed by a key corresponding to terms of the query; and

identifying a region that is most consistent with all the terms of the query.

22. The method of claim 21 wherein the two-dimensional geometric relationship includes a geometric shape and contour of a bounding box.

23. The method of claim 21 wherein the key is an output of a hash function of the terms in the query.

24. A non-transitory machine-readable medium encoded with instructions, that when executed by one or more processors, cause the one or more processors to carry out a process for providing mixed media documents, the process comprising:

storing, at an index table, electronic descriptions of features extracted from paper documents and feature location information for the features, wherein the features include word bounding boxes, the index table associating each of the paper documents and locations with a mixed media document that combines printed and digital media;

receiving an image patch;

determining word bounding boxes from the image patch by aligning the image patch with a horizontal axis, detecting text lines in the image patch based on the aligned image patch, locating an area within each text line that is above a threshold as a word, and identifying the bounding boxes for words within the text lines;

generating a query from the image patch, at least one query term of the query comprising a two-dimensional geometric relationship between the word bounding boxes determined from the image patch, the two-dimensional geometric relationship specifying one or more of a direction, an angle, a distance between the word bounding boxes determined from the image patch, and geometric shape and contour of the word bounding boxes;

locating at least one mixed media document that contains the word bounding boxes determined from the image patch; and

determining that the at least one mixed media document is a potential match to the query based on determining a two-dimensional geometric relationship between the features stored in the index table, comparing the two-dimensional geometric relationship between the word bounding boxes determined from the image patch with the two-dimensional geometric relationship between the features stored in the index table, computing a matching score for the at least one mixed media document, and returning the at least one mixed media document as a match to the query if the matching score is above a threshold.

25. The machine-readable medium of claim 24, the process further comprising:

storing additional characteristics associated with the image patch, the additional characteristics including one or more actions including at least one of retrieval of textual information, retrieval of graphical information, executing a procedure, executing a command, placing an order, retrieving a video, retrieving a sound, storing information, creating a new document, printing a document, and displaying a document.

26. The machine-readable medium of claim 24 wherein locating the at least one mixed media document and determining that the at least one mixed media document is a potential match to the query include:

computing a ranked set of the mixed media documents, pages, and location hypotheses based on data from the index table.

27. The machine-readable medium of claim 24 wherein the at least one query term of the query further comprises one or more word pairs associated with word separators, and wherein the word separators indicate that a word pair is horizontally adjacent using a dash and vertically adjacent using a plus sign.

28. The machine-readable medium of claim 24 wherein the index table comprises an inverted term index table, where each unique term in the inverted term index table points to a list of records, and each record identifies a candidate region on a page within the mixed media document, and wherein locating the at least one mixed media document and determining that the at least one mixed media document is a potential match to the query include:

examining every record indexed by a key corresponding to terms of the query; and

identifying a region that is most consistent with all the terms of the query.

29. The machine-readable medium of claim 28 wherein the two-dimensional geometric relationship includes a geometric shape and contour of a bounding box.

30. The machine-readable medium of claim 28 wherein the key is an output of a hash function of the terms in the query.