viola-jones detector

The Viola–Jones detector, published in 2001, was the first method to detect faces in real time on ordinary hardware, and for a decade it was the face-finder inside cameras and webcams. Its breakthrough was not a single idea but the marriage of three: extremely cheap features, a trick to compute them in constant time, and a cascade that spends almost no effort on the easy non-faces that make up most of an image. The intuition is that a face has stable light-and-dark structure — the eye region is darker than the cheeks below it, the bridge of the nose is brighter than the eyes beside it — and you can test for such patterns with simple rectangular contrasts.

Concretely, the features are Haar-like features: you sum the pixels in one rectangle and subtract the sum in an adjacent rectangle, giving a single number that responds to an edge or bar of brightness. There are tens of thousands of possible such rectangles in a 24×24 window, so AdaBoost is used both to pick the few hundred most discriminative ones and to combine them into a strong classifier. To make each rectangle sum instant, the image is first converted into an integral image (summed-area table), where each location stores the sum of all pixels above and to the left; then the sum of any rectangle is recovered with just four array lookups, no matter how large the rectangle.

The final piece is the attentional cascade: instead of one big classifier, the detector is a sequence of stages, each a small boosted classifier. A window must pass every stage to be declared a face; the moment any stage rejects it, scanning stops. Because the first stages are tiny (the very first uses only two features) yet reject a large fraction of background windows, the average window costs only a handful of operations. This is why a full sliding-window-plus-pyramid scan runs in real time. The trade-off is that Viola–Jones is tuned for roughly frontal, upright faces under reasonable lighting; it degrades on profile views, large rotations, and heavy occlusion, which is exactly where modern CNN detectors such as MTCNN and SSD-style face detectors took over.