Mixed media reality brokerage network with layout-independent recognition

• US 7,769,772 B2
• Filed: 07/08/2009
• Issued: 08/03/2010
• Est. Priority Date: 08/23/2005
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Nudd, Geoffrey H., Hart, Peter E., Hull, Jonathan J., Weyl, Stephen A.
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US12/499,574
• Publication Number:
  US 20090313245A1
• Time in Patent Office: 391 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 382/154, 382/190, 382/305, 348/211.2, 709/217
• US Class Current: 707/765
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18133 regional/local feature not essentially salient, e.g. local binary pattern
• 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: H04N 2201/3249 data relating to a linked page or object, e.g. hyperlink
• CPC Class Codes: H04N 2201/3264 of sound signals
• CPC Class Codes: H04N 2201/3267 of motion picture signals, e.g. video clip
• CPC Class Codes: H04N 2201/3269 of machine readable codes or marks, e.g. bar codes or glyphs
• CPC Class Codes: H04N 2201/3271 Printing or stamping

Abstract

A Mixed Media Reality (MMR) system 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 as a second medium. The MMR system of the present invention provides mechanisms for forming a mixed media document that includes media of at least two types, such as printed paper as a first medium and a digital photograph, digital movie, digital audio file, or web link as a second medium. The present invention also includes a number of novel methods including: a method for layout independent MMR recognition, a strip fragment candidate generation process, and a page candidate accumulation process.

Claims

1. A computer-implemented method for layout independent recognition of an input document, the method comprising:

receiving an electronic document as the input document;

rendering the electronic document using a layout process to produce a layout independent document with a layout defined by the layout process;

extracting an image patch from the layout independent document;

segmenting the image patch into an input text strip; and

locating from a plurality of stored pages a page with a matching text strip that matches the input text strip to produce a candidate page corresponding to the electronic document.

2. The method of claim 1, further comprising performing a layout independent mixed media reality action.

3. The method of claim 2, further wherein the layout independent mixed media reality action is one from the group of:

performing patch detection, performing patch modification, regenerating a database document, and re-rendering a document using an electronic document from a database.

4. The method of claim 1, further comprising:

locating pages each having a matching text strip that matches the input text strip to produce candidate pages; and

ranking the candidate pages according to an amount of similarity to the text strips.

5. The method of claim 4, wherein locating pages uses a strip fragment candidate generation process to produce a set of strip candidates, each defined by a document ID, a page ID, and bounding boxes of strips as they occur in database documents.

6. The method of claim 4, wherein locating pages comprises:

performing feature extraction;

performing a database look up for matching features; and

adding matching documents to the candidate set.

7. The method of claim 4, wherein locating pages includes determining document-pages in a database that could have generated the input image using a vertical context to limit the page candidates.

8. The method of claim 4, wherein locating pages comprises:

determining matching document pages from a database;

modifying a feature extraction score of each matching page;

sorting the matching document pages from highest score to lowest score;

calculating a percentage of the image patch found in the matching page; and

outputting the matching document pages sorted by percentage.

9. The method of claim 8, wherein modifying is based at least in part on a term frequency-inverse document frequency measure.

10. The method of claim 8, further comprising estimating a length of each line of text by comparing a linear position of a beginning of each character string in the database document and calculating a gap between strips of text with a difference between a first character and a last character in the previous strip.

11. The method of claim 8, further comprising estimating the column width from which the image patch was extracted.

12. The method of claim 4, further comprising grading candidate pages to determine the pre-specified patches that match the image patch.

13. The method of claim 12, wherein grading candidate pages includes assigning a score proportional to the amount of a patch covered by the text in the image patch.

14. The method of claim 1, wherein performing further comprising estimating characteristics of text within the extracted image patch.

15. The method of claim 1, wherein segmenting the image patch produces an ordered set of text strips, one per line of text.

16. A computer-readable storage medium containing computer program instructions for layout independent recognition of an input document, the computer program instructions performing the steps of:

receiving an electronic document as the input document;

rendering the electronic document using a layout process to produce a layout independent document with a layout defined by the layout process;

extracting an image patch from the layout independent document;

segmenting the image patch into an input text strip; and

locating from a plurality of stored pages a page with a matching text strip that matches the input text strip to produce a candidate page corresponding to the electronic document.

17. The computer-readable storage medium of claim 16, further comprising:

locating pages each having a matching text strip that matches the input text strip to produce candidate pages; and

ranking the candidate pages according to an amount of similarity to the text strips.

18. The computer-readable storage medium of claim 17, wherein locating pages comprises:

performing feature extraction;

performing a database look up for matching features; and

adding matching documents to the candidate set.

19. A system for layout independent recognition of an input document, the system comprising:

a processor;

means for receiving an electronic document as the input document;

means for rendering the electronic document using a layout process to produce a layout independent document with a layout defined by the layout process;

means for extracting an image patch from the layout independent document;

means for segmenting the image patch into an input text strip; and

means for locating from a plurality of stored pages a page with a matching text strip that matches the input text strip to produce a candidate page corresponding to the electronic document.

20. The system of claim 19, further comprising:

means for locating pages each having a matching text strip that matches the input text strip to produce candidate pages; and

means for ranking the candidate pages according to an amount of similarity to the text strips.