How conv2 works?

I am trying to do filter some images with low pass filters and currently I am using conv2 to convolve a 2D image with a 1D filter function. I am wondering how does matlab perform the convolution? Is it doing 1D convolution to each row of the image and uses a for loop to loop through all the rows? The reason I am asking this is that I am trying to find out if there is a faster way to do the convolution.

[Bruno Luong]

There are 2 faminlies of algorithms for convolution

• straighforward sliding sum of main array x flipped kernel
• Use DFT/FFT and perform in the convolution in Fourier domain which is multiplication element wise. This methods is very efficient especially when the kernel size is medium or large (> 10 x 10)

Furthermore if the kernel is seperable In 2D (rectangular kernel, isotropic Gaussien), the convolution can be performed as two succesive 1D convolution along column/row or row/column.

It seems MATLAB uses straighforward sliding sum of flipped kernel. I'm not sure if it detects separability and do another branching of successive 1D.

In all branch the algorithm can be easily implemented in multi-threadings, which is the case of MATLAB conv/conv2.

Answer 1

[Walter Roberson]

conv2 does conv() and then transposes the result and does a second conv() and then transpose back.

Each conv() step operates over the first dimension.

The internal implementation of conv() is not well documented to the public. However if you happen to look in the right places then there is mention that in some cases, conv() decomposes the kernel into steps that are easier to vectorize and then combines the results.

[Jiayun Liu]

It would seem to me that matlab does 1D convolution for every row/column depending on whether the 1D vector is a row/column vector and then that's it. It doesn't do a second convolution.

x=magic(5);
y=[1,2,3,4,5];
conv(x(1,:),y)

ans = 1×9

17 58 100 150 215 178 82 100 75

x=magic(5);
y=[1,2,3,4,5];
conv2(x,y)

ans = 5×9

17 58 100 150 215 178 82 100 75 23 51 86 135 200 127 139 134 80 4 14 37 80 145 186 211 188 110 10 32 73 135 200 205 188 117 15 11 40 94 150 215 214 160 46 45

The first line of conv2(x,y) is exactly the same as conv(x(1,:),y). Am I misunderstanding something?

[Bruno Luong]

"The first line of conv2(x,y) is exactly the same as conv(x(1,:),y). Am I misunderstanding something?"

Why it surprises you? It is exactly the result to be expected.

[Jiayun Liu]

"conv2 does conv() and then transposes the result and does a second conv() and then transpose back."

I was responding to this sentence. If there is a second conv, it shouldn't look the same as in my example where I only conv once.

[Bruno Luong]

The code conv2 and convn is no longer mfiles, but builtin. At some point in the pass those code are mfiles.

It sounds like what Walter describes is (2) successive 1D convolutions where there is a loop on working dimensions and for each loop

• the working dimension is permuted to the first dimension
• do 1D convolution along the 1st dimension
• swap back first dimension to the working dimension

This kind of implementation is often use for separable operator, not only for convolution, but also for example for filtering, inear/spline gridded nd interpolation, etc...

But he would eventually explain exactly to you the sentense he wrote.

[Walter Roberson]

Doing a high performance convolution is more difficult than it seems at first. It is easy to say that in theory it is just a bunch of multiplications and additions, but because of the sliding window, you have to worry about the details of how values are read from memory into the processor. And if you can detect symmetry in the kernel then you can potentially reduce the number of multiplications (which are expensive by comparison)