Thread Subject: fast 3D convolution

Is there a faster way to do 3D convolution than convn or
using fftn for convolution?

FFTs appear to be many times faster based on a quick
experiment. For a 101x101x101 volume convolved with a
11x11x11 volume, convolving in the frequency domain looks to
be ~16 times faster...

Am I missing something?

Any good tools on the exchange for 3D convolution that might
go faster?

Any idea why convn seems to be so slow?




Here's the code:

%% Compare convn to n-D convolution in the frequency domain
M=rand(101,101,101)>.99;
ker=rand(11,11,11);

tic;A1=convn(M,ker);t1=toc;
A2=convn(ker,M);t2=toc;
A3=conv3Dfreq(M,ker);t3=toc;

disp(['convolution with convn(big,little) took
',num2str(t1),' seconds']);
disp(['convolution with convn(little,big) took
',num2str(t2-t1),' seconds']);
disp(['convolution with conv3Dfreq(big,little) took
',num2str(t3-t2),' seconds']);


Where conv3dfreq.m is:

function MFout=conv3Dfreq(cprocl,vker)

cprocl=double(cprocl);
smoothcell=zeros(size(cprocl));
centerpix=floor(size(cprocl)/2);
centerker=floor(size(vker)/2);

embed1i=centerpix(1)-centerker(1)+[1:size(vker,1)];
embed2i=centerpix(2)-centerker(2)+[1:size(vker,2)];
embed3i=centerpix(3)-centerker(3)+[1:size(vker,3)];

smoothcell(embed1i,embed2i,embed3i)=vker;

% disp('matched filter correlating observed volume');
% Correlation through FFT needs:
% a. Finding FFT(S) and FFT(C)
FFT1=fftn(cprocl);
FFT2=fftn(smoothcell);
% b. ComplexArray=FFT(S) * Conj{FFT(C)}
CPXARR2=FFT1.*conj(FFT2);
% c. IFFT{ComplexArray}
MFout=2*abs(fftshift(ifftn(CPXARR2)));

"John " <nospam@nospam.com> wrote in message <fdeacr$7ps$1@fred.mathworks.com>...
>
> Is there a faster way to do 3D convolution than convn or
> using fftn for convolution?
>
> FFTs appear to be many times faster based on a quick
> experiment. For a 101x101x101 volume convolved with a
> 11x11x11 volume, convolving in the frequency domain looks to
> be ~16 times faster...
>
> Am I missing something?
>
> Any good tools on the exchange for 3D convolution that might
> go faster?
>
> Any idea why convn seems to be so slow?
>
>
>
>
> Here's the code:
>
> %% Compare convn to n-D convolution in the frequency domain
> M=rand(101,101,101)>.99;
> ker=rand(11,11,11);
>
> tic;A1=convn(M,ker);t1=toc;
> A2=convn(ker,M);t2=toc;
> A3=conv3Dfreq(M,ker);t3=toc;
>
> disp(['convolution with convn(big,little) took
> ',num2str(t1),' seconds']);
> disp(['convolution with convn(little,big) took
> ',num2str(t2-t1),' seconds']);
> disp(['convolution with conv3Dfreq(big,little) took
> ',num2str(t3-t2),' seconds']);
>
>
> Where conv3dfreq.m is:
>
> function MFout=conv3Dfreq(cprocl,vker)
>
> cprocl=double(cprocl);
> smoothcell=zeros(size(cprocl));
> centerpix=floor(size(cprocl)/2);
> centerker=floor(size(vker)/2);
>
> embed1i=centerpix(1)-centerker(1)+[1:size(vker,1)];
> embed2i=centerpix(2)-centerker(2)+[1:size(vker,2)];
> embed3i=centerpix(3)-centerker(3)+[1:size(vker,3)];
>
> smoothcell(embed1i,embed2i,embed3i)=vker;
>
> % disp('matched filter correlating observed volume');
> % Correlation through FFT needs:
> % a. Finding FFT(S) and FFT(C)
> FFT1=fftn(cprocl);
> FFT2=fftn(smoothcell);
> % b. ComplexArray=FFT(S) * Conj{FFT(C)}
> CPXARR2=FFT1.*conj(FFT2);
> % c. IFFT{ComplexArray}
> MFout=2*abs(fftshift(ifftn(CPXARR2)));
>
>
I do not think your method could work. As the arguements 'FFT1' and 'FFT2' are M-by-N-by-P matrix, but matlab could not calculate the multiplication of a 3D matrix

> Is there a faster way to do 3D convolution than convn or
> using fftn for convolution?

Are you convolving with a separable kernel? If so you can exploit separability (or should be able to) and convolve along x, y, and z successively.

"Yin Wang" <tigerwang_nj@hotmail.com> wrote in message <gh3pep$ifo$1@fred.mathworks.com>...
> "John " <nospam@nospam.com> wrote in message <fdeacr$7ps$1@fred.mathworks.com>...
> >
> > Is there a faster way to do 3D convolution than convn or
> > using fftn for convolution?
> >
> > FFTs appear to be many times faster based on a quick
> > experiment. For a 101x101x101 volume convolved with a
> > 11x11x11 volume, convolving in the frequency domain looks to
> > be ~16 times faster...
> >
> > Am I missing something?
> >
> > Any good tools on the exchange for 3D convolution that might
> > go faster?
> >
> > Any idea why convn seems to be so slow?
> >
> >
> >
> >
> > Here's the code:
> >
> > %% Compare convn to n-D convolution in the frequency domain
> > M=rand(101,101,101)>.99;
> > ker=rand(11,11,11);
> >
> > tic;A1=convn(M,ker);t1=toc;
> > A2=convn(ker,M);t2=toc;
> > A3=conv3Dfreq(M,ker);t3=toc;
> >
> > disp(['convolution with convn(big,little) took
> > ',num2str(t1),' seconds']);
> > disp(['convolution with convn(little,big) took
> > ',num2str(t2-t1),' seconds']);
> > disp(['convolution with conv3Dfreq(big,little) took
> > ',num2str(t3-t2),' seconds']);
> >
> >
> > Where conv3dfreq.m is:
> >
> > function MFout=conv3Dfreq(cprocl,vker)
> >
> > cprocl=double(cprocl);
> > smoothcell=zeros(size(cprocl));
> > centerpix=floor(size(cprocl)/2);
> > centerker=floor(size(vker)/2);
> >
> > embed1i=centerpix(1)-centerker(1)+[1:size(vker,1)];
> > embed2i=centerpix(2)-centerker(2)+[1:size(vker,2)];
> > embed3i=centerpix(3)-centerker(3)+[1:size(vker,3)];
> >
> > smoothcell(embed1i,embed2i,embed3i)=vker;
> >
> > % disp('matched filter correlating observed volume');
> > % Correlation through FFT needs:
> > % a. Finding FFT(S) and FFT(C)
> > FFT1=fftn(cprocl);
> > FFT2=fftn(smoothcell);
> > % b. ComplexArray=FFT(S) * Conj{FFT(C)}
> > CPXARR2=FFT1.*conj(FFT2);
> > % c. IFFT{ComplexArray}
> > MFout=2*abs(fftshift(ifftn(CPXARR2)));
> >
> >
> I do not think your method could work. As the arguements 'FFT1' and 'FFT2' are M-by-N-by-P matrix, but matlab could not calculate the multiplication of a 3D matrix

Yin,
The code does work. You can tell by running it. The .* is array multiplication and is different from * which is matrix multiplication.

See here for how matlab works:
www.mathworks.com/access/helpdesk/help/techdoc/ref/arithmeticoperators.html

"Matt" <mjacobson.removethis@xorantech.com> wrote in message <gh3s52$3h1$1@fred.mathworks.com>...
>
> > Is there a faster way to do 3D convolution than convn or
> > using fftn for convolution?
>
> Are you convolving with a separable kernel? If so you can exploit separability (or should be able to) and convolve along x, y, and z successively.

Matt,

Thanks.

That's a good suggestion for decomposing the convolution, but unfortunately my kernel is not separable. I used a random kernel in the example, which is almost never separable.

A collaborator used imfilter and told me it was faster than convn--for specific kernel sizes, I believe.