Keypoints and Descriptors

The scene above is 48 pixels on a side, and it holds a square, a disc, a diagonal bar, three copies of a small cross and a brightness ramp that makes the left side of it darker than the right. Photograph it twice, moving the camera a little between the two, and the question that matters is which position in the first picture is which position in the second.

Answering it by describing every position is the obvious plan. It is expensive, and the more serious trouble is that most of the descriptions it produces do not distinguish anything from anything.

A five-wide patch fits at 1,936 of the scene’s 2,304 pixels, so the obvious plan writes down 1,936 descriptions. When I counted how many of those are distinct, only 815 were. The remaining positions share a description with at least one other position, 1,179 of them in all, and the largest group that agree exactly runs to 86 positions. Those 86 cannot say where they came from, however carefully they are compared, because there is nothing to compare that differs.

It is worth watching that happen rather than taking it. Put a bright square on dark ground, cut a five-wide patch from the middle of its left edge, and then slide a window down that edge one row at a time, measuring how far what the window sees is from the patch we cut. Five of the fifteen stops come out at a distance of exactly zero.

Not nearly zero; the same numbers in the same order. Slide the same window past the corner instead and exactly one stop matches, which is the corner itself.

…

This is the aperture problem, and the name is a good one. Look at a long edge through a small hole and you can see when it moves across itself and not when it moves along itself, so the hole gives you one of the two numbers you wanted and there is nothing to be done about the other. A corner shows through the same hole as two edges at once, and moving it in any direction changes what the hole sees.

So the method has three stages and they are worth naming before any of them is built. Score every position by how firmly a window there is pinned, and keep the few best. Describe what surrounds each of the kept ones, in a form that does not move when the lighting does. Then match one picture’s descriptions against another’s, keeping only the matches that were not close calls. The rest of this page is those three stages, in that order, and then what they cost and where they stop.

Take the square again and look at three positions on it, one corner, one point in the middle of an edge four pixels clear of any corner, and one patch of empty ground. At each of them, draw the nine gradient vectors inside a three by three window, each arrow pointing the way brightness rises there and as long as brightness rises fast. The three drawings are the whole argument of this part, and they say it before any arithmetic does.

…

On flat ground there are no arrows. Along the edge every arrow points the same way, to the right, because that is the only direction in which anything is changing. At the corner some arrows point right and some point down. What separates the three is how many directions the change comes in, which is a statement about the spread of the arrows rather than about their length, and the middle drawing has arrows quite as long as the corner’s.

A spread of directions is awkward to hold, and it turns out that three numbers hold it exactly. Square the across gradient, square the down gradient, multiply the two together, and average each of the three over the window. Those three averages arrange themselves as a small symmetric matrix, one per pixel, and every corner measure ever proposed reads that matrix and nothing else.

across energy  =  average over the window of ( across × across )
shared term    =  average over the window of ( across × down )
down energy    =  average over the window of ( down × down )

                 [  across energy    shared term  ]
    the matrix = [                                ]
                 [  shared term      down energy  ]

across energy  =  (1² + 1² + 3² + 3² + 4² + 4²) / 9  =  52 / 9  ≈  5.777778
down energy    =  (1² + 3² + 4² + 1² + 3² + 4²) / 9  =  52 / 9  ≈  5.777778
shared term    =  (1×1 + 1×3 + 3×1 + 3×3) / 9      =  16 / 9  ≈  1.777778

across energy  =  (6 × 4²) / 9  =  96 / 9  ≈  10.666667
down energy    =  0
shared term    =  0

That last point is easy to read as a smoothing step, a tidying-up applied to numbers that would have worked anyway, and it is not. Take the window down to a single pixel and the matrix at every position becomes one gradient vector multiplied by itself, which describes one direction because one vector is all it was given. Any score that asks for two directions is then zero everywhere by construction. Scored that way, the square has no corners, and neither has any other picture.

…

The second row of that drawing is the honest answer, four places on a picture with four corners. The first row is a one-pixel window, which finds nothing anywhere. The rows below are wider windows, which is a different failure and is the subject of Part 7.

A symmetric matrix of this size is completely described by two numbers, its trace and its determinant, and its eigenvalues follow from those two by the quadratic formula. That is worth saying because no measure below ever computes an eigenvalue as such. Every score on this page is read off the same two pictures, one holding a sum and one holding a difference of products.

trace        =  across energy + down energy

determinant  =  across energy × down energy − shared term × shared term

eigenvalues  =  ( trace ± √( trace² − 4 × determinant ) ) / 2

The trace is the total amount of change in the window, whatever direction it is in, and the page calls it the total energy from here on. The determinant is the product of the two eigenvalues, so it is large only when both of them are, and the page calls it the shape term, since knowing about shape is the whole of what it adds. The next part is what happens when each of the two is asked to find a corner.

Start with the trace, since it is the obvious candidate and the one most people reach for. It is the total gradient energy in the window, so it is zero on flat ground and large wherever brightness is changing. On the square it reads 11.555556 at the corner and 10.666667 in the middle of the edge, which are the numbers from the worked example above added up.

A corner beats an edge by a factor of 1.083333. On this square, which is as clean as a picture gets, a threshold anywhere between 10.666667 and 11.555556 does separate the two, and that gap is the whole of what the energy has to offer. The energy grows with the square of the contrast, so an edge with five per cent more contrast than this one already outscores the corner, and the ordering holds only while every edge in the picture is as sharp as every other.

Now the determinant, and here the numbers stop being close. The corner reads 30.222222. The middle of the edge reads 0.0, and it is worth being careful about what kind of zero that is. It is not a small number that rounding could have moved; it is zero because of what the matrix is.

Flat ground gives zero for a duller reason, which is that all three averages are zero there. So the determinant reads 0.0 at the edge and 0.0 on flat ground, and the number it gives at the corner is more than thirty times either.

Put those two together and the smaller eigenvalue falls out. It is the direct answer to the question the method asked, since a window is pinned in both directions exactly as far as the weaker of the two directions is pinned. On the square it reads exactly 4.0 at each of the four corners, exactly 0.0 along each of the four edges, and exactly 0.0 on the ground outside and inside.

trace        =  5.777778 + 5.777778  =  11.555556
determinant  =  5.777778 × 5.777778 − 1.777778 × 1.777778  ≈  30.222222

trace² − 4 × determinant  ≈  133.530864 − 120.888889  =  12.641975
√12.641975  ≈  3.555556

smaller eigenvalue  =  (11.555556 − 3.555556) / 2  =  4.0
larger eigenvalue   =  (11.555556 + 3.555556) / 2  ≈  7.555556

smaller eigenvalue  =  (10.666667 − √(10.666667² − 4 × 0)) / 2  =  0
larger eigenvalue   =  (10.666667 + 10.666667) / 2  =  10.666667

I had expected a middling number in the middle row and there is not one, and that is the most interesting thing on this page. An edge is not partway between a corner and empty ground. It scores what empty ground scores, because it is exactly as unlocatable along its own length as empty ground is in every direction, and a measure that ranked it higher would be putting keypoints precisely where a keypoint cannot be pinned.

Harris and Stephens wanted the same answer without the square root, and the score they wrote down subtracts a multiple of the squared energy from the shape term. It is large and positive where both directions change, near zero where nothing does, and negative where exactly one direction changes.

Harris score  =  determinant − sensitivity × trace²

On the square that is 24.880988 at the corner, 0.0 on flat ground and −4.551111 along the edge, so an edge scores below empty ground rather than above it. The subtracted term has nothing to bite on where the energy is zero and a great deal to bite on along an edge. Both measures are saying the same thing in their own words, and neither of them puts an edge above the ground.

Those three figures use a sensitivity of 0.04, and each is one subtraction from numbers already worked above.

corner  =  30.222222 − 0.04 × 11.555556²  ≈  30.222222 − 5.341235  ≈  24.880988
edge    =  0 − 0.04 × 10.666667²          ≈  −4.551111
ground  =  0 − 0.04 × 0²                  =  0

The sensitivity is the awkward part. It is a number with no principled value, and the guidance in the literature amounts to somewhere between 0.04 and 0.06. It also has a ceiling that is a fact rather than a convention. The determinant of a real symmetric matrix is at most a quarter of its squared trace, so from a sensitivity of a quarter upward the score cannot be positive anywhere, whatever the picture holds. Just below that, at 0.24, the square’s own corners read −1.825185 and nothing is found at all.

A corner is a few pixels across and the window is three pixels wide, so the score around a corner is a blob rather than a spike. On the square, 32 pixels score above a threshold of 0.5, which is four corners reported eight times each. The repair is to work downward from the strongest score and refuse any later candidate lying within a few pixels of one already taken, and because it works downward, anything kept was the strongest thing within its own radius without a second pass being needed to check.

…

On the square, a separation of two takes 32 answers to 4, and so does every larger separation up to seven. On the workbench scene, 457 pixels score above 0.05 and the same rule takes that to 446 at a separation of one, 101 at two, 47 at three and 16 at seven. Nine tenths of what the scoring stage produces on this scene is the blob around a place rather than a place, so the suppression is carrying most of the work of turning a picture into a short list.

There is one more rule, and it is the one that hides a bug. A description is a patch cut around a place, so a place too near the frame has no patch to cut, and those places have to be left out. The obvious way to write that is to drop them from the candidates before the suppression runs, and the obvious way is wrong.

…

Dropping a candidate first means the corner inside the border never gets to suppress anything, so the pixel on its shoulder survives and is reported in its place. On a square whose corners sit two pixels from the frame, at a border of three, that answers four places rather than one, three of them a single pixel off, scoring 3.5556 where the corners they stand beside score 4.0.

The count looks right, the strengths look plausible, and every position is wrong. The rule that works is to let a place inside the border suppress its own neighbourhood and then decline to report it.

We now have a short list of places, and the list on its own is worth very little. The whole reason for finding them was that two photographs of one scene put the same corner at different positions, so the position is the thing being solved for and cannot be the thing that is matched. What travels between two photographs is what surrounds the corner.

So the description is the square of brightness around the place. Five pixels on a side, which is twenty-five numbers, read row by row. Left there it would be useless, because turning a lamp up adds to every one of those numbers and moving a lamp closer multiplies them, and neither of those changes anything about the scene.

Two steps repair both. Subtract the patch’s own mean from every one of its numbers, which removes anything that was added to all of them. Then divide by the length of what is left, which removes anything that multiplied all of them. What remains is a direction rather than a quantity, and two of them can be compared by the straight-line distance between them, a distance running from zero for two identical patches to two for a patch against its own exact opposite.

centred      =  patch − mean of patch

description  =  centred / length of centred

distance     =  length of ( one description − the other )

…

mean = 9 / 25 = 0.36
centred bright pixel = 1 − 0.36 = 0.64
centred background pixel = 0 − 0.36 = −0.36
squared length = 9 × 0.64² + 16 × (−0.36)² = 5.76
length = √5.76 = 2.4

bright entry = 0.64 / 2.4 ≈ 0.266667
background entry = −0.36 / 2.4 = −0.15

It is worth checking that they buy what they promise rather than assuming it. Add ten to every pixel of the picture and the description of that same corner moves by 1.2 × 10⁻¹⁵. Multiply every pixel by three and it moves by 2.0 × 10⁻¹⁶. I expected both of those to be exactly zero and they are not, because the subtraction and the division are done in floating point and their last bits do not always land where the algebra says.

On a scale whose maximum is 2, moving by 10⁻¹⁵ is nothing, but it is rounding rather than identity and the difference is worth stating.

…

The other rows of that drawing are the ones that give the scale its meaning. Two different corners of the same square sit 1.443376 apart. A corner against its own picture with the brightness reversed sits at 2.0, the furthest two descriptions can be. And two patches of flat ground, one outside the square and one inside it, sit at exactly 0.0 from each other, because neither has any variation to normalise and both come back as twenty-five zeros.

That last row is the aperture problem again, now in the description rather than in the score.

gap in one differing entry  =  0.266667 − (−0.15)  =  0.416667
distance  =  √(12 × 0.416667²)  ≈  1.443376

Two claims are worth separating here, because they come out differently and the difference is what this kind of description can and cannot promise. Shift the whole picture down two rows and right three columns. Every place moves by exactly that much, every strength is identical to the last bit, and every description is at distance exactly 0.0 from where it was.

Now increase contrast and brightness while keeping the same scene. The strength scores change under this transformation, while the normalized descriptions remain nearly unchanged.

New pixel value = (1.6 × original pixel value) + 0.15
Strength multiplier = 1.6² = 2.56

The largest change to a description is approximately 1.2 × 10⁻¹⁵, within floating-point rounding for this experiment.

…

Now turn the picture a quarter circle, which is the one rotation that needs no interpolation, so nothing that follows can be blamed on resampling. All 47 places land exactly where the coordinate map says they should, with strengths that agree to the last bit, because the trace and the determinant do not care how the axes are labelled and a square window is unchanged by a quarter turn.

The descriptions do not survive it at all. On the square, all four corners end up 1.443376 from their own turned selves, which is precisely the distance between that square’s top-left corner and its top-right one. On the workbench scene, where the brightness ramp makes no two corners quite alike, the corresponding pairs come out between 0.052724 and 1.545328 apart, and not one of them at zero.

Two pictures are now two short lists of descriptions, and matching them is the obvious search. For each description in the first list, find the nearest in the second. The nearest always exists, whatever the two pictures are of, so the search answers even when it should not, and the only defence is to ask whether the answer means anything.

Asking whether the winner is near is the first thing anybody tries and it does not work. How near is near depends on the contrast of the pictures, the amount of noise in them and the size of the patch, and a threshold tuned on one pair is wrong on the next. There is no number to put there that carries.

Lowe’s rule replaces that question with one that needs no units. Compare the nearest against the second nearest. A place that is genuinely distinctive leaves its runner-up far behind; a place that is one of many similar ones has a runner-up right behind it, and the ratio of the two distances says which of those we are in without ever naming a scale.

ratio  =  distance to the nearest / distance to the second nearest

…

Three arrangements, on the three buttons above. One square photographed twice, moved down four rows and right five columns, gives four matches, each at a distance of exactly 0.0 against a runner-up at 1.443376, so each ratio is 0.0 and each winner is the corner that moved by the known shift. The same square searched for in a picture holding two identical copies of it gives four matches at a distance of 0.0 against a runner-up also at 0.0, which is a ratio of 1.0 and is refused.

Laying a faint ripple over that second picture breaks the exact tie, and the ratios become numbers the arithmetic computed rather than a convention, 0.980729 for the first of them, which is still refused.

The twin squares raise a case the formula cannot evaluate. Both candidates sit at distance exactly zero, so the ratio is a zero divided by a zero and there is no value it takes. It has to be decided rather than derived, and the decision that agrees with what the number means is one, since one is what the ratio says when the runner-up is exactly as good as the winner.

Any other choice does damage. Answering zero would give the most ambiguous case the score reserved for the most distinctive one, so every duplicated shape in a picture would come back as a confident match. That case is not exotic, since a brick wall, a window grid and a keyboard are all made of it.

Run all three stages on the workbench scene against its relit self, which is the easiest test the method will ever be given, since the two pictures are the same scene under a lamp that has been turned up. The detector finds 47 places in each. The ratio test keeps 32 of the 47 matches and refuses 15, and all 15 of the refusals sit on the three identical crosses, which are the one piece of repeated structure in the scene and are correctly declined.

…

Of the 32 it kept, only 26 landed on the position they came from. The other six landed on a corner of a different cross, and the table says why. Every description in this run agrees with its true partner at the level of rounding, so the winner’s distance is around 1.6 × 10⁻¹⁶ and the runner-up’s is around 2.5 × 10⁻¹⁶, and the ratio of two rounding errors is a number that can land anywhere. Here it landed between 0.5726 and 0.7219, comfortably under the threshold, and six coincidences were reported as matches.

The saving is downstream and it is worth being exact about where. Finding the places costs a full pass over the picture whatever happens, since a score has to be computed at every one of the 2,304 pixels before the strongest few can be chosen, and that is one sweep per gradient direction plus one per averaged product. Nothing about keeping 47 answers makes that stage cheaper.

…

What changes is everything after it. Describing every position of this scene is 48,400 numbers and describing the 47 places is 1,175, a factor of 41. Comparing every position of one picture against every position of another is 3,748,096 comparisons and comparing the places is 2,209, a factor of 1,697.

numbers, every position   =  1,936 positions × 25  =  48,400
numbers, the places       =  47 places × 25       =  1,175

comparisons, every position  =  1,936 × 1,936  =  3,748,096
comparisons, the places      =  47 × 47        =  2,209

A description is twenty-five numbers wherever it is cut, so the first saving is just the shorter list. The second is the shorter list squared, because every description of one picture is compared against every description of the other. The two timings in the drawing were measured when this page loaded and will differ from machine to machine, but the counts will not, and the counts are where the argument is.

There is a picture on which the obvious plan beats this one outright, and it is not a contrived one. Photograph a horizon, then photograph it again with the camera three rows lower. The corner score is exactly 0.0 at every pixel of both, so the method finds nothing, describes nothing and matches nothing, and it is right to, since there is no corner anywhere in either picture.

…

Describing every position instead does answer. A five-wide patch fits at 289 positions, of which 221 are flat and indistinguishable, and the 68 that straddle the edge each find their partner in the second photograph at a distance of exactly 0.0 and exactly three rows lower. The vertical move is recovered perfectly by the plan this whole page replaced.

The horizontal move would not be, since every position along the edge looks like every other, so the dense plan has the same aperture problem; it simply does not throw away the one direction it can still see.

Everything above needed six numbers that no part of the mathematics supplies. The width of the averaging window, the threshold on the score, the separation between two kept places, the border, the side of the patch, and the ratio a match must beat. Each of them is a decision about what counts as a corner rather than a setting that could in principle be derived.

The window is the one that bites hardest, because it changes the answer rather than trimming it. Widening it on the square from three pixels to nine takes the score at the top-left corner from 4.0 down to 1.62963, and takes the number of places kept from 4 up to 25, on a picture that has four corners. At nine pixels the window is large enough that two different corners share one, so what the extra twenty-one answers report is the overlap between corners rather than a corner.

Three limits are properties of this description rather than of any particular way of computing it, and it is better to say them plainly than to let a reader assume otherwise, because assuming otherwise produces a plausible answer rather than a complaint.

The patch descriptor on this page records pixels relative to the image frame. Rotate the image and those pixels move to different coordinates within the descriptor, even if we found the same physical point.

To reduce this sensitivity, a more developed method can estimate a local orientation from gradients and describe the patch relative to that orientation. This introduces an extra measurement whose repeatability matters.

Scale creates a related problem: a fixed pixel-sized patch covers a different amount of the scene when the apparent object size changes. Detecting points across several scales and choosing a characteristic scale can make the compared neighborhoods more consistent.

Those orientation and scale stages are not implemented by the small descriptor demonstrated here. Their absence explains the rotation and scale failures in the earlier experiments.

And a corner is a property of brightness rather than of an object. Put a pale block on a lit floor, and beside it a patch of shadow the same size and the same distance from the floor’s brightness, one above it and one below. The method finds eight places and scores every one of them at 0.64, because the score reads the size of the step in brightness and there is nothing else in it to read.

The descriptions do tell the two apart, since reversing brightness moves a description by the full 2.0, but a detector counting corners in a room counts the shadows’ corners among them.

Beneath the choices there are inputs on which the method does not become approximate. It becomes undefined, because some quantity it needs is not there to be had. Each line below is a fact about the mathematics rather than a matter of taste, and several of them are cases where a value has to be decided and something turns on which.