> However this linear correlation thing is not reliable for anything.
Well, it may perhaps not have been useful in your application, but
to leap from there to say that it is not useful for *anything*
seems to be a bit too harsh... ;)
But I agree with your overall view. Test the method and see how
well it works in your application.
Rune
Reply by Tilman JOCHEMS●June 19, 20052005-06-19
Hello Robert,
robert bristow-johnson a =E9crit :
>
>
> C[n] =3D 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] =3D 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.
>
Thank you for correcting the equation for convolution of my previous
post. I was confused, of course I should have written
c(x)=3Dsum[a(i)*b(x-i)] //sum over i
Best regards,
Tilman JOCHEMS
http://mfj.chez.tiscali.fr/html/index_en.html
Reply by erine●June 19, 20052005-06-19
"Thomas Richter" <thor@math.tu-berlin.de> ha scritto nel messaggio
news:d92djc$2v2$1@mamenchi.zrz.TU-Berlin.DE...
> tru wrote:
[omissis]
> 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.
Not always valid. When I did the Sodar experiment that I cited in a my
previous post, I retained the mean value to obtain a significant
correlation. This had to be because what was correlated was not the
turbulence (zero averaged) of the vertical wind but the values of the wind
itself. Sometimes the constant matters.
Angelo
> It is also often useful to normalize the inputs such that their norm is
> one.
>
> So long,
> Thomas
>
Reply by Thomas Richter●June 18, 20052005-06-18
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
Reply by Martin Leese●June 18, 20052005-06-18
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.
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
Reply by Angelo Ricotta●June 18, 20052005-06-18
"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
Reply by robert bristow-johnson●June 18, 20052005-06-18
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."
Reply by Tilman JOCHEMS●June 18, 20052005-06-18
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
Reply by tru●June 18, 20052005-06-18
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.