Pyramid match kernel and related techniques

• US 20070217676A1
• Filed: 03/15/2007
• Published: 09/20/2007
• Est. Priority Date: 03/15/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Grauman, Kristen, Darrell, Trevor
• Granted Patent: US 7,949,186 B2
• Time in Patent Office: Days
• US Class Current: 382/170
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

A method for classifying or comparing objects includes detecting points of interest within two objects, computing feature descriptors at said points of interest, forming a multi-resolution histogram over feature descriptors for each object and computing a weighted intersection of multi-resolution histogram for each object. An alternative embodiment includes a method for matching objects by defining a plurality of bins for multi-resolution histograms having various levels and a plurality of cluster groups, each group having a center, for each point of interest, calculating a bin index, a bin count and a maximal distance to the bin center and providing a path vector indicative of the bins chosen at each level. Still another embodiment includes a method for matching objects comprising creating a set of feature vectors for each object of interest, mapping each set of feature vectors to a single high-dimensional vector to create an embedding vector and encoding each embedding vector with a binary hash string.

Claims

1. A method for classifying or comparing data objects comprising:

detecting points of interest within two data objects;

computing feature descriptors at said points of interest;

forming a multi-resolution histogram over feature descriptors for each data object; and

computing a weighted intersection of multi-resolution histogram for each data object.

2. The method as recited in claim 1 where the weight of each weighted intersection is determined by a bin size.

3. The method as recited in claim 1 wherein the forming a multi-resolution histogram comprises:

setting a histogram resolution level and detecting matching points within two data objects at said resolution level;

changing the histogram resolution level and confirming existing matching points and providing a weight reflecting distance estimate between matched points; and

changing again the histogram resolution level and confirming existing matching points and providing a weight reflecting distance estimate between matched points accordingly to provide an identifying feature.

4. The method as recited in claim 3 wherein each histogram resolution level is changed by a factor of two.

5. A method for assessing data objects comprising:

characterizing an data object by a set of feature vectors;

partitioning feature space into a plurality of bins with multiple levels with the size of the bins changing at each level;

computing a histogram over the partitioned feature space using the set of feature vectors for the data object; and

approximating the similarity to another data object according to partial matching in similar feature space.

6. The method as recited in claim 5 wherein characterizing the data object by a set of feature vectors comprises:

detecting points of interest within a data object that relate with the plurality of bins at each level of the feature space;

recognizing corresponding points along the different levels of the feature space which provide feature descriptors; and

from the feature descriptors and points of interest provide the set of feature vectors.

7. The method as recited in claim 5 wherein the partitioning of feature space is in the form of a pyramid with variable bin sizes.

8. The method as recited in claim 5 wherein the plurality of bins with multiple levels vary in bin size from the smallest bin at the finest resolution varying in size getting larger at each level until at the last level the bin size encompasses the entire feature space.

9. The method as recited in claim 5 wherein approximating the similarity to another object comprises comparing the histograms with a weighted histogram intersection computation to approximate the similarity of the best partial matching between feature sets.

10. A method for matching data objects comprising:

characterizing each data object by a set of feature vectors;

partitioning feature space into a plurality irregularly shaped and sized bins with multiple levels and forming a pyramid shape;

encoding point sets of interest from the feature vectors into multi-resolution histograms;

providing a matching value indicative of the probability of a match among data objects from any two histogram pyramids.

11. The method as recited in claim 10 wherein partitioning feature space into a plurality of irregularly shaped and sized bins with multiple levels and forming a pyramid shape comprises:

randomly selecting some example feature vectors from a feature type of interest;

form a representative feature corpus from the randomly selected examples; and

perform a hierarchical clustering operation to build a pyramid tree.

12. The method as recited in claim 11 wherein the hierarchical clustering operation comprises performing a hierarchical k-means clustering using the Euclidean distance to build the pyramid tree.

13. The method as recited in claim 10 wherein each irregularly shaped and sized bin has a center and for each point of interest, calculating a bin index, a bin count and a maximal distance to the bin center;

choosing a bin at each level of the pyramid; and

providing a path vector indicative of the bins chosen at each level.

14. The method as recited in claim 10 wherein partitioning feature space into a plurality of irregularly shaped and sized bins with multiple levels and forming a pyramid shape comprises determining the number of levels and determining the number of bins in each level.

15. The method as recited in claim 11 wherein boundaries of the plurality of irregularly shaped and sized bins are determined by Voronoi cells surrounding cluster centers.

16. The method as recited in claim 10 wherein encoding point sets of interest from the feature vectors into multi-resolution histograms is determined by nearest bin centers of the pyramid.

17. The method as recited in claim 10 wherein encoding point sets of interest from the feature vectors into multi-resolution histograms includes providing a bin index, a bin count and a distance to a bin center value for each point.

18. A method for matching objects comprising:

creating a set of feature vectors for each object of interest;

mapping each set of feature vectors to a single high-dimensional vector to create an embedding vector; and

encoding each embedding vector with a binary hash string.

19. The method as recited in claim 18 further comprising providing, from an encoded embedding vector, a matching value indicative of the normalized partial matching score among any two objects that generated the histograms pyramids.

20. The method as recited in claim 19 wherein providing a matching value comprises taking the dot product of two encoded embedding vectors.