2D convolution by 1D convolution using separable properties

Question

I am writing a program in which I am doing lots of 2D convolution. So i thought that a more efficient approach may be that to use 1D convolution. But I seem to be stuck on this .

Till now, I have referred to this links :

check this 1) http://blogs.mathworks.com/steve/2006/10/04/separable-convolution/

check this 2) http://blogs.mathworks.com/steve/2006/11/28/separable-convolution-part-2/

I have a gaussian kernel(K) of size 5X5. I need to convolve this kernel function with the image. My image size is forced to be 4000X4000. I am giving the program down below:

clc;clear all;close all;
imgID = 5;
Img = imread([num2str(imgID),'.bmp']);
Img = double(Img(:,:,1));
Img = imresize(Img,[4000 4000]);

sigma=3.0;   
K=fspecial('gaussian',round(2*sigma)*2+1,sigma);     % the Gaussian kernel

%%
%//Trying to use 1D convolution instead of using 2D convolution
[U,S,V] = svd(K);
K1 = U(:,1) * sqrt(S(1,1));
K2 = V(:,1)' * sqrt(S(1,1));

%%
tic
KI=conv2(Img,K,'same');
toc

tic
KI1 = imfilter(Img,K1,'conv');                            
KI1 = imfilter(KI1,K2,'conv');
toc


tic
KI2 = imfilter(Img,K,'conv');
toc

tic
KI3 = conv2(K1,K2,Img,'same');
toc

I checked the rank of the matrix K. It does come 1 so it is indeed a separable vector which can be expressed as the outer product of two 1 D vectors. The 1 D vectors here are termed as K1 & K2. I then timed it to get a feel of which method is faster ? The results are shown below :

%//1st method

Elapsed time is 0.375002 seconds.

%//2nd method

Elapsed time is 1.601285 seconds.

%//3rd method

Elapsed time is 1.884165 seconds.

%//4th method

Elapsed time is 0.315134 seconds.

As you guys can see , The first method is the fastest while the third method is also quite fast. The third & second method also has very low error in the order of e-14 but both of these methods are extremely slow compared to the first one using conv2.

Can you guys tell me why is the method involving the 1D convolution is the slowest ?

Thanks in advance to all of u!!

Edit:Please see my 4th method!!

Which is 4th method ? Do you have any paper to refer it? Thank you — user3051460

Luis Mendo Luis Mendo · Accepted Answer · 2013-09-02T10:23:38

The result in the second method is not KI1*KI2, but KI2. Note that KI2 has already been convolved twice. If you compute KI- KI2 with the second method you get a small error.

As for the speed, I have these comments:

The line KI - KI2 in the second method and the line KI - KI3 in the third are slowing things down, and should not be included in the comparison. Just remove them.
In method two, reuse variable KI1 instead of defining a new KI2: that is, replace KI2 = imfilter(KI1,K2,'conv'); by KI1 = imfilter(KI1,K2,'conv');. That probably reduces time spent in memory allocation.
Your Img matrix is very small. With larger matrices the second method is fastest.

With a 4000 times 4000 Img matrix, and applying the other changes, I respectively get:

Elapsed time is 4.924468 seconds.
Elapsed time is 0.793251 seconds.
Elapsed time is 0.854416 seconds.

2D convolution by 1D convolution using separable properties

1 Answers