Wavelets Final Project

Sunday March 17th, 2002

I've just updated the webpage and uploaded my new code to the code archive section. I think the function names are pretty self-explanatory, and the structure is designed in such a way that if you don't care for the nitty details, you will still understand what is going on in the code. The code now will process color photographs as well, though I'm hesitant to post those jpg files because they are close to 500kB each if I keep all the quality.

The biggest changes in the code happen at the fundamental level of how to reconstruct a signal perfectly. (filter_signal.m) It's hard to explain it without working through an example, but I'm saving that for my writeup... If you take a simple signal say [1 2 3 4 ... n], do you get perfect reconstruction? Mine initially didn't if n was even, but did when n was odd (however, the number of coefficients that I had were greater than n).

The main changes that can be made to the code is implementing an L2 compression or an L1 compression routine (as decribed in some useful reference articles that I list below), but that is quite easy to implement and I don't think it will provide more insight into how wavelets work. The current compression has perfect reconstruction for some compression ratios of the testpat images, (which is to be expected since they are purely black/white with no grey scale images)

I do plan however to work on some surface morphing algorithms as listed in the bottom two pdf files. We'll see how time permits after our final.

I suspect that this workbook will not be updated unless I start working on the morphing algorithms, however, check back at the writeup link because I may post a PDF of each section as it's completed. Have fun coding =)

reference article 1

reference article 2

If you're having having problems seeing both pictures side by side, (i.e., your monitor isn't big enough, try going directly to the http://www.sfu.ca/~bwo/wavelets/workbook . Actually, do yourself a favour, download the code and run it.

100% of the coefficients kept

75% of the coefficients kept

25% of the coefficients kept

5% of the coefficients kept

Saturday March 16th, 2002

Hmm, I've thought a lot about my code, and I finally realized that I had a big bug... mostly in the way I approached the filter coefficients. I think all the gibberish below on the size of the image is completely wrong; we do require an even number of coefficients to have a complete reconstruction of the image. More to follow shortly.

Friday March 15th, 2002

updated 3am

I can't believe it took me all night, by my code is finally finished including the compression algorithm. The biggest problems I ran into were the unfriendly picture size (256x256) instead of (257x257). Note that if you use the 257x257 picture size, you won't be able to get that fancy tree like diagram, however, you can create your perfect reconstruction. Be forewarned and do something smart about it instead of spending hours trying to debug your code. I also had a fair bit of round-off error that caused me grief for a while.

I"ll be writing up the project in the next couple of days or so. I'll post the codes too after I've added some comments.

Thursday March 14th, 2002

I've finally been able to get back to working on the project. It feels like eons ago that I worked on it. I finally clarified some issues with myself. If you look at some of the plots below, you notice that there are a couple of funny patches. This is because the image was "not" a perfect size for working on. In order to go to the jth order wavelet decomposition, the domain must have 2^j equal intervals or 2^j +1 datapoints. Thus, testpat2.tif was a 256x256 was not really suitable for wavelet decomposition. 257x257 would have been ideal. There are different ways to handle this, but for the time being, I'm just going to leave at and assume the the image given to me has 2^j equal subintervals in the x-direction and 2^m equal subintervals in the y direction. That means that we can do j row decompositions and m column decompositions.

I also realized that since we are working with the Haar wavelets, it is completely analagous to the filter bank problem which we learnt. There is no messy scaling function or mother wavelet to worry about.

Compression on the otherhand is quite a challenge. I think that the main idea is to sort through the wavelet coefficients, and chuck out the smallest terms depending on how much tolerance is desired or what percentage of the coefficients we want to keep.

I've revamped my code a little bit so that there is a seperate decomposition function, a reconstruction function and a soon to be added, compression function. I was having fun thinking about the sorting algorithm to implement, but matlab already has a pretty awesome routine which I can just call. (sort)

The thing that has been bugging me is the difference between using wavelets and using wavelet packets. Personally to do the compression, I would not work further on the "detail" (high pass) matrix. I mean, what does it really mean to do the wavelet transformation on the detail matrix? Can we really compress that result without lossing any vital information?

Friday March 1st, 2002

updated 11:45am

Here are the codes that I used to generate the plots. I have always been cautious about posting my codes before the project is handed in, but I think it's almost cryptic enough that you won't be able to completely copy it. If you do use my codes as a reference, please state it in your writeup =)

As a general convention, I try to keep each function and script file to 12 lines or less, so you need all these functions

code archive

updated 12:15am

Well, my code is working now, with possibly one bug when it comes to filtering columns of the image... I'm not sure yet. In the mean time, here's some pretty pictures to feast your eyes on. Some comments are included on the bottom of the pictures. I won't post the codes tonight because they aren't completely commented yet, but I should have time to finish it by noon tomorrow morning.

Filtering rows of testpat2.tif

Filtering both the columns and rows of testpat2.tif

Filtering both the columns and rows of testpat1.tif

Filtering both the columns and rows of cameraman.tif

When plotting these results, note that we are plotting the downsampled image, thus you may not see some of the averaging (grey lines in testpat2.tiff for example).

Remember that the high pass filter gives an idea of the gradient of the image, so plotting results from that don't directly make sense... In an arbitrary filter, you may find that some of these gradients are negative. The thing to do is to scale them with the mid point of the image, in my case the grey level.

To deal with color, there are several options. I would personally work with the 3 matrices individually and combine the "plots" afterwards, though I have yet to code it up.

With respect to compression, we note that the high pass filter gives the "detail" of the problem. It is quite compressible with mostly zero gradients, and the crudest filter would just ignore all of the detail level.

Thursday Feb 28th, 2002

updated 9:15pm

(codes posted above)

I've been told my importing image routine is excessive, but I have Matlab Release 12 (not 12.1) which apparently has a bug in the image routine for gray scale images, and this is one way to get around it.

A short note for people trying to plot grayscale images, I had to reformat the gray scale matrix to a red, green and blue matrix in order to get the greyscale image. This probably won't make any sense until you try plotting the greyscale images and run into problems =)

updated 4:15pm

Well, I have taken a couple of hacks at the project now. Here's some discoveries / comments from my work.

1. You'll need the imread to read an image file into a matrix. To view that matrix file as an image in matlab, you may want to try the image command. Very convenient.

2. I spent a lot of time trying to use the matrix to plot a black and white picture. The solution of course is trivial (after hours of work), you take your matrix A and create a (:,:,3) structure with (:,:,i) = A. Fine.

3. double(A) will convert your matrix to a useable form to do filter operations on

4. I'm still haven't quite tied the link between filters and wavelets. I understand the recursive nature that we can implement, but where are those cool mother and daughter wavelets and scaling functions?

some pretty pictures to come.

Tuesday Feb 26th

I found out yesterday that the project report is due on friday (gasp). I was under the impression that we had the whole of March to work on it, but I guess Manfred wanted to keep us on our toes. I'll start working on this project on thursday after my midterm. Until then, stay tuned!