Training Deformable Part Models with Decorrelated Features

Ross B. Girshick, Jitendra Malik

In this ICCV 2013 paper, Ross Girshick and Jitendra Malik address a significant bottleneck in computer vision: the extensive time required to train Deformable Part Models (DPMs). By introducing a novel approach called "Latent LDA," they demonstrate how to achieve state-of-the-art detection performance with a fraction of the traditional training time.

The Bottleneck: Hard Negative Mining

In 2013, DPMs were the standard for object detection, but their training relied on Latent SVM (LSVM). This non-convex optimization process requires "hard negative mining"—iteratively scanning thousands of images to find background patches that confuse the detector. This process was notoriously slow, often taking hours or days, which significantly slowed the pace of research and model iteration.

Proposed Methods: Latent LDA and LM-LLDA

The authors propose two primary strategies to accelerate the training pipeline:

  1. Latent LDA (LLDA): This method generalizes Linear Discriminant Analysis to handle latent variables, such as unknown object poses. By "whitening" input features (decorrelating them using a global covariance matrix), LLDA can be solved in a closed-form, avoiding the iterative data mining required by SVMs.
  2. LM-LLDA (The Hybrid Approach): While pure LLDA is fast, it can slightly trail SVMs in accuracy. The authors developed a hybrid approach where LLDA is used to quickly "warm start" the model by imputing latent labels (part locations). A final, single "large-margin" (SVM-style) pass is then performed with limited data mining to refine the results.
  3. Feature Whitening: An efficient method for estimating the covariance of HOG (Histogram of Oriented Gradients) patches was introduced, allowing background statistics to be pre-calculated once and reused across all object classes.

Key Results and Speedup

The primary contribution of this work is the dramatic reduction in training time without a significant sacrifice in detection quality. The hybrid LM-LLDA method achieved a median training time of approximately 20 minutes, a 4x speedup over the fastest standard implementations of the time.

Comparison of training wall time (in minutes) between standard Latent SVM (A) and the proposed LM-LLDA (B) across varying numbers of negative images.

In terms of accuracy, the methods remained highly competitive. On the PASCAL VOC 2007 benchmark, the fast hybrid method achieved 32.3% mAP, nearly matching the 33.7% mAP of the much slower full Latent SVM. Notably, even a version trained with zero negative images (LLDA-0) remained competitive with some existing baselines.

Performance comparison (mAP) on PASCAL VOC 2007 and 2011 datasets, comparing the proposed LLDA variants against established baselines.

Insights and Implications

  • Latent Label Robustness: The authors found that LLDA is exceptionally good at identifying part locations (latent labels), making it an ideal initialization tool for more complex discriminative learners.
  • Efficiency of Negatives: The research revealed a law of diminishing returns regarding negative training data; using just 200 negative images (roughly 10% of the standard set) captured 95% of the potential performance.
  • Joint Training: The study confirmed that joint training of parts and their spatial relationships is essential, as two-stage training significantly underperforms.

While the field eventually shifted toward Deep Learning and Convolutional Neural Networks, the insights regarding feature whitening, efficient data mining, and latent variable initialization remain foundational concepts in structured prediction and efficient model training.

Summary updated

Abstract

In this paper, we show how to train a deformable part model (DPM) fast-typically in less than 20 minutes, or four times faster than the current fastest method-while maintaining high average precision on the PASCAL VOC datasets. At the core of our approach is "latent LDA," a novel generalization of linear discriminant analysis for learning latent variable models. Unlike latent SVM, latent LDA uses efficient closed-form updates and does not require an expensive search for hard negative examples. Our approach also acts as a springboard for a detailed experimental study of DPM training. We isolate and quantify the impact of key training factors for the first time (e.g., How important are discriminative SVM filters? How important is joint parameter estimation? How many negative images are needed for training?). Our findings yield useful insights for researchers working with Markov random fields and part-based models, and have practical implications for speeding up tasks such as model selection.
BibTeX
@inproceedings{girshick2013training,
  author = {Ross B. Girshick and Jitendra Malik},
  title = {{Training Deformable Part Models with Decorrelated Features}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  doi = {10.1109/iccv.2013.375},
}
Figure