View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Fast 2-D convolution

5.0 | 7 ratings Rate this file 29 Downloads (last 30 days) File Size: 5.77 KB File ID: #22619 Version: 1.3

Fast 2-D convolution


David Young (view profile)


08 Jan 2009 (Updated )

Speeds up many 2-D convolutions using the SVD; also finds a fast approximation in other cases.

| Watch this File

File Information

CONVOLVE2 can be used wherever CONV2 is used, taking the same arguments and returning the same results to within a small tolerance. The computation is speeded up by using the singular value decomposition of the mask to express it as a sum of outer products. Each of these can be computed efficiently as convolution with a row and a column vector. CONV2 is used to carry out the individual convolutions.
Separable masks are a particular case and are handled by CONVOLVE2 much as FILTER2 does. Many other masks which are not separable have low rank (e.g. Gabor function masks) and are handled more efficiently by CONVOLVE2.
The function will also compute a reduced-rank approximation to a given mask if required and will use this if it will speed up the computation. An extra argument allows control over the error.
Additional shape options allow: (a) 2-D "circular" convolution - that is, the input array is taken to be periodic rather than surrounded by zeros; (b) a "reflection" boundary condition - that is, the input array is taken to be surrounded by reflected copies of itself.
See 'Computer and Robot Vision' Vol I, by R.M. Haralick and L.G. Shapiro (Addison-Wesley 1992), pp. 298-299.


This file inspired Image Correspondences Using Cross Correlation.

Required Products MATLAB
MATLAB release MATLAB 8.2 (R2013b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (9)
16 Nov 2015 YoonOh Tak

YoonOh Tak (view profile)

Fast and accurate!

01 Sep 2015 Stefan Karlsson

Stefan Karlsson (view profile)

Great submission. Works as described without a flaw and is well documented in code.

A Suggestion if anyone feels like working on this great code further:

One could clearly seperate the code that analyses the filter from the actual filtering (convolution). This would make the benefits clearer for iterative variational methods and/or real-time video processing.


27 Mar 2013 Evgeny Pr

Evgeny Pr (view profile)

17 Oct 2010 Rossella Blatt

Thank you David! I use this a lot and it always improves dramatically the speed of my algorithms. Great job!

31 Mar 2010 David Young

David Young (view profile)

Rob, you are right that the tolerance parameter makes no difference if the mask is ones(n). The reason is that the mask can be decomposed into 1D masks without any loss of accuracy, so this is done regardless of the tolerance. The same is true of many simple masks, e.g. those produced by the 'gauss' and 'log' arguments to fspecial, and Gabor function masks.

The tolerance becomes useful if the mask is complex - for example, if it is obtained by snipping out part of an image. Then, to get full accuracy, a full 2D convolution is needed and there will be no gain over conv2 (indeed, a slight loss of time); however, if the tolerance is large enough an approximation to the mask will be used, allowing a speed-up at a cost of accuracy.

Comment only
30 Mar 2010 Rob Campbell

Rob Campbell (view profile)

I get the following speed improvements. I didn't see an effect of changing the tolerance value. It would be nice to have usage examples where this parameter makes a difference to computation speed.

>> tic,for i=1:100;C=conv2(randn(1000),ones(10),'same');end,toc
>> Elapsed time is 17.121093 seconds.
>> tic,for i=1:100;C=convolve2(randn(1000),ones(10),'same',1);end,toc
>> Elapsed time is 10.800977 seconds.
>> tic,for i=1:100;C=convolve2(randn(1000),ones(10),'same',0);end,toc
>> Elapsed time is 10.419711 seconds.

Comment only
30 Mar 2010 Rob Campbell

Rob Campbell (view profile)

20 Nov 2009 James

James (view profile)

I'm fairly sure this used to have loads of 5* comments? Anyway, this script is great. The increase in speed over conv2 for me was 10 times. Really easy to use - outstanding!

24 Feb 2009 Joey Hyde

I use this a lot. It is very fast and well documented. A great replacement for conv2().
In some cases, a fft based convolution is faster. I've seen this be the case when the filter and image are the same size.
Does anybody know a c/c++ code which is as useful as this one? Multi-purpose, fast, reliable, 2d convolution.

30 Mar 2010 1.1

Now uses exindex to simplify the boundary condition computation.

11 Apr 2011 1.2

Minor correction to help comments; updated exindex to current version.

20 Mar 2014 1.3

Alternative names for shape options for consistency with other functions.

Contact us