Why can Sum of Squared Differences (SSD) seen as cross-correlation?

Question

In this slides, on page 4, the SSD can be seen as cross-correlation:

http://www.lira.dist.unige.it/teaching/SINA/slides-current/pyramids.pdf http://www.cse.yorku.ca/~kosta/CompVis_Notes/ssd_cross-correlation.pdf

The SSD is defined as:

$$SSD(m,n) = \sum_i \sum_j [g(i,j) - t(i-m,j-n)]^2,$$

and expand the SSD. It looks like this:

$$SSD(m,n) = \sum_i \sum_j [g(i,j)^2 + t(i-m,j-n)^2 - 2g(i,j)t(i-m,j-n)], $$

where the squared terms can be assumed as constant. As a result, the cross-correlation remains:

$$R(m,n)= \sum_i \sum_j [g(i,j) t(i-m, j-n)].$$

Question: Why can we assume that the squared terms are constant?

Answer 1

Short Answer:

The statement "the the squared terms are constant" is true only if some further theoretical assumptions are made. In practice, the terms are often not constant (i.e. they are dependent on $m$ and $n$). For many discussions however, it's ok to treat the terms as constant.

Details:

The term $\sum_{i,j}\left[g(i, j)\right]^2$ is not interesting since it is clearly independent on $m$ and $n$. The term $\sum_{i,j} \left[t(i-m, j-n)\right]^2$, however, formally depends on $m$ and $n$, as $m$ and $n$ appear in the summed expression. Nevertheless, it may be effectively constant depending on how the bounds for the running variables $i$ and $j$ are chosen and whether $t$'s support is bounded or not.

In theoretical discussions, the image function $t(x,y)$ is usually assumed to have bounded support. This means that there are minimum and maximum values of both $x$ and $y$, outside of which all image pixels can be assumed to be zero. This assumption is plausible because a real digital image only has a finite number of pixels, e.g., $1024$x$768$ pixels.

The sum is often assumed to cover the entire space, that is $i$ and $j$ go from negative to positive infinity: $\sum_{i,j}$ really means $\sum_{i=-\infty}^{+\infty}\sum_{j=-\infty}^{+\infty}$.

Only if these two assumptions (bounded image and infinite sum) are silently made, then the squared terms are independent of $n$ and $m$. No matter what $n$ and $m$ are you will always "hit" all the pixels of image $t$: $\sum_{i,j} \left[t(i-m, j-n)\right]^2 = \sum_{i,j} \left[t(i, j)\right]^2, \textrm{for all } n, m$.

In practical template matching, the sum will often cover only the pixels of the template, for performance reasons. This means that, in the (larger) image, only the pixels are regarded which are currently covered by the template given the current $m$ and $n$. In these cases, the squared terms are not independent if $n$ and $m$.

As a last note, in your squared difference implementation you can choose to omit calculating the squared terms and only regard the mixed term. This way, you get the same result as if you would have taken the infinite sum (up to a constant), and thus the theoretical considerations will hold again.

Answer 2

The second term is constant because $\sum_{i, j}t(i-m, j-n)^2$ is simply the energy of the template and importantly does not depend on $m$ or $n$.

Assuming that $\sum_{i, j}g(i,j)^2$ is constant is equivalent to assuming that the energy in the section of the image that aligns with the template does not vary with the position of the template (dictated by $m$ and $n$). I am not quite sure why this is a valid assumption, perhaps someone else may be able to help here.