# Normalized cross-correlation in frequency domain

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?

• the fourier transform of a gaussian is a gaussian. if your fft is large, using the continuous fourier result is typically reasonable.
– user28715
Mar 9, 2019 at 16:45

$$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]}}$$