Connexions

You are here: Home » Content » Signal Processing in Processing: Convolution and Filtering

Recently Viewed

This feature requires Javascript to be enabled.

Signal Processing in Processing: Convolution and Filtering

Module by: Davide Rocchesso, Pietro Polotti. E-mail the authors

Summary: Discrete-time systems and their description with the impulse response. The convolution operator. Filtering.

Systems

For our purposes, a system is any processing element that, given as input a sequence of samples xn x n , produces as output a sequence of samples yn y n . If the samples are coming from a temporal series we talk about discrete-time systems. In this module we will not be concerned with continuous-time processing, even though the principles here described can be generalized to functions of continuous variable. Instead, the sequence of number can come from the sampling of an image, and in this case it will be appropriate to talk of discrete-space systems and use two indeces m m and n n if sampling is done by a rectangular grid of rows and columns.

In this module we are only dealing with linear systems, thus meaning that the following principle holds:

Definition 1: Superposition principle
If y 1 y 1 and y 2 y 2 are the responses to the input sequences x 1 x 1 and x 2 x 2 then the input a 1 x 1 + a 2 x 2 a 1 x 1 a 2 x 2 produces the response a 1 y 1 + a 2 y 2 a 1 y 1 a 2 y 2

Another important concept is time (and space) invariance.

Definition 2: Time invariance
A system is time-invariant if a time shift of D D samples in the input results in the same time shift in the output, i.e., xnD x n D produces ynD y n D .
Cases of non-invariance are found whenever the system changes its characteristics in time (or space), for example as an effect of human control. Those systems where the sampling rate at the input is different than the one at the output are also non-invariant. For instance, decimators are time-variant systems.

A series connection of linear time-invariant (LTI) blocks is itself a linear and time-invariant system, and the order of blocks can be changed without affecting the input-output behavior.

LTI systems can be thoroughly described by the response they give to a unit-magnitude impulse.

Definition 3: The impulse in discrete time (space)
is the signal δ δ with value 1 1 at the instant zero (in the point with coordinates 00 0 0 ), and 0 0 in any other instant (point).

Impulse response and convolution

We call h h the output signal of a LTI system whose input is just an impulse. Such output signal is called impulse response. Since any discrete-time (-space) signal can be thought of as a weighted sum of translated impulses, each sample that shows up to the input activates an impulse response whose amplitude is determined by the value of the sample itself. Moreover, since the impulse responses are activated at a distance of one sampling step from each other and are extended over several samples, the effect of each input sample is distributed over time, on a number of contiguous samples of the output signal. Being the system linear and time-invariant, the successive impulse responses sum their effects. In other words, the system has memory of the past samples, previously given as input to the system, and it uses such memory to influence the present.

To have a physical analogy, we can think of regular strokes of a snare drum. The response to each stroke is distributed in time and overlaps with the responses to the following strokes.

Example 1

Consider the signal x x that is zero everywhere but at the instants 1 1 , 0 0, and 1 1 where it has values 1 1, 0.5 0.5, and 0.25 0.25, respectively. At every instant n n, xn x n can be expressed as 1δn+1+0.5δn+0.25δn1 1 δ n 1 0.5 δ n 0.25 δ n 1 . By linearity, the output can be obtained by composition of carefully translated and weighted impulse responses: yn=1hn+1+0.5hn+0.25hn1 y n 1 h n 1 0.5 h n 0.25 h n 1 .

To generalize the example Example 1 we can define the operation of convolution.

Definition 4: Convolution of two signals h h and x x
yn=h * xn= m =xmhnm y n h * x n m x m h n m

The operation of convolution can be fully understood by the explicit construction of some examples of convolution product. The module Discrete-Time Convolution gives the graphic construction of an examples and it offers pointers to other examples.

Properties

The properties of the convolution operation are well illustrated in the module Properties of Convolution. The most interesting of such properties is the extension:

Property 1

If xn x n is extended over M 1 M 1 samples, and hn h n is extended over M 2 M 2 samples, then the convolution product yn y n is extended over M 1 + M 2 1 M 1 M 2 1 samples.

Therefore, the signal convolution product is longer than both the input signal and the impulse response.

Another interesting property is the commutativity of the convolution product, such that the input signal and the impulse response can change their roles without affecting the output signal.

Frequency response and filtering

The Fourier Transform of the impulse response is called Frequency Response and it is represented with Hω H ω . The Fourier transform of the system output is obtained by multiplication of the Fourier transform of the input with the frequency response, i.e., Yω=HωXω Y ω H ω X ω .

The frequency response shapes, in a multiplicative fashion, the input-signal spectrum or, in other words, it performs some filtering by emphasizing some frequency components and attenuating some others. A filtering can also operate on the phases of the spectral components, by delaying them of different amounts.

Filtering can be performed in the time domain (or space domain), by the operation of convolution, or in the frequency domain by multiplication of the frequency response.

Exercise 1

Take the impulse response that is zero everywhere but at the instants 1 1 , 0 0, and 1 1 where it has values 1 1, 0.5 0.5, and 0.25 0.25, respectively. Redefine the filtering operation filtra() of the Sound Chooser presented in the module Media Representation in Processing. In this case filtering is operated in the time domain by convolution.

Solution



void filtra(float[] DATAF, float[] DATA, float WC, float RO) {
//WC and R0 are useless, here kept only to avoid rewriting other
//parts of code
for(int i = 2; i < DATA.length-1; i++){
DATAF[i] = DATA[i+1] + 0.5*DATA[i] + 0.25*DATA[i-1];
}
}



Causality

The notion of causality is quite intuitive and it corresponds to the experience of stimulating a system and getting back a response only at future time instants. For discrete-time LTI systems, this happens when the impulse response is zero for negative (discrete) time instants. Causal LTI systems can produce with no appreciable delay an output signal sample-by-sample, because the convolution operator acts only on present and past values of the input signal. In Exercise 1 the impulse response is not causal, but this is not a problem because the whole input signal is already available, and the filter can process the whole block of samples.

2D Filtering

The notions of impulse response, convolution, frequency response, and filtering naturally extend from 1D to 2D, thus giving the fundamental concepts of image processing.

Definition 5: Convolution of two 2D signals (images)
ymn=h * xmn= k = l =xklhmknl y m n h * x m n k l x k l h m k n l
If x x is the image that we are considering, it is easy to realize that convolution is performed by multiplication and translation in space of a convolution mask or kernel h h (it is the impulse response of the processing system). As in the 1D case filtering could be interpreted as a combination of contiguous samples (where the extension of such cluster depends on the extension of the filter impulse response) that is repeated in time, sample by sample. So, in 2D space filtering can be interpreted as a combination of contiguous samples (pixels) in a cluster, whose extension is given by the convolution mask. The so-called memory of 1-D systems becomes in 2-D a sort of distance effect.

As in the 1D case, the Fourier transform of the impulse response is called Frequency response and it is indicated by H ω X ω Y H ω X ω Y . The Fourier transform of the system output is obtained by Fourier-transforming the input and multiplying the result by the frequency response. Y ω X ω Y =H ω X ω Y X ω X ω Y Y ω X ω Y H ω X ω Y X ω X ω Y .

Exercise 2

Consider the Processing code of the blurring example and find the lines that implement the convolution operation.

Solution



for(int y=0; y<height; y++) {
for(int x=0; x<width/2; x++) {
float sum = 0;
for(int k=-n2; k<=n2; k++) {
for(int j=-m2; j<=m2; j++) {
// Reflect x-j to not exceed array boundary
int xp = x-j;
int yp = y-k;
//... omissis ...
//auxiliary code to deal with image boundaries
sum = sum + kernel[j+m2][k+n2] * red(get(xp, yp));
}
}
output[x][y] = int(sum);
}
}



Content actions

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks