2-D convolution using the FFT

Convolution in 2-D using the Fast Fourier Transform.

This function can be used instead of CONV2 (with the same arguments). It will produce the same results to within a small tolerance, and may be faster in some cases (and slower in others). Two additional shape options are included, offering periodic and reflective boundary conditions.

The Convolution Theorem states that convolution in the time or space domain is equivalent to multiplication in the frequency domain. Convolution may therefore be implemented using ifft2(fft(x) .* fft(m)), where x and m are the arrays to be convolved. The fiddly part is getting the array positioning and padding right so that the results are consistent with the conventional convolution function, CONV2. CONV_FFT2 handles these problems, offering a potentially more efficent plug-in replacement for CONV2.

In practice, whether this is faster depends on many factors, of which the most important is the size of the mask (or kernel) compared to the size of the main input array (often an image). Larger masks will tend to give the FFT approach the advantage, but it is necessary to test this experimentally in any application. For small masks, CONV2 or CONVOLVE2 (available from the file exchange) may be faster.