normalised cross correlation by FFT

[sangthong]

Hi,

I have a problem of doing normalised cross correlation by FFT, which th
result doesn't satisfy with the result from the one from time domain metho
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 cros
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 an
y, and the denominator is just like in step 6) above. By this, I got th
correct result, so I applied it to the frequency domain method as show
above. However, the result is wrong, which I don't now why. Can any bod
tell me whether the steps I used above is correct or not?

Thanks, Sangthong

[steve]

On Apr 28, 8:29*pm, "sangthong" <[email protected]> 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, Sangthong

Isn'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)

[Rune Allnor]

On 29 Apr, 02:29, "sangthong" <[email protected]> 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