time domain and fft correlation paradox

Hello!

Okay, this is really disturbing.

Given 1d signals A and B.

Computing a signal C[x] as:

C[x]=SUM( A[x]*B[x+j] ) //sum over j

gives what some call linear correlation or just (cross)correlation of A
and B. (is that correct?)
It is used to check where signals match most ( for some position of x
C[x] is max and this is the pos where they match).

Well, my application is image recognition, but let's consider just the
1-d case since it's the same and a bit simpler. This formula C[x]=SUM(
A[x]*B[x+j] ) does not compute anything useful (i.e. it doesn't max at
the position where the best match is, not even close). In most articles
about image recongition I see other correlation formulas (normalized
correlation) which just divides C[x] by sqrt(SUM(B[x+j]^2)) or
something like that. This works perfectly!!

Now, it gets interesting...

I have a mathematical proof that C[x] can be computed in the freq
domain using the fourier transform like this:

C'[x]=IFFT(FFT(A)*conj(FFT(B))

I implemented this and I got other values for C[x] (i.e. C'[x]!=C[x] ).
Something more - C'[x] actually recognizes the exact location of the
pattern signal/image, while C[x] gets totally lost. C'[x] has nothing
to do with C[x], i plotted both signals and they are completely
different (not just scaled or cut version of each other).

Something fundamental is missing here. Apparently my implementation of
the FFT correlation is correct (it always makes a nice peak at the
position where the pattern is located, even when noised). In thery C[x]
and C'[x] should be the same, just ping me for the proof if you doubt.

Can some1 explain what could be wrong?
Did any1 ever find useful this measure of correlation C[x]=SUM(
A[x]*B[x+j] )? (I doubt it's useful at all)

Thanks in advance!

"tru" <truseddsp@yahoo.com> wrote in message 
news:1119046453.838067.147490@g49g2000cwa.googlegroups.com...
> Computing a signal C[x] as:
>
> C[x]=SUM( A[x]*B[x+j] ) //sum over j
>
> gives what some call linear correlation or just (cross)correlation of A
> and B. (is that correct?)

No.  You want:

C(x) = SUM[ A(j)*B(x+j) ] //sum over j

--
Matt

in article 1119046453.838067.147490@g49g2000cwa.googlegroups.com, tru at
truseddsp@yahoo.com wrote on 06/17/2005 18:14:

> Given 1d signals A and B.
> 
> Computing a signal C[x] as:
> 
> C[x]=SUM( A[x]*B[x+j] ) //sum over j
> 
> gives what some call linear correlation or just (cross)correlation of A
> and B. (is that correct?)

maybe not.  i'm gonna change the notation a little

    C[n] = SUM{ A[j] * B[j+n] }          (summing over all j)
            j

where n is the integer lag or offset in the correlation.  now if A[] and B[]
both have finite length of non-zero values, then the number of non-zero
terms of A[j] * B[j+n] gets smaller and smaller as n increases and fewer
terms need to be summed.  there will be a sorta triangular envelope to C[n].
 
> C'[n] = IFFT( FFT(A[n]) * conj(FFT(B[n]) )

now, to do this right, make sure that the length of the FFT is at least as
large as the length of A plus the length of B so there is no circular wrap
around.  if you do that, and make sure your IFFT has the correct scaling,
then you should get C[n] = C'[n]

> Can some1 explain what could be wrong?

if you do what i wrote above and it still doesn't work, then i do not know
what is wrong.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Yes, actually I got confused, wrote the wrong C[x] forumla and then
pasted it again a few times.. As I said, when normalized, the formula
works for image recongition.

So you guys have used this correlation formula:
C[n] = SUM{ A[j] * B[j+n] }          (summing over all j)
            j

and it works?

Can you tell me in what application you were using it?

About my FFT correlation implementation, yes I zero padded correctly
and as expected it works fine, except for the fact that it doesn't
produce the same values as the TD correlation formula.

Hello Tru,

You have used the following method:

c(x)=sum[a(x)*b(x+j)] 	//sum over j

If your replace j by -i (it make no difference, if you sum over j or
-i), you get:

c(x)=sum[a(x)*b(x-i)] 	//sum over i

This expression is known as convolution between the signal a(x) and the
filter b(x). A convolution in the spatial domain corresponds to a
multiplication in the frequency domain. This is why you can calculate:

c(x)=IFFT[FFT(a)*FFT(b)]

However, you are searching an algorithm which shows if a(x) and b(x)
match for a given position. Thus the right formula is, how already
explained by Matt and Robert:

c(n)=sum[a(x)*b(x+n)] 	//sum over x

This function (correlation) shows the dependency between 2 signals. By
"+n" you shift the signal b, if a(x) and the shifted signal b(x+n) are
similar, c(n) will have a maximum.

I don't know your application. But if you are searching samples, I
don't think that correlation is a good method: if the values of a and b
are identical, but very small, the product will not increment very much
c...

Perhaps you could use differences between the signals, thus something
like

c(n)=sum[abs[a(x)-b(x+n)]] 	//sum over x

if a(x) and b(x) have the same amplitude, c will be low. I used an
accelerated version of the method to recognize watermarks in cigarette
paper (demo in our image analysis system).


Best regards,

Tilman JOCHEMS
http://mfj.chez.tiscali.fr/html/index_en.html

in article 1119085054.352951.114340@o13g2000cwo.googlegroups.com, tru at
truseddsp@yahoo.com wrote on 06/18/2005 04:57:

> So you guys have used this correlation formula:
> 
>    C[n] = SUM{ A[j] * B[j+n] }          (summing over all j)
>            j
> 
> and it works?

it is what it is.  dunno how well that "works".

> Can you tell me in what application you were using it?

for me, the determination of the period or fundamental frequency of a
quasi-periodic musical tone.

> About my FFT correlation implementation, yes I zero padded correctly
> and as expected it works fine, except for the fact that it doesn't
> produce the same values as the TD correlation formula.

is it off by a factor?  it *should* give you the same thing to the extent
that is numerically allowed.  i presume you're doing this in floating-point?
i could give you a MATLAB script that shows the equivalence.


    C[n] = SUM{ A[j] * B[n-j] }          (summing over all j)
            j

is very similar to correlation, it is "convolution" and that is equivalent
to

    C[n] = IFFT( FFT(A[n]) * FFT(B[n]) )

when you change B[n-j] to B[n+j], that imposes the conj() operator on the
FFT of B[n].  it should work out to be the same.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

"tru" <truseddsp@yahoo.com> ha scritto nel messaggio 
news:1119085054.352951.114340@o13g2000cwo.googlegroups.com...
> Yes, actually I got confused, wrote the wrong C[x] forumla and then
> pasted it again a few times.. As I said, when normalized, the formula
> works for image recongition.

If you used the correct formula, as pointed out by Robert, this is strange, 
because the normalization factor is only a constant.
Perhaps there is a bug in your program.

> So you guys have used this correlation formula:
> C[n] = SUM{ A[j] * B[j+n] }          (summing over all j)
>            j
>
> and it works?

You have to try also C[n] = SUM{ A[j+n] * B[j] }//(summing over all j)
                                 j
to be sure to find some correlation, if it exists (think about two retarded 
or anticipated pulses).

> Can you tell me in what application you were using it?

In a SODAR experiment I tried to measure the horizontal wind profile 
correlating, at the same heights, the signal received from three vertical 
antennas spaced 100 metres apart. Actually i didn't correlate the 
intensities of the signal but the vertical wind, because it was more 
reliable. I used both the formulas above because I didn't know in advance 
what was the wind direction. They worked in my case.

> About my FFT correlation implementation, yes I zero padded correctly
> and as expected it works fine, except for the fact that it doesn't
> produce the same values as the TD correlation formula.

Did you use the correct scaling factor? I think it is 1/N where N=number of 
points (but I haven't checked it).
Haven't you tried to use coherence and its phase?

Angelo 

Problem solved. As you all probably expected it was all my fault :).
The fft function used a preprocessing function input, which I failed to
see while debugging.

However this linear correlation thing is not reliable for anything.

As Tilman JOCHEMS pointed, i am better off computing the distances in
most cases. Which makes me think that most publications about image
recognition based on linear correlation are flawed, but since they
don't provide any source code or working programs i can say for sure.

Normalization helps, but it's very slow and doesn't product sharper
peaks than the diferrence algorithm.
Another thing that helps is remobing the mean from the input
images/signals (really helps).
Both normalization and subtracting the mean make the algorithm slow
(though the mean removal is not too slow).

Thanks all

tru wrote:
...
> However this linear correlation thing is not reliable for anything.
> 
> As Tilman JOCHEMS pointed, i am better off computing the distances in
> most cases. Which makes me think that most publications about image
> recognition based on linear correlation are flawed, but since they
> don't provide any source code or working programs i can say for sure.

Cross correlation (also called template matching) is
fine when it is used appropriately.  Otherwise a
difference measure is better; I prefer the square of
of the error.  See a previous thread on this
newsgroup at:
http://groups.google.ca/group/sci.image.processing/browse_frm/thread/42a74f75ec6ea636/dd601995272eb9de?q=author:martin+author:leese&rnum=102&hl=en#dd601995272eb9de

Cross correlation is appropriate when you have small
light objects on a dark background.  White letters on
black paper is the classic example.

-- 
Regards,
Martin Leese
E-mail: please@see.Web.for.e-mail.INVALID
Web: http://members.tripod.com/martin_leese/

tru wrote:

> Problem solved. As you all probably expected it was all my fault :).
> The fft function used a preprocessing function input, which I failed to
> see while debugging.
> 
> However this linear correlation thing is not reliable for anything.

Not with the formula you used, unless the input is normalized properly.

Here's why: Consider the original signals A and B, and modified signals

A'(x) := A(x) + c
B'(x) := B(x) + c

where c is a constant. Would you agree that the correlation between
A and B should give the same result as the correlation between A' and 
B'? I would, at least. However, the presented formula doesn't, it isn't 
shift-invariant.

Fix: Normalize input such that the average of A and B is zero.

It is also often useful to normalize the inputs such that their norm is one.

So long,
	Thomas