Project 1: Wavelet

CSE 457: Introduction to Computer Graphics

Project 1: Wavelet

Date Assigned: Wednesday, April 5, 1995
Date Due: Wednesday, April 19, 1995

Project description

Wavelet is an interactive image compressor that uses wavelets for lossy compression.

The project is based on the paper "Wavelets for Computer Graphics: A Primer Part I", by Eric Stollnitz, Tony DeRose, and David Salesin. A copy of the primer is/will be available in the Indy lab.

Project objectives

The purpose of this assignment is to give you experience working with basic raster image manipulation and user-interface design using libui, the user interface library. This project also exposes you to a really cool research area, namely wavelets. To get started, run the install program OR make a copy of the files located in

	/cse/courses/cse457/wavelet

Then compile and link to create the starting point version of the program. You may also run the starting point project and a partial solution online.

Using the sample solution program

Left mouse drag: Rubberband a zoom rectangle.
Right mouse drag: Rubberband a zoom square.
Show decomposition: Display the scaling function and wavelet coefficients.
Show compressed: Display the wavelet-compressed image.
Zoom In: Zoom in on the rubberbanded rectangle such that the contents of the rectangle will completely fill the window.
Zoom Out: Zoom out of the image in such a way that the current contents of the window will just fill the rubberbanded image. If this would zoom out beyond the edge of the image, then clamp to the image.
Load RGB: Load an RGB image into the left hand window. The image will be loaded in at the current zoom level.
Load Compressed: Load a compressed image into the right hand window. The image will be loaded in at the current zoom level.
Save RGB: Save the contents of the right hand window as an RGB image. The saved image will reflect the current zoom level.
Save Compressed: Save the wavelet-compressed image using run length encoding. The saved image will not reflect the current zoom level.
Quit: Quit.

The starting point program

The starting point program has most of the user interface already present, but the following features have been disabled:

Computing and displaying the the wavelet-compressed image.
Zooming in and out.
Reading/writing compressed images from/to disk.
Writing RGB images to disk.

Required extensions

Each project team must make the following extensions to the starting point:

Add code to perform non-standard wavelet compression.
Add the capability to zoom in on portions of the image in both windows. Already implemented is code to perform the rubberbanding, and storing of the coordinates of the rubberband box.
Add code to allow the user to save the right hand window / image as an RGB file. Pseudocode for doing this appears in the file wavelet_ui.c.

Implement a scheme for storing the wavelet-compressed image to disk. Two such schemes -- run length encoding and Huffman coding -- were discussed in lecture. Especially clever strategies (as judged by the TAs and/or professor) will be awarded an extra .

There isn't much starting point code to understand in this project. In some ways this is good, in that you aren't spending a lot of time just understanding someone else's code. But in other ways, it is bad because there is a fair bit of code to be written. But don't let this discourage you! Once you get the hang of wavelets in general, much of the code "writes itself". Also, additional information covered in the help session is available as well.

Bells and whistles

Each project team must implement at least three ``approved'' bells from the following list (remember: WHISTLE

). You can add items to this list by obtaining approval from the professor or one of the TAs.

You are also encouraged to go beyond the minimum number of bells and whistles by implementing more than three from the approved list, or by thinking up your own unapproved extensions.

Approved bells and whistles

1 Bell, 1 whistle The starting point project includes a slider for RMS error percentage. While this may be more intuitive for the user, it is certainly slower for processing. As an alternative, you could allow the user to specify what percentage of the wavelet coefficients are removed in the compression step. Add code to support this alternative scheme. Also extend the user interface so that there are two sliders, one for RMS error, the other for number of coefficeints. When the user selects a new value for one of them, update the corresponding value on the other slider.

1 Bell Add a button that will display the wavelet decomposition of the image. NB: Care must be take in dealing with the wavelet coefficients. These may be negative or greater than 255. See the sample solution for an example of what this should look like.

1 Bell, 1 whistle The simplest approach to the wavelet compression routine is to set many of the wavelet coeffiecients to 0.0, but leave them in the width by height array. While this method is simple, it does not take advantage of the fact that the "array" is typically very sparse. Design and implement an efficient data structure for handling these sparse sets.

1 Bell With an effiecient data structure, it is possible that the wavelet-compressed image could be updated in real time, i.e., as the user adjusts the slider, the image would update simultaneously. Add this capability to your program.

1 Bell, 1 whistle Add a menu to convert between different color spaces when wavelet-compressing the image. See Hearn & Baker, Chapter 15 for a discussion about color spaces. In particular, implement at least YIQ or HSV in addition to RGB (the default).

1 Bell The human eye does not respond the same to all wavelengths of light. For example, the eye is less sensitive to blue than it is to red. To take advantage of this discrepency, allow the user to select seperate detail levels (i.e., RMS error) for each color channel.

2 Bells There are many other wavelet bases besides the Haar basis. Implement another basis, such as Daubechies wavelets, and modify the user interface accordingly.

2 Bells Besides conserving disk space by compressing images, wavelets can also be used to store (and transmit) progressively higher resolutions of an image, until the full resolution is obtained. This could be very useful on, say, a slow network, where a user could elect to abort trasmission of an image when a suitable level of detail had been reached. Modify the user interface to simulate a slow network, and show the image being displayed with progressively more and more detail.

3 Bells The decomposition algorithm described in the primer evenly distributes the wavelets over the entire image. It is not always the case that this is the best method -- there may be some region of the image that should have more detail preserved than other regions. Devise an extention to the decomposition algorithm (and the subsequent interface) that would allow the user to specify where more detail should be included.

3 Bells One way to diminish the blocky artifacts of the wavelet compression is to arrange the coefficients in such away that the wavelet analysis does not always proceed along a scan line. To do this, implement a type of space-filling curve called a Peano curve. The idea is to define a space- filling curve that fills the image, but which does not have period of a power of two. Use this curve to convert the 2D image into a 1D array, and wavelet compress this array. With luck, the frequency of the Peano curve will deaden the artifacts caused by wavelet compression.

3 Bells Besides static image compression, wavelets can be used to compress video. Add code to support video compression, where the interface to the video is the IndyCam. For an additional 2 bells , extend your solution to allow for real-time video conferencing.

4 Bells There are many other things that can be done to the image after the wavelet decomposition, besides just compression. Add support for various image operations, such as blur, sharpen, edge detect, to your program, by manipulating the image through its wavelet decomposition.

And finally...

When you are finished with this assignment, type "make clean" to clean up unnecessary disk space.

corin@cs.washington.edu

CSE 457: Introduction to Computer Graphics