On the Crest of a Wavelet
This article first appeared in Personal Computer World, May 1997.
EVERY SO OFTEN, an idea comes along which really gets people hopping. One of the newest is a mathematical technique called "wavelets", which is having a massive impact on the computing world. Although the mathematics of wavelets can give you a headache at the best of times, the underlying ideas are fairly simple. So, without an equation in sight, and throwing mathematical rigour to the wind, welcome to the wonderful world of wavelets.
To get an idea of how wavelets work, we'll look at an example from image processing, a field in which wavelets are playing an increasingly important role. Consider one row of pixels taken from an 8 by 8 grey-level image. Here, the numbers represent the values of the pixels from left to right, in the range 0 (black) to 255 (white):
Pixels: 13 5 12 2 6 0 2 0
To create a wavelet representation of this image, we start at the left, and average the values of pairs of pixels, keeping a note of the difference between the average obtained, and the value of the first pixel. We'll call this difference the "wobble". For example, averaging the first two pixel values (13 and 5) we get 9, with a wobble of 4. If we do this for each pixel pair in turn, we end up with a lower resolution image (4 pixels instead of the original 8) and a list of their respective wobbles:
Pixels: 9 7 3 1 Wobbles: 4 5 3 1
Notice that we haven't lost any information. By taking each new pixel value and adding and subtracting its associated wobble, we can always retrieve the original two pixels. If we now average and wobblify again, we get:
Pixels: 8 2 Wobbles: 1 1
Repeating the averaging a final time, we get:
Pixel: 5 Wobble: 3
We've ended up with a single pixel, which is an average of all the original pixel values. If we list this final pixel's value, followed by each of the wobbles we recorded along the way, we have generated the wavelet representation for the image:
Wavelet representation: 5 3 1 1 4 5 3 1
At first sight, we don't appear to have gained anything by this rather strange procedure. We certainly haven't saved any data storage (we still have eight numbers) and -- worse -- we appear to have averaged all our pixels into one mysterious shade of grey.
In fact, we have gained something. We can use the wavelet representation to generate versions of the original image at different resolutions. The wavelet representation gives us our lowest resolution image straight away. We can take the single average pixel value 5, and give all 8 pixels this value. It's not very interesting, and certainly there's no chance of anyone guessing what the original image looked like. But it's a low-resolution version of the image nonetheless.
To display the image at the next higher resolution, we take the single pixel value 5 and apply its wobble to it, to recover the two pixels from which it is was averaged. This gives: 8 (5+3) and 2 (5-3). Now we can set the first four pixels to 8, and the second four to 2, to give a slightly better resolution image. Repeating the process, we take each of these two pixel values, apply their wobbles (1 and 1 respectively), to recover the pixels from which they were averaged: these values are 9 (8+1), 7 (8-1), 3 (2+1) and 1 (2-1). Now we have four pixel values, which we can assign to each pair of the eight image pixels. Repeating the process once more brings back the original image.
Clearly this isn't particularly useful with an image of eight pixels. But for a complete image, if we have its wavelet representation, we can very easily display the image at a number of resolutions, ranging from best (no averaging) to worst (the average shade of the whole image). For an image of 512 x 512 pixels, we would have 9 choices of resolution, for 1024 x 1024, 10 choices, and so on. Having different choices of resolution readily available is very useful in image editing, and incremental display of Web graphics. The great advantage of the wavelet representation is that from it, you can generate an image at many different resolutions -- without needing to store each in a separate file. And the idea is easily extended to colour images.
Wavelets can also perform image compression. Let's look again at our example wavelet-encoded image:
5 3 1 1 4 5 3 1
Some of the wobbles are rather small, so will have little effect on the image reconstruction. For example, let's arbitrarily decide to not bother with wobbles less than 2, replacing them with zeros:
5 3 0 0 4 5 3 0
What effect will this have on the reconstructed image? Repeatedly applying the wobbles to the averages, as we did above, leads to the following image, which we can compare with the original image:
Reconstructed image: 12 4 13 3 5 -1 2 2 Original image: 13 5 12 2 6 0 2 0
They are clearly not identical, but they are extremely close (don't worry about the pixel value -1 -- we'll just display that as a zero). So, having removed three of the wobbles from the wavelet representation, we have still been able to recreate an image which is almost the same as the one we began with. We have effectively compressed the image, and made a storage saving of 37.5% (the wavelet representation now has 5 numbers instead of the original 8). This is an example of "lossy" compression, where we save storage space at the expense of degrading the image quality. This may sound like a bad idea, but with full-colour images, you can distort the pixel values quite a lot before any differences become visible to the eye. In fact, this happens in every JPEG file you see on the Web (although wavelets are not involved).
In practice, the details of wavelets are considerably more complex than this simple example illustrates, but the underlying principle is the same. Just as in classical Fourier analysis, where a complex signal can be dissected into a collection of pure sine waves, wavelets provide a means of taking complex data, and representing the same data as simple scales and shifts of standard wavelet functions (see the illustration for an example of a wavelet function). The wobbles express the scales and shifts required. Subsequently, the data can be processed by operating on the wobbles, and then reconstructing the original data.
For example, in computer graphics a curve can be analysed into a set of wavelets and wobbles, and by removing wobbles below a certain threshold value, the curve will be automatically smoothed when it is reconstructed. This technique can also be used for level-of-detail control in Virtual Reality, where objects are only drawn in high detail, with lots of polygons, when you are close enough to them. The further away from them you get, they are drawn using fewer, but bigger, polygons, in an effort to keep the animation rate constant.
Recently, wavelets have been cropping up in all kinds of unexpected places, from cleaning up a noisy old recording of Brahms playing his "First Hungarian Dance" on the piano, to reducing the storage by a factor of 20 in the FBI's archives of 30 million fingerprints. Wavelets are being used to extract hidden patterns from satellite and radio telescope data, for speech recognition, earthquake prediction, radar, and optics. Research is in full swing worldwide into applications such as sound synthesis, with the promise of creating realistic natural sounds at little cost, analysing financial markets, and modelling the human visual system.
As you might expect, the Web is alive with information about wavelets, and there is much free software you can download to play with. A good place to start is www.amara.com/current/wavelet.html. But a word of caution: if you feel tempted to dip into the mathematics behind it all, have a stiff drink first.
Toby Howard teaches at the University of Manchester.