Journey of Curiosity Arshad Kazi
← All Days

Day 1 · Fri, Nov 6 · 4,272 words · 19 min

SIFT: detecting and matching keypoints across images

Before any geometry, two photos have to agree on landmarks: this speck here is that speck there. SIFT finds points that survive zooming, turning and changes of light, and gives each a 128-number fingerprint.

TangentWhat is SIFT, anyway?

SIFT, the Scale-Invariant Feature Transform, is David Lowe's method for finding distinctive points in an image and describing them so the same points can be found again in another image. First published at ICCV in 1999, then in full in 2004 as Distinctive Image Features from Scale-Invariant Keypoints, one of the most cited papers in computer vision.

What goes in, what comes out. In: a greyscale image. Out: a few hundred to a few thousand keypoints, each with a position $(x, y)$, a size $\sigma$, an orientation $\theta$, and a 128-number descriptor. Two keypoints from different photos with nearby descriptors are probably the same physical point.

Why it mattered. Before SIFT, corner detectors like Harris found points well but couldn't say how big they were, so matching broke as soon as the camera moved closer or further. SIFT made points survive changes of scale, rotation and lighting, and tolerate moderate changes of viewpoint, which is what real photo collections need.

Where it went. It powered panorama stitching, object recognition and, for reconstruction, Photo Tourism (2006), the system that rebuilt landmarks in 3D from internet photos. COLMAP, today's standard structure-from-motion tool, still uses SIFT by default. Its ideas live on in HOG (gradient histograms for pedestrian detection), faster cousins like SURF and ORB, and the learned detectors that replaced it on benchmarks.

The patent. The University of British Columbia held a patent on SIFT, which kept it out of OpenCV's main library for years. It expired in March 2020, and SIFT moved into OpenCV's main module in version 4.4 as cv2.SIFT_create().

  1. 1Features
  2. 2Matching
  3. 3Two-view geometry
  4. 4Triangulation
  5. 5Structure from motion
  6. 6Bundle adjustment
  7. 7Dense reconstruction

Part IScale

1

Creating Gaussian spaces

At different levels and scales

  • Create Gaussian spaces at different levels and scales
$$L(x, y, \sigma) = G(x, y, \sigma) * I(x, y), \qquad G = \frac{1}{2\pi\sigma^2}\, e^{-(x^2+y^2)/2\sigma^2}$$

Think of the image as a landscape of brightness. Blurring it with a Gaussian of size $\sigma$ is like looking through fog that hides anything smaller than about $\sigma$. Sweep $\sigma$ upwards and you get a film: fine texture melts first, then small blobs, then bigger ones, until only broad shading is left. Stack the frames and you have scale space, a 3D volume $L(x, y, \sigma)$.

Why a Gaussian and not any blur? Scale-space theory (Witkin, Koenderink, Lindeberg) shows that the Gaussian is the only kernel that is linear, treats every position and direction the same, and never creates new structure as $\sigma$ grows. A box blur can make ripples appear out of nothing. The Gaussian only ever destroys detail, so a blob found at a coarse scale is really in the image, not an artefact of the blur.

Blurring is diffusion. $L$ obeys the heat equation, $\partial L / \partial \sigma = \sigma \nabla^2 L$: brightness spreads from bright pixels to dark ones like heat. Diffusion changes each point by its Laplacian, how different it is from the average of its neighbours. So the difference between two moments of the diffusion, the DoG, is (to first order) the Laplacian. That's not a coincidence, it's the same equation.

Why the $\sigma^2$? Blurring flattens everything, so derivatives of $L$ shrink as $\sigma$ grows. Raw Laplacian responses at coarse scales would always lose to fine ones. Multiplying by $\sigma^2$ cancels that exactly and puts every scale on equal footing. DoG gets the $\sigma^2$ for free from the heat equation, which is why it can be compared across levels without any correction.

Characteristic scale, intuitively: take a dark disc of radius $r$. The normalised Laplacian at its centre is strongest when $\sigma = r/\sqrt{2}$. Photograph it from half the distance and $r$ doubles, so the peak moves to $2\sigma$. The peak follows the object. That is the whole of scale invariance in one sentence.

TangentWhat is the Laplacian, really?

Short version: the Laplacian at a point measures how different that point is from the average of its neighbours. That's it. Everything else, the blobs, the edges, the heat, follows from that one sentence. Here's how.

Start in one dimension. Take a row of pixels with brightness $f(x)$. The first derivative $f'$ is the slope: how fast brightness changes as you walk along. The second derivative $f''$ is how fast the slope changes: the curvature. Positive $f''$ means the curve bends upwards like a bowl; negative means it bends down like a dome; zero means it's straight.

On a grid you can't take a true derivative, so you take differences. The slope between neighbours is $f(x{+}1) - f(x)$. The change in slope is the difference of two of those:

$$f''(x) \approx \big[f(x{+}1) - f(x)\big] - \big[f(x) - f(x{-}1)\big] = f(x{-}1) - 2f(x) + f(x{+}1)$$

Rearrange it and the meaning jumps out:

$$f''(x) \approx 2\left[\frac{f(x{-}1) + f(x{+}1)}{2} - f(x)\right] = 2\,(\text{neighbours' average} - \text{me})$$

So the second derivative is literally the average of my neighbours minus me, times two. If I'm darker than my surroundings, it's positive. If I'm brighter, it's negative. If I'm exactly in line with them, it's zero.

Try it on numbers. Run the kernel $[1, -2, 1]$ along a few rows:

SignalValuesLaplacian (middle)Reading
flat5, 5, 55 − 10 + 5 = 0nothing here
ramp2, 4, 62 − 8 + 6 = 0a steady slope is not interesting
bright spot2, 9, 22 − 18 + 2 = −14brighter than surroundings
dark spot8, 1, 88 − 2 + 8 = +14darker than surroundings
corner of a step2, 2, 82 − 4 + 8 = +6foot of the edge
top of the step2, 8, 82 − 16 + 8 = −6shoulder of the edge

Two things to notice. First, a ramp gives zero. The first derivative would shout about a ramp; the Laplacian ignores it, because every point on a straight slope is exactly the average of its neighbours. That's why it's good for finding things (spots, blobs) rather than gentle shading. Second, an edge gives a pair: positive at the foot, negative at the shoulder, crossing zero right on the edge.

brightness, blurredLaplacianflat: 0ramp: 0 insidebright spot: deep dipedge: + / − pair
Computed on a real profile: the Laplacian ignores the flat part and the inside of the ramp, plunges at the bright spot, and swings + / − across the edge.

Now two dimensions. An image has two directions to curve in, so add the curvature along $x$ and along $y$:

$$\nabla^2 f = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2} \quad\approx\quad \begin{bmatrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{bmatrix} * f$$

Read the kernel: add the four neighbours, subtract four times the centre. Again, neighbours' average minus me, times four. Same meaning, now in every direction at once.

Adding the two curvatures has a lovely consequence: the Laplacian is rotation invariant. Turn the image and $f_{xx}$ and $f_{yy}$ change individually, but their sum doesn't (it's the trace of the Hessian, and the trace doesn't care about rotation). The Laplacian doesn't know or care about direction. It only asks: am I a peak, a pit, or neither?

The problem: noise. Differences amplify noise, and second differences amplify it twice. On a raw photo, every grain of sensor noise is a tiny spot that differs from its neighbours, and the Laplacian lights up all over. So you blur first, then take the Laplacian. And because both are linear, you can merge them into a single filter:

$$\nabla^2 (G_\sigma * I) = (\nabla^2 G_\sigma) * I$$

$\nabla^2 G_\sigma$ is the Laplacian of Gaussian (LoG). Work it out and you get

$$\nabla^2 G_\sigma(x, y) = \frac{x^2 + y^2 - 2\sigma^2}{\sigma^4}\; G_\sigma(x, y)$$

Look at its shape. At the centre ($x = y = 0$) it's negative. At radius $\sqrt{2}\,\sigma$ it crosses zero. Beyond that it's positive and fades out. It's an upside-down Mexican hat: a dip in the middle surrounded by a ring. As a filter it asks, at every point: is the middle brighter than the ring around it?

Why that finds blobs, and their size. Convolution is template matching: the response is biggest where the image looks like the filter. A bright disc that fits the dip exactly gives the strongest (most negative) response. Too small a disc only fills part of the dip; too large a disc spills into the ring and cancels itself. So for each blob there's one $\sigma$ that fits best, and in 2D it's $\sigma = r / \sqrt{2}$ for a disc of radius $r$. Sweep $\sigma$, find the best response, and you've measured the blob's size. That's exactly what step 2's search across scales does.

Why multiply by $\sigma^2$? Each derivative of a blurred image scales like $1/\sigma$, since blurring stretches everything out and flattens slopes. Two derivatives: $1/\sigma^2$. Without a correction, big blobs at coarse scales would always lose to small ones. Multiplying by $\sigma^2$ cancels that, so a disc of radius 4 and a disc of radius 40 give the same peak response at their own best $\sigma$. That's the scale-normalised Laplacian, $\sigma^2 \nabla^2 G$.

And where DoG comes in. Blurring is diffusion: brightness flows from bright pixels to dark ones like heat. The heat equation says the rate of change at a point is its Laplacian: a point brighter than its neighbours (negative Laplacian) cools down, a darker one warms up. In scale-space form, $\partial G / \partial \sigma = \sigma \nabla^2 G$. So two snapshots of the diffusion, slightly apart in $\sigma$, differ by roughly the Laplacian:

$$G_{k\sigma} - G_\sigma \approx (k - 1)\,\sigma \cdot \sigma \nabla^2 G = (k - 1)\,\sigma^2 \nabla^2 G$$

That's the whole reason SIFT can use a subtraction instead of computing second derivatives: DoG is the scale-normalised LoG, for free, and the constant $(k - 1)$ is the same at every scale so it doesn't move any peaks.

Your eyes do this too. Retinal ganglion cells have centre-surround receptive fields: excited by light in a small centre, inhibited by light in the ring around it (or the reverse). Their response is modelled almost exactly by a difference of Gaussians. Marr and Hildreth (1980) built an edge detector on this idea, using the zero crossings of the LoG as edges. SIFT uses the same filter for the opposite job: not the zero crossings, but the strongest peaks and pits, which are blobs.

And physics. The Laplacian is everywhere because “how different am I from my surroundings” is what drives so much of nature: heat flows down it, a stretched soap film settles where it's zero everywhere (every point is the average of its neighbours), and gravitational and electric potentials are governed by it. In an image, it is the simplest possible question you can ask about a point, and it turns out to be the right one for finding things worth matching.

  • Blurring removes detail smaller than the blur, so a stack of blurs is like stepping further and further back from the scene
  • Levels: each blur is $k$ times the last. With $s$ levels per octave, $k = 2^{1/s}$, so the blur doubles across an octave
  • Octaves: once the blur has doubled, halve the image and start again. Same information, a quarter of the pixels
  • Lowe's settings: $\sigma = 1.6$, $s = 3$, input image doubled first (almost 4× more stable keypoints). Each octave needs $s + 3 = 6$ blurred images
  • Subtract neighbouring blurs to get the Difference of Gaussians, the space keypoints are found in:
$$D(x, y, \sigma) = L(x, y, k\sigma) - L(x, y, \sigma) \;\approx\; (k-1)\,\sigma^2 \nabla^2 G * I$$
  • The approximation comes from the heat equation, $\partial G/\partial\sigma = \sigma\nabla^2 G$. $\sigma^2\nabla^2 G$ is the scale-normalised Laplacian, which responds most to a blob of its own size
  • So DoG is a band-pass filter. A feature peaks at the blur that matches its size, which tells you how big it is as well as where
2

Comparing each space with the one above and below

  • Compare each point with its neighbours, including the spaces above (↑) and below (↓)
  • $(3 \times 3 \times 3) - 1 = 26$

Step 1 gave a 3D volume $D(x, y, \sigma)$. A keypoint is a local extremum of that volume in all three directions at once. A peak in space alone isn't enough: a blob gives a spatial peak at many blur levels, strongest at its natural size and fading either side. Asking for a peak across $\sigma$ as well picks exactly one level, the characteristic scale. So every keypoint comes out as $(x, y, \sigma)$: where it is and how big it is.

Maxima and minima mean different things. At the centre of a bright blob, more blur pulls the centre down, so $D = L(k\sigma) - L(\sigma)$ is negative: bright blobs are minima. Dark blobs are maxima. SIFT keeps both.

Why only the immediate neighbours? $3 \times 3 \times 3$ is the smallest neighbourhood that can define an extremum. Lowe tested how many levels per octave to sample: 3 gave the most repeatable keypoints. More levels found more keypoints, but the extra ones were less stable.

σ·k² (above) σ·k (same level) σ (below) 3 × 3 × 3 − 1 = 26 neighbours 9 above · 8 around · 9 below
A candidate must beat every neighbour in space and in scale.
  • 8 around the point in its own layer, 9 in the layer above, 9 in the layer below
  • A candidate must be larger than all 26 or smaller than all 26. A peak in space means it stands out; a peak in scale means this is the size at which it stands out most
  • Most pixels fail in the first few comparisons. Still thousands of candidates per image, many bad. Steps 3 and 4 clean them up
3

Finding the keypoint: the maximum among the 26

Hessian matrix and Taylor expansion

  • Maximum point among the 26 → Hessian matrix, Taylor expansion → keypoint localisation
$$D(\mathbf{x}) \approx D + \nabla D^{\top}\mathbf{x} + \tfrac{1}{2}\,\mathbf{x}^{\top} H\,\mathbf{x}$$

The grid is coarse. In octave $o$ one sample stands for $2^o$ original pixels, and neighbouring levels are $k = 2^{1/3} \approx 1.26$ apart in $\sigma$. The real extremum of the continuous $D$ lives somewhere between grid points.

The fix is the same trick as finding the top of a hill from a few height measurements: fit the simplest curved surface through them and read off its top. In one dimension that's a parabola through three points. In $(x, y, \sigma)$ it's a quadratic surface, which is exactly what a second-order Taylor expansion is. The Hessian here is the curvature that bends that surface; the gradient is its tilt.

  • The maximum from step 2 is only accurate to one pixel and one blur level. The true peak sits between samples
  • $\mathbf{x} = (x, y, \sigma)$ is the offset from the sample, $\nabla D$ a 3-vector, $H$ the $3 \times 3$ Hessian over $x$, $y$, $\sigma$, all from differences of neighbouring samples
  • Set the derivative to zero to get the peak:
$$\hat{\mathbf{x}} = -H^{-1}\nabla D$$
  • If any part of $\hat{\mathbf{x}}$ is over 0.5, the peak is nearer another sample: move there and refit (OpenCV gives up after 5 tries)
  • The value at the peak, $D(\hat{\mathbf{x}}) = D + \tfrac{1}{2}\nabla D^{\top}\hat{\mathbf{x}}$, is the contrast. Drop the point if $|D(\hat{\mathbf{x}})| < 0.03$ (pixel values in $[0, 1]$): noise could move or erase it
TangentWhy on earth is a Taylor series useful here?

$D$ is a smooth function of $x$, $y$ and $\sigma$, but we only have it at integer pixels and a few blur levels. The true peak is between the samples, so we guess the shape of $D$ near the sample and find the peak of the guess.

A Taylor series is exactly that guess: describe a function near a point from its value and derivatives there. First order is a tilted plane, which has no peak. Second order is the simplest shape that has one, a dome or a bowl. That's why it stops at the Hessian.

In 1D, with three samples $f(-1)$, $f(0)$, $f(1)$:

$$f' \approx \frac{f(1) - f(-1)}{2}, \qquad f'' \approx f(1) - 2f(0) + f(-1), \qquad \hat{x} = -\frac{f'}{f''}$$

That's a parabola through three points. With $f(-1) = 0.60$, $f(0) = 0.80$, $f(1) = 0.70$: $f' = 0.05$, $f'' = -0.30$, so $\hat{x} \approx 0.17$. The peak is a sixth of a pixel towards the bigger neighbour, with value $0.80 + \tfrac{1}{2}(0.05)(0.17) \approx 0.804$.

In 3D the slope becomes a 3-vector and the curvature a $3 \times 3$ matrix, each entry a difference of neighbours, e.g.

$$D_{xy} \approx \tfrac{1}{4}\big[D(x{+}1, y{+}1) - D(x{+}1, y{-}1) - D(x{-}1, y{+}1) + D(x{-}1, y{-}1)\big]$$

and slope over curvature becomes $-H^{-1}\nabla D$: one $3 \times 3$ solve per keypoint.

The 0.5 rule: a Taylor expansion is only trustworthy near where it was built. An offset over half a sample means another sample is closer, and its expansion is better.

Why bother: errors scale with the octave. One pixel in the fourth octave is 8 original pixels, so 0.4 px off there is about 3 px in the image, and that goes straight into triangulation.

4

Filtering keypoints based on edges and corners

The Hessian again, now 2 × 2

  • Hessian of the keypoint:
$$H = \begin{bmatrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$$
  • Two eigenvalues: curvature in the horizontal and vertical directions
  • Corner condition: both eigenvalues will be high
  • Keep the point if:
$$\frac{\operatorname{Tr}(H)^2}{\det(H)} < \frac{(r+1)^2}{r}$$

Picture $D$ near a keypoint as a surface. A blob is a dome: it curves down in every direction. An edge is a ridge, like a long tent: it curves sharply across and stays flat along it.

Put a marble on top. On a dome it's pinned. On a ridge it can roll along the top. That rolling is the instability: noise, or a slightly different viewpoint, moves the detected point along the edge, and the two photos no longer agree on where it is.

The Hessian is the local shape of that surface. Its eigenvectors are the directions of strongest and weakest curvature; its eigenvalues say how strong. Dome: both large, same sign. Ridge: one large, one near zero. Saddle: opposite signs. The test only needs to tell a dome from a ridge, and the trace and determinant are enough for that.

flat α ≈ β ≈ 0 edge α ≫ β corner: keep α and β both large
Keep a point only where the curvature is high in both directions.
  • Why drop edges: DoG fires along edges too, but a point on an edge can slide along it and look the same, so it can't be matched reliably
  • Where the formula comes from: $\operatorname{Tr}(H) = \alpha + \beta$, $\det(H) = \alpha\beta$. Write $\alpha = r\beta$:
$$\frac{(\alpha+\beta)^2}{\alpha\beta} = \frac{(r\beta + \beta)^2}{r\beta^2} = \frac{(r+1)^2}{r}$$
  • $\beta$ cancels, so the test depends only on how lopsided the curvature is: smallest at $r = 1$, growing as the point gets more edge-like. No eigenvalues computed
  • Lowe uses $r = 10$, a threshold of $12.1$. If $\det(H) < 0$ the curvatures have opposite signs, a saddle, so drop it too
TangentWait, there are two Hessians. What's the difference?

A Hessian is the matrix of second derivatives: it measures curvature. SIFT uses it twice, for two different questions.

Localisation · 3 × 3

$$\begin{bmatrix} D_{xx} & D_{xy} & D_{x\sigma} \\ D_{xy} & D_{yy} & D_{y\sigma} \\ D_{x\sigma} & D_{y\sigma} & D_{\sigma\sigma} \end{bmatrix}$$

Over $x$, $y$ and $\sigma$. Asks where exactly is the top of the hill, in space and scale. Inverted to solve for the offset.

Edge test · 2 × 2

$$\begin{bmatrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$$

Over $x$, $y$ only. Asks is it a hill or a ridge. Only its trace and determinant are used.

The 2 × 2 is the top-left corner of the 3 × 3, so nothing new is computed. Scale is left out because "edge" is about shape in the image plane: how the response changes with blur says nothing about line versus point.

Hill or ridge, in numbers, with $r = 10$ so the cut-off is $12.1$:

$D_{xx}$$D_{yy}$$D_{xy}$$\operatorname{Tr}^2/\det$
ridge−0.40−0.02022.1drop
peak−0.30−0.250.024.1keep

Why trace and determinant: they don't change when the image rotates, because they are the sum and product of the eigenvalues. So the test asks how lopsided the curvature is without finding which way the edge runs.

The Harris corner detector asks the same question one derivative lower, using the structure tensor built from first derivatives.

Part IIRotation

5

Handling rotational invariance

Image gradients and a direction histogram

  • Calculate the image gradient:
$$m(x, y) = \sqrt{L_x^2 + L_y^2} \qquad \theta(x, y) = \operatorname{atan2}(L_y, L_x)$$

There are two ways to be rotation invariant. One is to design a description that looks the same at every rotation, which throws information away. SIFT does the other: it measures the patch's own dominant direction and describes everything relative to it.

It's how you'd describe a face: “the nose is below the eyes”, not “the nose is at the bottom of the photo”. Turn the photo and the first description still holds. The orientation is the patch’s own “up”.

Votes are weighted by magnitude so strong edges dominate, and by a Gaussian so the edge of the window, the part most likely to change between photos, counts least.

QuestionWhy do this again at the image level??

TangentWhy gradients again, at the image level?

Short answer: at the keypoint, the DoG has nothing left to say about direction. Long answer, in three parts.

1. The keypoint is an extremum of $D$, so $\nabla D = 0$ there. We chose it precisely because $D$ is flat at the top. Around it $D$ is a dome, so its gradients point straight in or straight out, the same all the way round. A dome has no preferred direction, and a histogram of its gradients is close to uniform. Using $D$ for orientation is like asking a ball which way it is facing.

2. DoG is a second-derivative operator. It approximates the Laplacian, which is rotationally symmetric: it measures how a point differs from its surroundings, not which way the surroundings change. An edge in the image becomes two lobes in $D$, positive on one side and negative on the other, crossing zero on the edge. Gradients of $D$ point in opposite directions on either side, so votes split 180° apart.

3. DoG throws away low frequencies. It's band-pass. The broad shading that says this patch gets brighter towards the top right is exactly what it subtracted out. Orientation needs that.

$L$, the blurred image, keeps all of it. Its first derivatives point across real edges, from dark to light, with a magnitude that says how sharp the edge is. That is what you want to vote with. So the two images play two roles: $D$ is the detector (where and how big), $L$ is the describer (what it looks like).

Why $L$ at the keypoint's own scale, not the original image? Scale invariance has to carry through. A keypoint found at $\sigma = 4$ is a structure about four times bigger than one at $\sigma = 1$. Reading gradients from $L$ at $\sigma = 4$ shows that patch at the same level of detail as the small one, so two photos taken at different distances produce the same gradient pattern. Raw image gradients would be dominated by fine texture the other photo can't even see.

Why $\operatorname{atan2}$: $\arctan(L_y / L_x)$ can't tell $(1, 1)$ from $(-1, -1)$; both give 45°. $\operatorname{atan2}$ looks at both signs, so a dark-to-light edge (45°) is told apart from light-to-dark (225°). Without it, every orientation would be ambiguous by half a turn.

  • Calculate the rotational gradient: a histogram of direction against magnitude
DirectionMagnitude
90°16
180°23
270°25
……
  • Lowe's histogram has 36 bins of 10°. Each pixel votes with its magnitude, weighted by a Gaussian of $1.5\times$ the keypoint's scale
  • The tallest bin is the orientation, refined with a parabola through it and its two neighbours
  • Any other peak within 80% of the tallest creates a second keypoint at the same spot. Here $23/25 = 0.92$, so 180° gets its own. About 15% of keypoints get more than one, and they noticeably help matching

Part IIIDescribe

6

Computing the descriptor

128 numbers per keypoint

  • For each keypoint, choose 4 × 4 → 16 surrounding regions
  • 16 × 16 pixel window → 4 × 4 regions, each with its gradients
  • Divide 360° into 8 bins, which gives 8 values per region
$$8 \text{ bins per region} \times 16 \text{ regions} = 128$$

Why not just store the 16 × 16 pixels? Raw pixels are brittle. Shift the window by one pixel, or change the viewpoint slightly, and every value changes. A histogram is forgiving: a gradient that moves a pixel or two inside its 4 × 4 region still lands in the same region and the same bin.

So the descriptor keeps position only roughly (which of 16 regions) and direction only roughly (which of 8 bins). Precise enough to be distinctive, coarse enough to survive a change of viewpoint. That balance is the whole design.

The idea comes from biology. Lowe cites a model of complex cells in the visual cortex (Edelman, Intrator and Poggio, 1997): neurons that respond to an edge of a particular orientation but don't mind if it moves a little within their receptive field. Matching with that kind of tolerance recognised 3D objects better than matching exact positions.

Why 4 × 4 × 8? Lowe tried grid sizes and bin counts. A 2 × 2 grid wasn't distinctive enough; bigger grids got too sensitive to distortion. 4 × 4 regions with 8 bins matched best, and that is where 128 comes from.

16 × 16 pixels split into 4 × 4 regions → each region: 8 directions (one weather vane per cell) → 8 × 16 = 128 bins per region × regions
Sixteen little weather vanes, each recording which way the gradients blow and how hard.
  • The window is rotated to the keypoint's orientation and directions are measured relative to it. This is where rotation invariance actually happens
  • Votes are weighted by a Gaussian with σ half the window width, so a small position error matters less
  • Each vote is shared between neighbouring regions and bins (trilinear interpolation), so a one-pixel shift doesn't flip a value into another bin
  • Normalise to unit length (cancels contrast; brightness offsets don't touch gradients), clip at 0.2 so glare-driven gradients can't dominate, normalise again

Part IVMatch

7

Matching

Extract descriptors from both images and compare

  • Distance between two descriptors:
$$d(d_A, d_B) = \sqrt{\sum_{i=1}^{128} \left(d_{A,i} - d_{B,i}\right)^2}$$
  • Low ratio test:
$$\frac{d_1}{d_2} < 0.8$$
  • Then RANSAC

Matching is a search in a 128-dimensional space. Every keypoint in image A is a point there; we look for the closest point from image B.

RANSAC is a vote. Each random minimal sample proposes a hypothesis for how the two views are related, and every match votes for or against it. Wrong matches are scattered at random, so they never agree on anything. Right matches all agree on the same geometry. The hypothesis with the most votes wins, and it doesn't matter how wild the wrong matches are.

  • Nearest neighbour alone fails: every keypoint has one, even when it isn't in the other image. A fixed distance threshold fails too, since some descriptors are more distinctive than others
  • $d_1$ is the nearest distance, $d_2$ the second nearest. The test asks for a clear winner; if they're close, the point is ambiguous (repeated windows, texture). Lowe: 0.8 removes about 90% of false matches and loses under 5% of correct ones
  • RANSAC: sample the fewest matches that fix a model, fit, count matches that agree within a few pixels, repeat, keep the model with most inliers, refit on them
  • The model: a homography (4 matches) for a flat scene or pure rotation, the fundamental matrix $F$ (7 or 8) for a general scene, the essential matrix $E$ (5) with calibrated cameras
  • Rounds needed, for inlier fraction $w$, sample size $n$, confidence $p$:
$$N = \frac{\log(1-p)}{\log(1-w^n)}$$
  • With $w = 0.5$, $p = 0.99$: 72 rounds for a homography, about 1,177 for 8-point $F$. That's why small minimal solvers matter, and where epipolar geometry comes in next
TangentWhy a ratio, and not a fixed distance?

In 128 dimensions distances behave strangely: random points end up at similar distances from each other (distances concentrate). So the raw distance to the nearest neighbour says little. A correct match on a blurry patch can be further away than a wrong match on a sharp one.

The second-nearest neighbour fixes this. If a keypoint has a true match, there is one correct candidate and everything else is wrong. So the second nearest is almost always a wrong match, and its distance estimates how close impostors get in this part of the space. The ratio asks: is the best candidate clearly closer than the typical impostor here?

Lowe plotted the ratio for correct and incorrect matches against a database of 40,000 keypoints. Correct matches cluster at low ratios; incorrect ones pile up near 1. A cut at 0.8 is where that gives the 90% / 5% split.

It fails where you'd expect: repeated structure. Two identical windows give two near-equal distances, a ratio near 1, and a true match gets thrown out. Losing it is better than being confidently wrong, and RANSAC can't rescue a match that was never kept.

NextOpen questions

Not answered yet

  1. Why $\sigma = 1.6$ and 3 levels per octave? What does the repeatability curve look like?
  2. Why does doubling the input image give almost four times as many stable keypoints?
  3. Where does the 0.2 clipping value come from?
  4. Why does RootSIFT (Hellinger kernel) match better than plain SIFT?
  5. How do you choose the RANSAC inlier threshold, and what goes wrong fitting $F$ to a nearly flat scene?
  6. How is the 8-point algorithm derived, and why does it need normalised coordinates?
  7. How do affine-invariant variants handle the large viewpoint changes SIFT can't?
  8. What do learned features (SuperPoint, LightGlue) learn that these hand-made steps miss, and where does SIFT still win?