PITY the FBI. Its 200 million fingerprint records are stored as inked impressions on paper cards. This archaic system makes comprehensive searches virtually impossible, and the bureau would dearly love to be able to keep its fingerprint library on computer instead. But there is a snag. Digitising the images and storing them at the present level of detail would create an archive occupying an impossibly huge 2000 terabytes of memory 鈥� enough to fill 2 million reasonably large hard discs. To make matters worse, 30 000 new cards are received every day, adding another 300 hard discs to the storage space required. The only way out is to find a way to simplify the data, picking out the bits of the image that make up enough of the overall shape to identify a match, while leaving out the irrelevant fine detail. But how?
The answer lies in a technique called wavelet analysis that emerged around a decade ago from an obscure branch of pure mathematics. In the past few years, wavelets have made the transition from a mathematician鈥檚 research tool to the latest way to clean up and compress images of various kinds. As well as being snapped up by the FBI, wavelet analysis is undergoing trials for cleaning up messy data in medical imaging, and even for improving the sound quality in fuzzy old recordings. The key to wavelets is that they provide a precise mathematical way to see the wood for the trees, by picking out key information while leaving out unnecessary and space-consuming detail.
Information seldom shows up in a way that makes it obvious which bits are relevant and which can be discarded. For instance, suppose you want to fax a friend a cartoon line-drawing that happens to be on a piece of rather dirty paper. Your fax machine has no idea that the specks of dirt are irrelevant to the overall image 鈥� it just scans the page line by line, and sends the image as a long string of binary black and white signals. Picking out which bits of information are crucial to the cartoon requires a much more sophisticated analysis, involving an appreciation of the overall spatial structure of the image and making a connection between widely separated data from several different scanning lines of the fax signal.
Advertisement
However, there are other ways to represent data. The one that eventually led to wavelets was introduced by Joseph Fourier in 1822 in a study of heat flow. Fourier wasn鈥檛 interested in images; what he was after was equations that would describe how some initial distribution of temperature along a metal bar would change as the heat flowed along it. Just as a hospital nurse graphs how a patient鈥檚 temperature varies in time, so Fourier could graph how the bar鈥檚 temperature varied in space. He eventually discovered that he could build up any kind of curve he wanted just by adding together a particular set of curves called sines and cosines.
More generally, any sequence of numerical data can be represented as a curve, so they too can be represented by a set of sine and cosine curves. The key feature of these curves is that they come as a series of regular wiggles which go on forever. The height of the wiggles is the amplitude of the sine or cosine curve, and the number of wiggles occurring in a given length is the frequency. By adding lots of sines and cosines of the right frequencies and amplitudes (see diagram below) you can end up with any curve you like, Fourier discovered. Now all he needed to do was separate the heat curve into its component sines and cosines, work out what would happen to each over time, and add the individual solutions together to give the answer for the metal bar.
Looked at from a slightly different angle, Fourier鈥檚 analysis gives us a way of changing how data are represented. From the original curve, you get a list of the amplitudes and frequencies of its component sines and cosines. Mathematical operations that are difficult or impossible with one representation of the data may become easy with the other.
For example, you can start with a telephone conversation, generate its Fourier transform, and strip out those parts of the signal whose Fourier components have frequencies too high or too low for the human ear to hear.
This makes it possible to send more conversations over the same communications channels, and it is one reason why today鈥檚 phone bills are relatively cheap. You can鈥檛 play this game with the original, untransformed signal, because that doesn鈥檛 have 鈥渇requency鈥� as an obvious characteristic. Fourier analysis has a long pedigree and is enormously useful, but it runs into big problems when it comes to representing a compact signal such as single blip. The trouble is that it takes huge numbers of sines and cosines to produce even a moderately convincing replica of a simple, short-lived blip. This is because sine and cosine waves go on forever: the problem is not getting the basic shape of the blip right, but making everything outside the blip equal to zero. You have to kill off the infinitely long wavy tails of all those sines and cosines, which you do by piling on sine and cosine curves of ever higher-frequency in a desperate effort to cancel out the unwanted junk. This makes the Fourier transform pretty hopeless as a method of data compression for blip-like signals, because the transformed version is so much more complicated than the original blip and needs more data to describe it.
This is where the wavelets come in. The principle is very similar to Fourier transformations, but now instead of sines and cosines you use blips as the basic components. First, you choose some particular shape of blip, of some particular size, to act as a 鈥渕other wavelet鈥�. Then you generate daughter wavelets (and granddaughters, great-granddaughters and so on) by sliding the mother wavelet sideways into various positions, and expanding or compressing it by a change of scale (see p 28).
Mother of all detail
Wavelets are designed to describe blip-like data efficiently. Moreover, because the daughter and granddaughter wavelets are just rescaled versions of the mother wavelet, it is possible to focus on particular levels of detail.
If you don鈥檛 want to see small-scale structure, you just remove all the great-granddaughter wavelets that appear in the wavelet transform. For instance, imagine a leopard represented by wavelets: a few big ones would get the body right, smaller ones would give you the eyes, nose and of course the spots, then very tiny ones would give individual hairs. If you decide that the individual hairs don鈥檛 matter much, you can cut down the amount of the data representing the leopard just by removing those particular component wavelets.
The great thing is, you don鈥檛 lose the spots, and the image still has the shape of a leopard. You would be stuck if you tried to do something similar with the Fourier transform of a leopard: the list of components is huge, it鈥檚 not clear which items you should remove, and whatever you do remove you will probably end up with something you can no longer recognise as a leopard.
As it happens, most of the mathematical tools required to develop wavelets have been around for half a century. They come from an area of pure mathematics called functional analysis, which was invented to unify huge amounts of classical analysis in an elegant way. When wavelets came along, it turned out that the esoteric machinery of functional analysis was exactly what was needed to understand them and develop them into an effective technique.
The only important missing ingredient was a good shape for the mother wavelet. 鈥淕ood鈥� here means that all the daughter wavelets are mathematically independent of their mother. There should be no overlap in the information encoded by mother and daughter, so no part of any daughter is redundant.
In the early 1980s, the geophysicist Jean Morlet and the mathematical physicist Alexander Grossmann devised the first successful shape for a mother wavelet and explained the advantages of wavelets in data analysis. In 1985, the mathematician Yves Meyer from the University of Paris IX improved upon Morlet and Grossmann鈥檚 wavelets in various technically useful ways. But the discovery that really got things going was made in 1987 by Ingrid Daubechies, a mathematician at AT&T Bell Laboratories in the US. Although previous mother wavelets looked suitably blip-like, they all had a very tiny mathematical tail that wiggled off to infinity. Daubechies found a mother wavelet with no tail at all: outside some interval, it was always exactly zero. This characteristic is especially useful in practical applications because it speeds up the computation of the wavelet transform. There are now dozens of such genuinely localised blips.
Wavelets are a godsend for data compression, because they act as a kind of numerical sieve that lets small stuff escape but retains anything larger than the chosen size of mesh. That is why in 1993 the FBI opted for a method known as wavelet scalar quantisation, or WSQ for short. The method was developed by Tom Hopper, project leader at the FBI鈥檚 Criminal Justice Information Services Division, and Jonathan Bradley and Chris Brislawn from Los Alamos National Laboratory鈥檚 Computer Research and Applications Group.
Serious snags
Before this, the FBI had been trying out the widely used JPEG image compression standard. This breaks the image into blocks eight pixels square, Fourier transforms each block, and compresses the resulting output data. For this application, JPEG鈥檚 big drawback shows up as soon as you attempt to squeeze the data to less than 10 per cent of its original size: the information lost in the process means that images reconstituted from the compressed data become unsatisfactory because of 鈥渢iling artefacts鈥�, in which the eight-pixel-square blocks leave marked boundaries.
For the FBI, these tiling artefacts are much more than just an aesthetic problem, as they seriously impair the ability of computer algorithms to search for matching fingerprints. And the fingerprint databank is so massive that no compression method will be much use to the FBI unless it can deliver compression ratios of at least 10:1. Alternative Fourier-based methods also introduce objectionable artefacts, all of which can be traced to the problem of infinite 鈥渢ails鈥� in Fourier sines and cosines. So Fourier methods just can鈥檛 hack it.
Wavelet transform methods, however, do not need to create artificial subdivisions with sharp edges. They work with the image as an integrated whole, and instead of removing information by creating tiling artefacts, WSQ removes fine detail throughout the image. This detail can be fine enough to be irrelevant to the eye鈥檚 ability to recognise the structure of the fingerprint. In the trials, three different wavelet methods all outperformed JPEG and another Fourier method called local cosine transform. The system also has a great deal of flexibility to accommodate future advances in image compression. WSQ is expected to provide a compression ratio of at least 15:1, reducing the cost of storage accordingly.
FBI compatible
Although the FBI has yet to install the system, the National Institute of Standards and Technology has now started to certify commercial implementations of WSQ. The idea is also spreading to other countries. In Britain, the Home Office, which currently uses JPEG compression for its fingerprint data, may switch to a system that is compatible with the FBI鈥檚.
As well as allowing image data to be compressed without unacceptable loss of quality, wavelets are very good at improving the quality of existing images. This is particularly useful in medical imaging. Hospitals now employ several different kinds of scanner which assemble two-dimensional cross sections of the human body. The techniques, which include computerised tomography (CT), positron emission tomography (PET) and Magnetic Resonance Imaging (MRI), all need to collect large amounts of data before they can build up a good enough image to provide a meaningful diagnosis. But the smaller the amount of data that the doctors can get away with, the larger the number of patients who can be examined with a single piece of expensive equipment. And in CT, where each projection requires an X-ray exposure, the individual patient benefits by not being exposed to unnecessary radiation.
Wavelet analysis provides a way of making do with a lower-quality image. For instance, noise in an image usually shows up on very fine scales. So you can use wavelets to cut out the finest scales 鈥� and with it, much of the noise 鈥� instead of having to collect more data. In 1992, Dennis Healy and John Weaver of Dartmouth College in New Hampshire applied this idea to MRI. With Fourier methods, it takes between 90 and 180 sequences to generate an image of a single slice through the body. With wavelets to clean up the image, Healy and Weaver needed far, reducing patient exposure time by at least a factor of three.
Wavelets can also be used to boost the contrast of an image 鈥� sharpening up the boundaries between regions with different light levels. Because such boundaries, like wavelets, are highly localised, they are easy to manipulate in a wavelet transformation. Andrew Laine, Jian Fan and Wuhai Yang from the University of Florida in Gainesville have used wavelets to enhance the level of contrast in mammograph images. After wavelet processing, images that look little better than a blur resolve themselves into clear, contrasting details. Doctors can then distinguish potentially cancerous cells more rapidly and with more confidence. Wei Quian and his colleagues at the University of South Florida in Tampa are also using wavelet-enhanced mammographs to help computers pick out danger areas.
Transforming pictures into a series of wavelets could also be useful for modelling human visual processing. People whose ability to process visual information is impaired, often see pictures as if they had very little contrast. But because it is the processing that is at fault, simply boosting the contrast of the images they see does not always fix the problem. Steven Rogers and his colleagues at the Wright-Patterson Air Force Base in Dayton, Ohio, are investigating ways of using wavelets to manipulate images and simulate what the images look like to patients. From this they hope to work out how to make them look normal.
The cleanup capabilities of wavelets are not restricted to images 鈥� they can be applied to any kind of data that can be represented as a curve. For instance, in 1994 Jonathan Berger and a team from Yale used a wavelet analysis package created by Victor Wickerhauser from Washington University in St Louis to remove unwanted noise from a recording of Brahms playing one of his own Hungarian Dances. Brahms made the recording in 1889 on a wax cylinder. After the cylinder had partially melted, the recording was transferred onto a 78-rpm disc. Berger started from a radio broadcast of the disc, by which time the music was virtually inaudible amid the noise. After wavelet cleansing, you could at least hear what Brahms was playing.
Researchers in the esoteric field of turbulent flow are also adapting wavelets for their purposes. Wavelets are ideal here, because the favoured theory is that turbulence is a combination of innumerable structures, such as vortices. Like wavelets, these have a definite pattern, and extend over only a very small region. The actual flow pattern in a turbulent fluid is composed of millions of interacting vortices of all sorts of sizes. You cannot just look at a picture and see which vortex is which. But you can decompose the flow pattern into component wavelets, and that gives a handle on the physics of the individual vortices.
Turbulence trouble
Last year, Meinhard Meyer and Carl Friehe from the University of California at Irvine and Lonnie Hudgins from Northrop Corporation in Hawthorne, California, used wavelet analysis in their investigations of atmospheric turbulence. They were able to show that during turbulent flow over land, large vortices tend to be followed by a sort of wake of smaller ones. But in flow over water, they found no such association, so it seems that atmospheric turbulence behaves in fundamentally different ways over land and water. Although this is pure research, results like these could help improve the aircraft safety during takeoff and landing.
Ten years ago, nobody had heard of wavelets, and functional analysis was just another esoteric toy for mathematicians. Now they are showing up almost everywhere. And while scientists learn how to get the best out of this clever new tool, politicians might reflect that this is another poke in the eye for those who insist that research cannot be worthwhile unless it has a specific goal.