Hi, I have a problem of doing normalised cross correlation by FFT, which the result doesn't satisfy with the result from the one from time domain method and I don't know where it goes wrong. From my understanding, this is the cross covariance in frequency domain, which gives me the correct result. (If there are signals x and y) 1) Do FFT of x 2) Do FFT of y 3) Conjugates 1) or 2) 4) Multiply 1) with 3) 5) Do inverse FFT of 4) Then when I tried to develop a programme for doing the normalised cross correlation, I use the step below. 1) Do FFT of x-(mean of x) 2) Do FFT of y-(mean of y) 3) Conjugates 1) or 2) 4) Multiply 1) with 3) 5) Do inverse FFT of 4) 6) divide 5) by the standard deviations of x and y In the equation in time domain method, the mean is subtracted from x and y, and the denominator is just like in step 6) above. By this, I got the correct result, so I applied it to the frequency domain method as shown above. However, the result is wrong, which I don't now why. Can any body tell me whether the steps I used above is correct or not? Thanks, Sangthong

# normalised cross correlation by FFT

Started by ●April 28, 2008

Reply by ●May 6, 20082008-05-06

On Apr 28, 8:29�pm, "sangthong" <sangthong2...@yahoo.com> wrote:> Hi, > > I have a problem of doing normalised cross correlation by FFT, which the > result doesn't satisfy with the result from the one from time domain method > and I don't know where it goes wrong. > > From my understanding, this is the cross covariance in frequency domain, > which gives me the correct result. (If there are signals x and y) > > 1) Do FFT of x > 2) Do FFT of y > 3) Conjugates 1) or 2) > 4) Multiply 1) with 3) > 5) Do inverse FFT of 4) > > Then when I tried to develop a programme for doing the normalised cross > correlation, I use the step below. > > 1) Do FFT of x-(mean of x) > 2) Do FFT of y-(mean of y) > 3) Conjugates 1) or 2) > 4) Multiply 1) with 3) > 5) Do inverse FFT of 4) > 6) divide 5) by the standard deviations of x and y > > In the equation in time domain method, the mean is subtracted from x and > y, and the denominator is just like in step 6) above. By this, I got the > correct result, so I applied it to the frequency domain method as shown > above. However, the result is wrong, which I don't now why. Can any body > tell me whether the steps I used above is correct or not? > > Thanks, SangthongIsn't the mean different for each delay? The FFT effectively does all the delays simultaneously, while the time domain version the mean is recomputed every delay. so I can't see how you can do a normalized cross correlation in the freq domain, I suppose for circular cross correlation this may work but not for linear (with zero padding)

Reply by ●May 6, 20082008-05-06

On 29 Apr, 02:29, "sangthong" <sangthong2...@yahoo.com> wrote:> However, the result is wrong,Of course it is...> which I don't now why....yes you do. See below.> Can any body > tell me whether the steps I used above is correct or not?You already know why, because I showed you the reasons a couple of months ago: http://groups.google.no/group/comp.dsp/msg/c9ddc70cfa59d685 This time around, make sure you look up the post I referred you to, read it, and contemplate what is said. Rune