CODEWITHSUNDEEP
matlabimage-processingmatrixvectorconvolution
JDS
JDS

Reputation: 16988

Image convolution in MATLAB - how is conv is 360x faster than my hand-coded version?

I am playing with image processing algorithms in MATLAB. One of the basic ones is convolving an image with a Gaussian. I ran the following test on a grayscale 800x600 image:

function [Y1, Y2] = testConvolveTime(inputImage)
[m,n] = size(inputImage);

% casting...
inputImage = cast(inputImage, 'single');

Gvec = [1 4 6 4 1]; % sigma=1;

Y1 = zeros(size(inputImage)); % modify it
Y2 = zeros(size(inputImage)); % modify it


%%%%%%%%%%%%%%%%%%% MATLAB CONV %%%%%%%%%%%%%%%%%%%%%
t1 = cputime;

for i=1:m
    Y1(i,:) = conv(inputImage(i,:),Gvec,'same');
end

for j=1:n
    Y1(:,j) = conv(inputImage(:,j),Gvec','same');
end
      
Y1 = round(Y1 / 16);
e1 = cputime - t1

%%%%%%%%%%%%%%%%%%% HAND-CODED CONV %%%%%%%%%%%%%%%%%%%%%
t2 = cputime;

for i=1:m
    Y2(i,:) = myConv(inputImage(i,:),Gvec)';
end

for j=1:n
    Y2(:,j) = myConv(inputImage(:,j),Gvec');
end
      
Y2 = round(Y2 / 16);
e2 = cputime - t2

end

Here is the code I wrote implementing convolution of 2 vectors:

% mimic MATLAB's conv(u,v,'same') function
% always returns column vec
function y = myConv(u_in, v_in)

len1 = length(u_in);
len2 = length(v_in);

if (len1 >= len2)
   u = u_in;
   v = v_in;
else
   u = v_in;
   v = u_in;
end

% from here on: v is the shorter vector (len1 >= len2)

len1 = length(u); 
len2 = length(v); 
maxLen = len1 + len2 - 1;

ytemp = zeros(maxLen,1);

% first part -- partial overlap
for i=1:len2-1
    sum = 0;
    for j=1:i
       sum = sum + u(i-j+1)*v(j);
    end
    ytemp(i) = sum;
end

% main part -- complete overlap
for i=len2:len1
    sum = 0;
    for j=1:len2
       sum = sum + u(i-j+1)*v(j);
    end
    ytemp(i) = sum;
end

% finally -- end portion
for i=len1+1:maxLen
    %i-len1+1
    sum = 0;
    for j=i-len1+1:len2
       sum = sum + u(i-j+1)*v(j);
    end
    ytemp(i) = sum;
end

%y = ytemp;

startIndex = round((maxLen - length(u_in))/2 + 1);
y = ytemp(startIndex:startIndex+length(u_in)-1); 
% ^ note: to match MATLAB's conv(u,v,'same'), the output length must be
%   that of the first argument. 
end

Here are my test results:

>> [Y1, Y2] = testConvolveTime(A1);

e1 =

    0.5313


e2 =

  195.8906

>> norm(Y1 - Y2)

ans =

     0

The norm being 0 verifies mathematical correctness. My questions are as follows:

  1. How can my hand-coded function be >360x slower than the one that uses MATLAB's conv?

  2. Even MATLAB's conv is still "slow" for image processing. If convolving with a Gaussian takes 0.5 of a second, what hope is there for running any image processing algorithms in real-time (e.g. at 24 FPS)? For reference my CPU is Intel N3540 @ 2.16 GHz. w/ 8GB of RAM.

  3. ^ The real question: when I switch to OpenCV on C++, will operations like this become much faster?

Upvotes: 3

Views: 1054

Answers (3)

Bashar Haddad
Bashar Haddad

Reputation: 368

Why convolution in matalab is faster? The implementation itself is very efficient. They use fast techniques to perform multiplication and convolution. check the BLAS, ATLAS packages if you want to see tricks to do these things very fast.

in practical (convolution in the original domain \ time or space) and (multiplication in frequency domain) are equivalent. what they do is to transform to frequency domain by using FFT (Fast Fourier Transform) and then perform the multiplication and then go back to the original domain.

Upvotes: 2

percusse
percusse

Reputation: 3106

Because (discrete) convolution is often represented via linear algebra but certainly not via for loops. In fact everytime you walk through rows or columns you should seek for ways to represent it as an algebraic operation.

The typical way is to do it via Toeplitz matrices but can be extended to way faster algorithms. And once you have the toeplitz structure then you can optimize the multiplication even further

https://en.wikipedia.org/wiki/Toeplitz_matrix#Discrete_convolution

http://www.netlib.org/utk/people/JackDongarra/etemplates/node384.html

Note that native Matlab functions can still be slow. It is not an indication of speed but maintenance level. Often you can find the algorithm used linked in the documentation and you can decide whether you should go for the custom implementation or the standard.

Upvotes: 2

Dima
Dima

Reputation: 39389

1) conv is so much faster because it is an built-in native function, while your function is interpreted MATLAB code with nested loops.

2) Try imfilter in the Image Processing Toolbox. It may be faster than conv, and it works on uint8 arrays. Or, if you get a more recent version of MATLAB, and if you only need the Gaussian filter, try imgaussfilt.

Upvotes: 5

Related Questions