Return to search

Pyramid Match Kernels: Discriminative Classification with Sets of Image Features

Discriminative learning is challenging when examples are setsof local image features, and the sets vary in cardinality and lackany sort of meaningful ordering. Kernel-based classificationmethods can learn complex decision boundaries, but a kernelsimilarity measure for unordered set inputs must somehow solve forcorrespondences -- generally a computationally expensive task thatbecomes impractical for large set sizes. We present a new fastkernel function which maps unordered feature sets tomulti-resolution histograms and computes a weighted histogramintersection in this space. This ``pyramid match" computation islinear in the number of features, and it implicitly findscorrespondences based on the finest resolution histogram cell wherea matched pair first appears. Since the kernel does not penalize thepresence of extra features, it is robust to clutter. We show thekernel function is positive-definite, making it valid for use inlearning algorithms whose optimal solutions are guaranteed only forMercer kernels. We demonstrate our algorithm on object recognitiontasks and show it to be dramatically faster than currentapproaches.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/30420
Date17 March 2005
CreatorsGrauman, Kristen, Darrell, Trevor
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
Format12 p., 68553886 bytes, 13808123 bytes, application/postscript, application/pdf
RelationMassachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory

Page generated in 0.002 seconds