Finding Faces in Real Time: Sliding Windows, Haar Features, and Boosting

Classification vs detection: adding the word 'where'

In the last two guides we built a machine that answers one question about a whole picture: 'Is this a face?' Feed it a tightly cropped photo and it returns a single label. That is classification, and it is the final box in the classical recognition pipeline you already know: turn the image into a feature vector, then hand that vector to a classifier. But real photos are not tidy crops. A holiday snapshot might contain three faces, a dog, and a lot of sky. Classification has no vocabulary for that scene, because it can only say one word for the entire frame.

Detection adds a second, harder question: not just what is in the image, but where — and there may be many answers. The answer to 'where' is a bounding box: four numbers (for example the left, top, width, and height) that draw a tight rectangle around one object. A detector's output is therefore a list of boxes, each tagged with a label and usually a confidence score. Detection is strictly harder than classification because it must localise every instance, and it must not invent boxes where nothing is there.

Here is the beautifully simple bridge from one to the other. If you already have a good classifier, you can turn it into a detector by asking it the same question over and over at every possible location. Slide a small box across the image — left to right, top to bottom — and at each stop crop out that sub-window and run the classifier on it. Wherever the classifier shouts 'face!', you record a box. This is sliding window detection, and conceptually that is the whole idea: detection becomes classification applied to millions of little windows.

One more idea we need from the start: how do we even say a predicted box is 'correct'? A detector rarely lands a box on the exact pixel; it gets close. So we measure overlap between the predicted box and the true box with a number called Intersection-over-Union (IoU) — roughly, how much the two rectangles agree, on a scale from 0 (no overlap) to 1 (perfect). We will define it precisely in the final section, but keep it in mind: IoU is the yardstick both for deciding which boxes count as hits and, later, for cleaning up duplicate detections.

Sliding windows and image pyramids

Let us make the search concrete. Pick a fixed window size — say 24×24 pixels, the size Viola-Jones actually used for faces. Place that window at the top-left corner, crop the pixels under it, turn them into a feature vector, and score them with the classifier. Then slide the window over by a few pixels (the stride) and repeat. When you reach the right edge, drop down a stride and start the next row. Sweep the whole image this way and you have asked the classifier a question at every position the window can sit.

But a 24×24 window can only ever match a face that is about 24 pixels tall. A face filling the whole frame would never fit inside it. The fix is an image pyramid: keep the window the same size, but repeatedly shrink the image — say by 10–20% each step — and rescan at every smaller copy. A big face that was too large in the full-resolution image becomes 24 pixels tall a few levels down the pyramid, where the window finally matches it. Stacking the original plus its shrunken copies looks like a pyramid, hence the name. So 'try all sizes' becomes 'try all positions, at every level of the pyramid'.

Each window, at each level, follows the same little pipeline: crop → feature vector → classifier → a score. Collect every window whose score clears a threshold and you have a raw list of candidate boxes. That is a complete, working detector. The only problem is speed — and to see how bad it is, let us count.

A back-of-the-envelope cost for naive sliding-window detection.

Read this as: the total amount of computation is roughly the number of window positions times the number of scales times the cost of judging one window. Here W and H are the image width and height in pixels, so W·H counts (with a stride of 1) how many places the top-left corner of the window can sit — for a 640×480 image that is about 300,000 positions. S is the number of pyramid levels you scan, perhaps 10–30. And c is the cost to extract features and score a single window. The factors multiply because the work is nested: for each scale you visit every position, and at each position you pay the full per-window cost c. Plug in numbers — 300,000 × 20 × c — and even a cheap c of a few thousand operations explodes into tens of billions of operations per frame. On 2001 hardware that is hopeless for real time. Notice exactly two knobs we can turn: shrink c (make each window cheaper to evaluate) and shrink the effective number of windows by rejecting most of them almost instantly. Viola-Jones attacks the first with Haar features and the integral image, and the second with the attentional cascade.

# Naive sliding-window detector over an image pyramid (pseudocode)
boxes = []
scale = 1.0
img = original_image
while img.height >= WINDOW and img.width >= WINDOW:   # build the pyramid on the fly
    for y in range(0, img.height - WINDOW, STRIDE):
        for x in range(0, img.width - WINDOW, STRIDE):
            patch    = img[y:y+WINDOW, x:x+WINDOW]    # crop one window
            features = extract(patch)                 # -> feature vector
            score    = classifier(features)           # -> confidence
            if score > THRESHOLD:
                # map the box back to ORIGINAL-image coordinates
                boxes.append((x/scale, y/scale, WINDOW/scale, WINDOW/scale, score))
    img   = shrink(img, factor=0.83)                  # next pyramid level (~20% smaller)
    scale = scale * 0.83
# 'boxes' still has many overlapping duplicates -> cleaned up later by NMS

Haar-like features and the integral-image trick

Instead of a generic feature vector, Viola-Jones uses an extremely cheap family called Haar-like features. Each one is just a pattern of adjacent white and black rectangles laid over the window. Its value is the sum of the pixel brightnesses under the white rectangles minus the sum under the black rectangles. That single number measures a contrast: a two-rectangle feature responds to an edge (bright beside dark), a three-rectangle feature to a line (a dark stripe between two bright areas), and a four-rectangle one to a diagonal or centre-surround pattern.

Why would such crude patterns find faces? Because faces share robust local contrasts. The eye region is reliably darker than the cheeks just below it — so a two-rectangle feature with a dark band over the eyes and a bright band over the cheeks fires strongly on almost any upright face, regardless of skin tone or identity. Likewise the bridge of the nose is brighter than the eye sockets on either side, which a three-rectangle 'line' feature captures. No single feature is a face detector, but a handful of them, in the right places, paint a recognisable signature.

But here is the catch that nearly kills the idea. Within a single 24×24 window you can place these rectangle patterns at every position and size, giving over 160,000 possible features. And you must evaluate the chosen ones inside every sliding window at every scale. Naively, summing the pixels under a rectangle means adding up all the pixels inside it — a 12×12 rectangle is 144 additions — and you would redo that work for overlapping rectangles billions of times. That is exactly the per-window cost c we needed to crush.

The rescue is the integral image (also called a summed-area table). Before doing any detection, we precompute, for every pixel location, the sum of all pixels above and to the left of it — including the pixel itself.

Definition: each integral-image cell holds the sum of the whole rectangle above-and-left of it.

In words: I(x',y') is the brightness of the original pixel at column x', row y'. The sum runs over every pixel whose column x' is at most x and whose row y' is at most y — that is, the entire rectangular block from the top-left corner of the image down to (x,y). So II(x,y) is one running total: 'everything up and to the left, added up.' If the bottom-right pixel of the image holds II, it equals the sum of the whole image. Computing II directly from the definition would itself be slow, but there is a one-pass recurrence.

The integral image is built in a single sweep using its neighbours.

This builds II from values we already computed for the cells just left, just above, and diagonally up-left. Intuitively: the block above-and-left of (x,y) is almost the block to its left, II(x−1,y), plus the block above it, II(x,y−1). But those two blocks overlap — they share the entire region above-and-left of (x−1,y−1), so that shared corner gets counted twice. We subtract II(x−1,y−1) once to cancel the double-count, then add the current pixel I(x,y) itself. The result: the whole integral image is filled in one pass, a constant amount of work per pixel. Pay this cost once per image (or per pyramid level), then reuse it for every window.

Any rectangle's pixel sum from its four corners — four lookups, regardless of size.

This is the payoff. Label a rectangle's corners A (top-left), B (top-right), C (bottom-left), D (bottom-right). II(D) is the sum of everything up-and-left of the rectangle's far corner — that big block already contains our rectangle but also three unwanted strips. II(B) removes the tall block above the rectangle; II(C) removes the wide block to its left. But the corner region above-and-left of A has now been subtracted twice (it sat in both B's block and C's block), so we add II(A) back once. What remains is exactly the rectangle's sum — computed with four array lookups and three arithmetic operations, no matter how big the rectangle is. A 4×4 rectangle and a 400×400 rectangle cost the same. This is O(1) per rectangle, and it is the single trick that turns the per-window cost c from hundreds of additions into a tiny constant — the reason real-time detection became possible at all.

A tiny worked example. Take a 3×3 patch of brightnesses, row by row: top [1, 2, 3], middle [4, 5, 6], bottom [7, 8, 9]. Its integral image (each cell = sum above-and-left, 1-indexed) comes out as top [1, 3, 6], middle [5, 12, 21], bottom [12, 27, 45] — and indeed 45 is 1+2+...+9, the whole sum. Now ask for the sum of just the bottom-right 2×2 block {5,6,8,9} = 28. Using the corner rule with that rectangle's corners: D is the bottom-right cell II=45, B is the cell just above-right of the block II(row1,col3)=6, C is the cell just left-below the block's start II(row3,col1)=12, and A is the diagonal cell II(row1,col1)=1. Then 45 − 6 − 12 + 1 = 28. It matches, with four lookups instead of adding the four pixels — and the saving only grows as rectangles get larger.

AdaBoost: a committee of simple rules

We now have cheap features but no classifier yet. Viola-Jones builds one with boosting, and specifically AdaBoost. The atom of the system is a weak learner: take one Haar feature, compute its value, and compare it to a threshold — 'if the eye-band-minus-cheek-band contrast exceeds θ, vote face, else vote not-face.' That is a one-line rule. On its own it is barely better than a coin flip; it might be right 55% of the time. The magic is combining hundreds of such weak rules into one strong one.

AdaBoost works in rounds. Start with a labelled training set of face and non-face windows, and give every example an equal weight. In each round: (1) search the whole feature pool for the single weak learner that does best on the currently weighted examples; (2) compute its weighted error and convert that into a vote weight; (3) increase the weights of the examples it got wrong, so the next round is forced to focus on the hard cases its predecessors keep missing. After many rounds, the final 'strong' classifier is a weighted vote of all the weak learners chosen along the way.

The strong classifier is a weighted vote of T weak learners.

Decode it piece by piece. The input x is one image window. Each h_t(x) is the t-th weak learner's verdict, an output of +1 ('face') or −1 ('not face'). The number α_t (alpha) is that learner's vote weight — how loud its voice is in the committee. We sum the signed votes α_t·h_t(x) over all T rounds, then take the sign of the total: if the weighted votes lean positive, H(x) = +1 and we declare a face; if negative, not a face. So a learner with a big α_t can sway the decision, while a weak voice barely nudges it. The magnitude of the sum before the sign even doubles as a rough confidence score, useful later for ranking boxes.

A learner's vote weight grows as its weighted error shrinks.

Here ε_t (epsilon) is the weak learner's weighted error in round t — the total weight of the examples it misclassifies, a number between 0 and 1. The formula turns that error into the vote weight α_t. Read the ratio (1−ε_t)/ε_t as 'how often right versus how often wrong.' If a learner is nearly perfect, ε_t is tiny, the ratio is huge, the log is large and positive, and α_t is big — a strong voice. If the learner is at chance, ε_t = 0.5, the ratio is 1, ln(1) = 0, and α_t = 0 — its vote is ignored, which is right, since it knows nothing. Crucially ε_t must be below 0.5: a learner worse than a coin flip would give a negative α_t. (That is actually fine — a negative weight just means 'trust the opposite of what it says' — but the convention is to pick learners better than chance.) A quick number: ε_t = 0.2 gives α_t = ½·ln(0.8/0.2) = ½·ln 4 ≈ 0.69.

Re-weighting: examples the round got wrong become more important next round.

This is the step that makes later learners specialise. D_t(i) is the weight of training example i going into round t — how much attention the algorithm pays it. The true label y_i is +1 or −1, and h_t(x_i) is what the round-t learner predicted for that example. Look at the product y_i·h_t(x_i): if the learner was right, true and predicted signs match, the product is +1, and the exponent −α_t·(+1) is negative, so exp(...) < 1 and the weight shrinks. If the learner was wrong, the signs disagree, the product is −1, the exponent −α_t·(−1) = +α_t is positive, exp(...) > 1, and the weight grows. So every round the spotlight swings onto the examples just missed, and (because α_t scales it) confident mistakes are punished hardest. The '∝' means we then renormalise all the weights to sum to 1.

The attentional cascade: be lazy on purpose

We have made each feature nearly free (integral image) and each classifier accurate (AdaBoost). But we still face millions of windows per frame, and even a fast strong classifier of, say, 200 features run on every one of them is too slow. The Viola-Jones detector adds one more idea that is almost philosophical: be lazy on purpose. The overwhelming majority of windows — sky, walls, shirts — are obviously not faces. It would be foolish to spend 200 features ruling each of them out. We should spend almost nothing on the easy rejects and save the effort for the rare, ambiguous windows.

The mechanism is the attentional cascade, also called a Haar cascade classifier. Arrange a sequence of stages, each itself a small AdaBoost classifier, in order of increasing complexity. A window is fed to stage 1; if stage 1 rejects it, we stop immediately and the window is declared not-a-face — no further stages run. Only if it passes does it go on to stage 2, then stage 3, and so on. A window must pass every stage to be finally declared a face. It is a gauntlet of checkpoints: fail any one and you are out; survive all of them and you are in.

The clever part is the ordering. The first stage uses very few features — Viola-Jones famously used just two in stage 1 — tuned to be extremely lenient: it must almost never reject a true face, but it happily throws out, say, 50% of background windows at a glance. Since most windows are background, that one cheap test eliminates roughly half of all work instantly. Each later stage uses more features and is stricter, but it only ever sees the small fraction of windows that survived all the earlier filters. The expensive 200-feature reasoning runs only on the rare promising candidates, not on the millions of obvious rejects.

Overall detection and false-positive rates are the products of the per-stage rates.

These two products explain why a cascade can be both lenient at each step and tight overall. K is the number of stages. For stage k, d_k is its detection rate (the fraction of true faces it correctly lets through) and f_k is its false-positive rate (the fraction of non-faces it wrongly lets through). Because a window must survive all stages, the chances multiply, just like passing a series of independent gates: the overall detection rate D is the product of every stage's d_k, and the overall false-positive rate F is the product of every stage's f_k. Put in numbers: design 10 stages each letting through half the background, f_k = 0.5. Then F = 0.5^10 ≈ 0.001 — only about one background window in a thousand survives to the end, even though no single stage was strict. Meanwhile keep each d_k very high, say 0.995; then D = 0.995^10 ≈ 0.95, so we still catch about 95% of faces. That is the cascade's whole bargain: a tiny false-positive rate from many gentle filters, without throwing away the real faces.

Cleaning up: non-maximum suppression and scoring detectors

Run the cascade and you get a messy result: around each real face the detector fires on a cluster of overlapping windows — slightly shifted, slightly rescaled versions all clearing the bar. One face produces a dozen near-duplicate boxes. We want exactly one box per face, so we need a cleanup step. That step is non-maximum suppression (NMS): among a pile of overlapping boxes, keep the strongest and suppress the rest that overlap it too much.

To say 'overlap too much' precisely we reuse the IoU from Section 1. Here is its definition.

Intersection-over-Union: the shared area divided by the combined area of two boxes.

A and B are two boxes. The intersection A∩B is the overlapping region — picture sliding one rectangle over the other; the small rectangle where they cover the same pixels is the intersection, and its area is its width times height (zero if they do not touch). The union A∪B is the total area the two cover together, counting the shared part only once; a handy way to get it is area(A) + area(B) − area(A∩B), subtracting the intersection so it is not double-counted. IoU divides the shared area by the combined area, giving a number from 0 (no overlap at all) to 1 (the boxes coincide exactly). A quick feel: two identical boxes give IoU = 1; two boxes that half-overlap give something like 0.3–0.4; boxes that barely graze give near 0. The beauty is that a single threshold on IoU does two jobs in this guide — it decides which boxes NMS suppresses as duplicates, and (in evaluation) whether a predicted box overlaps a true box enough to count as a correct detection.

1. Collect all candidate boxes the detector fired, each with its confidence score, and pick an IoU threshold (commonly 0.5).
2. Sort the boxes by score, highest first.
3. Take the top-scoring box, accept it as a final detection, and remove it from the list.
4. Compute the IoU between that accepted box and every remaining box; discard any whose IoU exceeds the threshold (they are duplicates of the same face).
5. Return to step 3 with the boxes that survived, and repeat until the list is empty.

This is greedy NMS: at each turn it commits to the current best box and clears away everything crowding it, then moves on. It is greedy because it never reconsiders an earlier choice. The result is one clean box per object — the highest-scoring representative of each cluster. (One pitfall: set the IoU threshold too low and you suppress genuinely separate faces standing close together; too high and you keep duplicates. The threshold is a knob to tune for the scene.)

Finally, how do we say a detector is good? We extend the evaluation framework from Guide 2 straight into detection. First, match each predicted box to a ground-truth box using IoU: a prediction with IoU ≥ 0.5 against an unmatched true box is a true positive (TP); a prediction matching nothing real is a false positive (FP); a real face no prediction covered is a false negative (FN). From those counts come the same two measures as before: precision = TP / (TP + FP), 'of the boxes I drew, how many were real faces?', and recall = TP / (TP + FN), 'of the real faces, how many did I find?'.

There is always a trade-off between the two: lower the detector's confidence threshold and it accepts more boxes — recall climbs but precision falls; raise it and the reverse. Sweeping the threshold across its full range traces out the precision-recall curve (and the closely related ROC curve from Guide 2), summarising performance at every operating point in one picture; the area under it is a single quality number. This is the payoff of the whole arc: the exact same precision/recall language that judged a sliding-window classifier now judges the boxes of a Viola-Jones detector — one consistent yardstick from classification all the way to detection.