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!

# time domain and fft correlation paradox

Started by ●June 17, 2005

Reply by ●June 17, 20052005-06-17

"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

Reply by ●June 17, 20052005-06-17

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

Reply by ●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.

Reply by ●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 ●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 ●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 ●June 18, 20052005-06-18

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 ●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.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/

Reply by ●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