Invisible Junction Features for Patch Recognition

• US 20090016604A1
• Filed: 07/11/2007
• Published: 01/15/2009
• 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
• Granted Patent: US 8,086,038 B2
• Time in Patent Office: Days
• US Class Current: 382/176
• 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 also includes methods for feature extraction, feature indexing, feature retrieval and geometric estimation.

Claims

1. A method for generating an invisible junction, the method comprising:

receiving an image of an electronic document;

determining an invisible junction from the image; and

creating a feature descriptor for the invisible junction.

2. The method of claim 1 wherein:

determining is performed for a plurality of the invisible junctions; and

creating produces a plurality of feature descriptions.

3. The method of claim 1 wherein:

determining the invisible junction from the image includes determining a junction location; and

the feature descriptor includes the junction location.

4. The method of claim 1 wherein:

determining the invisible junction from the image includes determining a junction size; and

the feature descriptor includes the junction size.

5. The method of claim 1 wherein:

determining the invisible junction from the image includes determining a junction orientation; and

the feature descriptor includes the junction orientation.

6. The method of claim 1 wherein determining the invisible junction from the image comprises:

binarizing the image to create a binarization of the image;

applying a distance transformation to the binarization of the image to generate a distance transform;

detecting a skeleton in the distance transform; and

determining junction points in the skeleton as the invisible junctions.

7. A method for generating and storing an invisible junction, the method comprising:

receiving an image of an electronic document;

extracting an invisible junction feature descriptor from the image;

creating an feature index from the invisible junction feature descriptor; and

storing the feature index.

8. The method of claim 7, wherein extracting the invisible junction feature descriptor from the image comprises:

determining an invisible junction from the image; and

creating the invisible junction feature descriptor for the invisible junction.

9. The method of claim 7, wherein storing the feature index comprises storing the feature index in a database.

10. The method of claim 7, wherein storing the feature index comprises storing the feature index and the feature descriptor in a database.

11. The method of claim 7, wherein creating the feature index from the invisible junction feature descriptor comprises:

creating a quantization tree; and

adding a feature point to the quantization tree for the invisible junction feature descriptor.

12. The method of claim 7, wherein the quantization tree and the feature point are stored in a database.

13. The method of claim 11, further comprising:

extracting an additional invisible junction feature descriptor; and

adding a second feature point to the quantization tree for the additional invisible junction feature descriptor.

14. The method of claim 13, wherein the quantization tree is trained by a set of training features using hierarchical clustering.

15. The method of claim 13, wherein the feature point is added to the quantization tree by adding a leaf node including a page ID and coordinates (x, y) of the feature point.

16. The method of claim 7, wherein creating the feature index from the invisible junction feature descriptor comprises:

organizing the feature point into a k-d tree;

reducing a feature dimension using principal component analysis; and

ordering the feature dimensions to effectively partition the k-d tree.

17. A method for retrieving an electronic document using invisible junction features, the method comprising:

receiving an image of an input electronic document;

extracting an invisible junction feature descriptor from the image; and

retrieving an output electronic document using the invisible junction feature descriptor.

18. The method of claim 17, wherein retrieving the output electronic document comprises:

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

selecting one of the plurality of output electronic documents as the output electronic document using a geometric constraint.

19. The method of claim 17, wherein retrieving the output electronic document comprises querying a database using the invisible junction feature descriptor.

20. The method of claim 17, wherein retrieving the output electronic document comprises:

retrieving the feature descriptor;

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

organizing retrieved points by their corresponding document identification.

21. The method of claim 18, wherein retrieving the plurality of output electronic documents using the invisible junction feature descriptor comprises:

retrieving the feature descriptor;

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

organizing retrieved points by their corresponding document identification.

22. The method of claim 18, wherein selecting one of the plurality of output electronic documents comprises:

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

ranking the sorted plurality of output electronic documents using geometric constraints; and

outputting an electronic document with the highest rank.

23. The method of claim 18, wherein the outputting includes outputting a document identification, a point, and a viewing region for the electronic document with the highest rank.

24. A system for generating an invisible junction, the system comprising:

a feature determination unit having an input and an output for determining an invisible junction from an image, the input of the feature determination unit coupled to receive an image of an electronic document; and

a descriptor creation unit having an input and an output for creating a feature descriptor for the invisible junction, the descriptor creation unit having an input coupled to the output of the feature determination unit to receive information about the invisible junction, the output of the descriptor creation unit providing the feature descriptor.

25. The system of claim 24, further comprising a database to store features descriptor, the output of the descriptor creation unit coupled to the database.

26. The system of claim 24, wherein the feature determination unit comprises a location determination module having an input and an output for determining a junction location, the input of the location determination module coupled to receive the image of the electronic document, the output of the location determination coupled to the input of the descriptor creation unit.

27. The system of claim 26, wherein the feature determination unit comprises a size determination module having an input and an output for determining a junction size, the input of the size determination module coupled to the output of the location determination module to receive the junction location, the output of the size determination coupled to the input of the descriptor creation unit.

28. The system of claim 27, wherein the feature determination unit comprises an orientation determination module having an input and an output for determining a junction orientation, the input of the orientation determination module coupled to the output of the size determination module to receive the junction size, the output of the orientation determination coupled to the input of the descriptor creation unit.

33. The system of claim 27, wherein the feature indexing unit also provides the invisible junction feature descriptor.

34. The system of claim 27, wherein the feature indexing unit creates a quantization tree and adds a feature point to the quantization tree for the invisible junction feature descriptor.

35. The system of claim 34, wherein the feature indexing unit adds the feature point by adding a leaf node including a page ID and coordinates (x, y) of the feature point.

36. The system of claim 27, wherein the feature descriptor include a feature point and the feature indexing unit organizes the feature point into a k-d tree, reduces a feature dimension of the k-d tree using principal component analysis;

and orders the feature dimensions to effectively partition the k-d tree.

29. A system for generating an invisible junction, the system comprising:

a 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 the image of an electronic document; and

a feature indexing unit having an input and an output for creating a feature index for the invisible junction, the input of the feature indexing coupled to the output of the feature extraction unit to receive the invisible junction feature descriptor, the output of the feature indexing unit providing the feature index.

30. The system of claim 29, further comprising a database to store the feature index, the output of feature indexing unit coupled to the database.

31. The system of claim 29, wherein the feature extraction unit wherein the feature extraction unit determines the invisible junction from the image and creates the invisible junction feature descriptor for the invisible junction.

32. The system of claim 29, wherein the feature extraction unit comprises:

a location determination module having an input and an output for determining a junction location, the input of the location determination module coupled to receive the image of the electronic document;

a size determination module having an input and an output for determining a junction size, the input of the size determination module coupled to the output of the location determination module to receive the junction location;

an orientation determination module having an input and an output for determining a junction orientation, the input of the orientation determination module coupled to the output of the size determination module to receive the junction size; and

wherein the feature extraction unit is coupled to the feature indexing unit to provide the junction location, junction size and junction orientation.

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

a 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 having an input and an output for retrieving an output electronic document using the invisible junction feature descriptor, the input of the feature retrieval unit coupled to the output of the feature extraction unit, the output of the feature retrieval unit providing information about an output electronic document.

38. The system of claim 37, further comprising a database store a plurality of invisible junction feature descriptors and corresponding information about output electronic documents, the output of feature retrieval unit coupled to the database.

39. The system of claim 38, wherein the feature retrieval unit queries the database using the invisible junction feature descriptor.

40. The system of claim 37, wherein the feature retrieval unit retrieves a plurality of output electronic documents using the invisible junction feature descriptor, and selects one of the plurality of output electronic documents as the output electronic document using a geometric constraint.

41. The system of claim 37, 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.

42. The system of claim 40, wherein the feature retrieval unit sorts the 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.

43. The system of claim 40, wherein the information about the output electronic document is document identification, a point, and a viewing region.

44. The system of claim 40, wherein the information about the output electronic document is an electronic version of the output electronic document.