Approximate Correspondences in High Dimensions

By Kristen Grauman, Trevor Darrell. 2006

121 citations recorded by the source corpus.

Pyramid intersection is an efficient method for computing an approximate partial matching between two sets of feature vectors. We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains accurate even for sets with high-dimensional feature vectors. The matching similarity is computed in linear time and forms a Mercer kernel. Whereas previous matching approximation algorithms suffer from distortion factors that increase linearly with the feature dimension, we demonstrate that our approach can maintain constant accuracy even as the feature dimension increases. When used as a kernel in a discriminative classifier, our approach achieves improved object recognition results over a state-of-the-art set kernel.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Nonparametric kernel estimators for image classification (2012, methodology): “We also use the vocabulary-guided pyramid matching kernel ( PMK ) [7]; this variant performs better for high-dimensional data.”
On Valid Optimal Assignment Kernels and Applications to Graph Classification (2016, methodology): “An adaptive partitioning with non-uniformly shaped bins was used to improve the approximation quality in high dimensions [10].”
Gaussian Processes for Object Categorization (2010, methodology): “A semi-supervised method using normalized cuts to cluster a graph deﬁned by Pyramid Match distances between examples was presented in Grauman and Darrell (2006b), but this method is not probabilistic nor does it provide for an active learning formalism.”
Active Learning with Gaussian Processes for Object Categorization (2007, methodology): “experiments on two other flavors of PMK that included one with data-dependent partitions [10] and the other where the SIFT descriptors are extracted only at salient points detected with a Harris-Affine interest operator [17].”
Contextual Object Detection Using Set-Based Classification (2012, methodology): “Comparison of SetBoost algorithm with PMK [7].”
The Pyramid Match Kernel: Efficient Learning with Sets of Features (2007, methodology): “To enable accurate pyramid matching even with high-dimensional feature spaces, we have developed a variant where the pyramid bin structure depends on the distribution of the data (Grauman and Darrell, 2007).”
Single View Human Action Recognition using Key Pose Matching and Viterbi Path Searching (2007, background): “This issue is also reported by Grauman and Darrell in [8], where they propose to use hierarchical k-means clustering to partition the high-dimensional feature space into a hierarchy of non-uniformly shaped bins.”
A survey on graph kernels (2019, methodology): “Moreover, in [47] the Descriptor Matching kernel is defined, which captures the graph structure by a propagation mechanism between neighbors, and uses a variant of the pyramid match kernel [86] to compare attributes between vertices.”
Learning Globally-Consistent Local Distance Functions for Shape-Based Image Retrieval and Classification (2007, methodology): “Of this work, [9], [13], and [8] focused specifically on defining good imageto-image kernel functions over sets of patch-based features for use with support vector machines (SVMs).”
Handbook of Big Data (2016, background): “In practice, particularly in large-p problems, there is rarely suﬃcient data to truly”