Information retrieval using invisible junctions and geometric constraints

• US 8,144,921 B2
• Filed: 07/11/2007
• Issued: 03/27/2012
• Est. Priority Date: 07/11/2007
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Hull, Jonathan J., Ke, Qifa
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US11/776,520
• Publication Number:
  US 20090016564A1
• Time in Patent Office: 1,721 Days
• Field of Search: 382/100, 382/103, 382/176, 382/181, 382/190, 382/195, 382/199, 382/209, 382/217, 382/229, 382/276, 382/305, 348/169, 348/E5.024, 704/231, 704/236, 704/E15.001, 706/46, 707/3, 707/5, 707/E17.001, 707/E17.014, 707/E17.019, 707/E17.044, 715/255, 715/849
• US Class Current: 382/100
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

The present invention uses invisible junctions which are a set of local features unique to every page of the electronic document to match the captured image to a part of an electronic document. The present invention includes: an image capture device, a feature extraction and recognition system and database. When an electronic document is printed, the feature extraction and recognition system captures an image of the document page. The features in the captured image are then extracted, indexed and stored in the database. Given a query image, usually a small patch of some document page captured by a low resolution image capture device, the features in the query image are extracted and compared against those stored in the database to identify the query image. The present invention advantageously uses geometric estimation to reduce the query results to a single one or a few candidate matches. In one embodiment, the two separate geometric estimations are used to rank and verify matching candidates.

Claims

1. A computer-implemented method for retrieving an electronic document using invisible junction features, the method comprising:

receiving an image of an input electronic document;

extracting, with a processor, an invisible junction feature descriptor from the image; and

retrieving, with the processor, information for an output electronic document using the invisible junction feature descriptor and a geometric constraint.

2. The method of claim 1, wherein retrieving information for the output electronic document comprises:

identifying a plurality of output electronic documents using the invisible junction feature descriptor;

ranking the plurality of output electronic documents using the geometric constraint; and

selecting information corresponding to an electronic document having a highest rank.

3. The method of claim 2, wherein retrieving information for the output electronic document comprises sorting the plurality of output electronic documents based on a number of feature points in each document.

4. The method of claim 1 wherein the information is one from the group of a document identification, a point in the document, a page in the document, a viewing region in the document, and the output document itself.

5. The method of claim 1, wherein retrieving information for the output electronic document comprises querying a database using the invisible junction feature descriptor and the geometric constraint.

6. The method of claim 1, wherein retrieving information for the output electronic document comprises:

receiving the feature descriptor;

retrieving k nearest neighboring points for a feature of the feature descriptor; and

organizing retrieved points by their corresponding document identification.

7. The method of claim 1, wherein retrieving information for the output electronic document comprises:

sorting a plurality of output electronic documents based on a number of feature points in each document;

removing outliers from the plurality of output electronic documents using an estimated affine transformation to identify inlier electronic documents;

refining the affine transformation using the inliers electronic documents to a projective transformation; and

selecting information for an electronic document using geometric constraints on the projective transformation.

8. The method of claim 7, wherein the estimated affine transformation is a RANdom Sample Consensus (RANSAC) algorithm.

9. The method of claim 1, wherein retrieving information for the output electronic document comprises:

sorting a plurality of output electronic documents based on a number of feature points in each document;

ranking the plurality of output electronic documents using a first geometric constraint to produce a first ranking;

ranking the plurality of output electronic documents using a second geometric constraint to produce a second ranking;

reconciling the first ranking with the second ranking to generate a third ranking; and

selecting information corresponding to an electronic document having a highest rank in the third ranking.

10. The method of claim 9, wherein ranking the plurality of output electronic documents using the first geometric constraint to produce the first ranking occurs at least partially in parallel with the ranking the plurality of output electronic documents using the second geometric constraint to produce the second ranking.

11. The method of claim 9, wherein the ranking the plurality of output electronic documents using the first geometric constraint to produce the first ranking uses feature detection with geometric constraints.

12. The method of claim 9, wherein the ranking the plurality of output electronic documents using the second geometric constraint to produce the second ranking uses a projective transformation with geometric constraints.

13. The method of claim 1, wherein the invisible junction features are feature points, the feature points being junctions of an intrinsic skeleton in a blank space of a text document.

14. A system for retrieving an electronic document using invisible junction features, the system comprising:

a processor;

a feature extraction unit stored on a memory and executable by the processor, the feature extraction unit having an input and an output for producing an invisible junction feature descriptor from an image, the input of the feature extraction unit coupled to receive an input image; and

a feature retrieval unit stored on the memory and executable by the processor, the feature retrieval unit having an input and an output for retrieving information about an output electronic document using the invisible junction feature descriptor and a geometric constraint, the input of the feature retrieval unit coupled to the output of the feature extraction unit, the output of the feature retrieval unit providing the information about the output electronic document.

15. The system of claim 14, further comprising a database storing a plurality of invisible junction feature descriptors and corresponding information about output electronic documents, the input and output of feature retrieval unit coupled to the database.

16. The system of claim 15, wherein the feature retrieval unit queries the database using the invisible junction feature descriptor and the geometric constraint.

17. The system of claim 14, wherein the feature retrieval unit identifies a plurality of output electronic documents using the invisible junction feature descriptor, ranks the plurality of output electronic documents using the geometric constraint, and selects the information corresponding to an electronic document having a highest rank.

18. The system of claim 17, wherein the feature retrieval unit sorts the plurality of output electronic documents based on a number of feature points in each document.

19. The system of claim 14, wherein the information is one from the group of a document identification, a point in the document, a page in the document, a viewing region in the document, and the output document itself.

20. The system of claim 14, wherein the feature retrieval unit retrieves k nearest neighboring points for a feature of the feature descriptor;

and organizes the retrieved points by their corresponding document identification.

21. The system of claim 14, wherein the feature retrieval unit sorts a plurality of output electronic documents based on a number of feature points in each document, ranks the sorted plurality of output electronic documents using geometric constraints, and outputs an electronic document with the highest rank.

22. The system of claim 14, wherein the feature retrieval unit sorts a plurality of output electronic documents based on a number of feature points in each document, removes from the plurality of output electronic documents using an estimated affine transformation to identify inlier electronic documents, refines the affine transformation using the inliers electronic documents to a projective transformation, and selects information for an electronic document using geometric constraints on the projective transformation.

23. The system of claim 22, wherein the estimated affine transformation is a RANdom Sample Consensus (RANSAC) algorithm.

24. The system of claim 14, wherein the feature retrieval unit sorts a plurality of output electronic documents based on a number of feature points in each document, ranks the plurality of output electronic documents using a first geometric constraint to produce a first ranking, ranks the plurality of output electronic documents using a second geometric constraint to produce a second ranking, reconciles the first ranking with the second ranking to generate a third ranking, and selects information corresponding to an electronic document having a highest rank in the third ranking.

25. The method of claim 24, wherein the feature retrieval unit ranks the plurality of output electronic documents using the first geometric constraint to produce the first ranking at least partially in parallel with ranking the plurality of output electronic documents using the second geometric constraint to produce the second ranking.

26. The method of claim 24, wherein the feature retrieval unit uses feature detection with geometric constraints to rank the plurality of output electronic documents using the first geometric constraint to produce the first ranking.

27. The method of claim 24, wherein the feature retrieval unit uses a projective transformation with geometric constraints to rank the plurality of output electronic documents using the second geometric constraint to produce the second ranking.

28. The system of claim 14, wherein the invisible junction features are feature points, the feature points being junctions of an intrinsic skeleton in a blank space of a text document.

29. A computer-program product for retrieving an electronic document using invisible junction features comprising a non-transitory computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

receive an image of an input electronic document;

extract, with a processor, an invisible junction feature descriptor from the image; and

retrieve, with the processor, information for an output electronic document using the invisible junction feature descriptor and a geometric constraint.

30. The computer-program product of claim 29, wherein the invisible junction features are feature points, the feature points being junctions of an intrinsic skeleton in a blank space of a text document.