Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

2D convolution in matlab - code optimization

this is our exercise in image processing homework. my code is working fine. i would like to get some help with code optimization.

function C = convolve_slow(A,B)
(file name is accordingly convolve_slow.m ) 
This routine performs convolution between an image A and a mask B.
Input:      A - a grayscale image (values in [0,255]) 
            B - a grayscale image (values in [0,255]) serves as a mask in the convolution.
Output:     C - a grayscale image (values in [0,255]) - the output of the convolution. 
                      C is the same size as A.

Method:  Convolve A with mask B using zero padding. Assume the origin of B is at 
     floor(size(B)/2)+1.
Do NOT use matlab convolution routines (conv,conv2,filter2 etc). 
Make the routine as efficient as possible: Restrict usage of for loops which are expensive (use matrix multiplications and matlab routines such as dot etc).
To simplify and reduce ifs, you should pad the image with zeros before starting your convolution loop.
Do not assume the size of A nor B (B might actually be larger than A sometimes).

Here is our solution

function [ C ] = convolve_slow( A,B )
%This routine performs convolution between an image A and a mask B.
% Input:      A - a grayscale image (values in [0,255])
%             B - a grayscale image (values in [0,255]) serves as a mask in the convolution.
% Output:     C - a grayscale image (values in [0,255]) - the output of the convolution. 
%             C is the same size as A.
% 
% Method:  Convolve A with mask B using zero padding. Assume the origin of B is at floor(size(B)/2)+1.
% init C to size A with zeros
C = zeros(size(A));
% make b xy-reflection and vector
vectB = reshape(flipdim(flipdim(B,1),2)' ,[] , 1);
% padding A with zeros
paddedA = padarray(A, [floor(size(B,1)/2) floor(size(B,2)/2)]);
% Loop over A matrix:
for i = 1:size(A,1)
    for j = 1:size(A,2)
        startAi = i;
        finishAi = i + size(B,1) - 1;
        startAj = j;
        finishAj = j + size(B,2) - 1;
        vectPaddedA = reshape(paddedA(startAi :finishAi,startAj:finishAj)',1,[]);
        C(i,j) = vectPaddedA* vectB;
    end
end
end  

since i'm new to Image Processing and Matlab. can you please help me with code optimization , specifically with matrix based operations. is it possible not to use loops?

like image 331
Gilad Avatar asked Dec 15 '12 21:12

Gilad


2 Answers

Without writing the code out explicitly, I can see a way to get it down to one main for loop. Basically, think of the matrix A and B as column vectors by unwrapping each column of A and B into a vector (that's how it's stored internally in MATLAB). Then each (i,j) coordinate of A can be mapped to a linear index k (using the function sub2ind for example). Then, for each linear index within the body of A (ignoring padding), compute the list of linear indices corresponding the a submatrix around this linear index (that's probably the hardest part here). Then compute the dot product of A( theseIndices ) and B(:). With this method you are just looping over each linear index of A.

like image 116
MarkV Avatar answered Oct 12 '22 13:10

MarkV


Dont know if this is faster, but at least there are no for loops (which does not mean it has to be faster anymore in recent matlab versions)

function A = tmpConv(A,B)

    filterSize = size(B,1);
    filterSize2 = floor(filterSize/2);
    inputSize = size(A);

    A = padarray(A,[filterSize2 filterSize2]);

    f = repmat(B(:),[1 inputSize(1)*inputSize(2)]);
    A = im2col(A,[filterSize filterSize]);
    A = reshape(sum(A.*f),inputSize);
like image 43
user1958650 Avatar answered Oct 12 '22 11:10

user1958650