Linear and Shift Invariant Systems

Definition

A filter f is linear if the following is valid:

f[ w1 . A + w2. B] = w1 . f[A] + w2 . f[B]

where A and B are two images and w1 and w2 are two arbitrary constants.

Additionally, a filter is shift invariant if a translation of the input causes the same translation on the output.

Suppose we have the following scenario

An Image Processing student, I. M. Age, playing with a Photo Composer program in his personal PC and wants to discover how to implement the filter f under the menu IMAGE SMOOTHING. All he knos is that the filter is linear and shift invariant. What is the procedure the student should follow to discover what the filter does?

Answer

As any good student, Age remembered about the linear and shift invariant properties and thought: "If I know the output of the filter to an image with a single unitary impulse, then I can combine that response to all pixels on the image I want to filter using the pixel value as the weighting factors, and translating each one to the pixel coordinate position".

So he created a small image with a single pixel with value 1 at the center of the image. Assume the image is

Applying this image to the unknown linear filter, he got the folowwing output image

0 0.00 0.00 0.00 0
0 0.11 0.11 0.11 0
0 0.11 0.11 0.11 0
0 0.11 0.11 0.11 0
0 0.00 0.00 0.00 0

Now to implement the same filtering algorithm in his own software package, he did the following: given any image, he decomposed it using the following scheme

5 3 2 5 3       1 0 0 0 0       0 1 0 0 0       0 0 1 0 0
2 4 3 6 1       0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
2 4 6 0 2 = 5 . 0 0 0 0 0 + 3 . 0 0 0 0 0 + 2 . 0 0 0 0 0 + ... +
1 3 2 5 1       0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
2 3 6 1 2       0 0 0 0 0       0 0 0 0 0       0 0 0 0 0


                0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
                1 0 0 0 0       0 1 0 0 0       0 0 1 0 0
          + 2 . 0 0 0 0 0 + 4 . 0 0 0 0 0 + 3 . 0 0 0 0 0 + ... +
                0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
                0 0 0 0 0       0 0 0 0 0       0 0 0 0 0

...

                0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
                0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
          + 2 . 0 0 0 0 0 + 3 . 0 0 0 0 0 + 6 . 0 0 0 0 0 + ...
                0 0 0 0 0       0 0 0 0 0       0 0 0 0 0
                1 0 0 0 0       0 1 0 0 0       0 0 1 0 0

The response of the filter to an impulse image is known. By applying the filter to each impulse image in the decomposition above, the filtering algorithm is implemented.

Conclusions

Two important conclusions from Age's procedure:

All that is needed to completely specify any linear shift-invariant filter is knowing its response to the unitary impulse. This response is also called PSF (Point Spread Function).
In the example above the PSF is an average kernel in a 3x3 neighborhood.
```
0.11 0.11 0.11
0.11 0.11 0.11
0.11 0.11 0.11
```
Where the coordinate (0,0) is at the center of the PSF.
The algorithm used to apply the PSF to an image is called convolution.

Other names for PSF are are convolution kernel, filter, window, mask, etc. The equation for convolution is given below, where f is the image and g is the PSF.

f(x,y) * g(x,y) =    SUM   (f(i,j) . g(x-i,y-j))
                  all i,j

Convolution Theorem

A discrete, linear and shift-invariant sytem can be described in terms of linear difference equations with constant coefficients. That is, we are interested in obtaining the input/output relationship. If we apply transform methods, like the Fourier transform, a system can be described in terms of algebraic equations. Another method of describing a system is via discrete convolution.

There is also a very important connection between convolution and transform methods. Utilizing the Fourier transform, the theorem states that the convolution of two functions in one domain is equivalent to multiplication in the second domain and vice versa. Assuming we have two images, p(x,y) and q(x,y), with dimensions AxB and CxD respectively, the theorem states:

   a) p(x,y) * q(x,y) <-------> P(u,v) Q(u,v)
   b) p(x,y) q(x,y) <-------> P(u,v) * Q(u,v)
where
      *   indicates the convolution operation
    <---> Fourier transform pair