Learning detectors quickly using structured covariance matrices

Jack Valmadre, Sridha Sridharan, Simon LuceyarXiv 2014 · arXiv

Introduction

Training robust object detectors typically relies on Hard Negative Mining (HNM), an iterative process that identifies and incorporates misclassified background samples into the training set. While effective, HNM is computationally intensive, requiring multiple passes over large datasets. This paper presents a method to accelerate detector training by orders of magnitude by exploiting the inherent mathematical structure of image statistics, specifically through the use of structured covariance matrices.

The Stationarity Assumption

The core innovation lies in the assumption of spatial stationarity for background image statistics. Stationarity implies that the correlation between two pixels depends only on their relative displacement, not their absolute coordinates. This assumption allows the covariance of image patches to be modeled as a Block Two-Level Toeplitz matrix.

Figure 4: The stationarity assumption posits that the statistics of image patches are invariant to translation, allowing for a more compact representation of background noise.

By leveraging this structure, the authors can pre-calculate global background statistics once, eliminating the need for repeated dataset scans during the training of new detectors.

Methods: Structured LDA and Circulant Preconditioning

The authors frame the detection problem as Linear Discriminant Analysis (LDA). However, for high-dimensional features like HOG, the covariance matrix is too large for direct inversion. To solve this efficiently, the paper introduces two key techniques:

  1. Toeplitz Matrix Representation: The stationarity assumption reduces the number of parameters needed to represent the covariance matrix, making it memory-efficient and suitable for embedded applications.
  2. Circulant Preconditioning: While Toeplitz matrices are structured, they are still non-trivial to invert. The authors use a circulant matrix as a preconditioner for the Preconditioned Conjugate Gradient (PCG) solver. Circulant matrices are a special class of Toeplitz matrices that assume periodic boundary conditions (wrap-around) and can be diagonalized using the Fast Fourier Transform (FFT).
Figure 6: The circulant approximation (right) assumes periodic wrap-around of image patches, enabling near-instantaneous inversion via FFT to accelerate the iterative solver.

This approach provides a theoretical link to Multi-Channel Correlation Filters (MCCFs), showing that structured LDA is essentially a more accurate version of correlation filtering that accounts for finite image boundaries rather than assuming periodicity.

Results and Performance

Evaluated on the INRIA Pedestrian and ImageNet datasets, the proposed method demonstrates significant gains:

  • Speed: Training time is reduced by nearly two orders of magnitude compared to standard Cholesky factorization. A detector can be trained in a fraction of a second.
  • Accuracy: Despite the massive speedup, the "Toeplitz" detector achieves a precision-recall curve nearly identical to traditional SVM-based Hard Negative Mining.
  • Convergence: The use of the circulant preconditioner drastically reduces the number of iterations needed for the solver to reach a stable solution.

Conclusion

By bridging the gap between classical LDA and modern correlation filters through the lens of structured covariance, this work enables the rapid deployment of object detectors. The method's memory efficiency and speed make it particularly suitable for real-time applications. Future work may involve exploring how these structured assumptions manifest in the feature maps of deep neural networks.

Summary updated

Abstract

Computer vision is increasingly becoming interested in the rapid estimation of object detectors. Canonical hard negative mining strategies are slow as they require multiple passes of the large negative training set. Recent work has demonstrated that if the distribution of negative examples is assumed to be stationary, then Linear Discriminant Analysis (LDA) can learn comparable detectors without ever revisiting the negative set. Even with this insight, however, the time to learn a single object detector can still be on the order of tens of seconds on a modern desktop computer. This paper proposes to leverage the resulting structured covariance matrix to obtain detectors with identical performance in orders of magnitude less time and memory. We elucidate an important connection to the correlation filter literature, demonstrating that these can also be trained without ever revisiting the negative set.
BibTeX
@misc{valmadre2014learning,
  author = {Jack Valmadre and Sridha Sridharan and Simon Lucey},
  title = {{Learning detectors quickly using structured covariance matrices}},
  year = {2014},
  eprint = {1403.7321},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.7321},
}
Figure