3

So I wrote this:

function y = convolution(u,v)

[m,n] = size(u);
[w,z] = size(v);

y = zeros(m-w+1,n-z+1);
for i = 1:m-w+1
    for j = 1:n-z+1
        y(i,j) = sum(sum(u(i:i+w-1,j:j+z-1).*v));
        end
    end


    end

And then I compared it to conv2() in matlab with this:

function timedConv
a = im2double(rgb2gray(imread('picture.png')));

tic
convolution(a,[4 5 6;0 0 0;3 2 1]);
toc

tic
conv2(a,[4 5 6; 0 0 0; 3 2 1]);
toc
end

and found that mine takes over 4 seconds to run, while matlab's conv2 takes about 0.01 seconds. What's more, mine is outputting a m-w+1 x n-z+1 matrix, while matlab's outputs a m+w-1 x n+z-1, so it's assuming zero rows and columns outside of the image to do convolutions on the edges of the image. When I display the results, they look the same, so my function must be working. It's just so much slower and I have no idea why.. Can I get rid of the for loops somehow?

qwert
  • 331
  • 2
  • 12
  • `"Can I get rid of the for loops somehow?"` - http://stackoverflow.com/questions/25449279/efficient-implementation-of-im2col-and-col2im – Divakar Nov 08 '16 at 18:53
  • That would probably still take just as long to run I'm pretty sure, but thanks! Didn't know about im2col before – qwert Nov 09 '16 at 00:33

1 Answers1

2

Matlab uses a FFT in order to perform a convolution Conv = FFTinv(FFT(Image) x FFT(Kernel)), which is much faster than a classical convolution. More specifically, Matlab call a C++ library to perform the FFT, which is tens of times faster than Matlab.

FiReTiTi
  • 5,597
  • 12
  • 30
  • 58
  • Interesting. I'm not familiar with the fast Fourier transform; I'll have to look into it. Do you happen to know what makes FFT so much faster and why C++ is faster than matlab? – qwert Nov 08 '16 at 21:48
  • Short answer for FFT: less and constant number of operations. For MatLab, it is a script language without types, when C++ is compiled ans highly optimized. So MatLab is one of the slowest language by itself, but when it is possible, it call C++ function to perform the operations, like operations on matrices, FFT, etc. – FiReTiTi Nov 08 '16 at 22:55
  • Hmm, ok thanks! Would it be worth figuring out how to write my own convolution function using FFT or should I just abandon that and use conv2()? – qwert Nov 09 '16 at 00:32
  • You know that conv2 was optimized, tested, etc. so it works and it works fast! So if you want to use only MatLab, then conv2 is the best option. If you want to build your own C++ library, it already exists many FFT libraries highly optimized. – FiReTiTi Nov 09 '16 at 00:50
  • 1
    @FiReTiTi Do you have any reference that matlab actually uses FFT underneath the hood? From the official [document](https://www.mathworks.com/help/matlab/ref/conv2.html) it seems like it is doing spatial convolution. – Sounak Jun 15 '18 at 07:05
  • Matlab script language is too slow, so they use a FFT. – FiReTiTi Jun 15 '18 at 10:00
  • 1
    @FiReTiTi are you drawing that conclusion solely based on this logic? Doesn't FFT expect a circular boundary option. How do they do the fft based convolution for other boundary options such as "symmetric" or "replicate". Do you have a document or a resource that supports your claim? – Sounak Jun 15 '18 at 20:10
  • No, we used convolution with Matlab and found them surprisingly fast. When we checked what was happening, we found out that a FFT was used. Maybe Matlab automatically switches to FFT is the image/kernel are big. – FiReTiTi Jun 17 '18 at 00:59
  • 1
    @FiReTiTi "When we checked what was happening, we found out that a FFT was used." How did you exactly do that? Did you have source code access? – Sounak Jun 18 '18 at 05:59