Efficient face detection by a cascaded support–vector machine expansion

S. Romdhani, P. Torr, Bernhard Schölkopf, Andrew BlakeProceedings of the Royal Society A Mathematical Physical and Engineering Sciences 2004 · DOI

TL;DR

This paper introduces a novel cascaded approach to Support Vector Machine (SVM) based face detection, significantly speeding up the process by evaluating simpler classifiers first. By using a sequence of increasingly complex "reduced-set" SVMs, most non-face image patches are quickly rejected, leading to a substantial performance improvement without sacrificing accuracy.

What Problem Does This Paper Address?

Detecting human faces in large collections of images, such as photographic databases or the internet, is a computationally intensive task. Traditional methods often involve scanning an image with a fixed-size window at numerous locations, scales, and orientations. When using powerful classifiers like Support Vector Machines (SVMs), which can achieve high accuracy, the computational cost becomes a major bottleneck due to the large number of support vectors required to define the decision boundary. This paper aims to address this efficiency problem by developing a faster face detection system that leverages the strengths of SVMs while mitigating their computational expense.

Methods

The core innovation of this paper is the cascaded reduced-set machine (CRSM). Instead of evaluating the full SVM decision function for every image patch, the CRSM employs a hierarchical approach:

  • Reduced-Set SVMs: The authors first approximate the full SVM decision surface with a series of "reduced-set" expansions. These are essentially simpler SVMs that use a smaller number of "reduced-set vectors" (akin to support vectors but not necessarily from the training set) to define the decision boundary. The paper details a method for iteratively computing these reduced-set vectors and their corresponding coefficients.
  • Cascaded Evaluation: The key idea is to use these reduced-set SVMs in a cascade. Each stage of the cascade uses a progressively more complex classifier (i.e., one with more reduced-set vectors). Image patches are first evaluated by the simplest classifier. If a patch is confidently classified as a non-face, it is rejected immediately, saving computation. Only patches that are not easily rejected proceed to the next, more complex stage. This "early rejection" strategy is central to the speedup.
  • Optimized Training: The training process involves an initial SVM training on a large dataset of faces and non-faces. Misclassifications from this initial training are then used to refine the classifier through a second training phase, incorporating both generated "virtual faces" and false positives from a non-face dataset. This iterative refinement aims to improve both accuracy and robustness.

Datasets

  • Training: The paper mentions training on 3600 frontal face examples and 25,000 non-face examples. Non-face patches were randomly sampled from 1000 images containing no faces. A second training phase involved adding 110,000 false-positive patches and generated virtual faces.
  • Evaluation: The system was evaluated on a test set containing 800 faces and 5000 non-faces. For comparison with other methods, they also used a test set from Rowley et al. (1998), which includes images from Sung & Poggio (1994) and Osuna et al. (1997), totaling 130 images with 507 faces.

Key Insights and Ideas

  • Cascading for Efficiency: The most significant insight is that by structuring the classification process as a cascade of increasingly complex models, computational efficiency can be dramatically improved. This is particularly effective for problems like face detection where the vast majority of image patches are not faces.
  • Reduced-Set Vectors as Efficient Proxies: The concept of reduced-set vectors provides a way to approximate complex SVM decision boundaries with simpler, faster classifiers. These vectors are not necessarily the original support vectors, allowing for a more flexible and potentially more efficient representation.
  • "Optimal" Greedy Approximation: The method for computing reduced-set vectors aims to provide an optimal greedy approximation of the full SVM decision boundary at each stage of complexity. This ensures that each step in the cascade contributes meaningfully to the overall discrimination power.
  • Speed-Accuracy Trade-off: The paper highlights that the thresholds used in the cascaded classifiers directly influence the speed-accuracy trade-off. By adjusting these thresholds, one can prioritize speed (accepting more false negatives) or accuracy (requiring more computation).

Key Results

  • Significant Speedup: The CRSM achieved a thirtyfold speed-up over an evaluation using the full set of reduced-set vectors, which itself was already thirty times faster than using all the original support vectors. On average, only 2.8 reduced-set vectors were needed per patch for classification.
  • Comparable Accuracy: Despite the speed improvements, the accuracy of the CRSM was comparable to that of the full SVM and the RSM (Reduced-Set Machine).
  • Performance Metrics: On a test set of 800 faces and 5000 non-faces, the CRSM achieved a detection rate of 80.7% with a false detection rate of 0.001% (1 false positive per 100,000 patches) when compared to Rowley et al.'s results.
  • Computational Load: Figure 9 illustrates the speed-accuracy trade-off, showing that a false-negative rate of 2% requires approximately 4.45 kernel evaluations per patch, while a 10% false-negative rate reduces this to 2.82 evaluations.

Limitations and Future Work

  • Kernel Choice: The authors explored the Gaussian kernel but suggest that tailoring the kernel specifically for facial detection might yield further improvements.
  • Reduced-Set Selection Criteria: While the current method minimizes a distance metric, future work could focus on directly optimizing criteria that minimize classification error for the reduced sets.
  • Contextual Information: Adapting thresholds based on contextual information (e.g., the expected scale and orientation of other faces given one is detected) could further enhance detection speed.
  • Generalizability: Although demonstrated for face detection, the cascaded approach is expected to be applicable to a wide range of other detection and classification problems.

Summary updated

Abstract

We describe a fast system for the detection and localization of human faces in images using a nonlinear ‘support–vector machine’. We approximate the decision surface in terms of a reduced set of expansion vectors and propose a cascaded evaluation which has the property that the full support–vector expansion is only evaluated on the face–like parts of the image, while the largest part of typical images is classified using a single expansion vector (a simpler and more efficient classifier). As a result, only three reduced–set vectors are used, on average, to classify an image patch. Hence, the cascaded evaluation, presented in this paper, offers a thirtyfold speed–up over an evaluation using the full set of reduced–set vectors, which is itself already thirty times faster than classification using all the support vectors.
BibTeX
@inproceedings{romdhani2004efficient,
  author = {S. Romdhani and P. Torr and Bernhard Schölkopf and Andrew Blake},
  title = {{Efficient face detection by a cascaded support–vector machine expansion}},
  booktitle = {Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences},
  year = {2004},
  doi = {10.1098/rspa.2004.1333},
}

Loading related content...

Figure