Beyond Hard Negative Mining: Efficient Detector Learning via Block-Circulant Decomposition
- 1 December 2013
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2760-2767
- https://doi.org/10.1109/iccv.2013.343
Abstract
Competitive sliding window detectors require vast training sets. Since a pool of natural images provides a nearly endless supply of negative samples, in the form of patches at different scales and locations, training with all the available data is considered impractical. A staple of current approaches is hard negative mining, a method of selecting relevant samples, which is nevertheless expensive. Given that samples at slightly different locations have overlapping support, there seems to be an enormous amount of duplicated work. It is natural, then, to ask whether these redundancies can be eliminated. In this paper, we show that the Gram matrix describing such data is block-circulant. We derive a transformation based on the Fourier transform that block-diagonalizes the Gram matrix, at once eliminating redundancies and partitioning the learning problem. This decomposition is valid for any dense features and several learning algorithms, and takes full advantage of modern parallel architectures. Surprisingly, it allows training with all the potential samples in sets of thousands of images. By considering the full set, we generate in a single shot the optimal solution, which is usually obtained only after several rounds of hard negative mining. We report speed gains on Caltech Pedestrians and INRIA Pedestrians of over an order of magnitude, allowing training on a desktop computer in a couple of minutes.Keywords
This publication has 14 references indexed in Scilit:
- Event Retrieval in Large Video Collections with Circulant Temporal EncodingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Correlation Filters for Object AlignmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Accelerated Training of Linear Object DetectorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Hybrid Classifiers for Object Classification with a Rich BackgroundLecture Notes in Computer Science, 2012
- Ensemble of exemplar-SVMs for object detection and beyondPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Object Detection with Discriminatively Trained Part-Based ModelsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2009
- Groups of Adjacent Contour Segments for Object DetectionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2007
- Visual features of intermediate complexity and their use in classificationNature Neuroscience, 2002
- The Nature of Statistical Learning TheoryPublished by Springer Science and Business Media LLC ,2000
- Fast training of Support Vector Machines for regressionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2000