```
tru wrote:

> 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

```
```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

```
```"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
>

```
```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

```
```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:

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
Web: http://members.tripod.com/martin_leese/
```
```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" <truseddsp@yahoo.com> ha scritto nel messaggio
> 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.

> 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

```
```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.

> 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."

```
```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

```
```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?