Self-Adaptable Templates for Feature Coding

Xavier Boix, Gemma Roig, Salomon Diether, Luc Van Gool

TL;DR

This paper reveals that Second-Order Pooling (O2P)—previously thought to be a "template-free" method—is actually a coding-pooling scheme where the templates are the eigenvectors of the input features. By identifying this relationship and applying Sparse Quantization (SQ) to the input features, the authors achieved a massive performance boost on the PASCAL VOC 2007 benchmark, jumping from 18.8% to nearly 51% accuracy.

What Problem Does This Paper Address?

In the standard computer vision pipeline for object recognition, features (like SIFT) are typically processed in two steps: coding and pooling.

  1. Coding: Comparing input features to a fixed set of "templates" (a codebook or dictionary) learned during a training phase.
  2. Pooling: Aggregating those comparisons into a single vector representation.

Second-Order Pooling (O2P) emerged as a powerful alternative that didn't seem to follow this rule. It builds a correlation matrix of features and uses its logarithm as a descriptor. Because it didn't use a fixed codebook, it was hard to relate O2P to traditional methods or apply common optimization tricks like feature quantization. The authors set out to bridge this gap: Is O2P really template-free, or are the templates just hidden?

Methods

By reformulating the underlying mathematics of O2P, the authors demonstrate that the inner product between two O2P descriptors is mathematically equivalent to a traditional coding-pooling scheme.

The Key Discovery: In O2P, the "templates" are actually the eigenvectors of the feature correlation matrix. Unlike Bag-of-Words or Fisher Vectors, where templates are fixed after training, O2P's templates are self-adaptable—they are recomputed for every single image.

Comparison of feature coding methods showing O2P's self-adapted templates.

Building on this insight, the authors introduced Sparse Quantization (SQ). Before performing O2P, they keep only the $k$ highest values of each input feature vector and set the rest to zero. This reduces noise and variability, making the "self-adapted" templates more robust to the clutter found in complex images.

Key Insights and Ideas

  • Templates are Eigenvectors: The most significant theoretical contribution is the proof that O2P is just a coding scheme where eigenvectors play the role of the codebook.
  • Self-Adaptation vs. Learning: Most models "learn" what an object looks like once and stay fixed. O2P "adapts" its internal representation to the specific statistics of the image it is currently looking at.
  • Quantization as a Regularizer: In O2P, having too much information can actually be a disadvantage. When images have high variability, the self-adapted templates can become "confused" by noise. Sparse Quantization acts as a filter, forcing the model to focus on the most prominent feature signals.

Key Results

The researchers evaluated their approach on two classic computer vision benchmarks: Caltech 101 (generally considered less complex due to centered objects) and PASCAL VOC 2007 (a much more challenging dataset with high variability in object scale, orientation, and background clutter).

The impact of adding Sparse Quantization to O2P was dramatic, especially on the more difficult data:

Performance of O2P with Sparse Quantization on Caltech 101 and PASCAL VOC 2007.
  • PASCAL VOC 2007: Standard O2P performed poorly, with a mean Average Precision (mAP) of only 18.81%. By adding Sparse Quantization and a spatial pyramid, the accuracy skyrocketed to 50.97%.
  • Caltech 101: The improvement was more modest but still significant, moving from 76.52% to 78.63%.
  • Efficiency: Because Sparse Quantization is computationally "negligible" (just picking the top $k$ values), these massive performance gains come with almost no extra processing cost.

Limitations and Future Work

  • Template Constraints: In O2P, the number of templates is strictly tied to the dimensionality of the input features ($M$). You cannot increase the number of templates without changing the feature length, which limits the model's flexibility compared to Bag-of-Words (where you can have a codebook of any size).
  • Deep Learning Integration: While this paper focuses on hand-crafted features like SIFT, the authors note that the next logical step is analyzing how these self-adaptable templates behave within deep hierarchical networks (CNNs).
  • Quantization Sensitivity: The performance depends heavily on the choice of $k$ (the sparsity level), which may need to be carefully tuned for different datasets to achieve optimal results.

Summary updated

Abstract

Hierarchical feed-forward networks have been successfully applied in object recognition. At each level of the hierarchy, features are extracted and encoded, followed by a pooling step. Within this processing pipeline, the common trend is to learn the feature coding templates, often referred as codebook entries, filters, or over-complete basis. Recently, an approach that apparently does not use templates has been shown to obtain very promising results. This is the second-order pooling (O2P). In this paper, we analyze O2P as a coding-pooling scheme. We find that at testing phase, O2P automatically adapts the feature coding templates to the input features, rather than using templates learned during the training phase. From this finding, we are able to bring common concepts of coding-pooling schemes to O2P, such as feature quantization. This allows for significant accuracy improvements of O2P in standard benchmarks of image classification, namely Caltech101 and VOC07.
BibTeX
@inproceedings{boix2014self,
  author = {Xavier Boix and Gemma Roig and Salomon Diether and Luc Van Gool},
  title = {{Self-Adaptable Templates for Feature Coding}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure