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., xn-D x n D produces yn-D y n D .

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.

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=-∞∞xmhn-m 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.

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.

                 
	  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];
	      }
	    }
             	      
	  

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=-∞∞xklhm-kn-l y m n h * x m n k l x k l h m k n l

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 .

                 
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);  
  } 
}