import matplotlib
if not hasattr(matplotlib.RcParams, "_get"):
    matplotlib.RcParams._get = dict.get

10.4 The short-time Fourier transform

Granular synthesis showed that frame-based processing can do genuinely creative things. Now we turn to perhaps its most powerful application: the short-time Fourier transform (STFT), which reveals how a sound’s frequency content evolves over time.

Recall the limitation of the DFT: it integrates over all time, turning \(N\) samples into \(N\) bins and, in the process, discarding when each frequency occurred. But of course frequency content changes over time in music, that is what a musical melody is. How can we see those changes? The idea is exactly the frame-based recipe: slice the signal into frames and take the DFT of each one.

Definition 32 (Short-time Fourier transform)

The short-time Fourier transform of a signal \(x\) applies the DFT to each extracted frame:

\[\texttt{STFT}_k(x) = \texttt{DFT}(x_k), \qquad x_k[n] = x[k \cdot N_H + n].\]

For a signal of \(N\) samples with hop length \(N_H\) and frame length \(N_F\), the output is a complex matrix of shape \(\frac{N}{N_H} \times N_F\): one row per frame, one column per frequency bin (or \(\frac{N_F}{2}+1\) columns for real-valued audio).

Taking the magnitude of each frame and stacking the frames side by side gives a spectrogram, a two-dimensional image with time on the horizontal axis, frequency on the vertical axis, and amplitude encoded as color intensity. Because our ears perceive amplitude roughly logarithmically, we usually take the \(\log\) of the magnitude before mapping it to color. For the same reason, the frequency axis is often drawn on a log scale too: our sense of pitch is logarithmic, so an octave (a doubling of frequency) sounds like a constant step no matter where it falls, and a log axis gives every octave equal space. We will develop this logarithmic view of pitch in Chapter 15.

The spectrogram is one of the most important visualizations in all of audio. Here it is on a simple rising melody, C-D-E-F-G played as sine tones, shown three ways for comparison:

The C-D-E-F-G melody

The same rising C-D-E-F-G melody shown three ways: in symbolic form (top), as a log-frequency spectrogram (middle), and as a plain DFT of the whole signal (bottom). The DFT finds all five pitches but loses their order; the spectrogram shows each pitch at the moment it sounds, so the rising melody is unmistakable.

The plain DFT sees all five notes as five peaks but cannot tell you their order. The spectrogram shows each note stepping up in turn. That extra time axis is the whole point of the STFT.

The STFT is really just the frame-based recipe with a DFT in the middle: cut the signal into frames, and take the DFT of each one.

Fig. 70 The STFT as analysis: each frame is sent through its own DFT, and the resulting spectra, stacked side by side, form the spectrogram.

Configuring the frame length

The STFT has two key parameters, the frame length \(N_F\) and the hop length \(N_H\), and choosing them well is something of an art. Consider \(N_F\) first. What happens as we make frames longer?

The upside is better frequency resolution. Recall that the DFT bin spacing is \(\Delta f = f_s / N_F\), so longer frames pack the bins closer together and resolve nearby frequencies more finely. But this comes at a cost in time resolution: a longer frame smears a wider stretch of time into a single spectrum. In the extreme where \(N_F\) grows to the whole signal length \(N\), we are back to a single all-of-time DFT, having thrown away time entirely. This is a fundamental trade-off, and you can watch it play out by sweeping \(N_F\) through powers of two:

Fig. 71 The time-frequency resolution trade-off. At the beginning of the animation, short frames give sharp timing but coarse frequency; by the end, long frames give fine frequency detail but blur events together in time.

There is also a computational cost to longer frames, though it is a secondary consideration. A longer frame means a larger per-frame DFT (\(O(N_F \log N_F)\) under the FFT). But in practice the hop usually scales with the frame, since we tend to fix the overlap (say 50%), so a longer frame also produces fewer frames, and the two effects largely offset. We will account for the STFT’s cost more carefully when we turn to the hop length next. For choosing \(N_F\) itself, the dominant consideration is the time-frequency trade-off above.

There is no universally best \(N_F\); it depends on the application. A few rules of thumb: use a power of two for FFT efficiency, and make the frame at least one cycle of the lowest frequency you care about. The lower limit of human hearing is around \(20\) Hz, a cycle of which is \(\frac{1}{20}\) seconds or \(50\) ms, and at \(44.1\) kHz a \(4096\)-sample frame (\(\approx 93\) ms) comfortably covers it.

Configuring the hop length

The hop length \(N_H\) is a gentler knob. Unlike \(N_F\), it does not affect frequency resolution at all: the DFT of each frame is unchanged no matter how far apart the frames sit. Instead, \(N_H\) controls two things. The first is time resolution, since a smaller hop means more frames per second and a finer-grained view of how the sound changes. The second is computational cost: an STFT of \(N\) samples produces \(\frac{N}{N_H}\) frames, so halving the hop doubles the number of DFTs we must compute.

We usually express the hop as an amount of overlap, the quantity \(\frac{N_F - N_H}{N_F}\) we defined at the start of the chapter. Recall that we must keep \(N_H \le N_F\) or we will skip samples between frames. In the STFT, a common choice is \(N_H = N_F / 2\) (50% overlap), and heavy overlaps like 75% (\(N_H = N_F/4\)) are typical when reconstruction quality matters.

Windowing revisited

We can now settle the question we deferred earlier: why bother with smooth windows? The answer is spectral leakage, which we studied in Chapter 8. Extracting a frame multiplies the signal by a window, and by the convolution theorem this convolves the signal’s spectrum with the window’s spectrum, smearing each sharp spectral line into a blur. A plain (rectangular) frame has a sinc spectrum with tall side lobes, so it leaks energy far and wide, whereas a Hann window concentrates energy in a narrow central lobe and leaks far less. We saw the side-by-side spectra of the two windows in Chapter 8.

Because every STFT frame is windowed, this leakage is present in every spectrogram, and it is worse than in a plain DFT because each frame is shorter. The effect is plainly visible in the spectrogram itself, where a rectangular window’s leakage shows up as vertical smearing that a Hann window mitigates:

Fig. 72 Log-frequency spectrograms of the running example with a rectangular window (top) and a Hann window (bottom). The Hann window’s reduced leakage yields a noticeably cleaner picture.

This is also why granular synthesis windowed each grain: the same smoothing that reduces spectral leakage also removes the audible clicks at grain edges. In the STFT, where we window every frame repeatedly, it is especially important.

Spectral analysis

The spectrogram is a powerful analysis tool. Suppose we are handed the C-D-E-F-G recording from earlier and asked which pitches it contains and when. We can march through the STFT frame by frame, find the loudest frequency in each frame whose energy exceeds some threshold, round it to the nearest musical pitch, and emit a note whenever the detected pitch changes. This turns a pq.Audio into a pq.Score, a crude form of music transcription:

# hide
from typing import Iterator
import numpy as np
import pyquist as pq


def iter_frames(audio: pq.Audio, N_H: int, N_F: int) -> Iterator[np.ndarray]:
    for start in range(0, len(audio) - N_F + 1, N_H):
        yield audio.samples[start:start + N_F]


def overlap_add(frames: np.ndarray, N_H: int, sample_rate: int) -> pq.Audio:
    num_frames, N_F, num_channels = frames.shape
    out = np.zeros((N_H * (num_frames - 1) + N_F, num_channels), dtype=frames.dtype)
    for k, frame in enumerate(frames):
        out[k * N_H:k * N_H + N_F] += frame
    return pq.Audio(out, sample_rate)

from pyquist.helper import frequency_to_pitch

# A tiny monophonic transcriber: for each frame, find the loudest frequency,
# round it to the nearest musical pitch, and emit a note when the pitch changes.
audio = pq.Audio.from_file("./assets/audio-melody.wav")
pq.play(audio)                                   # hear the melody we will transcribe
sr = audio.sample_rate
N_F, N_H = 4096, 1024

# One magnitude spectrum per frame: window each frame, then take its DFT.
frames = np.array(list(iter_frames(audio, N_H, N_F)))[:, :, 0]   # (num_frames, N_F), mono
S = np.abs(np.fft.rfft(frames * np.hanning(N_F), axis=1))
freqs = np.fft.rfftfreq(N_F, 1 / sr)
seconds_per_frame = N_H / sr
threshold = 0.05 * S.max()

events, current, onset = [], None, 0.0
for k in range(len(S)):
    if S[k].max() < threshold:                   # silence
        pitch = None
    else:
        pitch = int(round(frequency_to_pitch(freqs[np.argmax(S[k])])))
    if pitch != current:                         # the note changed
        if current is not None:
            events.append((onset, {"pitch": current, "duration": k * seconds_per_frame - onset}))
        current, onset = pitch, k * seconds_per_frame
if current is not None:                          # flush the final note
    events.append((onset, {"pitch": current, "duration": len(S) * seconds_per_frame - onset}))

score = pq.Score(events)
for event in score:
    print(f"t = {event.time:4.2f}s   MIDI pitch {event.kwargs['pitch']}")

t = 0.00s   MIDI pitch 60
t = 0.46s   MIDI pitch 62
t = 0.98s   MIDI pitch 64
t = 1.46s   MIDI pitch 65
t = 1.97s   MIDI pitch 67

Transcription in general is a hard problem, especially for polyphonic music where many notes sound at once, but this simple peak-picking approach works well enough for clean, monophonic input like our sine melody.