doc.md

The Pyramid Match Kernel: Discriminative Classification with Sets of Image Features

Kristen Grauman and Trevor Darrell

Massachusetts Institute of Technology

Computer Science and Artificial Intelligence Laboratory

Cambridge, MA, USA

Introduction

Related Work

Pyramid Match Kernel

Satisfying Mercer’s Condition

Results

Conclusions

It is often useful to represent a single example by the collection of local features or parts that comprise it.

The image can be described by local features extracted from patches around salient interest points, or a shape may be described by local descriptors defined at edge points.

Set of Features in two images

To perform learning tasks like categorization or recognition with such representations is challenging in such cases.

Support Vector Machine (SVM) is a widely used approach to discriminative classification that finds the optimal separating hyperplane between two classes.

Kernel functions, which measure similarity between inputs, introduce non-linearities to the decision functions; the kernel non-linearly maps two examples from the input space to the inner product in some feature space.

Conventional kernel-based algorithms are designed to operate on fixed-length vector inputs and hence commonly used general-purpose kernels defined on n inputs (e.g., Gaussian RBF, polynomial) are not applicable in the space of vector sets.

The pyramid match kernel – a new kernel function over unordered feature sets that allows them to be used effectively and efficiently in kernel-based learning methods. Each feature set is mapped to a multiresolution histogram that preserves the individual features’ distinctness at the finest level.

To perform learning tasks like categorization or recognition with such representations is challenging in such cases.

Pyramid Match Kernel

Pyramid matching: an efficient method that maps unordered feature sets to multi-resolution histograms .

Computes a weighted histogram intersection to find implicit correspondences based on finest resolution histogram cell where a matched pair first appears .

Approximates similarity measured by optimal correspondences between feature sets of unequal cardinality .

1GraumanandDarrell, The PyramidMatchKernel:DiscriminativeClassificationwithSetsofImageFeatures, IEEEICCV2005,Vol2, pp.1458–1465

histogram pyramids

number of newly matched pairs at level i

measure of difficulty of a match at level i

Pyramid Match Kernel

Weights inversely proportional to bin size

Normalize kernel values to avoid favoring large sets

Histogram Intersection

matches at this level

matches at previous level

Difference in histogram intersections across levels counts number of new pairs matched

Histogram Intersection

Pyramid Match Kernel: Method

1-D point sets X, Y on grid of size 1

Pyramid Match Kernel: Method

1-D point sets X, Y on grid of size 1 - level 0 histograms

Pyramid Match Kernel: Method

1-D point sets X, Y on grid of size 1 - level 0 histograms - intersection

Pyramid Match Kernel: Method

1-D point sets X, Y on grid of size 1 - level 0 histograms - intersection 2.

Matches weighted by 1.

Using the total similarity score: 2 × 1 = 2

Pyramid Match Kernel: Method

1-D point sets X, Y on grid of size 2 - level 1 histograms – intersection.

(2 matches weighted by 1) + (2 weighted by ½ ).

Using calculate total similarity score: 2 × 1 + 2 x ½ =3

Pyramid Match Kernel: Method

1-D point sets X, Y on grid of size 4 - level 2 histograms - intersection.

(2 matches weighted by 1) + (2 weighted by ½ ) + (1 weighted by ¼ )

Using total similarity score: 2 × 1 + 2 x ½ + 1 x ¼ = 3.25

Pyramid Match Kernel: Method

Weighted sum of histogram intersections at different levels of two images approximates their optimal pairwise matching

Pyramid Match Kernel: Efficiency

For sets with m features of dimension d, and pyramids with L levels, computational complexity of

Pyramid match kernel:

Existing set kernel approaches:

Results: Approximate Partial Matchings

Trial number (sorted by optimal distance)

Trial number (sorted by optimal distance)

2-D points with values uniformly distributed between 1 and 1000.

In one data set, each point set had equal cardinalities (100 points each), while in the other cardinalities varied randomly from 5 to 100.

Results : Approximate Partial Matchings

Equal cardinality case (plot on left), both the pyramid match and the L1 embedding produce good approximations; both are on average less than 9% away from the optimal measure.

Pyramid match also approximated the partial matching for the unequal cardinality case and its matchings continue to follow the optimal matching’s trend since it does not penalize outliers, whereas the L1 embedding fails because it requires all points to match to something.

This method was less than 9% on an average away from the optimal matching’s measure for the unequal cardinality case, while the L1 matching has an average error of 400%

Results : Object Recognition

• Train SVM by computing kernel values between all labeled training examples.
• Classify novel examples by computing kernel values against support vectors
• ETH-80 database:
• - 8 object classes
• Features:
  • - Harris detector
  • - PCA-SIFT descriptor, d=10

Results : Object Recognition

• Caltech objects database 101 object classes
• Features:
  • SIFT detector
  • PCA-SIFT descriptor, d =10
• 30 training images / class
• 43% recognition rate
• (1% chance performance)
• 0.002 seconds per match