CS559
Fall 2005

Written Assignment 2:
Imaging and Transforms

This assignment is due on Tuesday, October 18th at 9:30. Papers will be collected in class.

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]

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 ... ].

Notice that the deconvolution is ill-posed. If we don't tell you more about f, then there are an infinite number of possible answers (f could have started with [2 3]). If the kernel was [-1 1] then there is no signal that is the deconvolution of h.

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:

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.

Question 4:

Give a linear homogeneous 2D transformation (e.g, a 3x3 matrix) that maps the unit square such that the (0,0) corner maps to (a,b), the (1,0) corner maps to (c,d), and the (1,1) corner maps to (e,f).

Note that it is possible to define an affine transformation between any two triangles.

Question 5:

Describe how to create a reflection about a line through point x,y with angle t given only the "basic" affine transformations. (translate, rotate about the origin, reflect about the x axis, scale about the origin, ...).

Your answer should have the form of a little "program" like: