Wavelets for Computer Graphics: A Primer

Wavelets for Computer Graphics; A Primer
by
Eric J. Stollnitz
Tony D. DeRose
David H. Salesin

1 Introduction

In any discretised wavelet transform, there are only a finite number of wavelet coefficients for each bounded rectangular region, each coefficient requires the evaluation of an integral.
This numerical complexity can be avoided if the scaled and shifted wavelets form a multiresolution analysis(MRA).
This means that there has to exist an auxiliary function, the father wavelet.
Note that not every orthonormal discrete wavelet basis can be associated to a multiresolution analysis.

• the detail coefficient(mother wavelet)
• the scale coefficient(father wavelet)

The simplest wavelet analysis is based on Haar scaling function.

2 The Haar wavelet basis

The Haar basis is the simplest wavelet basis.

2.1 The one-dimensional Haar wavelet transform

Suppose we are given a one-dimensional “image” with a resolution of 4 pixels, we can decompose the original image into a lower resolution ( 2 pixels, by averaging ) version and a pair of detail coefficients







For simplicity, don't consider the normalization of the basis temporarily,

Resolution  Averaging(sub-sampling)        Coefficients
----------  ------------                   ------------
   4        [ 9 7 3 5 ]
   2           [ 8 4 ]                     [ 1 -1 ]
   1            [ 6 ]                     [ 2 ]

We define the wavelet transform of our original 4 pixels image as

    [ 6 2 1 -1 ]

The way we computed the wavelet transform, by recursively averaging and differencing coefficients, is called a filter bank.
Note that no information has been gained or lost by this process. The original image had four coefficients, and so does the transform. Also note that, given the transform, we can reconstruct the image to any resolution by recursively adding and subtracting the detail coefficients from the lower resolution versions.

2.2 One-dimensional Haar wavelet basis functions

We will use the concept of a vector space from linear algebra.
We can think of images as piecewise-constant functions on the half-open interval [0, 1).

• A one-pixel image is just a function that is constant over the entire 1 interval: [0, 1). We’ll let V0 be the vector space of all these functions.
• A two-pixel image has two constant pieces over the 2 intervals: [0, 1/2) and [1/2, 1). We’ll call the space containing all these functions V1
• If we continue in this manner, the space Vj will include all piecewise-constant functions defined on the interval [0, 1) with constant pieces over each of 2 **j equal subintervals.

The mathematical theory of multiresolution analysis requires this j nested set of spaces.

The basis functions for the spaces Vj are called scaling functions, and are usually denoted by the symbol Phi.


We can now define a new vector space Wj as the orthogonal complement of Vj to V(j+1).
A collection of linearly independent functions spanning Wj are called wavelets.
These basis functions have two important properties:

• The basis function of Wj, together with the basis function of Vj, form a basis of V(j+1).
• Every basis function of Wj is orthogonal to every basis function of Vj under the chosen inner produce.

Thus, the “detail coefficients” are really coefficients of the wavelet basis functions.
The Haar wavelets, given by

Let's express the 4 pixels image as a linear combination of basis functions in V2:



Note that the coefficients c0 , c1, c2 , c3 are just the four original pixel values [9 7 3 5].
The image can be expressed in terms of basis functions in V1 and W1 ,

And, it can be expressed in V0 , W0 and W1


The Haar basis possesses an important property known as orthogonality, which is not always shared by other wavelet bases.
We can normalize ( < u, u > = 1 ) the Haar basis by replacing our earlier definitions with


The following two pseudocode procedures accomplish this normalized decomposition:

2.3 Application I: Compression

The goal of compression is to express an initial set of data using some smaller set of data, either with or without loss of information.

3 Wavelets in two dimensions

3.1 Two-dimensional Haar wavelet transforms