Combining adaBoost with a Hill-Climbing evolutionary feature search for efficient training of performant visual object detector

Yotam Abramson, Fabien Moutarde, Bogdan Stanciulescu, Bruno SteuxHAL 2006

TL;DR

This paper introduces a novel "evo-HC" hybrid search algorithm for efficiently training visual object detectors. By combining evolutionary and hill-climbing techniques, it significantly speeds up the feature selection process for the adaBoost algorithm, leading to highly accurate car detectors with reduced training times compared to traditional random search methods.

What Problem Does This Paper Address?

Training effective visual object detectors, like those used for recognizing cars in images, often involves a computationally intensive feature selection process. The seminal Viola-Jones framework uses adaBoost, which iteratively selects the best "weak learner" (a simple feature detector) at each step. While exhaustive search for these features is accurate, it's prohibitively slow for large feature sets. Existing methods to speed this up often compromise performance. This paper tackles the challenge of finding a feature selection method that is both efficient and capable of discovering highly performant features, specifically for the "control-point" feature family, which is much larger and more complex than the Haar-like features used in the original Viola-Jones work.

Methods

The core of this paper is the evo-HC (evolutionary-Hill-Climbing) hybrid search weak-learner. This algorithm is designed to efficiently explore the vast space of "control-point" features for the adaBoost training process. Here's how it works:

  • Initialization: It starts with a population of 70 random, simple control-point features.
  • Generational Improvement: In each generation:
  • The top 30 features from the previous generation (based on their weighted error) are selected.
  • These top features undergo a hill-climbing process: each feature is mutated up to 5 times, and a mutation is only kept if it improves the feature's performance (reduces its error).
  • The population is then supplemented with 40 new, randomly generated simple features.
  • Termination: The algorithm stops when there's no improvement for 40 consecutive generations, and the best feature from the final generation is chosen for the current adaBoost step.

This approach is "hybrid" because it combines evolutionary concepts (population-based search, mutation) with hill-climbing (local refinement of good solutions). The "control-point" features themselves are a generalized family of image features defined by sets of positive and negative points within a detection window, allowing for more complex feature definitions than simple Haar-like filters.

Datasets

  • Training and Validation: The authors used a dataset of 3291 labeled images, with 1224 positive examples of car rear views. This dataset was split into a training set (2204 examples) and a validation set (1087 examples) to monitor for overtraining. The data was collected from an on-vehicle camera.
  • Testing: For final testing, an independent recording was used, along with a manually built "ground truth" to ensure an unbiased evaluation.

Key Insights and Ideas

  • The "Control-Point" Feature Space is Huge: The paper highlights that the proposed "control-point" features, while powerful, lead to an astronomically large search space (over 10^35 possible features). This makes exhaustive search completely infeasible.
  • Hybrid Search is Key to Efficiency: The evo-HC algorithm demonstrates that a combination of evolutionary exploration and local hill-climbing refinement is a highly effective strategy for navigating such large feature spaces efficiently.
  • Performance vs. Random Search: The evo-HC method significantly outperforms a simple random search for feature selection, even when the random search is given a very large number of trials. This suggests that the guided search of evo-HC is crucial for finding good features.
  • Generalizability: The authors note that this approach has previously shown success for face and pedestrian detection, suggesting its potential as a general method for training various visual object detectors.

Key Results

  • High Detection Performance: The trained car detector achieved a 95% positive detection rate with a false detection rate of 1:40,000. This translates to less than one false positive per image frame in their test setup.
  • Efficient Training: Training a 500-feature detector using evo-HC took approximately 2.5 hours on a typical desktop (Pentium IV 3Ghz). This is significantly faster than what would be required for exhaustive search.
  • Superiority over Random Search: ROC curves clearly show that detectors trained with evo-HC consistently outperform those trained with random search, even when the random search uses a large number of trials and the evo-HC detector uses fewer features.
  • Time Savings: While random search with many trials can achieve acceptable performance, it requires significantly more training time (nearly 10 times) compared to evo-HC.

Limitations and Future Work

  • Limitations: The paper acknowledges that while evo-HC is efficient, a deeper study and comparison with other sophisticated search algorithms could be beneficial. The "random search" comparison, while illustrative, is a very basic baseline.
  • Future Work: The authors suggest further investigation into comparing their weak-learner with other advanced search techniques. They also express optimism about the general applicability of their adaBoost training with evo-HC weak-learner for a wide range of object detection tasks.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{abramson2006combining,
  author = {Yotam Abramson and Fabien Moutarde and Bogdan Stanciulescu and Bruno Steux},
  title = {{Combining adaBoost with a Hill-Climbing evolutionary feature search for efficient training of performant visual object detector}},
  booktitle = {HAL},
  year = {2006},
}
Figure