0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ well, for those of us in audio and speech processing, we've been calling this "ASDF" (for Average Squared Difference Function) and have only one dimension instead of two. but the reason for its relationship to autocorrelation is the same and shown in this answer from before. $\endgroup$ – robert bristow-johnson Mar 15 '19 at 0:55
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Why do the not-squared terms depend on m or n? $\endgroup$ – j35t3r Feb 13 '19 at 15:37
  • $\begingroup$ For each $m$ and $n$ the template ends up over a different region in the image, which means that $g(i,j)t(i-m, j-n)$ differs for each $m$ and $n$. $\endgroup$ – Abraham Feb 13 '19 at 22:15
  • $\begingroup$ @j35t3r Nobody is claiming that the squared terms don't individually depend on $m$ and $n$. What is being claimed is that the sum of the squared terms is a constant, I,e.. not dependent on $m$ and $n$. $\endgroup$ – Dilip Sarwate Mar 20 '19 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.