# Question #4

Convolution is an operation that combines two signals to produce a resulting signal. Convolution is widely used in image processing to filter images. Convolution is also used to explain the process of sampling in computer graphics.

A. (5 points) A box-shaped pulse is a very simple signal. Suppose the box has a width equal to 1 and a height equal to 1. Draw the resulting signal formed by convolving a box with itself. Make sure you clearly label the width and the height of the result.

3 pt for shape
1 pt for range
1 pt for height

C. (10 points)

Suppose a discrete digital image was created by sampling a bandlimited continuous image. That is, that the continuous image had no frequencies greater than half the sampling rate. Suppose further, that a continuous image is reconstructed from the sampled image using bilinear interpolation. That is, the values between pixels are generated by linearly interpolating in x, and then linearly interpolating in y. Is the output image the same as the input image? Why or why not? Answer:

5 pt for saying:

No.
5 pt for one of the following explanations:
In 1D, if you take a sine wave, sample it at a high rate, and then try to reconstruct the sine wave using bilinear interpolation between the samples, you can get very close to the original sine wave, but the output is choppy. There is a corresponding 2D analogy.

The Nyquist limit requires a perfect reconstruction filter, which is a 2D sinc function in this case, not bilinear interpolation. Bilinear interpolation is a first-order approximation to the sinc function, but is not exact, and thus does not give back the exact answer.

Bilinear interpolation makes the reconstructed image's first derivatives discontinuous, which requires infinite freqencies in the Fourier domain. Since the input image is bandlimited, it has a finite number of frequencies, and thus cannot be the same image.

Answers of this form got 3 pt:
The sampling rate is above the Nyquist limit, and therefore by Shannon's Theorem, the image loses no information by sampling. Bilinear interpolation thus can reconstruct the input image.

hanrahan@cs.stanford.edu