Computational Complexity of 2D Convolution

Question

I am using image filtering for an image processing algorithm I'm developing. I'm using a predefined Matlab function to do the convolution, but I'd like to know what the computational complexity is for this algorithm.

The simple way of thinking of this is that an $M \times N$ (grayscale) image and a $m \times n$ filter, each pixel needs $\mathcal{O}(mn)$ computations, so the 2D convolution would have an approximate complexity of $\mathcal{O}(MNmn)$. (Of course it would matter is you're padding the sides of the images or not, but assuming that $m$ and $n$ are small compared to $M$ and $N$, it shouldn't make too much of a difference.)

My questionis : Is this true? Is the complexity of 2D convolution $\mathcal{O}(MNmn)$, or are there optimizations that make it less?

Answer 1

There are a lot of ways to speed up convolution is specialized contexts, e.g.:

• If your filter is separable, i.e. $h = h_1 * h_2$ with $h_1\in\mathbb{R}^{n\times 1}$ and $h_2\in\mathbb{R}^{1\times m}$, calculating $(u*h_1)*h_2$ is much faster than $u*(h_1*h_2)$.
• Convolving with $h = [1\ \dots\ 1]$ (for any length) can be done recursively with basically two operations per pixel. Combining this with the previous point gives a huge speedup for a rectangular moving average.
• Sometimes factoring filters is beneficial: E.g. convolving with $[\tfrac14\ \tfrac12\ \tfrac14]$ can be done by convolving with $[1\ 1]$ twice and then dividing by 4. The latter convolution only need additions (no multiplications) and a bit shift and that may be much faster in certain environments.
• Combining the previous point with the first one, one gets good approximations to convolution with Gaussians by convolving $n$ times with $[1\ 1]$ and $n$ times with $[1\ 1]^T$ (with the appropriate bit shifts).
• When using the FFT (as Wolfgang Bangerth mentioned) for the convolution of a large image with a small filter, the overlap add method further improves speed.

However, how much speedup is actually observed in practice depends a lot on the specific architecture and language .

Answer 2

A convolution becomes a product if you apply it in Fourier space, so you can express the operation $I * m$ ($I$ being the image, $m$ being the mask with which you filter) as $I * m = F^{-1}(F(I) \cdot F(m))$ (where $F$ is the Fourier transform) which will cost you $O(MN \log (MN))$ operations. Whether this is cheaper than what you have depends on the size of your filter mask: For small filters, a direct application is cheaper, but if the filter applies the mask over an area that is a significant subset of the image, then the Fourier transform may become cheaper.

Answer 3

You can optimize the convolution, using separable theorem. Let me give an example.

Image ($M\times N$): 1024, 768 (Grayscale) Convolution mask ($k\times k$): 7x7

Computational complexity: Convolution -> $O(MNkk)$

Computational complexity: Separable convolution -> $O(2*MNk)$

being k = kernel size.

Using normal convolution you got O(1024*768*7*7) = 38535168 operations.

Using separable convolution you got(2*1024*768*7) = 11010048 operations.

And here you got a real example.

Answer 4

For some 2D convolution operations (e.g. mean filters) an integral image (a.k.a. summed area table) can be used to speed up the calculation considerably. In particular, applying the filter on the integral image rather than on the original image can allow for convolution using very large kernel sizes since the performance becomes independent of the kernel size, i.e. it takes as many calculations to perform a 100 x 100 convolution as a 3 x 3 convolution. It's simple to implement and can be extremely effective.

Answer 5

I am not so sure if this is right answer but based on my understanding, here is what I think:

Let's say there are n pixels (HxW) in a 2D image.

Say we have a filter that covers k pixels (hxw).

So we will have kn computations in total.

In the worst case, k, being the filter could have a size of n and the big O notation would be O(n^2).

In the best case scenario, it would be Ω(n) with k being close to 1

My knowledge is quite limited so please take this with a grain of salt... Let's see what everyone else thinks about the correctness of this answer!