Matching cost surface: SSD, SAD, robust costs & NCC

Comparing a window at every shift

Given two images $I_0(\mathbf{x})$ and $I_1(\mathbf{x})$ with pixel positions $\mathbf{x} = (x, y)$ , we look for the displacement $\mathbf{u} = (u, v)$ for which $I_1(\mathbf{x} + \mathbf{u})$ is most similar to $I_0(\mathbf{x})$ . For one window with pixels $\mathbf{x}_i$ , each shift gives an error per pixel, $e_i = I_1(\mathbf{x}_i + \mathbf{u}) - I_0(\mathbf{x}_i)$ , and an error metric $E(\mathbf{u})$ combines them into one number. Plotted over all shifts, $E$ forms a surface whose minimum is the estimated motion. It is the same idea as the autocorrelation surface, where a window is compared with itself. For color images, the sum runs over the color channels or uses only the luminance, as here.

SSD and SAD

The simplest metric is the sum of squared differences, the squared L2 norm of the error vector:

E_{SSD}(\mathbf{u}) = \sum_i \left[ I_1(\mathbf{x}_i + \mathbf{u}) - I_0(\mathbf{x}_i) \right]^2 = \sum_i e_i^2

Small errors count little and large errors a lot. That makes the SSD tolerant to low-amplitude noise and easy to minimize, since it is smooth. But it is not robust: a few large errors, e.g. from an occluded part of the window, dominate the sum. The sum of absolute differences, the L1 norm, weighs them less:

E_{SAD}(\mathbf{u}) = \sum_i |e_i|

Lp norms and robust kernels

Both are special cases of the Lp norm of the error vector, with $p = 2$ and $p = 1$ :

E_{L_p}(\mathbf{u}) = \Big( \sum_i |e_i|^p \Big)^{1/p}

Values $p < 1$ also make sense for matching, even though the result is no longer a norm (it violates the triangle inequality). More generally, the sum of robust differences applies a kernel $\rho$ to each error:

E_{SRD}(\mathbf{u}) = \sum_i \rho(e_i), \qquad \rho_{GM}(x) = \frac{x^2}{1 + x^2 / a^2}

$\rho(x) = |x|^p$ gives the Lp norm, but for $p \le 1$ it is not differentiable at 0, which is bad for optimization methods. The Geman–McClure kernel is quadratic for small errors like the SSD, but it levels off at $a^2$ for errors much larger than $a$ , so outliers can only contribute a bounded amount.

Outside the image and masked pixels

A shifted window can leave the image, and some pixels may be known to be invalid, e.g. because they are covered by another object. Masks $w_0$ and $w_1$ , 1 inside the region of interest and 0 elsewhere, restrict the sum to pixels that are valid in both images:

E_{WSRD}(\mathbf{u}) = \sum_i w_0(\mathbf{x}_i)\, w_1(\mathbf{x}_i + \mathbf{u})\, \rho(e_i)

Now different shifts sum over different numbers of pixels, and a shift that pushes most of the window out of the image has a small sum simply because little is left. Dividing by the counted area $A(\mathbf{u}) = \sum_i w_0(\mathbf{x}_i)\, w_1(\mathbf{x}_i + \mathbf{u})$ makes them comparable:

E_{NWSRD}(\mathbf{u}) = \frac{1}{A(\mathbf{u})} \sum_i w_0(\mathbf{x}_i)\, w_1(\mathbf{x}_i + \mathbf{u})\, \rho(e_i)

Bias and gain

If the frames were taken with different exposure, aperture or even different cameras, their intensities are not directly comparable. A linear model maps one to the other, $I_0(\mathbf{x}) \rightarrow \alpha I_0(\mathbf{x}) + \beta$ , and the SSD becomes

E_{SSD}(\mathbf{u}, \alpha, \beta) = \sum_i \left[ I_1(\mathbf{x}_i + \mathbf{u}) - (\alpha I_0(\mathbf{x}_i) + \beta) \right]^2

For every shift, $\alpha$ and $\beta$ are found by linear regression, and what remains is the error the model cannot explain.

Cross-correlation

Instead of an error, cross-correlation measures a similarity that is largest for the best shift:

E_{CC}(\mathbf{u}) = \sum_i I_0(\mathbf{x}_i)\, I_1(\mathbf{x}_i + \mathbf{u})

On its own it prefers bright regions of $I_1$ , whatever they look like. Normalized cross-correlation subtracts the means $\bar I_0$ , $\bar I_1$ of both windows and divides by their spread:

E_{NCC}(\mathbf{u}) = \frac{\sum_i [I_0(\mathbf{x}_i) - \bar I_0][I_1(\mathbf{x}_i + \mathbf{u}) - \bar I_1]}{\sqrt{\sum_i [I_0(\mathbf{x}_i) - \bar I_0]^2} \sqrt{\sum_i [I_1(\mathbf{x}_i + \mathbf{u}) - \bar I_1]^2}}

The normalization removes linear changes of brightness and contrast, so NCC works when the frames were taken with different exposure. The same score finds a template in template matching.

Full search

The surface above is a full search: every shift within a radius $R$ is tried. This is expensive, since each of the $(2R + 1)^2$ shifts needs a sum over the whole window, and it only finds the best shift on the integer grid, not with subpixel accuracy. Gradient-based methods such as Lucas–Kanade avoid both problems by following the slope of $E$ from an initial guess.

Try this

With the defaults, the SSD surface has a single dark minimum at the true shift (3, −2). Click other shifts and watch the errors $e_i$ grow.
Click a flat region of $I_0$ : the surface is dark almost everywhere and the best shift is arbitrary. Click a straight edge: the minimum becomes a dark valley along the edge, since shifts along it change nothing.
Choose the zone plate or text image: repeated patterns give several minima of nearly the same depth.
Set the gain to 1.5 and the bias to 0.15. SSD, SAD and the robust costs grow at every shift and can pick a wrong one, CC runs to bright spots, while NCC and SSD with bias & gain keep the true shift. The fitted $\hat\alpha$ , $\hat\beta$ match the settings until the brightest pixels clip at 1.
Turn on the occluder: a block of large errors appears in the window. Compare SSD with SAD and Geman–McClure ( $a = 0.1$ ): the histogram shows the outliers, and the robust kernels limit their weight. With masks, the occluded pixels do not count at all.
Select a window near the border of the image, set $R = 12$ and choose masks (WSRD): shifts that leave the image count fewer pixels and look better. Normalized (NWSRD) removes this bias.
Set the true shift to (2.5, −2): the true minimum lies between pixels, and the full search can only report a neighbor.
Choose the Lp norm and move $p$ between 0.5 and 2: below 1 the kernel rises steeply at 0 and flattens for large errors, like a robust kernel with a sharp tip; at 2 it is the SSD.