GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing www.songho.ca — Convolution Convolution
Convolution is the most important and fundamental concept in signal processing and analysis. By using convolution, we can construct the output of system for any arbitrary input signal, if we know the impulse response of system.
Related Topics: 2D Convolution Example, Proof of 2D Separable Convolution, Window Filters
Definition
First, let's see the mathematical definition of convolution in discrete time domain. Later we will walk through what this equation tells us.
Impulse Function DecompositionIn order to understand the meaning of convolution, we are going to start from the concept of signal decomposition. The input signal is decomposed into simple additive components, and the system response of the input signal results in by adding the output of these components passed through the system. In general, a signal can be decomposed as a weighted sum of basis signals. For example, in Fourier Series, any periodic signal (even rectangular pulse signal) can be represented by a sum of sine and cosine functions. But here, we use impulse (delta) functions for the basis signals, instead of sine and cosine. Examine the following example how a signal is decomposed into a set of impulse (delta) functions. Since the impulse function, δ[n] is 1 at n=0, and zeros at n ≠ 0. x[0] can be written to 2·δ[n]. And, x[1] will be 3·δ[n-1], because δ[n-1] is 1 at n=1 and zeros at others. In same way, we can write x[2] by shifting δ[n] by 2, x[2] = 1·δ[n-2]. Therefore, the signal, x[n] can be represented by adding 3 shifted and scaled impulse functions.
In general, a signal can be written as sum of scaled and shifted delta functions;
Impulse Response
Impulse response is the output of a system resulting from an impulse function as input.
If the system is time-invariant, the response of a time-shifted impulse function is also shifted as same amount of time.
If the system is linear (especially scalar rule), a scaled in input signal causes an identical scaling in the output signal.
If the input has 3 components, for example, a·δ[n] + b·δ[n-1] + c·δ[n-2], then the output is simply a·h[n] + b·h[n-1] + c·h[n-2]. This is called additive property of linear system, thus, it is valid only on the linear system.
Back to the Definition
By combining the properties of impulse response and impulse decomposition, we can finally construct the equation of convolution. In linear and time-invariant system, the response resulting from several inputs can be computed as the sum of the responses each input acting alone.
To summarize, a signal is decomposed into a set of impulses and the output signal can be computed by adding the scaled and shifted impulse responses. Furthermore, there is an important fact under convolution; the only thing we need to know about the system's characteristics is the impulse response of the system, h[n]. If we know a system's impulse response, then we can easily find out how the system reacts for any input signal. Convolution in 1DLet's start with an example of convolution of 1 dimensional signal, then find out how to implement into computer programming algorithm.
x[n] = { 3, 4, 5 }
x[n] has only non-zero values at n=0,1,2, and impulse response, h[n] is not zero at n=0,1. Others which are not listed are all zeros.
One thing to note before we move on: Try to figure out yourself how this system behaves, by only looking at the impulse response of the system. When the impulse signal is entered the system, the output of the system looks like amplifier and echoing. At the time is 0, the intensity was increased (amplified) by double and gradually decreased while the time is passed.
From the equation of convolution, the output signal y[n] will be
Notice that y[0] has only one component, x[0]h[0], and others are omitted, because others are all zeros at k ≠ 0.
In other words, x[1]h[-1] = x[2]h[-2] = 0. The above equations also omit the terms if they are obviously zeros.
Let's look more closely the each output. In order to see a pattern clearly, the order of addition is swapped. The last term comes first and the first term goes to the last. And, all zero terms are ignored.
y[0] = x[0]·h[0]
Can you see the pattern? For example, y[2] is calculated from 3 input samples; x[2], x[1] and x[0], and 3 impulse response samples; h[0], h[1] and h[2]. The input sample starts from 2, which is the same index as the sample point of the output, and the index is decreased. The impulse response sample index starts from 0 and increased. Based on the pattern that we found, we can write an equation for any sample of the output;
C++ Implementation for Convolution 1DImplementing the convolution algorithm is quite simple. The code snippet is following;
However, you should concern several things in the implementation.
Convolution in 2D
2D convolution is just extension of previous 1D convolution by convolving both horizontal and vertical directions in 2 dimensional spatial domain. Convolution is frequently used for image processing, such as smoothing, sharpening, and edge detection of images.
The second image is 2D matrix representation of impulse function. The shaded center point is the origin where m=n=0.
Once again, a signal can be decomposed into a sum of scaled and shifted impulse (delta) functions;
And, the output of linear and time invariant system can be written by convolution of input signal x[m, n], and impulse response, h[m, n];
Exercise a little more about 2D convolution with an another example. Suppose we have 3x3 input and 3x3 kernel matrices as follow.
The ouput at (1, 1) for this example will be;
The complete solution for all 9 output can be found here; Example of 2D Convolution Separable Convolution 2D
In convolution 2D with M×N kernel, it requires M×N multiplications for each sample. For example, if the kernel size is 3x3, then, 9 multiplications and accumulations are necessary for each sample. Thus, convolution 2D is very expensive to perform multiply and accumulate operation.
And, convolution with this separable kernel is equivalent to;
As a result, in order to reduce the computation, we perform 1D convolution twice instead of 2D convolution; convolve with the input and M×1 kernel in vertical direction, then convolve again horizontal direction with the result from the previous convolution and 1×N kernel. The first vertical 1D convolution requires M times of multiplications and the horizontal convolution needs N times of multiplications, altogether, M+N products.
C++ Algorithm for Convolution 2D
We need 4 nested loops for 2D convolution instead of 2 loops in 1D convolution.
The above snippet code is simple and easiest way to understand how convolution works in 2D. But it may be the slowest implementation.
Take a look at a real example; convolution with 512x512 image and 9x9 Gaussian filter.
With my measurement, the seperable convolution is about 3 times faster than the normal convolution. You can see how much separable convolution is faster compared to normal 2D convolution. Download 2D convolution application and source code here: conv2d.zip (updated 2025-08-11) 2D convolution is commonly used for image processing, such as smoothing and edge detection. Window Filters explains common 2D kernels for image processing. The program uses OpenGL to render images on the screen. Note that the convolution can be further optimized using GLSL shaders. Please see the GLSL optimization of Gaussian blur page. |
| You are visitor 01402605 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |