Autocorrelation surface & second moment matrix, interactive demo

Interest points

Many tasks need points that can be found again in another image of the same scene: aligning images for a panorama, 3D reconstruction from many photos, tracking motion, image retrieval and object recognition. They all follow three steps: detect distinctive points, describe the neighborhood of each one as a vector, and match the descriptors between images. Good interest points are

repeatable: the same point is found despite geometric and photometric changes,
salient: each point is distinctive,
compact and efficient: there are far fewer points than pixels,
local: each point covers a small area, which makes it robust to clutter and occlusion.

The detector runs on each image independently, without knowing where the point will end up in the other image. What it can check is how stable a location is: how much its neighborhood changes when it is shifted slightly.

Change of appearance under a shift

The change of the window $w$ for a shift $(u, v)$ is the weighted sum of squared differences

E(u, v) = \sum_{x, y} w(x, y) \left[ I(x + u, y + v) - I(x, y) \right]^2

The window function $w$ is 1 inside the window and 0 outside (box), or a Gaussian that weights the center more. Here its weights sum to 1, so the values don't depend on the window size. Small values mean that the shifted window looks like the original one (high correlation, black), large values that it looks different (white). The shape of $E$ tells the three cases apart:

Flat region: $E$ is small for every shift, and the map is dark everywhere.
Edge: $E$ stays small along the edge, a dark line through the center.
Corner: $E$ grows in every direction, only a dark dot remains in the center.

A corner is a distinct minimum of $E$ . Computing $E$ directly is slow, though: it costs the window size times the number of shifts for every pixel of the image.

Quadratic approximation

For small shifts, a second-order Taylor expansion of $E$ around $(0, 0)$ describes its shape:

E(u, v) \approx E(0, 0) + \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} E_u(0, 0) \\ E_v(0, 0) \end{bmatrix} + \frac{1}{2} \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} E_{uu}(0, 0) & E_{uv}(0, 0) \\ E_{uv}(0, 0) & E_{vv}(0, 0) \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix}

$E(0, 0) = 0$ and, since this is a minimum, the first derivatives vanish as well. Only the quadratic term remains. The same result follows from the first-order expansion of the image, $I(x + u, y + v) \approx I(x, y) + I_x u + I_y v$ :

E(u, v) \approx \sum_{x, y} w(x, y) \left[ I_x u + I_y v \right]^2 = \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}, \qquad M = \sum_{x, y} w(x, y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}

The second moment matrix $M$ only needs the image derivatives, here central differences, and no shifted copies of the window. Compare the two maps: near the center they agree, further out $E$ levels off while the parabola keeps growing, because the derivatives only describe the image close to the pixel.

Eigenvalues and the ellipse

The lines of constant $[u \;\, v] \, M \, [u \;\, v]^\top$ are ellipses. Their axes point along the eigenvectors of $M$ , and their lengths are proportional to $\lambda^{-1/2}$ : the short axis $(\lambda_\text{max})^{-1/2}$ points in the direction of the fastest change, the long axis $(\lambda_\text{min})^{-1/2}$ in the direction of the slowest change. The eigenvalues therefore classify the window:

both eigenvalues small: flat, a huge ellipse,
one large and one small eigenvalue: edge, a long, thin ellipse along the edge,
both eigenvalues large: corner, a small ellipse.

How large is large depends on the contrast of the image. The Harris detector avoids choosing two eigenvalue thresholds and combines both into a single cornerness score.

Try this

Click in the flat background, on the straight side of a shape and on a corner of a rectangle, and compare the three $E$ maps with the classification.
On an edge, the dark line in $E$ runs along the edge, and the ellipse becomes a long, thin band. Try the diagonal sides of the triangle and the star, too.
Select a shift further away from the center: $E$ grows more slowly than the approximation, and the two sections separate from their parabolas.
Click on the border of the circle: every window along it sees an almost straight edge, so a circle has no corners.
Click on a rounded corner of the blue rectangle and increase the window radius from 2 to 8: the more of the curve fits into the window, the larger $\lambda_2 / \lambda_1$ becomes.
Add a little noise, $\sigma_n = 0.03$ , and select a flat pixel: $E$ is no longer zero for any shift, but both eigenvalues stay small.
Switch between the Gaussian and the box window while a corner lies near the border of the window: the box counts it fully, the Gaussian hardly at all.