FFT based convolution
logo

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3154
The Fourier transform of the convolution of two images is equal to the product of their
Fourier transform. With this definition, it is possible to create a convolution filter
based on the Fast Fourier Transform (FFT). The interesting complexity characteristics of
this transform gives a very efficient convolution filter for large kernel images.

This paper provides such a filter, as well as a detailed description of the implementation
choices and a performance comparison with the "simple" itk::ConvolutionImageFilter.
Code
plus Automatic Testing Results by Insight-Journal Dashboard on Wed Mar 10 12:02:06 2010 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 5

Reviews
minus Excellent implementation and analysis. by Matthew Mccormick on 2010-12-05 03:28:16 for revision #4
starstarstarstarstar expertise: 3 sensitivity: 5
yellow
Summary:

The author proposes filters to perform convolution of two images using FFT's.

Hypothesis:

Using an FFT to perform convolution is much faster for larger images than a Neighborhood Iterator.

Evidence:

A number of performance tests were performed.  Comparisons to the itk::ConvolutionImageFilter demonstrated that performance was much better for kernel sizes of 5 or 7 or larger.


Different FFT implementations were compared, including VNL, FFTW, and FFTW + wisdom.


The effect of the greatest prime factor with FFTW was examined.


Scaling with number of threads was examined.

Open Science:

The provides excellent, thorough details in the article, source code, tests, and data.


Some minor bugs were found and sent to the author, and they were quickly incorporated.  This is appreciated.

Reproducibility:

The code compiled fine against ITK 3.20 on linux-gcc-4.4.3, fftw-3.2.2.  Some tests failed:


10: fftconv: /tmp/fftconv/itkFFTWCommon.h:260: static fftwf_plan_s* itk::fftw::Proxy<float>::Plan_dft_r2c_2d(int, int, float*, float (*)[2], unsigned int, int, bool): Assertion `plan != __null' failed.



1/1 Test #10: FFTConv0 .........................***Failed    0.33 sec



 



11: fftconv: /tmp/fftconv/itkFFTWCommon.h:260: static fftwf_plan_s* itk::fftw::Proxy<float>::Plan_dft_r2c_2d(int, int, float*, float (*)[2], unsigned int, int, bool): Assertion `plan != __null' failed.


1/1 Test #11: FFTConv1 .........................***Failed    0.42 sec



13: fftconv: /tmp/fftconv/itkFFTWCommon.h:260: static fftwf_plan_s* itk::fftw::Proxy<float>::Plan_dft_r2c_2d(int, int, float*, float (*)[2], unsigned int, int, bool): Assertion `plan != __null' failed.

1/1 Test #13: FFTConv13 ........................***Failed    0.25 sec




Use of Open Source Software:

Demonstrates good use of ITK/CMake.

Open source Contributions:

The code was easy to use.  The article describes it well along with the Doxygen comments.


There are a number of classes that are separated into logical units and may also be useful for other purposes.

Code Quality :

The code seems to be multi-platform and is very well written.  It handles many use and corner cases, and addresses all the fine details of doing FFT convolution properly: shifting, cropping, boundary conditions, threading, FFT backends, flipping, memory handling, and cropping.


 


Some suggestions:


In FFTConvolutionImageFilterBase, there are a number of cascading PrepareImage(...) methods.  This is a clever way of organizing the different steps and allowing for progress to be tabulated.  However, it obfuscates things when attempting to read the code.  It would be nice if these would be renamed from PrepareImage(...) and ProduceOutput() to something more descriptive.


I may missed the point, but there does not seem to be a need for splitting FFTConvolutionImageFilterBase and FFTConvolutionImageFilter.  These could be merged.

Quality of the data :

The data included was good.  It would be good to use an image with non-unit spacing.

Interest:

I used some of these classes in some code for convolution's cousin correlation.  They worked well there, but it ended up being slower than a Neighborhood Iterator implementation.  Profiling with valgrind + kcachegrind revealed a good amount of time was spent generating the FFTW plan.  The FFTW threading improvements are very nice, but removal of the plan caching was not helpful for my use case.  I did lots of repeated pipeline executions on smaller images (kernel ~31x12).

Free comment :

This should be merged into core ITK.


Comment by Gaetan Lehmann: yellow
> In FFTConvolutionImageFilterBase, there are a number of cascading PrepareImage(...) methods. This is a clever
> way of organizing the different steps and allowing for progress to be tabulated. However, it obfuscates things
> when attempting to read the code. It would be nice if these would be renamed from PrepareImage(...) and
> ProduceOutput() to something more descriptive.

I must agree with that. I've never been good at choosing names in my programs, and it's worth with names in english.
If you have some time, could you propose better names for those methods?

> I may missed the point, but there does not seem to be a need for splitting FFTConvolutionImageFilterBase and
> FFTConvolutionImageFilter. These could be merged.

This is fully related to the other possible usage of this base class. See my contribution on deconvolution for several example of classes using FFTConvolutionImageFilterBase as base class.
minus A very useful contribution for fast convolution by Cory Quammen on 2010-10-07 21:18:33 for revision #4
starstarstarstarstar expertise: 5 sensitivity: 5
yellow
Summary:

Corrupting images by simulated noise is an essential process for generating realistic simulated images where the ground truth data is known and corrupted by noise with known characteristics.

Hypothesis:

Deconvolution algorithms can be added to ITK in a way that uses common API elements to minimize code duplication.

Evidence:

The author provides an implementation of numerous deconvolution algorithms organized into a design that minimizes code duplication. The class hierarchy also serves as a nice conceptual taxonomy of deconvolution algorithms.

Open Science:

All source code and example images are included with the publication. 

Reproducibility:

I could not compile this contribution on Windows because the type uint32 is not defined.

Use of Open Source Software:

All the software provided is open source and extends the open source ITK library.

Open source Contributions:

It took just a few short minutes to configure, compile, and run the examples.

Code Quality :

The code is high quality and appears to conform to ITK's coding style by visual inspection.


 

Quality of the data :

The test images were useful for demonstrating the operation of the noise filters.

Interest:

Adding simulated noise is incredibly useful for many, many fields.

Free comment :

This is a fantastic contribution.

Add a new review
Quick Comments
Comment by Jothybasu Selvaraj yellow
Does it works only with ITK 4.0. I want to use it with ITK 3.20.
Doesn't this journal a requirement to add author's email id.


Resources
backyellow
Download All
Download Paper , View Paper
Download Source code
Github

Statistics more
backyellow
Global rating: starstarstarstarstar
Review rating: starstarstarstarstar [review]
Code rating: starstarstarstarstar
Paper Quality: plus minus
1 comment

Information more
backyellow
Categories: Filtering, Parallelization, SMP
Keywords: FFT, Convolution, Kernel
Toolkits: ITK, CMake
Export citation:

Share
backyellow
Share

Linked Publications more
backyellow
Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy
by Vercauteren T., Pennec X., Perchant A., Ayache N.
Importing Contours from DICOM-RT Structure Sets Importing Contours from DICOM-RT Structure Sets
by Dowling J., Malaterre M., Greer P.B., Salvado O.

View license
Loading license...

Send a message to the author
main_flat
ISSN 2327-770X
Powered by Midas