Database for mixed media document system

Patent metadata

Field	Value
Publication number	US-9405751-B2
Application number	US-46116406-A
Country	US
Kind code	B2
Filing date	Jul 31, 2006
Priority date	Aug 23, 2005
Publication date	Aug 2, 2016
Grant date	Aug 2, 2016

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.

First claim

What is claimed is:

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 vide

Assignees

• Hull Jonathan J
• Lee Dar-Shyang
• Piersol Kurt W
• Ricoh Co Ltd

Inventors

• Hull Jonathan J
• Lee Dar-Shyang
• Piersol Kurt W

Classifications

• G06F16/434

  using image data, e.g. images, photos, pictures taken by a user · CPC title

• G06F16/41 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F17/3002 Primary

  Physics · mapped topic

• G06F17/30047

  Physics · mapped topic