Haar Cascades

Suppose we are looking for a bright band in a twelve-pixel-square patch. The band could appear at many locations in a larger picture. A straightforward baseline slides that window one pixel at a time and checks every position where it fits.

A scene sixty-six pixels square holds 3,025 such positions, and that number is fixed before we have decided anything at all about how the question is answered.

That is already the whole difficulty in miniature. Whatever we do to answer “is the band here”, we are going to do it three thousand times over on a scene the size of a postage stamp, and a real photograph is a thousand times larger and has to be searched at several sizes as well. So the first thing to settle is how little a single answer can be made to cost, and how accurate the answer is comes after that.

What we want to ask about a window is something like whether its middle rows are brighter than the rows above and below them, and to ask that we have to add up the brightness inside each of those regions. Adding up a rectangle costs one addition per pixel, so the cost of a question grows with the size of the region it asks about.

That is the wrong way round. A large region is exactly the one worth asking about, since it averages away the speckle, and it is the one that costs most.

It is worth seeing how badly wrong. On a picture six hundred pixels square, timing two thousand repetitions of each, adding up a one-pixel box and adding up the whole picture differ by a factor of between 107 and 130 across the six runs I measured. The box holds 360,000 times as many pixels and the arithmetic underneath is vectorised, so the ratio is far below the count of pixels, and it is still two orders of magnitude.

The method on this page is the Viola and Jones detector, which everybody calls a Haar cascade, and it is three separable ideas that happen to fit together. The first is a table of running totals that makes any rectangle’s sum cost four lookups whatever its size, so the cost of a question stops depending on how large a region it asks about.

The second is a family of very crude readings built out of those sums, each of them the total over some bright cells minus the total over some dark ones. The third is an ordering, in which the readings are grouped into stages and a window that fails a stage is dropped without the later stages ever seeing it.

Each of the three is worth having on its own, and the third is the one the method is named for. We take them in that order, because the second is only affordable given the first, and the third only becomes necessary once we have counted how many readings the second offers.

Take the picture and build a second grid the same shape, in which the entry at a given row and column is the total of every pixel that lies above it and to the left of it, itself included. Nothing about that is clever; it is a running total in two directions instead of one, and it can be filled in with a single pass over the picture in which each entry is read off from its three already-filled neighbours.

table[r, c] = picture[r, c] + table[r−1, c] + table[r, c−1] − table[r−1, c−1]

The last term is there because the region above and the region to the left overlap in the whole corner above and to the left of both, so that corner would otherwise be counted twice. In practice the table is built one row and one column larger than the picture, with that extra first row and column holding zeros, which is not padding for its own sake.

It is what lets a box touching the top edge be read by the same expression as a box in the middle, rather than by three special cases for the boxes whose first row or first column is zero.

Now take any box at all. The entry at its bottom-right corner holds everything above and to the left of that corner, which is the box plus a strip above it, plus a strip to its left, plus the corner region above and left of both. Subtract the entry at the top-right corner and the strip above goes; subtract the entry at the bottom-left corner and the strip to the left goes; the corner region has now been taken away twice, so add the entry at the top-left corner back.

sum over the box = table[bottom, right] − table[top, right] − table[bottom, left] + table[top, left]

Four reads and three additions, and not one of them mentions the size of the box. The widget below draws that on a picture whose pixel at row r and column c is 10r + c, so no two boxes can accidentally total to the same number and every sum can be worked out on paper, and on the workbench scene the rest of this section of the site uses. Drag on the picture to move the box, and watch the four lit entries move with it.

box sum = bottom-right − top-right − bottom-left + top-left
        = 340 − 10 − 124 + 1
        = 207

(12 + 13 + 14) + (22 + 23 + 24) + (32 + 33 + 34) = 39 + 69 + 99 = 207

…

Blue entries are added and red ones taken away. Look at what happens when the box is dragged to the top-left corner, where two of the four entries fall into the border of zeros and the expression is unchanged.

The claim that a rectangle total is a constant cost is easy to state and easy to believe for the wrong reason, so it is worth counting rather than asserting. A box of one pixel names four table entries. A box of 360,000 pixels names four table entries. That is not a saving of a factor of a few; it is the removal of the size of the box from the cost altogether.

Timed rather than counted, on the same six hundred pixel square picture, the table answered the whole-picture box in between 1.01 and 1.11 times what it took on the one-pixel box across six runs, where adding the pixels up took between 107 and 130 times as long. The small residue in the first figure is the cache, since the four entries of the large box are four corners of a large table and the four entries of the small box sit next to each other.

…

The timing is run afresh when the page is first opened, so the two ratios move by a few percent from one visit to the next. What does not move is the third column of the table.

The table is not free. It is one pass over the picture, and it allocates a grid slightly larger than the picture to hold the answer, so a search that only ever reads a handful of rectangles is better off adding pixels up and never building it. Measured on the six hundred pixel square picture, building the table took about 6,900 microseconds where one whole-picture read off the table took about 1.4 and adding the pixels up took about 171, so the table repays what it cost after roughly forty whole-picture reads and is a loss before that.

For the search this page is about, forty is nothing. There are 3,025 window positions and each of them reads several rectangles, so the table has repaid itself before the sweep has crossed the first row. It is worth saying plainly all the same, because it is the one place where the obvious alternative wins, and the condition under which it wins is roughly forty reads.

Given that any rectangle total is now cheap, the detector never reads a pixel again. What it reads is a small arrangement of neighbouring boxes, all the same size, some of which are added and some subtracted, and the number that comes back is the total over the added ones minus the total over the subtracted ones.

A reading of that kind says something about contrast between neighbouring regions, which is roughly what survives when the light in the room changes, where the raw brightness of a region says almost nothing that a lamp cannot change.

A reading is fixed by five things and nothing else. Which layout of cells it uses, how far down and how far across its top-left corner sits inside the window, and how tall and wide one cell is. The position is measured from the window’s own corner rather than the picture’s, which is what lets one reading be evaluated at every window position of a scene from a single table built once over the whole scene.

The original paper uses five layouts, and it is worth seeing what each answers on a picture with four pixels on a side. Two cells side by side, or two stacked, answer the question of whether there is an edge running one way or the other. Three in a row, or three in a column, set the middle cell against both flanks and so answer whether there is a strip or a band.

Four in a chequer sets one diagonal pair against the other, which neither of the first two kinds can see at all.

…

Here is something the textbook description of these readings usually leaves out, and it is not a small thing. Two cells added against two subtracted cancel exactly, so a layout with as many added cells as subtracted answers zero on a picture with no contrast in it at all, however bright that picture is. The three-cell layouts have one added cell against two subtracted, and they do not cancel.

Measured on a flat four by four picture with one-pixel cells, the two-cell layouts and the chequer answer 0.0 whether the picture reads 0.25 or 0.9, and both three-cell layouts answer −0.25 on the first and −0.9 on the second. So two of the five readings move when the lamp moves, which is the opposite of the property the whole family was chosen for.

This is not a slip in the arrangement, it is what the original paper describes, and the original paper answers it by normalising each window’s variance before any threshold is compared against anything. No such normalising happens here, so on this page the three-cell readings are the ones that would break first under a change in lighting, and Part 6 measures what that costs.

value on a flat picture = n b × (sum of the cell signs)

Since a reading is fixed by a layout, a position and a cell size, and every combination that fits inside the window is a legitimate reading, we can count them without building them. For a layout of r by c cells at a cell size of h by w, the reading is rh tall and cw wide and therefore fits at (H − rh + 1) times (W − cw + 1) positions, and the total is that summed over every cell size that fits at all and then over the five layouts.

cells 1 tall, 1 wide   (2 − 1 + 1) × (2 − 2 + 1)  =  2 positions
cells 2 tall, 1 wide   (2 − 2 + 1) × (2 − 2 + 1)  =  1 position

two cells side by side  =  2 + 1  =  3 readings

3 + 3 + 0 + 0 + 1 = 7 readings, on 4 pixels

A twenty-four-by-twenty-four window has far more candidate Haar features than pixels. The counts grow rapidly as the window grows.

pixels = 24 × 24 = 576
features per pixel = 162,336 / 576 ≈ 281.83

Even the small playground scene would be expensive if every feature were evaluated at every window position.

exhaustive evaluations = 3,025 windows × 10,344 features
                       = 31,290,600

The later stages select a small subset of useful features and reject many windows early.

…

Both counts are drawn on a scale where each step up is a factor of ten. Look at the gap between the two lines opening as the window grows.

One more thing about reading these values, which I did not expect and which is worth a paragraph because the conclusion runs the wrong way. A reading’s value is a total over its cells, and there are two natural ways to write that total. One adds the cells one at a time; the other hands the whole run to the language’s own summing, which since Python 3.12 compensates its rounding over a run of floating point numbers and is therefore more accurate.

Over 200 readings taken on five small pictures, the two totals disagreed on exactly one of them, by 2.2 times ten to the minus sixteen. The accurate total was −0.8391149931171449 and the one-at-a-time total was −0.8391149931171447. That is the last bit of a double and would be beneath notice anywhere else, and it is not beneath notice here, because a stage’s threshold is chosen to sit exactly on one of these values.

Set the threshold at the accurate total and ask whether a reading is above it, and the accurate route says no while the one-at-a-time route says yes. The two routes have to round identically or a rule chosen on one and applied on the other lands on the wrong side of its own threshold, so the accurate spelling is the wrong one and both routes here add one cell at a time.

This is the only method in this part of the site that is fitted rather than designed, so it needs examples. The target here is a bright band four rows deep across the middle of a twelve by twelve window, jittered one row up or down, laid over a cluttered ground and finished with a little speckle.

A background is that cluttered ground with no band in it. The clutter is blocky rather than per-pixel, in three by three blocks, and that choice is load-bearing, since per-pixel noise averages away inside the very first rectangle total and would have left the two classes trivially apart.

There are 50 targets and 2,000 backgrounds. That ratio is not an accident of the fixture, it is the ratio the method exists for, because a detector’s negatives are every window of every picture that is not the thing, and there are always vastly more of them than there are of the thing. The fit searches 600 readings drawn at random from the 10,344 the window admits, which is what a real implementation does for the same reason, since a search over a random subset finds rules very nearly as good for a fraction of the arithmetic.

The classifier the detector is built out of is the smallest thing that can be called a classifier. Take one reading, compare it against one number, and answer yes on one side of that number. It is the same object as a single split in a decision tree, written in the vocabulary of a window rather than of a column of data.

rule(window) = yes if reading(window) > threshold, otherwise no

A rule like that is barely better than a coin, and it is meant to be. On its own it separates almost nothing, since one contrast in one place is weak evidence about anything. What makes it useful is that it costs four lookups per cell to evaluate, and that a great many of them can be combined.

A stage is built by boosting. Give every training window a weight, half the total spread across the targets and half across the backgrounds; search every candidate reading and every threshold for the rule with the smallest weighted error; give that rule a voice worked out from how much better than guessing it was; then multiply the weight of every window it got wrong, so the next round is judged mostly on what the first one failed at. Repeat for as many rounds as the stage is allowed.

voice = ½ ln((1 − weighted error) / weighted error)

That expression is positive exactly when the rule is wrong on less than half the weight, which for two classes is exactly when the rule beats guessing, and it grows without bound as the error falls to nothing. A rule that would earn a voice of zero or less ends the stage instead of joining it, since a rule no better than a coin drags the vote rather than sharpening it.

The starting weights matter here in a way they do not for a plain boosted classifier. By the third stage the surviving backgrounds are a handful against every one of the fifty targets, and weights spread evenly over the rows would let a first rule score well simply by answering yes to everything. Splitting the weight half and half between the two classes stops that.

Now the part that makes a stage a stage rather than a classifier. A boosted vote ordinarily accepts a window when the rules that voted yes hold at least half the total voice. A cascade stage is allowed to lower that demand, and only to lower it, until the stage keeps every target it was trained on.

The reasoning is asymmetric on purpose. A background that gets through only means the next stage has a little more to look at, whereas a target that is dropped is gone, since no later stage ever sees it.

demand = min(½, the smallest share of the voice any training target attracted)

The consequence is that no stage is any good on its own, and that is the design rather than a shortfall. A filter tuned to keep everything of one class necessarily keeps a good share of the other. What a stage is for is to throw away some fraction of what reaches it, cheaply, and the accuracy is supposed to come from the fractions multiplying.

total voice  ≈  3.3737

only the louder rule says yes    1.8067 / 3.3737  ≈  0.5355
only the quieter rule says yes   1.5669 / 3.3737  ≈  0.4645
both say yes                     1
neither says yes                 0

Fitting on that set gave three stages holding five rules between them, two in the first, two in the second and one in the third. The first stage was handed all 2,000 backgrounds and threw away 1,895 of them, which is 94.75 percent. The second was handed the 105 that survived and threw away 102. The third was handed 3 and threw away all 3, at which point there was nothing left to fit a fourth stage on. All fifty targets came through every stage.

…

Each rule is drawn where it reads, added cells in blue and subtracted ones in red. Switch between a target and a background and notice that the first stage’s two rules both straddle the middle rows, which is where the band is.

The shape of those numbers is what the method is named for. Each stage is boosted on the backgrounds that survived the ones before it, so each in turn faces a smaller and harder problem and finds rules that are correspondingly more particular. The first stage’s two rules are cheap and general; the third stage’s single rule reads a pair of two by two cells stacked against the right-hand edge of the window, which is a question you would only ask of something that had already got past two other stages.

Fitting numbers flatter, so here is a fresh draw of the same fixture, 2,000 new backgrounds and 50 new targets, walked through the same three stages. The backgrounds fall 2,000 to 117 to 3 to 1, and the targets fall 50 to 47 and then not at all.

…

Read the two funnels together. The left one falls steeply, which is what the cascade is for, while the right one stays nearly flat, which is what the calibration bought.

The first stage on its own lets 117 of 2,000 fresh backgrounds through where all three together let 1, which is the whole argument for having three. The shares one stage passes to the next are 0.0585, then 0.0256, then 0.3333, and multiplying those three gives 0.0005, which is the 1 in 2,000 that arrives at the end.

Overall the fresh draw is scored at 0.998 accuracy, 0.94 recall and 0.9792 precision, and the recall is the honest cost of the calibration, which keeps every target it saw and promises nothing about a target it did not.

All three scores come from the two ends of the funnels. Of the 50 fresh targets 47 are accepted, and of the 2,000 fresh backgrounds 1 is accepted and 1,999 are turned away.

recall     =  47 / 50                  =  0.94
precision  =  47 / (47 + 1)            ≈  0.9792
accuracy   =  (47 + 1,999) / 2,050     ≈  0.998

The accuracy is the least informative of the three here. A detector that turned every window away would score 2,000 out of 2,050 on the same draw, because the backgrounds outnumber the targets forty to one.

Everything so far could have been assembled into a single boosted classifier of five rules that runs all five on every window. The cascade instead runs the first stage on every window, the second only on what survived the first, and the third only on what survived the second, so what a window costs on average is each stage’s rule count weighted by the share of windows that reach it.

rules per window = Σ over stages of (rules in the stage × share of windows reaching it)

The first share is always one, since every window meets the first stage, and the later shares are small if the earlier stages are doing their job. So the total approaches the first stage’s own cost however many stages follow it, which is why a detector of six thousand readings can end up costing what a detector of ten costs. It is also why the stages have to be in increasing order of expense, since the same three stages in the opposite order would run the expensive one on everything.

Sweeping the fitted detector across the sixty-six pixel square scene in the playground, one pixel at a time, 3,025 windows enter the first stage, 235 reach the second and 137 reach the third. That is 7.8 percent and 4.5 percent of the windows. The cheap stage runs on everything and the later ones run on almost nothing, and those three counts are what the whole method comes to.

expected rules ≈ 2 × 1 + 2 × 0.0777 + 1 × 0.0453 ≈ 2.2007
measured rules = 6,657 / 3,025 ≈ 2.2007

Broken out by stage, that is 6,050 evaluations in the first stage, 470 in the second and 137 in the third, so 6,050 of the 6,657 readings taken, which is 91 percent of them, are the two cheapest rules in the whole detector.

There are several things the sweep could be compared against and they give very different numbers, so it is worth setting all four beside each other rather than quoting whichever is most impressive.

…

The second row is the honest comparison for the ordering alone, holding the rules fixed, and it is only a factor of 2.27. That is worth saying plainly rather than hiding behind the last row, because the saving from ordering is bounded by how many rules there are to skip and this cascade has five of them.

A window rejected by the first stage skips at most three rules. The published detector has thirty-eight stages and over six thousand readings, and a window rejected by its first stage skips essentially all of them, which is where the famous numbers come from.

The last row is the comparison the method actually exists to win. Answering “is the band here” by measuring every reading the window admits, at every position, is 31,290,600 readings for this one small scene, and the cascade spent 6,657. That ratio grows with the window, because the count of readings grows faster than the area does.

Of the 3,025 windows, 111 survive all three stages, and all three planted targets are among them. Twenty-eight of the 111 sit within two pixels of one of those targets, which is the same target accepted several times over at neighbouring offsets, and the other 83 are patches of ground that happen to be brighter across their middle than above and below it.

That is what a three-stage cascade is, rather than a failure of this one. Each stage keeps every target and therefore keeps a fair share of the backgrounds, and the three shares of 0.0777, 0.583 and 0.810 multiply to 0.0367, which is small without being anywhere near zero. The answer is more stages, each multiplying the survival share down again, which is why the published cascade has thirty-eight of them and not three.

A real detector also merges the clusters of overlapping acceptances into one box per target, which nothing here does, so the 28 near-misses would be reported as three finds and not twenty-eight.

Every reading in this family is signed. A layout that says “the added cells are brighter than the subtracted ones” answers a large positive number on that pattern and a large negative number on the same pattern with bright and dark exchanged, and a rule thresholding it in one direction therefore rejects the exchanged pattern outright.

There is nothing gradual about it, and the method has no way to express “this contrast, either way round”, because the reading it is built from has a sign and the rule it is built into has a direction.

Measured on fifty of the same targets with bright and dark exchanged, the detector finds 0 of 50, where fresh upright ones are found 43 of 50. Following one reading through says why. The first rule’s layout answers −7.1856 on one target and 7.3344 on that same target relit, and the rule votes yes when the reading is at or below −2.6449, so it votes yes on the first and no on the second.

…

The three panels are the same fifty targets presented three ways. The two zeros are exact rather than rounded.

The same argument applies to orientation, by a different route. The layouts are axis-aligned, and the layout of two cells stacked and the layout of two cells side by side are different members of the family, so a rule that reads one of them has nothing at all to say about the other. Turning the target a quarter does not weaken the evidence the fitted rules read; it moves the evidence into readings those rules never look at.

The measurement is 0 of 50 again, on the same fifty targets with the band running down instead of across.

This is a fact about the family of readings rather than about any fit, and it is why real implementations fit one cascade per pose and run several of them. That is an honest statement about how little the method generalises, since a description that needs a separate fitted model for every orientation is not describing orientation at all.

The cost expression in step 19 says the speed comes from the shares of windows reaching the later stages being small, and those shares are a property of the scene rather than of the detector. On a scene in which most windows are the thing being looked for, almost nothing is rejected early and the ordering buys almost nothing.

…

The same detector, the same ground, and the only difference is how much of each scene is target. Watch the average cost climb towards the ceiling of five rules a window.

Measured, a window costs 2.1597 rules on ground with no target in it, 2.2007 on the scene with three planted, and 2.6552 when the ground is tiled edge to edge with them, while the saving over running the same five rules everywhere falls from 2.315 to 1.883. The ceiling is five rules a window and a saving of exactly one, which is what a scene entirely made of targets would cost, and at that point the flat classifier is the better arrangement because it does the same work without the per-window bookkeeping of deciding whether to continue.

This is the only regime measured on this page where the obvious alternative wins.

It is tempting to say the detector has learned what a band looks like. What it has learned is that certain rectangles of the window tend to be brighter than certain neighbouring ones, and that is a statement about contrast and not about an object. Anything with the same coarse pattern of contrast satisfies it, which is exactly what the 83 windows of plain clutter accepted in step 22 are.

This is the limit that no amount of extra training moves, because it is in the vocabulary rather than in the fit. The readings can express “brighter here than there” at every position and size, and they cannot express anything else, so any two things that agree on every rectangle contrast are indistinguishable to any cascade built from them however many stages it has. What extra training buys is a longer list of contrasts to check, which shrinks the set of things that pass without ever changing the kind of fact being checked.

Finally, the inputs on which there is no answer to give, or on which the answer is a decision rather than a consequence. These are facts about the method and not about any particular program, and where there is a genuine choice it is worth knowing what turns on it.

The last of those is the one most often glossed over, and it is worth being precise about what the table does and does not buy. Because a rectangle total costs four lookups whatever the size of the rectangle, growing every cell of a reading by a factor costs nothing extra, so searching several sizes costs the same per size rather than more for the large ones. What it does not do is remove the need to search them.