Written Assignment #2:
Imaging

Please answer the following questions. Please put your name and login on all sheets handed in. This assignment is due October 1.

Question 1:

The inverse of convolution is known as deconvolution. Basically, if

h(t) = f(t) * g(t) (where * is the convolution operator)

the deconvolution of h(t) with g(t) is f(t). Unlike convolution, deconvolution is usually ill-posed: given two signals, there may be many possible answers to the deconvolution.

Consider the discretely sampled case. Let the signal g(t) be the kernel =
[-1 1]

1A: What is the deconvolution of h(t) with g(t) where
h(t) = [0 1 2 3 2 1 0 1 2 3 2 1 0] and f(t) begins with [0 1 ... ].

NOTE: Problem 1B is poorly worded, and might be confusing. You don't have to answer it, but you should think about why deconvolution is ill-posed.
1B: The deconvolution of h(t) with g(t) is ill-posed. If you are not given how f(t) starts, there are an infinite number of possible values of f(t) that satisfy h(t) = f(t)*g(t). Give two more values for f(t).

Question 2:

Some 2D filter kernels have a special property that they are separable. This means that they can be divided up into two 1D convolutions (one in each direction). Gaussians and binomials have this property.

As it turns out, using the separated form is preferable (when it is possible) because it is much more efficient. Not only are there fewer operations, but the memory accesses are all in a "row" (often, it is best to implement things by grabbing a column out of the image into a row, computing the convolution, and then putting the row back into the column.

2A: Compute the width 5 1D binomial filter. Then compute the 5x5 binomial filter, both by repeatedly "squaring" the unit 2D box, and by applying the 1D kernel in both directions.

2B: This property of squaring a filter to get a "bigger" kernel, that effectively has a lower pass band, does not work with ideal low-pass filters (filters with gain 1 inside their pass band, and zero outside). Why?

2C: Give an explanation of why no non-zero filter with a finite kernel size (in the time domain) can be a true low-pass filter. (NOTE: there is a confusing double negative/existential quantifier in that sentence - a simpler way to say it: a finite kernel cannot be a true LPF)
HINT: consider what 2B says about the "square" of the kernel, and consider the edges of the kernel when it is convolved.

Question 3:

Given that Question 2 proved that an ideal low-pass filter cannot be implemented using the convolution methods we have been discussing, you will probably use an approximate low-pass filter, like a binomial or gaussian.

Describe/sketch a signal that would give a different result with a real low-pass filter and with a binomial or gaussian. Describe/sketch the different responses. Explain why we might actually prefer the approximation.

Question 4:

We considered 3 methods for Quantizing an image: error diffusion (like Floyd-Steinberg), ordered dithering, and thresholding. Consider the problem of converting a 256 level grayscale image to black and white. Describe/sketch an image that would give different results for each algorithm. Describe/sketch the output of each algorithm on the image.

Question 5:

When we downsample an image, we must be careful to do proper filtering to avoid aliasing. Too much, or too little filtering, and you'll get a bad result.

Consider reducing an image by a factor of 3. Describe/sketch an image that would be good for testing whether or not the sampling is done correctly. Describe/sketch the results if the frequency limit was too high or too low.

HINT: you might want to try using this by taking a signal, and applying binomial filters of various sizes to see what happens.