DATA ORGANIZATION AND ACCESS FOR MIXED MEDIA DOCUMENT SYSTEM

• US 20070047819A1
• Filed: 07/31/2006
• Published: 03/01/2007
• Est. Priority Date: 08/23/2005
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Piersol, Kurt, Lee, Dar-Shyang, Hull, Jonathan
• Granted Patent: US 9,171,202 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18086 by performing operations within image blocks or by using histograms
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

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 computer implemented method for organizing and accessing information in a mixed media document system, comprising:

generating an electronic representation of the paper document;

identifying features on the paper document that capture two-dimensional aspects of the paper document;

identifying locations of the features; and

indexing the features by their respective locations, thereby generating an index table.

2. The method of claim 1 further comprising the preliminary step of receiving the paper document.

3. The method of claim 1 further comprising:

storing one or more characteristics associated with at least one of the features.

4. The method of claim 3 wherein the one or more 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 method of claim 1 wherein identifying features on the paper document that capture two-dimensional aspects includes identifying horizontally aligned and vertically aligned objects.

6. The method of claim 1 wherein identifying features on the paper document that capture two-dimensional aspects includes identifying horizontal and vertical word-pairs.

7. The method of claim 1 wherein generating an electronic representation of the paper document is carried out during a scanning or printing process.

8. The method of claim 1 wherein identifying features on the paper document that capture two-dimensional aspects of the paper document includes grouping sequences of text into logical lines by checking amount of vertical overlap between two consecutive sequences.

9. The method of claim 1 further comprising:

receiving one or more query terms that capture two-dimensional relationships between objects in a target document; and

computing at least one mixed media document and location hypotheses potentially responsive to the query terms, based on data from the index table.

10. The method of claim 9 wherein receiving one or more query terms that capture two-dimensional relationships between objects in a target document is preceded by:

receiving the target document;

creating an image of at least a patch of target document; and

generating the one or more query terms based on the image.

11. The method of claim 10 wherein generating the one or more query terms based on the image includes generating horizontal and vertical word-pairs extracted from the image.

12. The method of claim 11 wherein computing at least one mixed media document and location hypotheses includes:

locating a stored page that most likely matches the patch of the target document; and

calculating a location within that page that is most likely the center of the patch.

13. The method of claim 12 wherein each word-pair is associated with an inverse document frequency, and locating a stored page that most likely matches at least a patch of the target document includes:

adding the inverse document frequency for each word-pair to an accumulator indexed by documents pages on which that word-pair appears; and

in response to a maximum value in that accumulator exceeding a threshold, outputting the corresponding document page as a match to the patch.

14. The method of claim 13 wherein calculating a location within that page that is most likely the center of the patch includes:

adding a weight to each cell in a zone around each word-pair, wherein the weight for each cell is determined by product of the inverse document frequency of that word-pair and a normalized geometric distance between that cell and the center of the zone;

searching a corresponding Accum array of the accumulator for the cell with a maximum value; and

in response to the maximum value exceeding a threshold, reporting coordinates of the cell as the location of the patch.

15. The method of claim 9 wherein computing at least one mixed media document and location hypotheses includes:

looking-up each of the one or more query terms in the index table to retrieve one or more locations associated with each query term; and

for each identified location, identifying one or more candidate regions that contain the location.

16. The method of claim 15 wherein computing at least one mixed media document and location hypotheses includes:

identifying one of the one or more candidate regions that is most consistent with all of the one or more query terms; and

in response to determining that the one of the one or more candidate regions satisfies a pre-defined matching criteria, confirming the region as a match to the target document.

17. A machine-readable medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for organizing and accessing information in a mixed media document system, the process comprising:

generating an electronic representation of the paper document;

identifying features on the paper document that capture two-dimensional aspects of the paper document;

identifying locations of the features; and

indexing the features by their respective locations, thereby generating an index table.

18. The machine-readable medium of claim 17, the process further comprising:

storing one or more characteristics associated with at least one of the features.

19. The machine-readable medium of claim 17 wherein identifying features on the paper document that capture two-dimensional aspects includes identifying horizontal and vertical word-pairs.

20. The machine-readable medium of claim 17, the process further comprising:

receiving one or more query terms that capture two-dimensional relationships between objects in a target document; and

computing at least one mixed media document and location hypotheses potentially responsive to the query terms, based on data from the index table.

21. A computer implemented method for accessing information in a mixed media document system, comprising:

receiving one or more query terms that capture two-dimensional relationships between objects in a target document; and

computing at least one mixed media document and location hypotheses potentially responsive to the query terms, based on data from an index table that indexes document features and feature locations of mixed media documents.

22. The method of claim 21 wherein receiving one or more query terms that capture two-dimensional relationships between objects in a target document is preceded by:

receiving the target document;

creating an image of at least a patch of target document; and

generating the one or more query terms based on the image.

23. The method of claim 22 wherein generating the one or more query terms based on the image includes generating horizontal and vertical word-pairs extracted from the image.

24. The method of claim 23 wherein computing at least one mixed media document and location hypotheses includes:

locating a stored page that most likely matches the patch of the target document; and

calculating a location within that page that is most likely the center of the patch.

25. The method of claim 24 wherein each word-pair is associated with an inverse document frequency, and locating a stored page that most likely matches at least a patch of the target document includes:

adding the inverse document frequency for each word-pair to an accumulator indexed by documents pages on which that word-pair appears; and

in response to a maximum value in that accumulator exceeding a threshold, outputting the corresponding document page as a match to the patch.

26. The method of claim 25 wherein calculating a location within that page that is most likely the center of the patch includes:

adding a weight to each cell in a zone around each word-pair, wherein the weight for each cell is determined by product of the inverse document frequency of that word-pair and a normalized geometric distance between that cell and the center of the zone;

searching a corresponding Accum array of the accumulator for the cell with a maximum value; and

in response to the maximum value exceeding a threshold, reporting coordinates of the cell as the location of the patch.

27. The method of claim 21 wherein computing at least one mixed media document and location hypotheses includes:

looking-up each of the one or more query terms in the index table to retrieve one or more locations associated with each query term; and

for each identified location, identifying one or more candidate regions that contain the location.

28. The method of claim 27 wherein computing at least one mixed media document and location hypotheses includes:

identifying one of the one or more candidate regions that is most consistent with all of the one or more query terms; and

in response to determining that the one of the one or more candidate regions satisfies a pre-defined matching criteria, confirming the region as a match to the target document.

29. A machine-readable medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for accessing information in a mixed media document system, the process comprising:

receiving one or more query terms that capture two-dimensional relationships between objects in a target document; and

computing at least one mixed media document and location hypotheses potentially responsive to the query terms, based on data from an index table that indexes document features and feature locations of mixed media documents.

30. The machine-readable medium of claim 29 wherein receiving one or more query terms that capture two-dimensional relationships between objects in a target document is preceded by:

receiving the target document;

creating an image of at least a patch of target document; and

generating the one or more query terms based on the image.

31. The machine-readable medium of claim 30 wherein generating the one or more query terms based on the image includes generating horizontal and vertical word-pairs extracted from the image.

32. The machine-readable medium of claim 31 wherein computing at least one mixed media document and location hypotheses includes:

locating a stored page that most likely matches the patch of the target document; and

calculating a location within that page that is most likely the center of the patch.

33. The machine-readable medium of claim 32 wherein each word-pair is associated with an inverse document frequency, and locating a stored page that most likely matches at least a patch of the target document includes:

adding the inverse document frequency for each word-pair to an accumulator indexed by documents pages on which that word-pair appears; and

in response to a maximum value in that accumulator exceeding a threshold, outputting the corresponding document page as a match to the patch.

34. The machine-readable medium of claim 33 wherein calculating a location within that page that is most likely the center of the patch includes:

adding a weight to each cell in a zone around each word-pair, wherein the weight for each cell is determined by product of the inverse document frequency of that word-pair and a normalized geometric distance between that cell and the center of the zone;

searching a corresponding Accum array of the accumulator for the cell with a maximum value; and

in response to the maximum value exceeding a threshold, reporting coordinates of the cell as the location of the patch.

35. The machine-readable medium of claim 29 wherein computing at least one mixed media document and location hypotheses includes:

looking-up each of the one or more query terms in the index table to retrieve one or more locations associated with each query term;

for each identified location, identifying one or more candidate regions that contain the location;

identifying one of the one or more candidate regions that is most consistent with all of the one or more query terms; and

in response to determining that the one of the one or more candidate regions satisfies a pre-defined matching criteria, confirming the region as a match to the target document.