Pyramid match kernel and related techniques

• US 7,949,186 B2
• Filed: 03/15/2007
• Issued: 05/24/2011
• Est. Priority Date: 03/15/2006
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Grauman, Kristen, Darrell, Trevor
• Primary Examiner(s): Ahmed; Samir A
• Assistant Examiner(s): Liu; Li
• Application Number:
  US11/724,571
• Publication Number:
  US 20070217676A1
• Time in Patent Office: 1,531 Days
• Field of Search: None
• 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, using a computer, a first set of points of interest in a first data object and a second set of points of interest in a second data object;

computing feature descriptors for each data object from said points of interest;

forming a multi-resolution histogram from the feature descriptors of each data object; and

computing a weighted intersection from the multi-resolution histogram for the first data object as compared with the multi-resolution histogram for the second 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 first histogram resolution level and detecting matching points in the feature descriptors of the first data object and the second data object at said resolution level to provide a set of matched points;

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

changing again the histogram resolution level to a third histogram resolution level and confirming existing matching points and providing a weight reflecting distance estimate between matched points in the third histogram resolution level 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, using a computer, a first 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 first data object;

characterizing, using a computer, a second data object by a set of feature vectors;

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

comparing the similarity of the histogram of the first data object with the histogram of the second data object to determine matching in similar feature space.

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

detecting points of interest within the first 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 partioning feature space into a plurality of bins with multiple levels with the size of the bins changing at each level step comprises varying the bin size from a smallest bin at a finest resolution to a larger bin at each level of the feature space until at the last level the bin size encompasses the entire feature space.

9. The method as recited in claim 5 wherein the comparing the similarity of the histogram of the first data object with the histogram of the second data object step comprises comparing the histograms of the first data object and the second data object with a weighted histogram intersection computation to determine the similarity of the best partial matching between similar feature space.