The problem is the number of windows
Before deep learning, real-time face detection looked impossible. GPUs were slow, and a webcam needed answers in 66 milliseconds. The Viola-Jones detector, published in 2001, solved it with three ideas: cheap features built from pixel sums, a cascade that rejects most windows after one or two checks, and a boosting algorithm that selects the right features automatically. This page walks through each of those ideas.
A finder has to answer one question. Is there a face here? — at each spot and each scale in the image. For a 384×288 frame, scanning with a 24×24 window at 11 scales gives roughly 180,000 windows. At 15 frames per second that is 2.7 million classifications each second, and all of them will be answered "no".
That framing shows the whole design. Viola and Jones did not build an accurate face classifier and then speed it up. They built a system whose cost is dominated by how quickly it can say *no*, and then made saying no almost free.
Idea one: features that are rectangle differences
A Haar-like feature takes two or more adjacent rectangles, sums the pixel values inside each, and subtracts. The two-rectangle feature stacked vertically is a flat edge finder. The three-rectangle feature is a light band between two dark ones.
Drag the feature in the explorer onto the eye region and the response jumps, because the eye band really is darker than the cheek below it. Drag it onto the background and the two halves are nearly equal, so the response merges toward zero. That is the entire feature. A subtraction — and it is chosen for one reason: a rectangle sum can be made free.
There are a lot of these. In a 24×24 window, counting each spot and each size of each prototype gives more than 160,000 features, which is far more numbers than there are pixels in the window. The point isn't that each one is good. It's that a few hundred of them, chosen well, are.
Idea two: the integral image
The integral image is a table the same size as the image where each entry holds the sum of all above and to the left of it:
ii(x, y) = sum of i(x', y') for all x' <= x and y' <= y
It's built in a single pass. Once it exists, the sum inside *any* axis-aligned rectangle is:
sum = ii(D) - ii(B) - ii(C) + ii(A)
where A, B, C, D are the rectangle's four corners. Four lookups, three math ops, and — this is the part that matters — the cost doesn't depend on the size of the rectangle. A 4×4 patch and a 200×200 patch cost just the same.
The explorer prints the four corner values and the subtraction for the rectangle you've placed. Make the feature ten times larger and the four numbers change. The amount of work doesn't.
Two consequences follow right away. Features of any size are affordable, so the finder never has to resize the image to handle different face sizes — it scales the *feature* instead. This Is a change to four coords. And a two-rectangle feature costs six lookups rather than hundreds of additions, which brings the per-window cost into a range where testing a few hundred features is realistic.
Idea three: AdaBoost picks the few hundred that matter
Of the 160,000 pick features, almost all are useless. AdaBoost is used as a feature selector: each round, it picks the single feature and threshold that best classifies the training set under the current sample weights, then grows the weight on the examples that feature got wrong so the next round has to attend to them.
Each selected feature turns a *weak classifier*. A threshold on one rectangle difference, right maybe 60–70% of the time. The boosted sum of a few hundred of them is a strong classifier.
The paper's first two features are worth knowing because they're so readable. The first checks the eye region against the region just below it, because the eyes are darker than the upper cheeks. The second checks the eyes against the bridge of the nose between them, because the bridge is lighter. Both are placed and sized by the training method, not by a person, and both are just what a human would have picked.
The cascade: spend nothing on the easy negatives
A single strong classifier of 200 features applied to 180,000 windows is 36 million feature tests per frame. Too slow. The insight is that overwhelming majority of windows are trivially not faces — flat sky, blank wall — and don't need 200 features to settle.
So the classifiers are arranged in stages, cheapest first, and a window is discarded the instant any stage rejects it:
| Stage | Features | Roughly what it removes |
|---|
| 1 | 2 | about 50% of all windows |
| 2 | 10 | most of what stage 1 let through |
| 3–5 | 25–50 each | harder background |
| 6–38 | 50–200 each | face-like non-faces |
Each stage is tuned to a very high spotting rate — around 99.9% — and a modest false-positive rate, around 50%. Chained, the spotting rates times to a thing acceptable (0.99938 is still about 96%) while the false-positive rates times to a thing tiny (0.538).
The final finder has 38 stages and 6,061 features, and the *mean* window is rejected after about ten feature tests. Move the stage slider in the explorer and watch the surviving-window count fall off a cliff at the first stage: that first drop is where the speed comes from, and it costs two features.
What it is still good for, and what it is not
Haar cascades aren't competitive with a CNN finder on fit. They're sensitive to pose — the classic frontal-face model degrades sharply past about 15° of rotation — and to lighting, and they give trait false positives on textures that happen to hold a dark-light-dark band.
But they still ship, and for reasons that haven't gone away:
- They run anywhere. No GPU, no framework, a few hundred kilobytes of model. On a microcontroller or an old browser this is at times the only option.
- They're deterministic and inspectable. When one fires wrongly you can find the feature that did it.
- They're a training-free dependency.
cv2.CascadeClassifier with a shipped XML file is three lines and no data collection.
import cv2
detector = cv2.CascadeClassifier(
cv2.data.haarcascades + "haarcascade_frontalface_default.xml")
gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
faces = detector.detectMultiScale(
gray,
scaleFactor=1.1, # shrink the search window 10% per octave step
minNeighbors=5, # how many overlapping hits before it counts
minSize=(30, 30),
)
scaleFactor is the scale pyramid: 1.05 is slower and finds more, 1.3 is faster and misses small faces. minNeighbors is the crude non-max suppression — raise it to kill false positives, lower it if real faces are being dropped. Those two knobs are most of what tuning a cascade consists of.
Two knobs and the failure each one causes
Almost each complaint about a cascade traces back to scaleFactor or minNeighbors, and the two fail in opposite directions.
scaleFactor is the ratio between successive search scales. At 1.05 the finder tries about twenty scales between the smallest and largest face it looks for. At 1.4 it tries five. The faces that fall *between* two scales are the ones that get missed. So A large factor is fast and makes the trait "it saw him last frame and not this one" flicker. There's no free lunch here: the cost is roughly proportional to the number of scales.
minNeighbors is the crude duplicate-removal step. A real face makes a cluster of shared detections at neighbouring spots and scales, and a spurious one often makes a single isolated hit. needing a few shared detections before reporting one so filters most false positives — and deletes any real face that only just cleared the cascade, which is just the small, dark or partly-turned one you wanted. Setting it to 0 returns the raw hits and is worth doing once to see how many there are.
The third setting that matters and gets left at its default is minSize. A finder searching for 20×20 faces in a 4K frame is scanning tens of millions of windows for a thing that is never there. Setting a realistic floor is often a larger speed-up than either of the other two.
The line to draw from here
each idea here reappears later in a different costume. The cascade is the ancestor of the two-stage finder: propose cheaply, verify expensively, which is just what R-CNN and its descendants do. The integral image is the ancestor of each "precompute a summed table so the query is O(1)" trick in vision. And the rectangle features are, in an uncomfortably direct sense, a hand-designed first convolutional layer — a small set of local difference filters, applied all over, whose responses are thresholded and mixed. The difference is that the next twenty years were spent learning those filters rather than enumerating them.
Questions people ask
Why does it fail on a face that is only slightly turned? Because the features encode a fixed brightness layout. A dark eye band above a lighter cheek, a light nose bridge between two darker eyes. Rotating the head moves those rectangles scaled to each other and the responses the cascade thresholds on collapse. Past roughly 15° the frontal model degrades sharply. The usual answer is a second cascade trained on profiles rather than a fix to the first.
Can it find faces smaller than 24×24? No. The search grows the window from the trained size upward and never shrinks below it. 24×24 is the floor. Distant faces in a wide shot need the frame upsampled first. Doubling the image quadruples the window count.
Is the integral image an guess? No, it's exact. It's a cumulative sum. The four-corner formula recovers any rectangle's total just in int math. The costs are one extra table per frame and a wide enough int type. A 1080p frame of 8-bit pixels sums to about 5×108. This Is why these tables are 32-bit or wider.
Why grayscale? The feature is a brightness difference. Colour carries nothing it can read. Converting once per frame also makes the integral image a third of the size.
Why does it fire on things that are obviously not faces? Each stage is tuned for about 99.9% spotting at roughly 50% false positives. The ensure lives in the product across 38 stages, not in any one of them. And a dark-light-dark band is just what the early features test. Bookshelves and railings truly do excite them. With 180,000 windows per frame even a tiny per-window rate leaves survivors. This Is what minNeighbors is for.
Should I train my own cascade? Rarely, now. opencv_traincascade wants thousands of positives and tens of thousands of negatives and can run for days. The result still inherits the pose sensitivity. If the object is rigid, near-frontal and inference has to be CPU-only it's viable. Or else fine-tuning a small CNN finder is less work and better.
Recap in one screen
- One feature is a subtraction: the mean under the white rectangles minus the mean under the black ones.
- The integral image makes any rectangle sum four lookups even so of size. This Is why the finder scales the *feature* rather than the image.
- AdaBoost is used as a feature selector over more than 160,000 picks. The shipped finder keeps 6,061 of them across 38 stages.
- The cascade is where the speed lives. Stage one costs two features and drops about half of all windows. The mean window dies after about ten.
- It assumes a fixed brightness layout. It's a controlled-pose finder. All after it learned the filters instead of enumerating them.