I never worked with signal processing and never really used Fourier transforms before, still I am working on a project consisting on taking the output of an accelerometer to detect some movement features between touching surfaces. Using a frame of the output, I compute the FFT. After analyzing the data for multiple experiments, it appeared to make sense to use gaussians to isolate bands of frequencies and use that to classify the features.

That does not work well, however, if I change the sensor I am using, the sampling rate or frame size. Thus, I want to calculate the normalized cross-correlation. Problem is: I could not find an algorithm to calculate the NCC in the frequency domain and I did not figure out how to transform the translated gaussians to the time domain.

For instance, I have a frequency spectrum from -F/2 to F/2 and L samples. I converted that to L/2+1 frequency bins from 0 to F/2 and defined a band using a gaussian with standard deviation s and centered on c.
To get the cross-correlation between the spectrum and the gaussian, I simply do the sum of the element-wise multiplication of them. Now, if I want that normalized, what can I do? Is there a way to normalize it right from the frequency domain?

  • 1
    $\begingroup$ the fourier transform of a gaussian is a gaussian. if your fft is large, using the continuous fourier result is typically reasonable. $\endgroup$ – user28715 Mar 9 '19 at 16:45

I was thinking on the math behind it and concluded that calculating the NCC in the frequency domain is basically the same process as in the time domain:

$F[k]$ is the (discrete) Fourier transform of my sample, $G[k]$ is the gaussian curve in the frequency domain. The cross-correlation is $$CC = \sum^{L-1}_{k=0}F[k]{\cdot}G[k]$$ Then, to get the normalized cross-correlation we first normalize the vectors $F$ and $G$, as would be done to any vector: $$\hat{v} = \frac{v}{|v|} = \frac{v}{\sqrt{\sum^{L-1}_{k=0}v^2[k]}}$$ Thus, the normalized cross-correlation should be the dot-product of the normalized vectors $\hat{F}$ and $\hat{G}$: $$NCC = \frac{\sum^{L-1}_{k=0}F[k]{\cdot}G[k]}{\sqrt{\sum^{L-1}_{k=0}F^2[k]\cdot\sum^{L-1}_{k=0}G^2[k]}}$$

| improve this answer | |
  • $\begingroup$ I think you need to take the complex conjugate of either F or G, prior to the multiplication, otherwise it's convolution rather than correlation ? $\endgroup$ – Paul R Nov 7 '19 at 18:21
  • $\begingroup$ I thought that convolution is the one you do with the conjugate of F or G (not sure, though). Since I only needed the magnitudes, that did not affect me. $\endgroup$ – Lurosset Nov 8 '19 at 18:41
  • $\begingroup$ You could be right - I did implement a frequency domain NCC some years ago and I think I had to use the conjugate of one of the FFT’d images, but my memory may well be failing me. ;-) $\endgroup$ – Paul R Nov 8 '19 at 21:08

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.