Cross Correlation

[Ratutus]

Hi,

I have a question regarding the cross correlation Vi.

I have made a simple test with a 480 X 640 array and it takes on average 720 ms for the Vi to compute the 2D cross correlation (using a Quad 9650 CPU @ 3 GHz). 

I am wondering why it is so slow and if it would be possible to compute the cross correlation

using FFT directly  . I tried to do it (sse attached image but it gives wrong results).

Or mayvbe someone knows a better way to do it.

Ant help appreciated.
Thanks

[GregSands]

Calling the 2D cross-correlation with the "frequency domain" algorithm will use essentially the same FFT algorithm as you provide.  You can certainly replicate it yourself, but it will take a similar amount of computational time.  What you will need to do is pad your array to the size of the sum of the sizes of the two input arrays (minus 1) which is the size of the result from the 2D CC.  Here's one way to do that, which requires almost exactly the same computational time:

You'll notice that the result from the FFT technique gives the maximum CC at (0,0) - i.e. when there is a zero pixel shift between images.  The CC function gives the maximum at the centre of the image (i.e. it treats the resulting array as running from [-M:M, -N:N]) - the answers are the same, just the way it's placed into the resulting array is different.  If you want it to match, you'll need to shift the array around.

CCs are simply slow if you have two large arrays like this.  One way you could get some speed up is to install the Sparse Linear Algebra Library from the NI Labs, and use its High Performance FFT routines which are optimised for parallel processing - it will drop from about 700ms to around 250ms on a 2-core machine, and faster still if it can use more cores.

One last note - depending on the arrays that you are correlating, you may want to consider using a normalised cross-correlation.  IMAQ provides such a function, although it seems to be coded incorrectly, but I've also created a 2D normalised CC routine which you may find useful.

[Ratutus]

Thanks for the detailled answer.

I checked on Matlab and it gives more or less the same computation time.

But I will try the optimized routines.
By the way, I have been using your  2D normalized cross correlation  routine for the last two weeks. It works just perfect. Thanks !

[Ratutus]

Just have checked. The optimized routines are just perfect. Using the 4 CPU, it goes about 4X faster (without shifting the array)
Shifting the array to get the same result as the cross correlation Vi slows down a bit the calculation: 2.5 X faster.
I was using something similar to this: http://forums.ni.com/ni/attachments/ni/170/413278/1/Normalized%202D%20FFT%20Correlation.vi . I am wondering if there is a better way to do it.
Best

[GregSands]

Shifting the array doesn't take much time for me - just 5-10ms.  Copying quadrants around like that is probably the quickest and easiest way to do it - the only thing that might be better is not to create a duplicate array - just extract the quadrants and then replace back into the original array. i.e. use the "Replace Array Subset" function rather than "Insert Into Array" and "Build Array".

[ratus]

Ok. Thanks again for the support.
Clearly, these routines are really optimized for multiple cores. As such, it becomes difficult to do other things that processing the data (e.g. acquiring an image simultaneously) cause all the CPUs are fully loaded with the computations.

[ratus]

I just have seen there is a routine, which might help 😉 

Set Num of Threads.vi ine