Invisible junction features for patch recognition

• US 8,086,038 B2
• Filed: 07/11/2007
• Issued: 12/27/2011
• Est. Priority Date: 07/11/2007
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Ke, Qifa, Hull, Jonathan J.
• Primary Examiner(s): KOZIOL, STEPHEN R
• Application Number:
  US11/776,510
• Publication Number:
  US 20090016604A1
• Time in Patent Office: 1,630 Days
• Field of Search: 382/190, 382/181, 382/176
• 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 computer-implemented method for generating invisible junctions, the method comprising:

receiving, with a processor, an electronic document;

applying, with the processor, a distance transformation to the electronic document to generate a distance transform;

detecting, with the processor, a skeleton in the distance transform;

determining, with the processor, junction points in the skeleton as the invisible junctions, the junction points having a distance transformation value based on the distance transform;

determining, with the processor, a junction size for at least one junction point, the junction size based at least in part on the distance transformation value; and

creating, with the processor, a feature descriptor for each invisible junction, the feature descriptor including the junction size.

2. The method of claim 1 wherein:

determining the junction points includes determining a junction location for each junction point; and

the feature descriptor includes the junction location.

3. The method of claim 1 wherein the junction size is the distance transformation value multiplied by a factor.

4. The method of claim 1 wherein:

determining the junction points includes determining a junction orientation for each junction point; and

the feature descriptor includes the junction orientation.

5. The method of claim 1 wherein the junction points are at least one of a local maxima of a distance transform field and a local maxima on the skeleton.

6. A computer-implemented method for generating and storing invisible junctions, the method comprising:

receiving, with a processor, an electronic document;

applying, with the processor, a distance transformation to the electronic document to generate a distance transform;

detecting, with the processor, a skeleton in the distance transform;

determining, with the processor, junction points in the skeleton as the invisible junctions, the junction points having a distance transformation value based on the distance transform;

determining, with the processor, a junction size for at least one junction point, the junction size based at least in part on the distance transformation value;

extracting, with the processor, an invisible junction feature descriptor from the electronic document for each invisible junction, the invisible junction feature descriptor including the including the junction size;

creating, with the processor, a feature index from the invisible junction feature descriptors; and

storing the feature index.

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

8. The method of claim 6, wherein storing the feature index comprises storing the feature index and the invisible junction feature descriptors in a database.

9. The method of claim 6, wherein creating the feature index from the invisible junction feature descriptors comprises:

creating a quantization tree; and

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

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

11. The method of claim 9, 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.

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

13. The method of claim 11, 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.

14. The method of claim 6, wherein creating the feature index from the invisible junction feature descriptors comprises:

organizing a feature point into a k-d tree;

reducing a feature dimension using principal component analysis; and

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

15. A system for generating invisible junctions, the system comprising:

a processor;

a feature determination unit stored on a memory and executable by the processor, the feature determination unit having an input and an output for applying a distance transformation to an electronic document to generate a distance transform, for detecting a skeleton in the distance transform, for determining junction points in the skeleton as the invisible junctions, the junction points having a distance transformation value based on the distance transform and for determining a junction size that is based at least in part on the distance transformation value, the input of the feature determination unit coupled to receive the electronic document; and

a descriptor creation unit stored on the memory and executable by the processor, the descriptor creation unit having an input and an output for creating a feature descriptor for each invisible junction, the feature descriptor including the junction size, the input of the descriptor creation unit coupled to the output of the feature determination unit to receive information about the invisible junctions, the output of the descriptor creation unit providing the feature descriptors.

16. The system of claim 15, further comprising a database to store the feature descriptors, the output of the descriptor creation unit coupled to the database.

17. The system of claim 15, 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 electronic document, the output of the location determination module coupled to the input of the descriptor creation unit.

18. The system of claim 17, wherein the feature determination unit comprises a size determination module having an input and an output for determining the 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 module coupled to the input of the descriptor creation unit.

19. The system of claim 18, 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 module coupled to the input of the descriptor creation unit.

20. A system for generating invisible junctions, 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 applying a distance transformation to an electronic document to generate a distance transform, for detecting a skeleton in the distance transform, for determining junction points in the skeleton as the invisible junctions, the junction points having a distance transformation value based on the distance transform, for determining a junction size based on the distance transformation value and for producing an invisible junction feature descriptor for each invisible junction, the invisible junction feature descriptor including the junction size, the input of the feature extraction unit coupled to receive the electronic document; and

a feature indexing unit stored on the memory and executable by the processor, the feature indexing unit having an input and an output for creating a feature index for the invisible junctions, the input of the feature indexing unit coupled to the output of the feature extraction unit to receive the invisible junction feature descriptors, the output of the feature indexing unit providing the feature index.

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

22. The system of claim 20, wherein the feature extraction unit creates the invisible junction feature descriptors for the invisible junctions.

23. The system of claim 20, 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 electronic document;

a size determination module having an input and an output for determining the 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.

24. The system of claim 20, wherein the feature indexing unit also provides the invisible junction feature descriptors.

25. The system of claim 20, wherein the feature indexing unit creates a quantization tree and adds a feature point to the quantization tree for the invisible junction feature descriptors.

26. The system of claim 25, 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.

27. The system of claim 20, wherein the feature descriptor includes 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 dimension to effectively partition the k-d tree.