Fast FFT convolution in 2D

Hello,

Is there a way to do fast 2D convolution according to: FFT Convolution performance ? In 2D it is not any faster, than standard MAtlab`s convolution. The same is reported of MathWorkd central files repository

pd = fspecial('Gaussian', 61, 10);
noise = poissrnd(0.2, [260 260]);

tic
zz1 = imfilter(noise, pd);
toc

tic
zz2 = conv2fft(noise, pd);
toc

% Compare the relative accuracy (the results are nearly identical)
zz2 = zz2(31:end-30, 31:end-30);
aa = max(abs(zz1-zz2)./abs(zz1));
disp(max(aa))

figure( 'units', 'normalized', 'outerposition', [0 0 1 1], 'name', 'Conv FFT 2D', 'numbertitle', 'off' );
subplot 141, imshow(zz1, []);      title('Convolution');
subplot 142, imshow(zz2, []);      title('FFT');
subplot 143, imshow(zz1-zz2, []);  title('Convolution - FFT'); impixelinfo
subplot 144, surf(zz1-zz2);        title('Convolution - FFT'); rotate3d on; colormap parula

Results:

Elapsed time is 0.048178 seconds

Elapsed time is 0.021171 seconds

1.0758e-15.

In 1D FFT version is ~300x faster.

Answer 1

[Image Analyst]

2D convolution is already very highly optimized in the functions conv2() and imfilter(), even more so for separable kernels. I know for a fact that they put special effort into making these as fast and efficient as possible.

Convolution via fft2 may not be faster, especially for smaller matrices like you have. In fact it might even be slower. Generally the fft method becomes faster only for very large matrices. You can test that by increasing the size of your matrices.