Histogram of Oriented Gradients

Everything on this page is worked on one small scene, 48 pixels on a side, drawn by arithmetic rather than photographed so that we can always say exactly what is in it. There is a square near the top left with four straight edges and four corners, a disc to the right of it whose edge points in every direction there is, a bar running diagonally across the bottom left, and three small crosses scattered about.

Laid over all of that is a ramp of brightness that makes the right-hand side of the scene lighter than the left, so the crosses on the right are brighter than the ones on the left although they are the same shape.

The question the whole page turns on is what we should write down about a patch of that scene so that we could recognise the same thing again somewhere else. The obvious answer is to write down the brightnesses, and the reason that answer fails is worth measuring rather than asserting.

Take that scene and light it differently. Multiplying every brightness by a number and then adding another is roughly what a stronger lamp and a second lamp do to a photograph, and nothing in the scene has moved by so much as a pixel. If our description is the list of 2304 brightnesses, every one of those 2304 numbers is now different.

relit = 1.6 × here + 0.15

Two lists of the same length can be compared one position at a time. Take the difference at every pixel, square it, add the 2304 squares up and take the square root, and the result is one number saying how far apart the two lists are. The same arithmetic on one list by itself, squaring each brightness rather than each difference, gives that list’s own length, which is the yardstick a distance has to be read against, since a distance means nothing until it is set beside how long the lists themselves are. Every distance and every length on this page is measured this way.

apart  = √( Σ over pixels of (relit − here)² )

length = √( Σ over pixels of here² )

Measured, the two lists are 19.52 apart, where the first list’s own length is 21.89. That is 89 per cent of the way to being an unrelated picture, for a change that a person looking at the two would describe as the same scene on a brighter day.

19.52 / 21.89 ≈ 0.89

…

Now read the same two pictures a different way, by asking at each pixel how fast the brightness is changing and in which direction. The added constant does not survive that question at all, since it is added to both of the neighbours whose difference is being taken and cancels out. The multiplier does survive, but it multiplies every rate of change by the same factor, which stretches all the arrows and turns none of them.

On the two pictures above, not one direction turned by more than 6.2 times ten to the minus thirteenth of a degree, which is the arithmetic’s own rounding rather than a real movement, and every rate of change grew by the same factor of 1.60, the smallest and the largest agreeing. So a description made of directions is already untouched by the added constant and off by one overall factor on account of the multiplier.

sum of weights = 0    so    sweep(picture + c) = sweep(picture)

So far nothing has been described. The scene had one number per pixel and now it has two, a length and an angle, which is 4608 numbers where there were 2304. Worse, those numbers are still tied to exact positions, so the same shape drawn one pixel to the left disagrees with the original at almost every position, in the same way the brightnesses did.

What is wanted is a way of keeping the directions, which held still under the lamp, while giving up some of the precision about where each one was, which is what moved when the shape moved. That trade is the whole of the method, and it happens in three stages.

Divide the patch into small squares of a fixed size, 8 pixels on a side by default, and treat each square on its own. Inside one square, throw away where each edge was and keep only which way it pointed, weighted by how sharply the brightness was changing at that pixel. What comes out is a handful of numbers saying that this square holds a great deal of nearly upright edge and a little diagonal, and nothing at all about whereabouts in the square any of it was.

Those squares are called cells, and the handful of numbers is the histogram of that cell. Two pictures whose shapes are two pixels apart inside the same cell produce exactly the same handful of numbers, which is the tolerance we came for, and what it costs is that the description no longer knows where anything was.

A histogram needs a fixed set of direction bins. With unsigned orientations, a direction and its reverse count as the same orientation, so the range is half a circle.

bin width = 180° / 9 = 20°

Each of the nine bins covers a twenty-degree interval.

bucket b covers  [ b × w , (b+1) × w )    and is centred at  (b + 0.5) × w

with  w = 180 / 9 = 20 degrees

So bucket 0 covers everything from 0 up to 20 degrees and is centred on 10, bucket 4 covers 80 up to 100 and is centred on 90, and bucket 8 covers 160 up to 180 and is centred on 170. The centres matter as much as the edges, and Part 3 is about why.

Remember that a direction here is the direction the brightness rises, which is across the edge. An upright edge with its bright side on the right has a direction of 0 degrees, and an edge running left to right with its bright side below has a direction of 90 degrees. When the drawings on this page show a stroke for a bucket, the stroke is turned a quarter circle from the bucket’s own direction so that it lies along the edge, which is what makes a grid of them look like the picture it came from.

Here is the smallest thing worth doing this to. Take a patch 6 pixels square whose left three columns are dark and whose right three are bright, so it holds one upright edge and nothing else, and use cells 3 pixels on a side so that the patch divides into four of them.

…

Two things in that drawing are worth pausing on. The four cells are identical although the weight is at a different place inside them, since the two cells on the left hold theirs in their rightmost column and the two on the right hold theirs in their leftmost, and that is the position tolerance arriving. And each cell’s star is a single stroke lying vertically, because the edge runs vertically even though the direction being counted is horizontal.

A pixel does not vote once. It votes with a weight equal to how sharply the brightness is changing there, so a pixel in the middle of a strong edge counts for a great deal and a pixel in a nearly flat region counts for almost nothing. That is what stops a large area of very slight shading from outvoting the outline that we actually care about.

H(cell, b) = sum over pixels in the cell of  magnitude(pixel) × share(direction(pixel), b)

Multiplying every brightness by 1.6 multiplies every gradient magnitude, and therefore every unnormalized histogram value, by 1.6. The change vector has sixty percent of the original magnitude.

relative change = 1.6 − 1 = 0.6
change in descriptor ≈ 0.6 × 221.49 ≈ 132.89

The measured values match this prediction. Normalization is needed to remove this dependence on overall contrast.

The tolerance is not free, and the price is measurable on three small patches. Draw a bright square 3 pixels across inside a cell, then draw the same square somewhere else inside that same cell, then draw it again over in the next cell along. Both moves change the brightnesses by exactly the same amount, 4.2426, since in each case the square is drawn clear of where it was.

…

The move that stays inside the cell leaves the description at a distance of exactly 0, which is the same vector rather than a nearby one. The move that crosses the cell edge takes it 1.4142 away, out of an answer whose own length is 1, and 1.4142 is the furthest apart two answers of that length can be.

So the same change in the brightnesses produces no change at all in one case and the largest change available in the other, and which of the two happens is decided by where the cell edges were drawn.

with no entry in common     apart² = 1² + 1² = 2     so     apart = √2 ≈ 1.4142

Dropping a vote whole into the bucket its direction falls in is the obvious rule and it has a bad property at the edges of the buckets. Two patches whose edges differ by an arbitrarily small amount, one on each side of a boundary, produce cells with no weight in common at all.

The cleanest way to see it is a picture whose brightness rises along a straight ramp, since the direction is then the same at every interior pixel and is exactly the angle the ramp was drawn at. Turn such a ramp from 19 degrees to 21, across the boundary at 20, and an interior cell’s histogram moves by 724.08 under the whole-vote rule, which is the entire contents of the cell leaving one bucket and arriving in another.

The repair is to look at the two bucket centres nearest the direction and give each of them a share in proportion to how near it is. A direction exactly on a centre gives that bucket everything; a direction a quarter of the way from one centre to the next gives three quarters to the first and a quarter to the second.

position = direction / w

lower = floor(position − 0.5)      upper = lower + 1

share of upper = position − 0.5 − lower       share of lower = 1 − that

At 19 degrees the cell reads 0.55 in the first bucket and 0.45 in the second, and at 21 degrees it reads 0.45 and 0.55. The same two degrees of turn now move it by 72.41 instead of 724.08, and the ratio between those two numbers is 10 to within 4.4 times ten to the minus fourteenth. Two degrees is a tenth of a 20 degree bucket, so a tenth is exactly what ought to move.

…

Now go back to the 6 by 6 patch, whose one edge is upright and whose direction is exactly 0 degrees, and switch the sharing on. Each cell’s 12 of weight comes apart into 6 in bucket 0 and 6 in bucket 8, and nothing anywhere else. That looks like a mistake and it is not one.

…

The first bin centre is ten degrees and the last is 170 degrees. Unsigned orientations wrap around after 180 degrees, making zero equally close to those two centres.

wraparound distance = 180° − 170° = 10°
ordinary distance = 10° − 0° = 10°
weight in each bin = 1/2

The square’s upright edges split their contributions equally between these neighbouring bins. The initial playground cell shows that split.

Compare that with an edge running left to right, whose direction is 90 degrees. That is the centre of bucket 4, so the sharing gives that bucket everything and the two rules agree exactly. What decides the behaviour is how far the direction falls from the nearest centre, and 0 degrees happens to be the furthest a direction can fall from one, which is 10 degrees under this arrangement of buckets.

Nothing has been gained for free. Under whole votes a pure direction lands in one bucket and the cell says with complete confidence which of the nine it was; under sharing the same pure direction is spread over two, and the fullest bucket holds between 0.5 and 1.0 of the cell depending on where the direction fell. So a reader of the description can no longer recover which single bucket a pure direction belonged to, and in return a turn of two degrees changes the answer by something proportional to two degrees.

Drag the slider above to 30 degrees and both rules put everything in the second bucket, since 30 is that bucket’s centre. Drag to 20, which is a boundary rather than a centre, and the shared rule reads a clean half and half while the whole-vote rule reads 0.4531 and 0.5469, because the ramp’s direction is worked out pixel by pixel and lands on either side of the boundary by amounts far below anything the picture could distinguish.

That is what a rule with a jump in it does when handed the jump, and it is why the shared rule is the one worth building on, at the price that no cell ever again reports a direction more precisely than the two buckets it falls between.

The counts in a cell still grow with the contrast of the picture, so we are one factor away from a description that does not read the lamp at all. Removing a common factor from a vector is easy, and the only real decision is which vector to remove it from.

The answer is neither one cell nor the whole patch. Cells are gathered into small groups, 2 by 2 by default, and each group is laid end to end into one vector of 36 numbers and divided by its own length. The 36 is four cells of nine buckets each, and the length is the same square root of a sum of squares that Part 1 used on two lists of brightnesses, so dividing by it leaves a vector of length exactly 1 whatever the contrast of the picture was. A group of cells is called a block, and the reason for choosing that size rather than the whole patch is that lighting across a real photograph is not uniform, so a factor that holds over a 16 pixel square often does not hold over a whole person.

block = ( cell₁ , cell₂ , cell₃ , cell₄ )        36 numbers

rescaled = block / ‖block‖

Here is the sharpest measurement on the page, and it contradicts the way the step is usually described. Rescaling the blocks is said to give the description its tolerance to lighting. Half of that is true. Split the change of lighting into its two parts, the constant added to every brightness and the factor every brightness is multiplied by, and measure each on its own with the rescaling switched off.

Adding 0.15 to every brightness moves the unrescaled description by 8.4 times ten to the minus fourteenth, which is nothing at all. That half was already free two stages earlier, bought by the weights of the sweep adding to nought. Multiplying every brightness by 1.6 moves the same unrescaled description by 132.89, against an answer whose own length is 221.49. Switch the rescaling on and the whole change together moves it by 2.3 times ten to the minus fifteenth.

Push the multiplier to 3.7 and the shift to 12, which is a far more violent relighting than any photograph would receive, and the unrescaled answer moves 598.02 while the rescaled one stays at about ten to the minus fifteenth. The rescaled distance does not grow with the multiplier at all, because the factor cancels exactly and what is left is the rounding of the arithmetic that cancelled it.

Dividing by the length is one choice among several, and all of them remove a common factor, which is the property that matters. They differ in how much weight they leave on a block’s loudest direction relative to its quietest.

Dividing by the sum makes a block add to one, which is the shape of a distribution; taking the square root of that pulls the large entries down towards the small ones and happens to leave the block a unit vector as well. Dividing by the length makes it a unit vector directly. The last row is the default and is the subject of the next step.

One extremely sharp edge inside a block can take almost the whole of that block’s allowance, leaving the weaker directions around it with nearly nothing to say. The default rule makes the block a unit vector, cuts any entry above 0.2 back to 0.2, and then makes it a unit vector again.

unit  =  block / ‖block‖

cut   =  min(unit, 0.2)

answer = cut / ‖cut‖

On the scene, the largest entry of the description falls from 0.9274 under plain division by the length to 0.5376 with the cut, so the loudest direction has lost a little over two fifths of its share and the rest of its block has gained it. What is bought is the ratio between the loudest direction in a block and the quietest, which is what lets a faint edge beside a strong one survive into the answer at all.

The last thing the method does looks wasteful. The blocks do not tile the grid of cells; they step one cell at a time, so a cell away from the border belongs to four different blocks and reaches the answer four times, each time divided by a different denominator.

Overlapping two-by-two blocks reuse cells. In a three-by-three cell grid, each corner belongs to one block, each non-corner edge cell to two, and the centre to four.

cell appearances = 4 × 1 + 4 × 2 + 1 × 4 = 16

The nine cells therefore contribute sixteen sets of histogram values. On the six-by-six scene, thirty-six cells produce one hundred such appearances.

Everything so far has folded a direction together with its reverse, so that 30 degrees and 210 degrees land in one bucket. That was a choice, and it can be made the other way by dividing the whole circle instead of half of it. The difference shows on the simplest fixture there is, a bright bar on a dark ground beside the same bar with its brightness turned inside out.

The bar has two edges, and they are one edge seen from either side, so their directions are exactly opposite. Over half a circle they fall in one bucket and the bar occupies a single bucket of the nine. Over the whole circle they fall in two, centred on 10 degrees and 190 degrees, half the weight in each.

…

The number that decides the choice is the distance between the bar and its inverted twin. Over half a circle it is exactly 0, the same vector to the last bit, so the description cannot see the inversion at all. Over the whole circle it is 1.41421, which is the furthest apart two answers of length 1 can be, so the description sees nothing else. On the whole scene the same comparison gives 4.2 times ten to the minus fifteenth against 5.9899, out of a length of 5.

A person in a dark coat against a bright wall and the same person in a light coat against a dark one produce gradients that point opposite ways along the same silhouette. A description over the whole circle calls those two people as different as two descriptions can be, when the thing a detector has to learn is that they are the same shape, and a description over half a circle hands it both of them as one case.

That is the argument Dalal and Triggs made, and the measurement above is that argument in two numbers.

It is not always the right choice. Where the direction of the contrast is itself information, keeping the whole circle is worth twice as many numbers per cell. Printed text is the obvious case, since light letters on a dark page and dark letters on a light page really are different things and a reader wants to know which, and there the 1.41421 measured above is the useful answer and the 0 is the useless one.

The length of the description follows from the arrangement and nothing else. Divide the sides of the patch by the cell side to get the grid of cells; the block positions along a side follow from the block’s own side and how far it steps; and each block contributes one number per bucket per cell it holds.

cells across = width / cell side          cells down = height / cell side

blocks across = cells across − block side + 1        (stepping one cell)

length = blocks across × blocks down × block side² × buckets

7 × 15 × 4 × 9 = 3780

The pedestrian window holds 8192 brightnesses and its description holds 3780 numbers, which is 0.46 numbers per pixel. So the description is smaller than the picture, though not by much, and it is a great deal larger than the 128 cells it is built from would suggest, because the overlap describes those 128 cells in 420 cells’ worth of numbers.

That is the price a sliding-window detector pays at every one of the many thousands of positions it examines in a photograph, so the arrangement is worth arguing about. Tiling the blocks instead brings the 24 by 24 case from 144 numbers to 36, and what it gives up is the second and third and fourth readings of each middle cell that Part 4 measured.

Every stage above measures a direction from a fixed axis and assigns a pixel to a cell by its fixed position, so turning the patch turns every direction with it and moves every pixel into a different cell. The description is not defined to survive that and it does not.

Turn the scene a quarter circle, which is exact because every pixel lands on a pixel and nothing has to be guessed in between, and the description moves 5.2331 where its own length is 5. The move is larger than the whole answer. Relighting the same scene moves it 2.3 times ten to the minus fifteenth. Those two figures are fifteen orders of magnitude apart, and quoting either one on its own gives a badly wrong impression of what the method does.

…

It would be comfortable to blame the buckets. At 9 buckets a quarter turn is four and a half buckets, so the directions do not land cleanly on new buckets, and one might hope that a count dividing 90 exactly would fix it. It does not. At 6 buckets, where each covers 30 degrees and a quarter turn is exactly three of them, the answer still moves 0.95 of its own length, and no way of rescaling a block brings any of it below 0.98.

The directions are only half of the problem, since the cells have moved as well, and no arithmetic over buckets can undo that.

The cell side is a number a person picks, and once picked it fixes what counts as a small movement. Nothing in the method derives it from the picture, and there is no sense in which 8 pixels is correct. That is a genuine gap rather than an omission, because the right cell size depends on how large the thing being described is in the picture, which is not known until it has been found.

The same fact makes the description depend on scale. An object twice as far from the camera fills a quarter as many cells, so its edges fall across a different arrangement of cells and its description is a different length, which cannot even be compared with the first. Two descriptions of different lengths do not correspond position by position and the distance between them has no meaning, so the comparison is undefined rather than merely poor.

The usual repair lives outside the method. Resize the picture several times over, run the whole thing at each size, and keep whichever answer scored best. That turns one description into a family of them and turns the cost measured in the last Part into that cost times the number of sizes tried.

Where the brightness is flat in both directions the rate of change is nought in both directions, and the angle of a vector of length nought does not exist. Every implementation has to answer something, and the reasonable answers are to record nought degrees, to record nothing at all, or to refuse. Since the vote is weighted by the magnitude, a pixel like that votes with weight nought whichever answer is chosen, so the choice is invisible in the counts.

A flat image region creates a zero gradient histogram. Normalizing that histogram requires care because its length is zero, and direct division by that length is undefined.

We therefore need a stated policy. We can leave a zero block unchanged, stabilize the denominator with a small positive constant, or reject the block. The first two preserve a useful interpretation, which is that this region has no measured edge structure.

The stabilizing constant also affects nearly flat regions, where dividing by a tiny length could amplify numerical noise. In the displayed uniform scene, the accumulated gradient weight is zero and the implementation returns a zero descriptor.

The cut at 0.2 is applied to a unit vector and the block is then made a unit vector again, so the cut entry is divided by a length that the cut itself made smaller. Whenever the cut removed anything at all it comes back above 0.2, and the arithmetic says so before any picture is involved.

original length = √(8 × 6²) = √288 ≈ 16.9706
normalized nonzero entry = 6 / √288 ≈ 0.353553
clipped nonzero entry = 0.2
clipped length = √(8 × 0.2²) ≈ 0.565685

0.2 / 0.565685 = 0.353553

On the scene, where the entries are not all equal, the cut does change the answer and still does not enforce the limit. The largest entry falls from 0.9274 to 0.5376, which is nearly three times the limit it was cut to. And the number of entries in the whole description above 0.2 rises from 170 to 248, because making each block a unit vector again lifts everything that was not cut.

What the step does is move weight from the loud entries of a block to the quiet ones, and the 0.2 governs how much moves rather than where any entry ends up.