Hello group, thanks to your help I was able to get my last problem solved (zero padding). Now it works, only small problem is still there: When my object moves x, y pixels it works when x, y is not too small. For example 10, 7 movement, it works brilliant. But when movement is -1, -1 or -1, 0 or -1, 1 or 0, -1 or 0, 1 or 1, -1 or 1, 0 it always detects a false positive maximum at 0, 0. These 7 cases are really the only thing not working. As soon as movement is 2, 0 or 2, 1 it works exactly. I have looked at the images and it really is so as I say: When I move -1, -1 for example and I normalize my CCXed picture to have values from 0-1000 then there is a pixel with value 1000 (my false positive maximum) in 0, 0 and a pixel with say 950 in -1, -1. How do I get around this? I really need to accurately see small movement too. I read something about dividing by the local variance but did not see a formula or anything and do not actually know if this would help my case. Can anyone think of something? Thank you very much! Greetings, Frederick
Again trouble with cross correlation
Started by ●July 14, 2009
Reply by ●July 14, 20092009-07-14
On 14 Jul, 21:35, Frederick Mengin <FrederickMen...@gmx.de> wrote:> Hello group, > > thanks to your help I was able to get my last problem solved (zero > padding). Now it works, only small problem is still there: When my > object moves �x, y pixels it works when x, y is not too small. For > example 10, 7 movement, it works brilliant. But when movement is -1, > -1 or -1, 0 or -1, 1 or 0, -1 or 0, 1 or �1, -1 or 1, 0 it always > detects a false positive maximum at 0, 0. These 7 cases are really the > only thing not working.So to get the overview: The cases that don't work are: (-1 -1) (-1 0) (-1 1) ( 0 -1) ( 0 1) ( 1 -1) ( 1 0) What is different with (1,1)? All the others represent movements along or across edges in the image, while the (1,1) movement represents a movement towards the interior of the image. Could this be an edge effect? Is the target area located too close to the edge of the image? Are there wrap-around effects that are not accounted for?> As soon as movement is 2, 0 or 2, 1 it works > exactly. I have looked at the images and it really is so as I say: > When I move -1, -1 for example and I normalize my CCXed picture to > have values from 0-1000 then there is a pixel with value 1000 (my > false positive maximum) in 0, 0 and a pixel with say 950 in -1, -1. > > How do I get around this? I really need to accurately see small > movement too. I read something about dividing by the local variance > but did not see a formula or anything and do not actually know if this > would help my case. Can anyone think of something?The one thing I would suggest is to use the cross *covariance*, not the cross correlation. Then test with perfect data, that is, noise-free simulated data. Rune
Reply by ●July 14, 20092009-07-14
Hello Rune, On 14 Jul., 22:02, Rune Allnor <all...@tele.ntnu.no> wrote:> So to get the overview: The cases that don't work are: > > (-1 -1) > (-1 �0) > (-1 �1) > ( 0 -1) > ( 0 �1) > ( 1 -1) > ( 1 �0) > > What is different with (1,1)?Actually nothing - it was my fault :-( The (1, 1) case does't work also just like the others above. I am sorry for this mistake that I made.> All the others represent > movements along or across edges in the image, while > the (1,1) movement represents a movement towards the > interior of the image. Could this be an edge effect? > Is the target area located too close to the edge of > the image? Are there wrap-around effects that are not > accounted for?It cannot be a wrap-around effect as the image is quite big (640x480) compared to the object (about 5x5) and the object is dead center.> > As soon as movement is 2, 0 or 2, 1 it works > > exactly. I have looked at the images and it really is so as I say: > > When I move -1, -1 for example and I normalize my CCXed picture to > > have values from 0-1000 then there is a pixel with value 1000 (my > > false positive maximum) in 0, 0 and a pixel with say 950 in -1, -1. > > > How do I get around this? I really need to accurately see small > > movement too. I read something about dividing by the local variance > > but did not see a formula or anything and do not actually know if this > > would help my case. Can anyone think of something? > > The one thing I would suggest is to use the > cross *covariance*, not the cross correlation. > Then test with perfect data, that is, noise-free > simulated data.I did as you instructed and tested with noise-free data: voila, it yielded perfect results. So could it be that because so many noise stays invariant (e.g. translated (0, 0)) this gives me a false positive? However I cannot simply ignore (0, 0) because sometimes the image does not move at all and I need to detect these case. Your tip using the cross covariance - how would I do that? From what I've read so far, I cannot distinguish between cross covariance and cross correlation, as both seem to be \int f^*(t) g(x + t) dt (so my operation would also be IFFT(FFT(F) * FFT(G)') where ' is the complex conjugate. Could you clearify this? Thanks you for your help! Greetings, Frederick
Reply by ●July 14, 20092009-07-14
On 14 Jul, 23:06, Frederick Mengin <FrederickMen...@gmx.de> wrote:> I did as you instructed and tested with noise-free data: voila, it > yielded perfect results. So could it be that because so many noise > stays invariant (e.g. translated (0, 0)) this gives me a false > positive?Yep.> However I cannot simply ignore (0, 0) because sometimes the > image does not move at all and I need to detect these case. Your tip > using the cross covariance - how would I do that? From what I've read > so far, I cannot distinguish between cross covariance and cross > correlation, as both seem to be \int f^*(t) g(x + t) dt (so my > operation would also be IFFT(FFT(F) * FFT(G)') �where ' is the complex > conjugate. Could you clearify this?Subtract the mean from both pictures: Cgf = IFFT(FFT(F-mean(F)) * FFT(G-mean(G))'); Rune
Reply by ●July 14, 20092009-07-14
Hello Rune, On 14 Jul., 23:20, Rune Allnor <all...@tele.ntnu.no> wrote:> On 14 Jul, 23:06, Frederick Mengin <FrederickMen...@gmx.de> wrote: > > > I did as you instructed and tested with noise-free data: voila, it > > yielded perfect results. So could it be that because so many noise > > stays invariant (e.g. translated (0, 0)) this gives me a false > > positive? > > Yep.Yikes :-(> > However I cannot simply ignore (0, 0) because sometimes the > > image does not move at all and I need to detect these case. Your tip > > using thecrosscovariance - how would I do that? From what I've read > > so far, I cannot distinguish betweencrosscovariance andcross > >correlation, as both seem to be \int f^*(t) g(x + t) dt (so my > > operation would also be IFFT(FFT(F) * FFT(G)') �where ' is the complex > > conjugate. Could you clearify this? > > Subtract the mean from both pictures: > > Cgf = IFFT(FFT(F-mean(F)) * FFT(G-mean(G))');Ok, I tried this - but it did not change the problem. Some things I'm thinking about: Maybe just looking for the "hottest" pixel is not a so good idea after all - could it help to also look at the sourrounding pixels to determine the center? Are there algorithms for doing these? I also thought about using a crude workaround: Just ignore (0, 0) when looking for the hottest pixel - then also subtract the images and take the L2 norm. If it is below a certain threshold the images are equal (i.e. not translated at all) otherwise the result from the CCX is correct. However I am reluctant to doing it this way because it would be kind of botch (I do not know if this is the correct word, I just typed it in into dict.cc - I'm looking for "Pfusch"). Thank you again for your help! Greetings, Frederick
Reply by ●July 14, 20092009-07-14
On 14 Jul, 23:46, Frederick Mengin <FrederickMen...@gmx.de> wrote:> > Subtract the mean from both pictures: > > > Cgf = IFFT(FFT(F-mean(F)) * FFT(G-mean(G))'); > > Ok, I tried this - but it did not change the problem.Then the next thing to try is to compute the *local* covariance across the image. This means that you can no longer use the FFT, but have to do a convolution. In pseudocode: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% x: Image y: (2L+1)*(2L+1) mask [M,N] / size(x) cxy = zeros(M,N) for n=1:N for m=1:M z = x(m-L:m+L,n-L:n+L); cxy(m,n) = sum(sum((z-mean(z)).*(y-mean(y)))); end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In plain English: For every (m,n), extract the (2L+1)*(2L+1) part of the image that is covered by the mask y into a variable z. Subtract the mean from this sub image and the mask y. Compute the correlation coefficient cxy(m,n) as the inner product between z and y, both with means subtracted. I think this will work, but it might take a lot longer to run. But more often than not, slow algorithms that actually work take presedence over fast algorithms that don't. Rune
Reply by ●July 14, 20092009-07-14
On 15 Jul., 00:18, Rune Allnor <all...@tele.ntnu.no> wrote:> On 14 Jul, 23:46, Frederick Mengin <FrederickMen...@gmx.de> wrote: > > > > Subtract the mean from both pictures: > > > > Cgf = IFFT(FFT(F-mean(F)) * FFT(G-mean(G))'); > > > Ok, I tried this - but it did not change the problem. > > Then the next thing to try is to compute the *local* > covariance across the image. This means that you can > no longer use the FFT, but have to do a convolution. > > In pseudocode: > > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% > x: Image > y: (2L+1)*(2L+1) mask > > [M,N] / size(x) > cxy = zeros(M,N) > for n=1:N > � �for m=1:M > � � � z = x(m-L:m+L,n-L:n+L); > � � � cxy(m,n) = sum(sum((z-mean(z)).*(y-mean(y)))); > � �end > end > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%OK, here is how I adapted this in (not yet working) C++ code: const unsigned int L = 5; Picture y(2 * L + 1, 2 * L + 1); /* How to initialize y? */ y -= y.Avg(); Picture cxy(N, M); cxy.Clear(); /* Cutoff at L because stencil z will be undefined otherwise */ for (unsigned int n = L; n < cxy.GetWidth() - L; n++) { for (unsigned int m = L; m < cxy.GetHeight() - L; m++) { Picture z(2 * L + 1, 2 * L + 1); z.CopyFrom(x, m - L, n - L); z -= z.Avg(); for (unsigned int x = 0; x < z.GetWidth(); x++) { for (unsigned int y = 0; y < z.GetHeight(); y++) { cxy(x, y) += z(x, y) * y(x, y); } } } }> In plain English: For every (m,n), extract the > (2L+1)*(2L+1) part of the image that is covered > by the mask y into a variable z. Subtract the mean > from this sub image and the mask y. Compute thecorrelationcoefficient cxy(m,n) as the inner > product between z and y, both with means subtracted.The problem is (I commented in the code also): How do I initialize y, the mask? What kind of stencil is appropriate here? Also: What do I do in the regions where I cannot fully copy from x into z (e.g. from 1 to L-1 and from Width - L to Width)? Just skip over them? Did I get the basic idea right at all?> I think this will work, but it might take a lot > longer to run. But more often than not, slow algorithms > that actually work take presedence over fast algorithms > that don't.Yes, if it would work that'd be awesome, no matter how long it takes (O (n^2) instead of O(n logn), but the main thing is the result is correct). Thanks again, Greetings, Frederick
