Wavelets

The Fourier transform breaks a signal into sine waves, and tells you how much of each frequency it contains. It’s the most useful tool in signal processing. But it answers which frequencies, not when. Real sounds change: notes start and stop, drums hit, a voice moves from vowel to vowel. Wavelets are a way of looking at a signal that keeps both: what frequencies are present, and when.

This page starts from the Fourier transform’s blind spot, tries the obvious fix, and finds the idea that works better: look at low frequencies for a long time and high frequencies for a short time. Then it builds the simplest wavelet transform by hand, shows the better wavelets real systems use, and uses them for two things they’re famous for: compressing images (as JPEG 2000 does) and removing noise.

A few terms first:

A frequency is how many times a second something repeats, in hertz (Hz). An octave is a doubling of frequency: 220 Hz to 440 Hz is one octave, and so is 2,000 to 4,000 Hz.
A spectrum is how much of each frequency a signal contains, as the Fourier transform measures it.
A coefficient is just one of the numbers a transform produces.

Take three notes, C, E and G, played one after another. Now play the same recording backwards: G, E, C. They sound completely different: one rises, the other falls. But their spectra are identical. The same three notes are present, for the same length of time, at the same strength. The order they come in is hidden away in the phases of the frequencies (where each sine wave is in its cycle), which a spectrum’s magnitudes don’t show.

Top: the three notes, rising. Middle: the same, backwards. Bottom: the two spectra (the strength of each frequency), one drawn over the other. Listen to both.

The largest difference between the two spectra is 2.0 × 10⁻¹⁴ % of the peak: rounding error. As far as the spectrum is concerned, they’re the same sound.

Everything a signal does is in its Fourier transform, but spread across every frequency’s phase, where you can’t see it. We need a picture that shows time directly.

2 · The obvious fix: the short-time Fourier transform

If one Fourier transform of the whole signal hides when things happen, take many: chop the signal into short pieces, called windows, and take each piece’s spectrum. Lined up side by side, with time across and frequency up, and strength as colour, they make a spectrogram. That’s the short-time Fourier transform (STFT), and it’s how most sound software shows sound.

There’s a catch. To tell two frequencies apart, a window must last long enough for them to drift apart by a whole cycle: about 1 ÷ (their difference) seconds. To pin down when something happened, the window must be short. You can’t have both. A window $T$ seconds long can separate frequencies about $1/T$ Hz apart, and moments about $T$ seconds apart, and their product is stuck at about 1. It’s a form of the uncertainty principle.

The spectrogram of the page’s test signal: a low hum at 150 Hz all the way through, a chirp gliding from 300 Hz up to 3 kHz between 0.4 and 1.6 s, and three short clicks, at 0.25, 1.0 and 1.75 s (8,000 samples a second). The slider sets the window.

With a 32 ms window, the spectrogram tells frequencies apart if they’re about 31 Hz apart, and moments if they’re about 32 ms apart. Shorten the window to 4 ms, and the clicks become sharp lines, but the hum spreads into a band 250 Hz wide. Lengthen it to 256 ms, and the hum is a fine line (3.9 Hz), but the clicks smear across a quarter of a second.

The trouble is that one window has to suit everything. The low hum wants a long window; the clicks want a short one. And the chirp wants something different at each end of its glide.

3 · The insight: scale

Notice what each part of the signal needs. Low frequencies change slowly: to see a cycle of a 100 Hz tone, you need to watch for 10 ms. High frequencies change fast, so a short look is enough, and it lets you pin down when they happen. So use long windows for low frequencies, and short windows for high ones.

A good way to picture this is to split the time–frequency plane into boxes, one per number a transform produces. Each box shows how precisely that number pins down time (its width) and frequency (its height). The uncertainty principle says every box has about the same area; what you can choose is its shape.

Four ways to split up the plane, all with the same number of boxes, each of the same area.

The samples themselves are thin vertical slivers: they say exactly when, and nothing about frequency. The Fourier transform is the opposite. The short-time Fourier transform uses one box shape everywhere. Wavelets change the shape with frequency: at the top, short and tall (precise in time); at the bottom, long and flat (precise in frequency). Each row is one octave.

Musicians already think this way. A piano’s keys are spaced evenly in octaves, not in hertz: the octave at the bottom of the keyboard spans 27 Hz, and the one at the top spans 2,000 Hz. Ears work the same way.

4 · A wavelet

A wavelet is a short burst of wave: a few cycles that grow and then die away. Make copies of it at different scales by stretching or squeezing it. A stretched copy is longer and has a lower frequency; a squeezed copy is shorter and has a higher one, but every copy has the same shape and the same number of cycles.

To analyse a signal, slide each copy along it, and at every moment measure how well it matches: multiply the two together and add up, exactly the correlation of the finding-signals page. A strong match means the signal contains that frequency, right then. Doing this for every scale and every moment gives the continuous wavelet transform, and drawn as a picture, it’s a scalogram.

Top: a Morlet wavelet (a cosine under a bell-shaped envelope), stretched to the chosen frequency, drawn on a fixed time axis so you can see it stretch. Bottom: the scalogram of the same test signal as section 2, with frequency on an octave scale. The dashed line is the wavelet shown above. Cycles sets how many oscillations each wavelet has.

With 6 cycles, the wavelet at 588 Hz lasts about 6.5 ms and responds to frequencies within about 98 Hz of its own. At 100 Hz it lasts 38 ms (and responds within 17 Hz); at 3 kHz, 1.3 ms (and within 500 Hz). So in the scalogram, the clicks are sharp at the top and broaden only near the bottom, while the hum is a narrow band. The chirp, which climbs evenly in octaves, keeps the same width all the way up.

The continuous wavelet transform is wonderful for looking at signals, but it’s wasteful: every row is as long as the signal, so a 2-second signal turns into 72 rows of 16,000 numbers. For compressing or cleaning a signal, we want a transform that turns $N$ numbers into exactly $N$ numbers, and can be undone exactly. That’s the discrete wavelet transform, and the simplest one can be done by hand.

5 · The simplest wavelet: Haar

Alfréd Haar described it in 1909, decades before anyone said “wavelet”. Take the signal two numbers at a time, and replace each pair with:

its average: (first + second) ÷ 2, and
its difference: (first − second) ÷ 2, how far each is from the average.

The averages are a half-length, smoothed copy of the signal. The differences are the detail the averages lost. Nothing is lost overall: the pair is always average + difference and average − difference, so it can be rebuilt exactly. Then do the same to the averages, and again, until a single average is left.

Eight numbers, transformed step by step. Blue bars are averages, orange bars are differences. Each step replaces the averages so far with their own averages and differences, and keeps all the differences. Rebuilt from these undoes every step.

8, 6, 7, 5, 3, 0, 9, 9 becomes, after one step, the averages 7, 6, 1.5, 9 and the differences 1, 1, 1.5, 0. After three steps, it’s 5.875 (the average of everything), then 0.625, then 0.5 and −3.75, then 1, 1, 1.5 and 0. Still eight numbers, and they rebuild the original exactly.

Why bother? Look at where the large numbers ended up. The original numbers are all much the same size, but after the transform, most of the information is in a few numbers (the overall average, and the big jump between 3, 0 and 9, 9), and the small differences describe the fine wobbles. Real signals are mostly smooth, so most of their differences are small. That’s what makes wavelets good for compression and for removing noise, as sections 8 and 9 show.

The Haar transform can be done in place, overwriting the pair as you go: work out the difference, then use it to update the first number to the average. That trick generalises to every wavelet, and it’s called lifting (Wim Sweldens, 1996). It’s how JPEG 2000 computes its wavelets.

6 · Many levels: a filter bank

Look at the Haar step another way. The average of each pair is a crude low-pass filter: it keeps the slow changes. The difference is a crude high-pass filter: it keeps the fast ones. And keeping only one number per pair halves the sample rate, as on the resampling page. So one step splits the signal into two halves of its frequency range, each at half the rate.

Repeating on the averages splits the low half again, and again. Each level’s details cover one octave, the top octave first: exactly the boxes of section 3. A set of filters like this is a filter bank, a close relative of the MP3 encoder’s polyphase filter bank, which splits sound into 32 equal bands instead of octaves.

The test signal (8,000 samples a second), split by the chosen number of levels. The top row is the averages that remain; each row below is one level’s details, labelled with the band of frequencies it covers.

With 4 levels, the 16,000 numbers become 1,000 averages, covering 0 to 250 Hz (where the hum is), and details in the octaves 250–500 Hz, 500–1,000 Hz, 1–2 kHz and 2–4 kHz. Still 16,000 numbers in all. The chirp moves from the low bands to the high ones as it rises. The clicks show up as sharp spikes in the top two bands, where they stand 12 to 18 times above anything else at quiet moments.

So every discrete wavelet transform is the same machine: a low-pass filter and a high-pass filter, keep every other sample of each, and repeat on the low half. What makes one wavelet different from another is only the pair of filters.

One thing makes the pair special. Keeping every other sample halves the rate, and as the resampling page showed, that aliases: anything above the new half-rate folds back down. Neither filter is a perfect cliff, so each half carries a folded copy of frequencies that belong to the other half. Rebuilt on its own, each half is wrong. But the two filters are designed as a matched pair, so that the aliasing in one half is exactly equal and opposite to the aliasing in the other: put back together, they cancel, and the signal comes back exactly.

Top: each level’s whole path (low-pass filters, then a high-pass) as a single filter: how much of each frequency reaches each level’s details, and the averages left after 4 levels. Bottom: a 1,600 Hz tone, split once (into 0–2 kHz and 2–4 kHz) and rebuilt from both halves or from one alone: the strength of each frequency in the result. Listen to the tone rebuilt from both halves, and from the low half alone.

The filters overlap: Haar’s finest details (meant for 2–4 kHz) still let through 1 kHz at −8.3 dB, while Daubechies 4 cuts it to −19.5 dB. Rebuilt from the low half alone, the 1,600 Hz tone gains an alias at 2,400 Hz (1,600 Hz mirrored about the 2 kHz middle): −6.5 dB with Haar. The high half alone carries the same alias, just as strong. From both halves, the alias cancels completely, and the tone comes back exactly.

7 · Better wavelets

First, what makes a wavelet good for compressing a signal, or cleaning it? After the transform, we want as many of the details as possible to be zero, or so small they can be thrown away, so that a handful of large numbers carry almost everything. A detail is zero when there’s nothing for it to add: when the averages alone already describe the signal at that point. So the question is, what kinds of signal leave nothing for the details?

For Haar, only a flat stretch. A detail is half the difference between two neighbouring samples, so it’s zero only when they’re equal. Give Haar a perfectly steady ramp, 0, 1, 2, 3, 4, …, and every detail comes out as −0.5. Nothing about a ramp is surprising, yet every number still costs something. On a gentle curve, it’s worse: the details grow as the curve steepens.

In 1988, Ingrid Daubechies found a family of wavelets that do much better, and still have everything that makes Haar work: they turn $N$ numbers into $N$ , keep the signal’s energy, and undo exactly. They’re also smoother: as filters, they let less of each band leak into its neighbours, as the previous figure showed.

What makes them better is called vanishing moments. A wavelet with $p$ vanishing moments gives a detail of exactly zero wherever the signal, over that wavelet’s width, follows a polynomial of degree less than $p$ : nothing for the details to add, because the averages already follow it perfectly. Haar has one vanishing moment, so only flat stretches (degree 0) give zero. The Daubechies wavelet with 4 vanishing moments (8 coefficients long, so “Daubechies 4”) also gives zero wherever the signal is a straight line, a parabola, or even a cubic curve. On the same ramp, its details are all exactly 0, except at the very end, where the transform wraps the ramp’s top round to its bottom: a jump. Smooth stretches of a signal cost nothing at all, and the large details sit only where something sudden happens.

Top: a signal made of three smooth pieces, with jumps between them (grey), and the same signal rebuilt from only the largest 5% of its wavelet numbers (blue). Middle: every detail, finest level first. Bottom: the shape of one wavelet.

With Haar, 472 of the 1,008 details are bigger than 0.001: every slope costs something. With Daubechies 4, only 79 are, almost all of them at the jumps. Rebuilt from the largest 5% of the numbers, the signal’s worst error is 0.0202 with Daubechies 4, against 0.0324 with Haar.

Daubechies’ coefficients come from solving the conditions for vanishing moments and exact reconstruction together; this page uses them rather than deriving them. What matters is what they achieve: a signal described by few large numbers, which is exactly what compression and noise removal need.

8 · Compressing images

A photograph is mostly smooth regions with edges between them: a two-dimensional version of section 7’s signal. A wavelet transform of an image works on the rows, then on the columns, and then again on the quarter-size averages, level after level. Most of the resulting numbers are tiny, so a compressor can keep the largest few and throw the rest away. That’s the heart of JPEG 2000, which uses a smooth wavelet called CDF 9/7 (after Albert Cohen, Ingrid Daubechies and Jean-Christophe Feauveau), computed by lifting.

The original JPEG does something similar with the discrete cosine transform (a close cousin of the Fourier transform), but in separate 8 × 8 blocks. That keeps each block’s calculation small, but it can’t share effort between blocks: every block costs at least one number, and when too much is thrown away, the block edges show.

First: the picture (256 × 256, in grey). Second: rebuilt from only the largest wavelet numbers (CDF 9/7, 5 levels). Third: rebuilt from the same number of JPEG-style 8 × 8 DCT numbers, keeping every block’s average first. PSNR (peak signal-to-noise ratio) measures how close each is to the original: higher is better, and above about 40 dB the differences are hard to see. Choose a photo to try your own (it stays on your computer).

Keeping the largest 2% of the numbers (1,311 of 65,536), the wavelets reach 34.1 dB and the DCT blocks 30.6 dB: the DCT’s sun and hills turn into steps, while the wavelets blur a little and keep their shapes. At 5%, the two are close (41.6 against 41.3 dB). Below about 1.6%, the DCT can’t keep even one number for each of its 1,024 blocks, and falls apart (11.5 dB at 1%), while the wavelets still manage 29.7 dB.

JPEG 2000 adds a lot to this: careful quantisation instead of a simple “keep or throw away”, and an arithmetic coder for the numbers that are kept. It compresses better than JPEG, especially at low quality, and degrades gracefully. It never replaced JPEG on the web (JPEG was already everywhere, and JPEG 2000 is slower), but it’s used where quality matters most: digital cinema distributes films as JPEG 2000, and it’s common in medical imaging and archives. Long before it, the FBI’s fingerprint archive used a wavelet method (WSQ), for the same reason: fingerprints are all fine ridges, and JPEG’s blocks would have damaged them.

9 · Removing noise

Noise added to a signal spreads evenly across all the wavelet numbers: a little in each. The signal, as section 7 showed, is concentrated in a few large ones. So shrink every small detail to zero, and the large ones a little, and transform back. Most of the noise goes, and the signal, including its sharp edges, stays. This is wavelet thresholding, from David Donoho and Iain Johnstone (1994).

How small is “small”? Donoho and Johnstone’s universal threshold is $\sigma\sqrt{2\ln N}$ , where $\sigma$ is the noise’s level and $N$ the number of samples. Pure noise almost never reaches it. Here, $\sigma$ is estimated from the finest details, which are mostly noise. The universal threshold removes almost all the noise, but for sound it also removes the quiet parts of the sound itself, so a fraction of it usually sounds and measures better.

The obvious alternative is a low-pass filter: noise reaches high frequencies, so cut them off. But sounds with sharp attacks, like drums, have their own high frequencies, and a low-pass filter can’t tell them from the noise.

Top: the sound with noise added, and where the close-ups are. Below: 20 ms close-ups, each method’s result against the clean sound (dashed): wavelet thresholding (Daubechies 4, 6 levels) and a low-pass filter. The readouts give each result’s SNR against the clean sound: higher is better. Listen to all four. Record your own sound to try it: it becomes the “clean” sound, and the noise is added to it.

For the drum loop with noise at 10 dB, wavelet thresholding at a quarter of the universal threshold reaches 15.9 dB, keeping 24.4% of the details, and follows the snare’s attack closely. The low-pass filter at 3 kHz manages 9.5 dB: it smooths the snare away along with the noise. At the full universal threshold, the wavelets keep only 1.3% of the details and reach 11.1 dB: too much of the snare goes with the noise. For speech, a low-pass filter does about as well by the numbers (17.6 dB, against the wavelets’ 16.8 dB), because speech’s energy is mostly at low frequencies; but listen to the “s” sounds.

10 · Where they’re used

Images: JPEG 2000 (digital cinema, medicine, archives, and many satellite images), and the FBI’s fingerprint archive.
Sound: analysing music and speech (the scalogram’s octave scale matches how we hear), detecting events such as onsets, and noise reduction.
Medicine: finding the features of heartbeats in ECG recordings, and of brain activity in EEG.
Geophysics: wavelets began here, in the early 1980s, when Jean Morlet, analysing seismic echoes for oil exploration, needed short waves for high frequencies and long ones for low.
Numbers: fast solvers for some equations, and the analysis of turbulence.

Summary

The Fourier transform says which frequencies a signal contains, not when: a sound and the same sound played backwards have the same spectrum.
The short-time Fourier transform chops the signal into windows, but one window length can’t suit both low notes and sharp clicks: precision in time and frequency trade off.
Wavelets use long looks for low frequencies and short ones for high frequencies: every octave gets the right balance.
The continuous wavelet transform correlates the signal with stretched copies of one wavelet, giving the scalogram.
The Haar transform replaces pairs with averages and differences, level after level, losing nothing.
It’s a filter bank: each level’s details are one octave of the signal.
Daubechies wavelets give zero detail wherever the signal is smooth, so smooth signals become a few large numbers.
Keeping only the largest numbers compresses images (JPEG 2000), without JPEG’s blocks.
Shrinking the small numbers removes noise while keeping sharp edges.