15.2 Lossy compression

15.2 Lossy compression#

We now arrive at the key question for this chapter: how can we leverage observations from psychoacoustics to improve codecs, by removing perceptually redundant information?

In this section, we will explore lossy codecs, whose round trip is imperfect:

\[\text{Decoder}(\text{Coder}(\mathbf{x})) \neq \mathbf{x}, \qquad \texttt{error}\big(\mathbf{x}, \text{Decoder}(\text{Coder}(\mathbf{x}))\big) > 0.\]

Our goal is for the distortion to be imperceptible to human ears, as it was for amplitude quantization. Lossy music compression formats (like MP3 and Ogg Vorbis files) can achieve compression factors around \(10\times\) relative to uncompressed CD-quality audio (\(1411\) kbps), with nearly imperceptible distortion. This is remarkable! About \(9\) out of every \(10\) bits that we use to store digital audio are redundant from the perspective of human perception of music. How is this possible?

First, test your ears. Below are three versions of the same drum loop: one uncompressed (\(1411\) kbps), one compressed to MP3 at \(128\) kbps (a compression factor of \(11\times\)), and one compressed to MP3 at \(64\) kbps (\(22\times\)). Which is which?

Version 1

Version 2

Version 3

Three versions of a drum loop. Recording from Freesound: 157373 by cheeseymofodude, License: CC0.

Reveal the answer

Version 1 is the MP3 at \(128\) kbps, version 2 is uncompressed, and version 3 is the MP3 at \(64\) kbps. Listen for the sizzle of the hi-hats in version 3, whose highest frequencies have been removed.

Unless you’re an unusually sensitive listener, you probably had a difficult time distinguishing between the uncompressed audio and the MP3 with \(11\times\) smaller file size. It turns out that musical sound has two sources of redundancy that codecs can exploit in the frequency domain: perceptual redundancy and statistical redundancy.

Critical bands and masking#

The first source of redundancy is perceptual. The inner ear decomposes sound into roughly \(24\) overlapping frequency bands, called critical bands. Each band is narrow at low frequencies (about \(100\) Hz wide) and wider at high frequencies (several kHz wide), roughly in proportion to our logarithmic perception of pitch. We can emulate them with a filterbank of \(24\) band-pass filters [Zwi61]. Applying the filterbank to every frame of a spectrogram gives a much coarser representation of sound, with just \(24\) “frequencies”:

Top: 24 overlapping triangular filters on a logarithmic frequency axis from 20 Hz to 16 kHz, alternating blue and orange, each peaking at a gain of 1. The filters are evenly spaced on the log axis above about 500 Hz, and wider in proportion below. Bottom left: a spectrogram of a drum loop over 3 seconds, with frequency up to 16 kHz, showing vertical stripes for each drum hit. Bottom right: the same drum loop as a critical-band representation, with 24 rows, one per band, showing the same stripes at much coarser frequency resolution.

Fig. 123 A filterbank of \(24\) triangular filters, one per critical band (top), and a drum loop represented as a spectrogram (bottom left) and by the energy in each critical band (bottom right).#

When several frequencies coexist within the range of a critical band, our perception has limited ability to distinguish between them. Specifically, louder frequencies mask quieter ones, making them harder or impossible to hear. There are several kinds of masking.

Frequency masking. A loud tone, the masker, raises the threshold of hearing for other tones in its critical band, and to a lesser extent in neighboring bands. In each example below, a steady \(1000\) Hz masker plays, while a quieter \(1100\) Hz probe beeps three times. First, set your volume so that the masker in the first example is comfortable. That example then plays the quietest probe (\(-40\) dB) on its own, with no masker. Then, in the other examples, how many beeps can you hear?

Masker, then probe alone (−40 dB)

Masker + probe at −6 dB

Masker + probe at −20 dB

Masker + probe at −40 dB

A plot of level relative to the masker in decibels versus frequency from 300 Hz to 4 kHz on a logarithmic axis. A tall blue bar at 1 kHz is the masker, at 0 dB. A dashed gray triangle peaks about 14 dB below the masker at 1 kHz and slopes down on both sides, more steeply toward low frequencies. The region beneath it is shaded and labeled masked, inaudible. Three red dots at 1.1 kHz mark probes at minus 6, minus 20, and minus 40 dB. The first is well above the triangle, the second just above it, and the third inside the shaded region.

A \(1000\) Hz masker and a \(1100\) Hz probe, at three levels relative to the masker. On its own, the probe is audible even at \(-40\) dB. With the masker, it falls below the masking threshold (dashed, schematic).

Temporal masking. A loud sound can also mask quieter sounds that occur shortly after it ends (and, to a lesser extent, shortly before it begins). In each example below, a \(1000\) Hz masker plays for half a second, followed by a short, quiet probe at the same frequency, \(40\) dB quieter, after different gaps. In the first example, the gap is long enough that the probe should be easy to hear. Can you hear the probe in the others?

Gap of 500 ms (reference)

Gap of 200 ms

Gap of 50 ms

Gap of 5 ms

Three plots of level relative to the masker in decibels versus time in milliseconds, for gaps of 200, 50, and 5 milliseconds. In each, a tall blue rectangle, the masker, ends at 500 milliseconds. A dashed gray curve, the masking threshold, decays from about minus 15 dB at 500 milliseconds toward minus 60 dB over the next 200 milliseconds. A short red bar, the probe, at minus 40 dB, starts after each gap. After 200 milliseconds, it rises above the threshold. After 50 and 5 milliseconds, it falls below.

A \(1000\) Hz masker, followed by a \(30\) ms probe at \(-40\) dB after three gaps. The masking threshold (dashed, schematic) decays over the \(100\) to \(200\) ms after the masker ends.

The absolute threshold. Finally, recall from the equal-loudness contours that the threshold of hearing depends on frequency. Even with no masker at all, quiet sounds at frequencies where we are less sensitive are inaudible. To hear this, play the \(4000\) Hz tone below, and turn your volume down until it is barely audible. Then, without changing your volume, play the \(8000\) Hz tone, which has the same amplitude (\(-40\) dBFS). (Afterwards, remember to turn your volume back up.)

4000 Hz at −40 dBFS

8000 Hz at −40 dBFS

A plot of sound pressure level in dB SPL versus frequency from 20 Hz to 12.5 kHz on a logarithmic axis. A dashed gray curve, the threshold of hearing, falls from about 78 dB SPL at 20 Hz to a minimum near minus 6 dB SPL around 3 to 4 kHz, then rises to about 13 dB SPL at 8 kHz. The region beneath it is shaded and labeled inaudible. A blue dot at 4000 Hz sits just above the curve, labeled barely audible. A red dot at 8000 Hz sits at the same level, about 15 dB below the curve, labeled inaudible.

Two tones at the same level, against the threshold of hearing. Once the \(4000\) Hz tone is barely audible, the \(8000\) Hz tone falls about \(15\) dB below the threshold.

Important

When frequencies cannot be perceived, whether because of masking or the absolute threshold, we can remove them from the spectrum. Removing them introduces distortion, but distortion that we cannot hear.

Lossy codecs do exactly this. Below are spectrograms of a guitar recording before and after MP3 compression at \(128\) kbps. Throughout the MP3’s spectrogram, the codec has replaced quiet frequency content (mostly above \(5\) kHz) with zeros, which show up as black holes. It has also removed everything above about \(16\) kHz, where our sensitivity is lowest:

Two spectrograms of a nylon guitar riff over 4.5 seconds, with frequency up to 20 kHz and magnitude in decibels from minus 110 to 0. Left, the original, has continuous energy up to 20 kHz, with horizontal lines for the harmonics of each note and vertical stripes for each pluck. Right, the MP3 at 128 kbps, looks similar below 5 kHz, but above that it is speckled with black holes where content has been replaced with zeros, and it has no energy at all above about 16 kHz.

Fig. 124 Spectrograms of a guitar recording, original (left) and as an MP3 at \(128\) kbps (right). Black regions are zero. Recording from Freesound: 388954 by FullMetalJedi, License: CC0.#

Sparsity in frequency#

What should we do with all of these zeros? Compress them! This brings us to the second source of redundancy, which is statistical.

Example: runs of zeros. Say that we need to store strings of \(32\) bits, which we expect to contain very long runs of \(0\)s, for example,

\[\texttt{00000000000010000000000000000100}.\]

We could store each string verbatim, with \(32\) bits. Or, we could store the lengths of its runs of \(0\)s. This string consists of \(12\) zeros, a one, \(16\) zeros, a one, and a final \(2\) zeros. Every run has at most \(31\) zeros, so we can store each run length as a \(5\)-bit number:

\[12, 16, 2 \;\;\longrightarrow\;\; \texttt{01100}\;\texttt{10000}\;\texttt{00010}.\]

To decode, we read one run length at a time, write that many \(0\)s, and then write a \(1\), unless we have reached \(32\) bits. This run-length encoding stores our string in \(15\) bits instead of \(32\), less than half. But notice that it only helps if we assume \(1\)s are rare. A string like \(\texttt{0101}\ldots\texttt{01}\) has \(16\) runs, so it would take \(16 \cdot 5 = 80\) bits. Compression works by exploiting what we can anticipate about the data.

Example: sparse frequencies. Say that we need to store a collection of \(1\) second audio files, which we know to be basic sinusoids, where \(x[n] = \sin(2 \pi f_0 n \Delta t)\), each with a different frequency \(f_0\). Uncompressed, at \(44.1\) kHz and \(16\) bits, each one takes \(705{,}600\) bits (mono). Alternatively, we could define a codec:

  • Coder: estimate the frequency \(f_0\) of \(\mathbf{x}\), and store it as a \(32\)-bit floating point number.

  • Decoder: synthesize \(x[n] = \sin(2 \pi f_0 n \Delta t)\) at \(44.1\) kHz for \(1\) second.

This only requires storing a single number, \(32\) bits instead of \(705{,}600\), a compression factor of \(22{,}050\times\)! Real sounds are not single sinusoids. But many musical sounds are made of relatively few prominent frequencies (Chapter 3), and after removing the masked and inaudible frequencies, their spectra are full of zeros. The more sparse a sound is in frequency, the more it can be compressed. Lossy codecs exploit this statistical sparsity with lossless compression techniques, which we will study in the next section.

MP3 and Ogg Vorbis#

Practical lossy codecs, like MP3 (MPEG-1 Audio Layer III, standardized in the early 1990s) and Ogg Vorbis (released in 2000 by the Xiph.Org Foundation), combine these two sources of redundancy. At a high level, the coder works like this:

A block diagram of six boxes connected left to right by arrows: digital audio, time-frequency transform, psychoacoustic model, quantized spectrogram, lossless compression, and file (.mp3, .ogg). The psychoacoustic model and quantized spectrogram are labeled lossy: removes what we can't hear. Lossless compression is labeled lossless.

Fig. 125 The coder of a typical lossy codec. The decoder reverses the lossless compression, and then synthesizes audio from the quantized spectrogram.#

  1. Transform frames of the digital audio into a spectrogram-like representation (Chapter 10).

  2. Apply a psychoacoustic model, which estimates how much of each frequency in each frame is masked or inaudible.

  3. Quantize the spectrogram, with fewer bits (or zero bits) for coefficients that the psychoacoustic model deems less perceptible. This step is lossy.

  4. Losslessly compress the quantized spectrogram, and store it in a file.

The decoder reverses the process: it decompresses the quantized spectrogram, and synthesizes audio from it, much like the inverse STFT.

There are lots of minutiae. For example, both codecs use the modified discrete cosine transform (MDCT) rather than the STFT, since its coefficients are real-valued and it is critically sampled (it produces as many coefficients as samples). MP3 also exploits redundancy between the two channels of stereo audio, which are often very similar, by encoding their sum and difference (mid/side, from Chapter 13). And interestingly, the MP3 standard specifies the decoder, but not the psychoacoustic model, so different coders can make different decisions about what to remove. These details are less important than the high-level ideas, but if you’re interested, read up on MP3 and Vorbis.