# 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 –  Dilip Sarwate Dec 18 '12 at 21:53
Maybe you can mess with the Mathematica Demo Regards –  Amzoti Dec 18 '12 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 '12 at 0:13
–  Juancho Dec 19 '12 at 10:19

## migrated from math.stackexchange.comDec 18 '12 at 23:01

This question came from our site for people studying math at any level and professionals in related fields.

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 '12 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. –  Jim Clay Dec 20 '12 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. –  Jim Clay Dec 20 '12 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 '12 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. –  Jim Clay Dec 22 '12 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". –  Andrey Dec 19 '12 at 13:41
Whats is a advantage of one or other? –  Juan Dec 20 '12 at 8:01
Circular conv. is faster thanks to the FFT. See the edited answer. –  sansuiso Dec 20 '12 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 '12 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. –  sansuiso Dec 25 '12 at 13:01