10.1 Reassembly with overlap-add

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

10.1 Reassembly with overlap-add#

Reassembling frames into a signal is similarly straightforward. Given frames \(x_k\) extracted at hop length \(N_H\), we reconstruct an estimate \(\hat{x}\) by adding each frame back at its original position:

Definition 28 (Overlap-add)

The overlap-add reconstruction of frames \(x_k\) at hop length \(N_H\) is

\[\hat{x}[n] = \sum_{k} x_k[n - k \cdot N_H].\]

Under what conditions does this round trip give perfect reconstruction, meaning \(\hat{x} = x\)? It depends entirely on the overlap, which we can see by tracking how many frames cover each sample:

Three panels showing the total coverage of each sample after overlap-add. Left, N_H equals N_F: coverage is a flat line at one, perfect reconstruction. Middle, N_H greater than N_F: coverage drops to zero in the gaps between frames, so samples are lost. Right, N_H less than N_F: coverage rises to two where frames overlap, doubling the amplitude.

Fig. 62 How overlap-add reconstructs, as a function of hop length. Only \(N_H = N_F\) covers every sample exactly once (perfect reconstruction). Larger hops leave gaps; smaller hops double-count the overlaps, changing the amplitude.#

  1. When \(N_H = N_F\) (no overlap), the frames tile the signal exactly once, and \(\hat{x} = x\). Perfect reconstruction.

  2. When \(N_H > N_F\), there are gaps between frames, and the samples that fall in them are simply lost.

  3. When \(N_H < N_F\), the frames overlap, and the overlapping samples get added together more than once, boosting the amplitude.

Both building blocks are only a few lines of code. Extraction walks the signal in hops, yielding one \(N_F\)-sample frame at a time and stopping once fewer than a full frame remains:

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]

Overlap-add takes the frames stacked into a single array and walks back the other way, adding each one into an output buffer at its hop position:

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)

The full runnable versions are in code/frames.py. You can hear perfect reconstruction (and break it) by playing with \(N_H\) and \(N_F\) yourself below:

Hide setup

 
# collapse
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)

# Extract frames and glue them back together. With a rectangular window and
# N_H = N_F (0% overlap) this is perfect reconstruction. Try N_H = N_F // 2
# (overlap, doubles the amplitude) or N_H = 2 * N_F (gaps) and listen!
audio = pq.Audio.from_file("./assets/audio-trio.wav")
N_F = 1024        # frame length (samples)
N_H = 1024        # hop length  (samples)

frames = np.array(list(iter_frames(audio, N_H, N_F)))
print(frames.shape)                                   # (num_frames, N_F, num_channels)
reconstructed = overlap_add(frames, N_H, audio.sample_rate)
pq.play(reconstructed)

(344, 1024, 1)