Harris corner detector step by step, interactive demo

From the second moment matrix to a score

The autocorrelation surface showed the idea: a window is distinctive if shifting it in any direction changes its content. The Harris detector builds on three approximations:

distinctiveness is approximated by the local autocorrelation $E(u, v)$ ,
the autocorrelation is approximated by the second moment matrix, $E(u, v) \approx [u \;\, v] \, M \, [u \;\, v]^\top$ ,
cornerness is a function of the eigenvalues $\lambda_1, \lambda_2$ of $M$ : a corner has two large eigenvalues.

Instead of computing the eigenvalues at every pixel, Harris uses that the determinant is their product and the trace their sum:

C = \lambda_1 \lambda_2 - \alpha (\lambda_1 + \lambda_2)^2 = \det(M) - \alpha \operatorname{trace}(M)^2

with a small constant $\alpha$ , commonly 0.04 to 0.06. $C$ is large and positive at corners, negative on edges, where one eigenvalue dominates, and close to 0 in flat regions.

The algorithm

Input: the image $I$ . $M$ is computed at every pixel.
Compute the image derivatives $I_x$ and $I_y$ , optionally after blurring the image ( $\sigma_D$ ).
Compute the entries of $M$ as products of the derivatives: $I_x^2$ , $I_y^2$ , $I_x I_y$ .
Filter each product with a Gaussian $g$ of width $\sigma$ : this is the window function $w$ .
Compute the cornerness with element-wise products $\odot$ :

C = g(I_x^2) \odot g(I_y^2) - g(I_x \odot I_y)^2 - \alpha \left[ g(I_x^2) + g(I_y^2) \right]^2

Threshold $C$ to keep only high cornerness. Here $t$ is a fraction of the largest $C$ in the image.
Non-maximum suppression: keep a pixel only if its $C$ is the largest in its neighborhood of $2r + 1$ pixels square.

Everything up to step 4 is linear filtering and pixel-wise arithmetic, which makes the detector fast.

The plane of eigenvalues

The plot next to the controls shows every pixel as a point $(\lambda_1, \lambda_2)$ with $\lambda_1 \ge \lambda_2$ . Flat pixels crowd near the origin, edge pixels lie along the $\lambda_1$ axis, and corners are the few points that also have a large $\lambda_2$ . The shaded regions are where $C \ge t$ and $C \le -t$ . Their borders are lines of constant $C$ , so the classification depends on the eigenvalues only.

$\alpha$ sets how equal the eigenvalues must be. For $t = 0$ , a pixel is a corner if $\lambda_2 / \lambda_1$ is above a ratio that grows with $\alpha$ : about 0.056 for $\alpha = 0.05$ . At $\alpha = 0.25$ , $C = -(\lambda_1 - \lambda_2)^2 / 4 \le 0$ , and nothing is a corner anymore.

The ellipses

The red ellipse at the selected pixel is a line of constant $[u \;\, v] \, M \, [u \;\, v]^\top$ . Its axes point along the eigenvectors and are proportional to $\lambda^{-1/2}$ : small and round at corners, long and thin along edges, and huge (clipped here) in flat regions. Turn on the grid to see the ellipses all over the image.

Which corners survive a change of brightness, a rotation or a change of scale is the topic of Harris invariance.

Try this

Select a pixel on a straight side of a rectangle and one on a corner, and compare their points in the eigenvalue plane and their ellipses.
Look at the cornerness $C$ : corners are bright spots, while edges are dark, negative lines.
Increase $\alpha$ towards 0.25: the corner region in the plane narrows towards the diagonal, and corners whose eigenvalues differ a lot drop out.
Add noise with $\sigma_n = 0.05$ and set the threshold to 0: hundreds of local maxima appear in the flat regions. A threshold of 0.01 brings back the corners of the clean image.
Increase the window $\sigma$ to 5: the window now covers several squares of the checkerboard, and only its inner corners remain.
Set the blur $\sigma_D$ to 0 with noise: the derivatives get much noisier, but the Gaussian window still averages most of it away.
Turn on the ellipses on a grid: along the sides of the shapes they are long and thin and follow the edge, on the checkerboard they are small and round.