Image Alignment
A camera can move or turn between photographs. Matching points gives us evidence of that movement, which we can use to work out how to bring the images into alignment.
17 sections · 15 questions · 4 coding challenges
The arrow keys move between sections too.
How Could We Align Two Views When Some Matches Are Wrong?
BOTIE
Fischler and Bolles introduced RANSAC in 1981 for model fitting in the presence of gross errors, with applications including image analysis and cartography. Instead of assuming every observation deserved equal influence, the method searched for a model supported by a consistent subset.
We fit a candidate transformation from a small sample of matches, then ask how many other matches agree with it. Repeating this can reveal a well-supported transformation despite outliers. The transformation still needs to suit the geometry: one planar mapping cannot generally account for arbitrary three-dimensional parallax. Agreement gives us evidence for alignment under the chosen model, not proof that every correspondence is correct.
Two Photographs Of One Scene
Two photographs of one scene, one taken with the camera tilted. The keypoints lesson found corners that survive a turn, and then showed that its descriptions do not, because a patch of brightness is read in the frame of the picture and turning the picture turns the patch.
We want to line the two pictures up. That needs descriptions that survive the turn, matches between them, and a way to read the camera's move off the matches.
The same corner, turned
A bright corner in the first picture is the same corner in the second, a quarter turn round. Read as a square patch in the picture's frame, the two patches are different arrangements of the same pixels, and a comparison between them fails.
First picture
Turned picture
Direction first, then description, then the move
The detailed lesson gives each corner a direction two ways, ORB's centre of brightness and SIFT's dominant gradient, and reads the patch in that frame two ways, as pixel pairs and as a grid of gradient counts.
It then recovers a planted move from the matches, names the matches that were wrong, and carries the second picture back onto the first, with every number computed on the shared scene.
Explore the full example
Plant a move, turning, scaling and shifting the scene, and watch the method find it again. Compare what it kept with what was actually right, then carry the second picture back and read the difference.
Centre of brightness for the direction, pixel pairs for the reading.
Part 1. What A Turn Does To A Description
The keypoints lesson ends on an admission with a number in it. After a quarter turn of the picture, every corner is found again in exactly the place it should be, with its strength agreeing to the last bit, and the descriptions of the corresponding corners sit 1.443376 apart on a scale whose maximum is 2.0. That is the same distance a square’s top-left corner sits from its own top-right corner. After the turn the descriptor does not recognise a corner as itself. It recognises it as some other corner.
The reason is where the patch is read from. The descriptor is the square of brightness around the keypoint, with its mean removed and its length divided out, and the square is cut with the picture’s up as up. Turn the picture and the brightness around the corner turns with it, so the square is now cut across a different arrangement of the same pixels. Two corners of one square differ from each other in precisely that way, by a turn, so a description that cannot tell a corner from its turned self also cannot tell it from its neighbours.
1. The cost, measured three ways
The bar below is the shape the keypoints lesson’s own checks use, an L rather than a square, because an L has six corners that differ from one another by what surrounds them. It is turned a quarter circle, which is the one turn that lands every pixel exactly on a pixel, so that whatever changes changed because of the turn and not because of any blurring on the way. Each corner is then compared with its turned self under three descriptions.
Reading the six corners twice.
The patch descriptor pays the keypoints lesson’s 1.443376 at every one of the six corners. The two descriptions this lesson builds pay nothing at all, zero bits of 256 and a distance of 0.0, because each is read in a frame that turned with the corner. Hold on to the nearest-other column, though, because it is the other half of what a description is for. Three of the six corners read as zero bits from some other corner too, and Part 3 says why.
Keep in mind
Part 2. A Direction That Belongs To The Corner
If the patch is going to be read in a frame that turns with the picture, the corner has to supply that frame, which means it has to supply a direction of its own. Two usual answers, and both are built from the brightness around the corner, so both turn when it does.
2. The centre of brightness
The first is ORB’s. Take a disc of radius four around the corner and treat every pixel’s brightness as a weight. The weights are heavier on the bright side of the corner, so the centre of mass of the disc sits off its middle, and the direction from the corner to that centre is the direction the corner faces. Written as the two moments of the disc, with the corner at the origin, rows running down and columns running right,
m_right = Σ column × brightness
m_down = Σ row × brightness
direction = atan2(m_down, m_right)The top-left corner of the bar
The corner at row 14, column 14 has brightness below it and to its right and nothing above or to its left. The disc gives equal moments of 25.0 rightward and 25.0 downward, so the direction is an eighth of a turn, 45 degrees measured from pointing right towards pointing down, which is the same convention the gradient field uses. The corner at row 34, column 14 has its brightness above and to the right, moments of 25.0 and minus 25.0, and faces minus 45 degrees. Same arithmetic, opposite sign, which is what a direction that belongs to the corner should do.
3. The dominant gradient
The second is SIFT’s. Instead of asking where the brightness is, ask which way it rises. Every pixel of the disc has a gradient, a direction and a sharpness, from the filters lesson. Sort the directions into thirty-six bins of ten degrees and let each pixel add its sharpness to its bin, weighted by a bell so the pixels nearest the corner count most. The fullest bin is the direction, refined by fitting a parabola through it and its two neighbours so that the answer is not stuck to a multiple of ten.
Reading the discs.
On the top-left corner the histogram has two equal peaks, at bins 18 and 27 with 14.198 in each, because two edges meet there at equal strength and the brightness rises across both, rightward across the left edge and downward across the top one. The refined directions come out at 5.54 degrees and 95 degrees. Neither is the centroid’s 45, and that is fine. A direction is only required to turn with the corner, not to agree with another rule’s.
Two peaks, two keypoints
4. What a quarter turn does to each
Turn the bar a quarter circle and every centroid direction moves by exactly a quarter circle, with no rounding at all, because the turn permutes whole pixels and the moments are sums of them. The gradient directions move by a quarter circle to within 4.4e-16 radians, for the same reason one step later, since the turn permutes the gradients and the histogram is a sum of those. Both are the property the frame needs, and both are measured rather than assumed.
Part 3. Reading The Patch In Its Own Frame
With a direction in hand, the patch is read with that direction as its first axis. Whatever is read then comes out the same before and after a turn, because the turn moves the direction and the reading with it. Two readings, matching the two directions.
5. Pixel pairs, one bit each
ORB’s reading is the simplest description there is. Draw 256 pairs of positions inside a fifteen-wide square, once, from a seeded generator, so that every corner in every picture reads the same pairs. Turn the pairs to the corner’s direction, round them to pixels, and for each pair answer one question. Is the first pixel darker than the second? The description is 256 bits, and the distance between two descriptions is how many bits differ, which is a count rather than a length. The pixels are read through a three by three mean, because a single pixel is noisy and a bit flips when it is.
Reading one corner twice.
The corner at row 14, column 14 faces 45 degrees. After the quarter turn it is at row 34, column 14 and faces minus 45 degrees, and the pairs, turned with it, land on the same brightness they landed on before. The 256 bits are identical, zero of them differ, and 96 of them are ones.
6. A grid of gradient counts
SIFT’s reading is the oriented gradients lesson’s idea, turned to the corner. A sixteen-wide square in the corner’s frame is cut into four by four cells, and each cell counts which way the brightness rises in eight directions, every direction measured relative to the corner’s own. Each sample is shared between the two nearest cells along each axis and the two nearest direction bins, in proportion to how near it sits, so that a sample on a cell boundary does not jump whole from one cell to the other under a change of a fraction of a pixel. The 128 counts are normalised to unit length, any entry above 0.2 is clipped so that one sharp edge cannot dominate, and the result is normalised again. Two readings are compared by ordinary distance.
On the same corner the two histograms, before and after the turn, are at distance 0.0, as the roses above show cell by cell.
7. What neither can do
Read in its own frame, a bright right-angled corner is a bright quadrant, whichever corner of the bar it is. Within the seven pixels the pairs reach, the top-left corner, the bottom-left corner and the bottom-right corner of the bar’s upright are bit-identical to each other, which is the zero in the nearest-other column of Part 1. The histogram’s wider square sees to where the bar’s arms end and still tells them apart, by 0.306, which is small beside the 1.138 that separates the concave corner from its nearest neighbour but is not zero.
That is the repeated-structure problem the keypoints lesson names, now with a reason. A rotation-invariant description cannot distinguish two things that differ only by a rotation, and two convex corners of one shape differ only by a rotation. What breaks the tie is context, and context is what a wider patch buys. The ratio test refuses the three ambiguous corners under the binary reading, at a ratio of exactly one, rather than guessing.
In a model
Check yourself
Questions on Parts 1 to 3
Question 1 of 5
After a quarter turn the patch descriptor from the keypoints lesson no longer finds the corner at all.
Part 4. Matching Across The Turn
Matching is the keypoints lesson’s ratio test, unchanged. Each description in the first picture finds its nearest in the second, and the match is kept only when the nearest is enough nearer than the second nearest, at Lowe’s threshold of 0.8. It applies to a count of bits exactly as it applies to a distance, since it compares two of the same thing.
8. The opening move
The playground’s opening move turns the shared scene by thirty degrees and shifts it three pixels down and five to the left, about the middle of the frame. Thirty degrees lands no pixel on a pixel, so the turned picture is resampled and nothing about it is exact, which is the case that matters. With the centre of brightness and the pixel pairs, the method finds 40 keypoints in each picture and the ratio test keeps 15 matches. Ten of those are right, which the page can say because it planted the move. Five are wrong, and they are wrong for the reason Part 3 gives, since the scene’s square has four corners that look alike in their own frames.
With the dominant gradient and the histogram, the same scene gives 34 matches of which 17 are right, more of both because a symmetric corner is two keypoints under that rule. Either way about a third of what survives the ratio test is wrong, and that is the input the next two parts have to work with.
| Pair of rules | Keypoints | Matches kept | Right | Wrong |
|---|---|---|---|---|
| Centroid and pairs | 40 and 40 | 15 | 10 | 5 |
| Gradient and histogram | 40 and 40 | 34 | 17 | 17 |
The opening move, a thirty-degree turn and a shift of three down and five left. A match is right when the planted move carries its first position to within 1.5 pixels of its second.
9. Turning the ratio test off
Set the ratio threshold to one in the playground and every keypoint keeps its nearest match. On the opening move that is 40 matches of which 16 are right, so the ratio test had refused 25 matches to lose 6 right ones. Whether that trade was worth it is the question Part 6 answers, since what comes next can cope with wrong matches up to a point and not beyond it.
Part 5. Two Matches Fix The Move
A match is a claim that one position in the first picture is one position in the second. If the camera moved rigidly, then every true match is explained by the same move, which here is a turn, a change of scale and a shift. That is a similarity transform, and it has four numbers in it.
second = scale × R(angle) × first + shift
R(angle) = [ cos −sin ]
[ sin cos ]
four numbers: scale, angle, shift down, shift rightTwo matched positions give four equations, two coordinates each, so two matches fix the four numbers exactly. More matches than two make the fit a least-squares one, and the closed form for it is short enough to read.
›The closed form
| Expression | What changed |
|---|---|
| centre both sets of positions on their means | the shift is whatever is left once the turn and scale are known, so it is found last |
| C = (second − mean)ᵀ (first − mean) | the two by two cross-covariance, which holds the turn |
| C = U S Vᵀ, R = U Vᵀ | the singular value decomposition, with a sign fixed so that R is a turn and not a reflection |
| scale = trace(S) / Σ |first − mean|² | the ratio of the spreads, read off the singular values |
| shift = mean(second) − scale × R × mean(first) | what carries the first centre onto the second |
Measured on three positions under a planted turn of 0.6 radians, a scale of 1.3 and a shift of four down and two left, the recovered four numbers agree with the planted ones to 1.3e-15, which is the arithmetic and not an approximation. Two positions recover them exactly as well.
Keep in mind
Part 6. Let The Matches Vote
Two matches fix the move, and a third of the matches are wrong. Fitting all fifteen at once would average the wrong ones into the answer. Fitting two at a time and asking the others whether they agree does not, and that is the whole of the method the world calls RANSAC.
10. Every pair proposes, the rest agree or do not
Take two matches, fit the move they imply, carry every first position through it, and count how many land within 1.5 pixels of their matched second position. That count is the pair’s support. Try every pair, keep the pair with the most support, breaking ties by the smaller total error, and refit the move on everyone who supported the winner. The matches that did not support it are the outliers, and they are reported rather than discarded, because which matches were wrong is half of what the method tells you.
Trying every pair.
On the opening move the 15 matches make 105 pairs, of which 104 propose anything, since one pair shares a position and fixes nothing. Twenty pairs explain only themselves. The pairs made of two right matches, 45 of the 104, propose nearly the same move as one another and explain up to ten matches, and ten pairs reach that ten. The winner proposes a turn of 30.51 degrees at a scale of 1.0, and the refit on the ten matches it explains lands at 30.56 degrees, 0.56 from the planted thirty, with the inliers sitting 0.56 pixels on average from where the move sends them.
11. Counting beats averaging
The reason to count agreement rather than average proposals is visible in the bars. A wrong match paired with anything proposes a move almost nobody agrees with, so wrong matches are not outvoted, they are simply never elected. An average would have let all five wrong matches pull on the answer; the vote lets them propose and then ignores them. With few matches every pair is tried in a fixed order, so the answer is the same on every run; with many, a seeded sample of pairs is tried, which is what the name describes.
Check yourself
Questions on Parts 4 to 6
Question 1 of 5
On the opening move the centroid and pairs keep 15 matches. How many are right, and why are the others wrong?
Part 7. Carrying The Picture Back
A recovered move is a claim about where every pixel went, and the claim can be checked by using it. Carry the second picture back through the inverse of the move, reading each output pixel from where it came from by interpolating between its four neighbours, and lay it over the first. If the move is right the two pictures agree almost everywhere.
12. One number for the whole alignment
The mean absolute difference between the first picture and the second is 0.1755 on the opening move. After the second is carried back by the recovered move it is 0.0187, a drop of more than nine tenths, and what remains is the resampling, twice over, plus the half-degree the turn is off by. With the gradient and histogram pair the recovered turn is 29.86 degrees, 0.14 off, and the difference after is 0.0186. Set the turn to a quarter circle and the whole chain becomes exact again, 32 matches of 32 right, a recovered turn of 90.0 degrees, and a difference after of 0.0.
13. The method’s verdict against the truth
The playground draws a two-by-two count that no method can draw for itself, because the page planted the move and the method did not. Down the side, whether the method kept a match as an inlier or refused it as an outlier. Across the top, whether the match was right. On the opening move the ten inliers are the ten right matches and the five outliers are the five wrong ones, with nothing in the two cells that would mean a mistake. Shrink the scene to 0.8 and turn it forty degrees and the count changes. Eleven matches, seven right, nine kept, so two wrong matches were kept because they happened to land within 1.5 pixels of where the move sends them, and the recovered turn is still 39.97 degrees.
| Move | Matches | Right | Kept | Kept and right | Turn recovered | Difference after |
|---|---|---|---|---|---|---|
| Turn 30, shift (3, −5) | 15 | 10 | 10 | 10 | 30.56 | 0.0187 |
| Scale 1.25, turn 25, shift (2, −3) | 13 | 7 | 7 | 7 | 25.3 | 0.0293 |
| Scale 0.8, turn 40, shift (−4, 2) | 11 | 7 | 9 | 7 | 39.97 | 0.0299 |
| Scale 1.6, turn 20 | 4 | 2 | 2 | 2 | 19.95 | none |
The centroid and pairs on four planted moves. The last row recovers the move from two matches, which is the fewest that can, and carries nothing back because two inliers leave no outlier to test the claim against.
Part 8. Where It Stops Working
14. A change of size
Nothing in Parts 2 and 3 handles a change of scale. A corner seen from twice as far away has a patch half the width, and a reading over a fixed fifteen pixels sees different things in it. The table in Part 7 shows how much the readings tolerate on this scene anyway, a scale of 1.25 or 0.8 with seven right matches, and 1.6 with two, which is the edge. ORB’s answer is a pyramid, the picture at several sizes, each 1.2 times smaller than the last, with keypoints found and described at every size so that a corner seen from further away is described at the size where it looks as it did.
Building the pyramids.
On the opening move, where the scale does not change, the pyramid measured worse than expected and the reason is worth knowing. Six levels find 126 keypoints where one level finds 40, because every corner is found again at each neighbouring size, and those copies are each other’s runners-up. The ratio test then refuses the true match, and six of 32 matches are right where ten of 15 were. The move is still recovered, from the six. So the pyramid is kept for the changes of size a single level cannot reach and is not switched on by default.
15. A change of viewpoint
Two photographs from one spot with the camera turned are related by four numbers. Two photographs from two spots are related by eight, a perspective transform, and a four-number fit of an eight-number move explains the matches near one part of the scene and not the rest. The vote then elects whichever part had the most keypoints, which is an answer, but not the one asked for. Fitting the eight numbers needs four matches a proposal and the same vote, and it is the usual next step.
16. Repeated structure
A brick wall, a window grid, a keyboard. Every corner reads the same in its own frame, the ratio test correctly refuses every match, and the method answers nothing rather than something wrong. That is the better of the two failures and is still a failure, and a wider patch helps only until the structure repeats at that width too.
Part 9. Implementation And Failure Contracts
Every refusal is by name and happens before an answer could be wrong. A disc or a turned pattern that would read outside the picture is refused with the border a detection needs to avoid it, rather than padded with invented pixels. A reading of one kind cannot be compared with a reading of the other, and two binary readings from different pair patterns cannot be compared either, since the bits would not mean the same thing. A set of readings mixing kinds is refused at construction.
A move cannot be fixed from fewer than two matches, and two matches that share a position on either side fix nothing, so a set of matches in which every pair shares a position is refused by name rather than answered with a transform that explains nothing. A scale that is not positive, an angle that is not finite and a ratio threshold outside the half-open unit interval are each refused where they are given.
What is deliberately absent is said as plainly. No sub-pixel refinement of a keypoint’s position, no scale space finer than the pyramid’s levels, and no learned pair pattern, which are what separate these readings from their reference implementations. The two refinements that cost nothing and matter are kept, sharing each sample between neighbouring cells and bins rather than rounding it into one, and refining the orientation peak with a parabola rather than taking a bin’s centre.
Check yourself
Questions on Parts 7 to 9
Question 1 of 5
The mean pixel difference between the two pictures of the opening move falls from 0.1755 to 0.0187 once the second is carried back. What accounts for the 0.0187 that remains?
Try it with Botie
Build with Botie
Write and run Python