The problem is, given two n by n arrays of pixels, referred to as $A_{i,j}$ and $B_{i,j}$, determine how alike they are.

One of the simplest comparisons is $$\sum_{i,j = 0,0}^{n,n}(A_{i,j}-B_{i,j})^2$$

If the camera did exact photometric measurements, and if lighting conditions remained unchanged between frames, this measure would be ideal. Unfortunately the camera response varies from place to place on the camera field due to the nature of the optics and complicated vidicon effects, from scene to scene because of target voltage response to illumination, and from time to time due to changes in battery voltage. In spite of these drawbacks the measure has been used successfully.

Another alternative is “normalized correlation,” the root mean square average displacement of co-ordinate pairs $(A_{i,j},B_{i,j})$ from a least squares regression line relating $A$ to $B$. Let $a_{i,j} = A_{i,j}-\overline{A}$ and $b_{i,j} = B_{i,j}-\overline{B}$, $\overline{A}$ and $\overline{B}$ being the means over the entire window. The normalized correlation coefficient is defined as: $$\sigma = {\sum{a_{i,j} b_{i,j}} \over \sqrt{\sum{a_{i,j}^ 2}\sum{b_{i,j}^ 2} }}$$

Normalized correlation is invariant under all linear transformations of the values of $A$ and $B$. The complete contrast insensitivity this implies is a needless waste of information, because contrast changes in actual pictures are relatively small from frame to frame. In addition, the measure has a degeneracy when all the values of either $A$ or $B$ are the same. This will happen often if the search window contains uniformly shaded areas, and must be handled by a special test. A different measure is called for.

Although the correlation coefficient itself remains unchanged, the “line of best fit” is different when calculated from $A$ to $B$ than from $B$ to $A$. For the best fit of $A$ to $B$, $b = ka$, we wish to find $k$ which minimizes $\sum(ka–b)^2$. This is $k = \sum{ab}/\sum{a^2}$. The line can be expressed $$a = {{\sigma\sqrt{\sum{a^2}}}\over{\sqrt{\sum{b^2}}}}\;b$$ for the best fit of $B$ to $A$, $a = kb$, we wish to find $k$ which minimizes $\sum(kb–a)^2$. This is $k = \sum{ab}/\sum{b^2}$. The line can be expressed $$b = {{\sigma\sqrt{\sum{b^2}}}\over{\sqrt{\sum{a^2}}}}\;a$$ these are equivalent if $\sigma$ is unity, i.e. if the correlation is perfect. Since for our application, the comparison of two picture patches, there is no particular reason for choosing one over the other, we compromise and choose a line equidistant from the two, removing the asymmetry between $A$ and $B$: $$b = {\sqrt{\sum{b^2}}\over\sqrt{\sum{a^2}}}\;a$$ or equivalently $$a = {\sqrt{\sum{a^2}}\over\sqrt{\sum{b^2}}}\;b$$

We will use this to obtain a correlation measure more suited to our needs.

Small contrast changes should be tolerated, large ones should not. Contrast is expressed by the slope of the line of best fit, a slope of unity denoting a perfect match, slopes of zero and infinity indicating that one or the other of the patches has no variations in intensity. Consider the normalized dot product of the line of best fit with a line of unity slope. Since this is the cosine of the angle between them, it will be unity for a perfect match, and very near unity for small contrast differences, since the cosine is flat around zero angle, and zero for a negative correlation. If we were to multiply this dot product by the normalized correlation coefficient, we would obtain a measure which was unity only for perfect correlation with no contrast differences, dropping rapidly with lessening correlation, and slowly at first and then rapidly with increasing contrast differences.

This measure still has a few flaws. If one of the patches is without
intensity variations, the normalized correlation coefficient becomes $0/0$
and the dot product $1/\sqrt{2}$.
In fact we want our measure to be zero in this case. This can be arranged
if we multiply the normalized coefficient by the cosine of *twice*
the angle between the correlation line and a line of slope 1. This cosine
will be zero for lines of slope zero or infinity, and the limit of the
product with the normalized correlation coefficient will also be zero in those
cases. In addition, perfect negative correlation will again appear as minus unity,
which might be an advantage in some circumstances.

Deriving an expression for this measure, we note that the cosine of our “compromise” correlation line with one of unity slope is $${\sqrt{\sum{a^2}} + \sqrt{\sum{b^2}}}\over \sqrt{2 \left( \sum{a^2} + \sum{b^2} \right)}$$ To convert this to the cosine of twice the angle with $a=b$, we use the identity $$\cos(2t) \; = \; 2 \cos^2(t) - 1$$ giving us $${{2 \left(\sqrt{\sum{a^2}} + \sqrt{\sum{b^2}}\right) ^2}\over {2 \left(\sum{a^2} + \sum{b^2}\right)}} - 1 \quad = \quad {2 \sqrt{\sum{a^2}\sum{b^2}} \over \sum{a^2} + \sum{b^2}}$$ multiplying by the normalized correlation coefficient, we get

Note that whereas normalized correlation consists of the
sum of the pairwise products of $A$ and $B$ divided by the geometric
mean of the sum of their squares, this new measure, referred
to as pseudo-normalized correlation, is the sum of the products
divided by the *arithmetic* mean of the sums of the squares.
Since it involves an addition and a halving rather than a multiplication
and a square root, it is actually easier to calculate. The prettiness
of the result leads me to suspect that a more elegant
derivation exists.

This pseudo-normalized measure works as well as any of the alternatives, and is easy to compute. It is the standard correlation measure in cart software.