7
$\begingroup$

I asked this over at Mathematics Stack Exchange, but since this sort of lies on the border of the questions normally asked over there and the questions you see over here I'll ask it here as well. (As of now, there's been no activity on my question over there.)

In 2-dimensional discrete signal analysis (specifically image processing), a definition I found for the normalized cross-correlation between two images, both of size $M\times N$ $g_1(x, y)$ and $g_2(x, y)$ is:

$$r_1 = (g_1 \star g_2)(x, y)_{\rm Normalized} = \frac{\sum\limits_{m=0}^{M-1} \sum\limits_{n=0}^{N-1}\left[g_1(m, n) - \overline{g_1}\right]\left[g_2(x + m, y + n) - \overline{g_2}\right]}{\sqrt{\sum\limits_{m=0}^{M-1} \sum\limits_{n=0}^{N-1} \left[g_1(m, n) - \overline{g_1}\right]^2 \left[g_2(x + m, y + n) - \overline{g_2}\right]^2}}$$

This is supposedly performed by the function normxcorr2 in the Signal Processing Toolbox in MATLAB, although using the Fast Normalized Cross-correlation algorithm by J. P. Lewis. Compared to the Phase Correlation method (with normalized cross-power spectrum) suggested by Kuglin and Hines:

\begin{align} G_1(u, v) &= \mathcal{F}\left\{g_1(x, y)\right\}\\ G_2(u, v) &= \mathcal{F}\left\{g_2(x, y)\right\}\\ r_2 &= \mathcal{F}^{-1}\left\{\frac{G_1^\ast (u, v) G_2(u, v)}{\lvert G_1^\ast (u, v) G_2(u, v) \rvert}\right\} \end{align}

Without the element-wise normalization before the inverse Fourier transform, $r_2$ is the same as non-normalized cross-correlation, with the exception that the Fourier transform assumes that the signal repeats in the spatial domain. It is clear that $r_1 \neq r_2$ by looking at the resulting correlation "images" in MATLAB, which I expected, but $r_2$ almost seems discontinuous from the images I am testing the method on, while $r_1$ always turns out much smoother (the resulting $r_2$ images are always "spotty", $r_1$ are not). Why is this? I assume it has something to do with the element-wise normalization in the Fourier domain, which I suppose is basically like cropping the signal in a way, but I don't know how to conclude this from any known properties of the (inverse) Fourier transform, if this is even a correct assumption.

Here are examples of the differences ($r_2$ has been amplified to clearer show the difference in characteristics of the images). They are performed on the same 2 images.

  • $r_1$: Normalized cross-correlation

enter image description here

  • $r_2$: Phase correlation

enter image description here

Summarizing my question: Why is $r_2$ so "spotty", while $r_1$ is not?

$\endgroup$
  • 1
    $\begingroup$ Consider asking your question on one site as cross-posting is not well received on SE. Read here $\endgroup$ – Gilles Jul 4 '16 at 16:47
  • $\begingroup$ Thank you for pointing that out, I didn't know that was frowned upon here. I am however conflicted. I do not know which site (of the two) would be the most appropriate. In your link the top answer says that "Many questions people have labeled as being applicable cross-site have been proven to be valid on a single site if written properly and thought through.". I do not know how to make my question more fitting for one site or the other without simply withholding information. The only option I can think of is to delete it from one site and move to the other, which seems like a strange solution. $\endgroup$ – Eric Sep 5 '16 at 12:36
  • $\begingroup$ for r2, try to demean g1 and g2 first then apply the fft. r1 and r2 should be the same. one for space domain and the other for frequency domain, but equivalent except a normalization by the norms. $\endgroup$ – Lee Mar 26 '18 at 13:53
1
$\begingroup$

I came across this conundrum in a 1 dimensional case, which is how I will present it. Consider two signals that you want to correlate. Signal 1 (figure panel a) is a damped sine wave and signal 2 (figure panel b) is two instances of signal 1 but at slightly different amplitudes.

enter image description here

Now consider using a normalized cross correlation as you defined in your question (figure panel c). The result is a smoothly oscilating function that has a peak amplitude when the peak from signal 1 and the peak from signal 2 are aligned. Conversely the normalized cross correlation function has troughs when the peak from signal 1 lines up with the troughs from signal 2.

Then consider using a phase correlation as you defined in your question (figure panel d). A phase correlation involves a division of the absolute value (or amplitude) of the two signals. In a 1D case that is a vector and in a 2d case, as your question is, that is a matrix. In either case the values in that divisor can be very close to zero and when you divide by something close to zero, you get spikes or discontinuities.

There are several strategies around this and include low pass filtering the input signals or the phase correlated function. This page on stack overflow might be helpful: https://stackoverflow.com/questions/30630632/performing-a-phase-correlation-with-fft-in-r

$\endgroup$

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.