Creating Gaussian spaces
At different levels and scales
- Create Gaussian spaces at different levels and scales
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:
Rearrange it and the meaning jumps out:
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:
| Signal | Values | Laplacian (middle) | Reading |
|---|---|---|---|
| flat | 5, 5, 5 | 5 − 10 + 5 = 0 | nothing here |
| ramp | 2, 4, 6 | 2 − 8 + 6 = 0 | a steady slope is not interesting |
| bright spot | 2, 9, 2 | 2 − 18 + 2 = −14 | brighter than surroundings |
| dark spot | 8, 1, 8 | 8 − 2 + 8 = +14 | darker than surroundings |
| corner of a step | 2, 2, 8 | 2 − 4 + 8 = +6 | foot of the edge |
| top of the step | 2, 8, 8 | 2 − 16 + 8 = −6 | shoulder 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.
Now two dimensions. An image has two directions to curve in, so add the curvature along $x$ and along $y$:
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$ is the Laplacian of Gaussian (LoG). Work it out and you get
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:
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:
- 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