Contributed by Fadil Santosa

This article is a synopsis of a talk presented by Dr. Wim Sweldens of Bell Laboratories, Lucent Technologies, at the IMA Industrial Problems Seminar on November 14, 1997

Introduction

While wavelet is a relatively new subject, it is an area of tremendous activity and growth. Indeed for most of us, it is hard to imagine that there already is a second generation of wavelets -- most of us are still struggling to understand the rudiments of (first generation) wavelet theory. However, as this summary will show, second generation wavelets are actually easier to understand and use. Moreover, they offer some generalities that make them applicable to new areas such as computer graphics.

What are wavelets and why do they work?

The key to understanding this question starts with the observation that digital data, i.e., data from speech, images, video, and graphics, are highly correlated, and contain redundancy. Wavelet exploits this structure by providing a system by which this type of digital data can be represented accurately with a few parameters. Moreover, the computation involved in obtaining the representation is fast and efficient, usually linear in complexity. Because of this property, wavelet has been used in data compression, data transmission, geometric modeling, as well as in numerical computations.

For clarity of presentation, let us consider a scalar function of a single variable f(x). We wish to find an economical representation of this function. The easiest way to think of wavelets is to imagine a basis generated by a function which

1. Is compactly supported,
2. Is smooth,
3. Has zero moments.

The a_jl are the wavelet coefficients of the function f(x).

That this representation will be economical can be explained by the fact that the basis function is localized in time and frequency. This means that if f(x) has high frequency components at x₀, the cost of accurately representing this feature at x₀ is not global, i.e., we do not have to pay for this at point far away from x₀. To see this more clearly, let us assume the mother wavelet has the form such that its dilates are as displayed on the left side of Figure 1. We show the function f(x). The wavelet coefficients of f(x) are organized in a table whose columns are increasing index l and whose row are increasing index j. For the function f(x) as shown in Figure 1, we would see the distribution of a_jl in the figure.

The computational machinery for actually finding the wavelet coefficients from the function, the forward wavelet transform, and its inverse, can be made very efficient. It has the similar properties to DFT which can be exploited in much the same way as FFT.

Another point worth noting is that wavelets provide a natural framework for multiresolution analysis of functions. That is, the wavelet transform in effect provides coarser and coarser versions of the same function while at the same time keeps track of the details missed going from fine to coarse. This realization gives a powerful tool for analysis and manipulation of functions.

Second Generation Wavelets

The need for improvement of wavelets come from a shortcoming that is inherent because of its construction. The main limitation is that the first generation wavelet works well for infinite or periodic signals but it is not clear how one should modify it for use in a bounded domain. In many applications, the domain of interest is not infinite, and signals are not periodic. Furthermore, even 1-D signals are often not sampled regularly. In higher dimension, domains are often have boundaries, and often the metric is not flat, i.e., we need to analyze functions on manifolds or surfaces.

The big issue is how to keep the "nice" properties of wavelets, namely time-frequency localization and fast algorithms, while being able to extend beyond simple geometries. The answer is to give up translation and dilation. The construction must therefore not use any Fourier analysis. Instead, the calculation will be entirely based on a new approach called The Lifting Scheme.

The basic idea is to first split a signal into its even and odd samples. That is, split an original signal x_k to the even set { x _k: k even} and the odd set { x _k: k odd}. Recall that wavelet starts with the key observation that digital signals are highly correlated, and the correlation structure is local. So the idea here is to predict the odd signal from the even part. What is missed by the prediction is called the detail. The even samples then are adjusted to serve the coarse version of the original signal. The adjustment is needed to maintain the same average for the fine and coarse versions of the same signal. The step can be described in the following algorithm

1. Split data: even and odd
2. Predict odd using even: detail = odd Ð P(even)
3. Update even using detail: coarse = even + U(detail)

The prediction operator is linear and depends on how one does the prediction. Linear prediction is described in Figure 2. The update operator, also linear, can be easily deduced by calculating an integral to represent an average.

To see the method more clearly, let us say that we have a signal s_jk, k is the sample, and j is the sampling level. The algorithm above yield s_(j-1)k and d_(j-1)k.

To complete the wavelet transform, one would repeat these steps on the coarse signals. In the end, one would have detail signals after each step, and a single number representing the average of the signal. An inversion algorithm reconstructs the original signal from these informations.

The forward transform can be viewed as a wire diagram as shown in Figure 3. The inverse transform can be easily constructed by "rewiring" the forward transform as shown.

These steps embody the key elements of the first generation wavelet transform. If one is interested in Fourier coefficients, one can easily calculate them from the detail and coarse signals at each step.

For functions that live on a finite interval that is sampled unevenly, the predict and update operators will vary from location to location on the interval. Formulas for these operators can be obtained by following a simple recipe.

For 2-D domain, an analog of the lifting mechanism described above can be devised. The possibility to generalize to higher dimensions, and to manifolds, depend on the availability of meshing.

The key point worth repeating is that desirable features of the first generation wavelets, namely fast computation and multiresolution capabilities, are retained in the second generation wavelets. Another desirable added feature of the second generation wavelet, which can be seen from the wiring scheme, is that the forward and inverse transforms are invertible no matter what choice we make for the operators P and Q. The wiring procedure allows us to construct wavelets transform with any degree of smoothness.

 A simple (lossy) compression strategy based on lifting is to "drop" detail components that are below a treshold prior to storing. Coding and implementation play a crucial role in the efficiency of the compression algorithm.

 A new application of wavelet is in geographical data analysis. One can think of the topography of the earth as function value defined on a sphere. Because of the flexibility of the lifting scheme, it is possible to create wavelets that live on a sphere. In this way, the topographic data of the earth can be compressed and manipulated much like a 1-D signal.

 Clearly such an approach can be exploited in areas such as computer graphics. A 3-D object that is meshed by triangles can be analyzed using the multiresolution scheme if we allow ourselves to think of the triangulation as the domain of the problem, and the coordinates of the vertices as function values. A recent book by DeRose et al describes a multiresolution approach for computer graphics. Zorin, Schroeder and Sweldens has recently developed an editing tool for 3-D objects based a variant of the Burt-Adelson pyramid, which is related to lifting, but is oversampled while lifting is always critically sampled. The tool can be used in computer animations. There has already been work in using multiresolution for solving the luminosity calculations arising in computer graphics. It is quite possible that classical problems of scattering of electromagnetic waves can also be solved using this approach. The lifting approach could provide a viable alternative to the fast multipole method that has recently been shown to be very successful for the scattering problem.