Circular and Linear Convolution

Question

What is the difference between circular and linear convolution? When would I choose one over the other? In image processing where a filter is applied to an image with a mask which type of convolution should I choose?

Answer 1

If you have a vector of data, $d$, that is composed of elements $d_1, d_2,... d_N$, then linear convolution operates on them in order, starting with $d_1$ and ending with $d_N$.

Imagine that the data vector $d$ is represented by a slip of paper with the $N$ elements written in order. Now, imagine forming the slip of paper into a circle by touching the end (where $d_N$ is written) to the beginning (where $d_1$ is written). Convolving that is circular convolution. In practice linear convolution and circular convolution are nearly the same, the difference happening at the beginning and the end of linear convolution. In linear convolution you assume that there are zero's before and after your data (i.e. we assume that "$d_0$" and "$d_{N+1}$" are 0), while with circular convolution we wrap the data to make it periodic (i.e. "$d_0$" is equal to $d_N$ and "$d_{N+1}$" is equal to $d_1$).

The same principles hold for multi-dimensional arrays. For linear convolution there is a definite start and end for each axis, with zeros assumed before and after. For circular convolution the data wraps around in each axis.

When would I choose one over the other?

With a few very rare exceptions we don't "choose" circular convolution. We almost always want linear convolution. The reason that circular convolutions pop up as much as they do is because convolutions via FFT's (FFT, multiply, inverse FFT) are circular convolutions, not linear.

Answer 2

When you implement convolution in images, you have to take care of boundary values, because at some point your convolution mask will get "out" of the image to process. Depending on how you fill the missing values will determine wether or not you implement circular convolution:

• if you fill the missing values with 0's then you stay in linear convolution
• if you fill the missing values by periodicity then you're likely to use circular convolution.

Note that if you implement the convolution in the Fourier domain then you have no other choice but circular convolution, because the FFT algorithm will implicitly periodize your images.

-- EDIT --

Convolution is often implemented in the Fourier domain (=> circular convolution) because it is significantly faster in most cases thanks to the FFT algorithm. Fast linear convolution algorithms exist, but are usually reserved to the separable kernel case where you can filter the image horizontally and vertically separately, which also yields less operations than a naive 2D implementation.