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.
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:
- 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.
- 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).
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