The pyramid match kernel: discriminative classification with sets of image features

By Kristen Grauman, Trevor Darrell. 2005

1,655 citations recorded by the source corpus.

Discriminative learning is challenging when examples are sets of features, and the sets vary in cardinality and lack any sort of meaningful ordering. Kernel-based classification methods can learn complex decision boundaries, but a kernel over unordered set inputs must somehow solve for correspondences epsivnerally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function which maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in this space. This "pyramid match" computation is linear in the number of features, and it implicitly finds correspondences based on the finest resolution histogram cell where a matched pair first appears. Since the kernel does not penalize the presence of extra features, it is robust to clutter. We show the kernel function is positive-definite, making it valid for use in learning algorithms whose optimal solutions are guaranteed only for Mercer kernels. We demonstrate our algorithm on object recognition tasks and show it to be accurate and dramatically faster than current approaches

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Media Technology

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

In Media Technology

Citations in the corpus

End-to-End Neural Ad-hoc Ranking with Kernel Pooling (2017, methodology): “e Deep Relevance Matching Model (DRMM) uses pyramid pooling (histogram) [7] to summarize the word-level similarities into ranking signals [9].”
Encoder-Decoder with Atrous Separable Convolution for Semantic Image Segmentation (2018, methodology): “In this work, we consider two types of neural networks that use spatial pyramid pooling module [23, 40, 26] or encoder-decoder structure [61, 3] for semantic segmentation, where the former one captures rich contextual information by pooling features at different resolution while the latter one is ab”
Rethinking Atrous Convolution for Semantic Image Segmentation (2017, background): “Spatial pyramid pooling: This model employs spatial pyramid pooling [24, 43] to capture context at several ranges.”
Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmentation (2019, neutral): “Therefore, PSPNet [88] performs spatial pyramid pooling [21, 41, 24] at several grid scales (including image-level pooling [50]), while DeepLab [8, 9] applies several parallel atrous convolution [28, 20, 68, 57, 7] with different rates.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “This approach has been useful for variants of edit distance [MS00, CMS01b, CMS01a, Cor03, CK06, OR07], earth-mover distance [Cha02, IT03, GD05, AIK08] and other metrics.”
Multi-scale Orderless Pooling of Deep Convolutional Activation Features (2014, background): “For much of the past decade, orderless bag-of-features (BoF) methods [15,17,18,19,20] were considered to be the state of the art.”
Automatic Description Generation from Images: A Survey of Models, Datasets, and Evaluation Measures (2016, neutral): “03 89”
SIFT Flow: Dense Correspondence across Scenes and Its Applications (2011, methodology): “Then, histograms of the visual words are obtained on a two-level spatial pyramid [ 24 ], [32], and histogram intersection is used to measure the similarity between two images.”
DeeperLab: Single-Shot Image Parser (2019, methodology): “Recently, PSPNet [36] proposes using spatial pyramid pooling [37, 38] at several grid scales (including imagelevel pooling [39]), and DeepLab [35, 40] proposes applying several parallel atrous convolutions [41, 42, 21, 43, 44] with different rates (called Atrous Spatial Pyramid Pooling, or ASPP).”
Affinity Derivation and Graph Merge for Instance Segmentation (2018, methodology): “To explore multi-scale information, PSPNet [48] designs a pyramid pooling structure [20,30,39] and Deeplabv2 [5] proposes Atrous Spatial Pyramid Pooling (ASPP) to embed contextual information.”
Face recognition in unconstrained videos with matched background similarity (2011, background): “PMK and our adaptation of LLC underperform, although more exploration of their parameter space might improve their results.”
Egocentric recognition of handled objects: Benchmark and analysis (2009, methodology): “As a comparison, we have also run the pyramid matching algorithm [9, 13] with the hierarchical clustering of SIFT features into words.”
Convolutional Neural Networks for Soft-Matching N-Grams in Ad-hoc Search (2018, methodology): “e DRMM model introduces the histogram pooling (pyramid pooling [11]) technique to summarize the translation matrix; it demonstrated that it is more eective to ‘count’ the word-level translation scores at dierent so match levels, instead of to weight-sum them [13].”
Local Features and Kernels for Classification of Texture and Object Categories: A Comprehensive Study (2006, positive): “To date, state-of-the-art results in both texture [31] and object recognition [18, 23 , 48, 61] have been obtained with local features computed at a sparse set of scale- or ane-in variant keypoint locations found by specialized interest operators [34, 43].”
Image classification by non-negative sparse coding, low-rank and sparse decomposition (2011, methodology): “Others tried to learn discriminative classifiers by considering the spatial information and correlations among visual words [2-4, 7, 10-11].”