The last task of this course consists of two (related) problems.

Problem 1:

Generate the file

kiel.arr

It contains a 512x512-matrix with integer entries that has been generated from a grayscale photograph of the same size, adding gaussian noise and doing a wavelet transformation (Daubechies-16). This wavelet transform is an orthonormal linear mapping, which leaves the noise unchanged in the sense that it can still be assumed to be gaussian with zero mean (and unknown variance).

The signal, however does change.  The transform splits the image into four quadrants, such that the upper left of the matrix contains a multiple of the downscaled original image, while all other quadrants form so-called subbands of their own, roughly corresponding to changes in pixel value in their respective directions. The top left quadrant will now contain a large portion of the original image's energy (sum of squares of entries), while the three subbands contain considerably less energy.

The process is iterated five times on the top left quadrant, such that in the end the top left 16x16 entries are a multiple of the down-scaled original image, while the rest of the matrix is made up of 5 (levels) times 3 (directions) subbands. If we had only three levels, then the subband structure would look like this:

Note: The wavelet transform gives real-valued entries, which have been discretized.

As a large part of the energy can be expected to lie inside the top left 16x16 matrix entries, it is probably a good idea to encode these as such. However, the entries in each subband can be assumed to come from a mixture of a gaussian (the noise, same variance in all subbands) and a generalized gaussian (in the sense of 'Version 1' on Wikipedia, http://en.wikipedia.org/wiki/Generalized_Gaussian_distribution) for the signal. Both signal variance alpha and the shape parameter beta may vary from subband to subband, but usually we have beta<1 ('superexponential').

There is a little program a2p that turns your matrix into a viewable image. Say

a2p kiel.arr kiel.ppm

to get this ppm image (here transformed to jpeg to have it displayed)

Problem 2:

Take the matrix kiddog.arr as input (side information) and produce a denoised version of the same. The format is as above and the (back-) transformed image looks as such:

Generate a file in given matrix format named "kd.arr" which is close to the (withheld) original in euclidean distance. The penalty for deviating from the original will be the log of the volume of a 512x512-dimensional ball with radius equal to the euclidean norm of the difference of the original and your guess. This is (roughly) the number of bits one would need to recover the original from your matrix.

Note: Due to encoding precision issues this number may be large, but if it is, then it is for all of you. Precision, in effect, adds a constant to the codelength.

Both tasks are due on Tue, Dec 4, 9am. As before, your package needs to also generate the files of all previous tasks.

The final report is due Fri, Dec 14, 12pm.