# Circular and Linear Convolution

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?

• I recommend that you ask the moderators to migrate this question to the signal processing site dsp.SE Dec 18, 2012 at 21:53
• Maybe you can mess with the Mathematica Demo Regards
– Amzoti
Dec 18, 2012 at 22:58
• mmm, understand but ... I always read that circular convolution is used to signal with finite support but also is used when the signal have periodicity. I don't understand this because a signal with finite support not always have periodicity, e.g images
– Juan
Dec 19, 2012 at 0:13
• Dec 19, 2012 at 10:19

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.

• If I used linear convolution without padding zeros the name of the problem in the boundary is aliasing? and another question Whats have a best perfomance (computational) linear or circular?
– Juan
Dec 20, 2012 at 8:22
• With linear convolution you don't need to actually pad with zeros- it's implicit in how you do the calculation. With circular convolution you pad with zeros to make it produce the same results as linear convolution. Dec 20, 2012 at 13:56
• For small convolution kernels, linear convolution has the best performance. For big convolution kernels, circular convolution via FFT's has the best performance. There is the complication of needing to pad with zeros to get the answer to come out right, though. Dec 20, 2012 at 13:58
• now I am confused because in the following answer, say "if you fill the missing values with 0's then you stay in linear convolution", but you say "With linear convolution you don't need to actually pad with zeros"
– Juan
Dec 22, 2012 at 13:08
• You can do the shortening of the convolution kernel with either linear or circular convolution. It is a separate issue. The zero padding is just for circular convolution. Dec 22, 2012 at 13:23

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.

• +1. You could pad the image with enough zeros to avoid this Fourier "periodization". Dec 19, 2012 at 13:41
• Whats is a advantage of one or other?
– Juan
Dec 20, 2012 at 8:01
• Circular conv. is faster thanks to the FFT. See the edited answer. Dec 20, 2012 at 8:57
• now I am confused because in the following answer, say "With linear convolution you don't need to actually pad with zeros", but you say "if you fill the missing values with 0's then you stay in linear convolution"
– Juan
Dec 22, 2012 at 13:09
• I think the first part of Jim Clay's comment is right: linear convolution will usually avoid explicit padding with 0's, but it's an implementation artifact (if you don't check for boundaries, then you have to allocate a big image and use padding). FFT-based approaches may use padding for i) faster execution (because there are even faster algorithms for some good image sizes) or ii) for image zooming (this is equivalent to sinc interpolation). Circular convolution (including FFT-based convolution) does not rely on any padding per se. Dec 25, 2012 at 13:01