[ITK] [ITK Community] Speeding up Cross Correlation

[Bradley Lowekamp]

Hello,

FFT's only operate on the whole image in the frequency domain, so the the cost to compute can not be changed as you ask. You should be able to crop the large image though to reduce the computation.

However, there is an alternative. I think you have a case to try the non-FFT version the NormalizedCorrelationImageFilter[1]. This filter operates in the spacial domain and appears to support updating an arbitrary area [2]. So you should be able to use an ExtractImageFilter or manually set the ROI to update and only update the needed area.

As you suspect this is still a really large neighborhood to do in the spacial domain the order of the operation is 500x500x50x50 = 6.25e8, where if the FFT operation is O(n log n), with n = 1000x1000 then the operation is on the order of 6e6. So it's likely the spacial domain algorithm will still be slower. 

This is an interesting case. I hope you report your conclusion.

Brad

[1] http://www.itk.org/Doxygen/html/classitk_1_1NormalizedCorrelationImageFilter.html
[2] https://github.com/InsightSoftwareConsortium/ITK/blob/master/Modules/Filtering/Convolution/include/itkNormalizedCorrelationImageFilter.hxx#L47-L90

On Nov 21, 2014, at 1:18 PM, Arjun S Kumar <arjun89 at cmu.edu> wrote:

> Hi all,
> 
> I am trying to cross correlate two images such that the output image displays the similarity of the first image and the second image as a function of the translation of the second image. 
> 
> Currently, I'm using the itk::FFTNormalizedCorrelationImageFilter class. However, only a small portion, close to the center, of the output image is relevant for me. For example, for two images of sizes 500x500, the output image is about 1000x1000. However, I only need a 50x50 portion of the output image, centered at the center of the output image. 
> 
> So my question is, can I use this fact to perform the cross correlation faster? I tried using the SetRequiredNumberOfOverlappingPixels method to discard regions outside the 50x50 portion of the image but this didn't have a discernible effect on the speed of the operation. Shouldn't setting the required number of overlapping pixels to a high number decrease the time needed by reducing the domain of the output image?
> 
> Is there a different way to manually set the size of the output image so that the computation is made faster? Can I change the requested region of the output image, just as we can do for input images?
> 
> Are there other ITK classes that are more suited for this purpose. Does anybody recommend using neighborhood iterators? The problem I see with this is using a 500x500 neighborhood, which is too high isn't it?
> 
> Please let me know. 
> 
> Thanks,
> 
> Arjun
> _______________________________________________
> Community mailing list
> Community at itk.org
> http://public.kitware.com/mailman/listinfo/community