Pitch shifting and time stretching

Play a record at the wrong speed and two things change at once: the music gets faster, and it gets higher. A sampler (a synthesiser that plays back recordings) relies on exactly that, to get every note on the keyboard from one recording. But very often we want only one of the two: a podcast at 1.5× speed without the squeaky voices, a song in a different key at the same tempo, or a singer’s flat note nudged up without the note getting shorter.

This page starts with the sampler, and with why speeding up a recording also changes the character of a voice. Then it builds up, one method at a time, to changing the duration and the pitch independently. It leans on three earlier pages:

• Changing the sample rate, for reading a recording at any speed.
• Pitch detection, for finding the cycles of a voice.
• The Fourier transform, for the phase vocoder’s spinning arrows.

Every figure can use your own voice. Record a few seconds here, ideally with a note or two held steady, and choose your recording in any figure.

A semitone is the step between neighbouring keys on a piano. Twelve of them make an octave, which doubles the frequency, so one semitone multiplies it by $2^{1/12} \approx 1.0595$. To play a stored note $n$ semitones higher, a sampler reads through the recording faster, by a factor of

Up 7 semitones (a fifth), it moves on 1.498 stored samples for every sample it outputs. It keeps a running position, the phase accumulator, which usually lands between two stored samples:

position = 0.0
for each output sample:
    output = read_between_samples(stored, position)
    position += r          # may change on every sample: bends, vibrato, glides

How to read_between_samples is the whole question, and it’s the question of the resampling page, with one twist: the ratio isn’t fixed. A pitch bend or vibrato changes it on every output sample. The answer from that page’s polyphase section still works, though. A table of finely spaced sub-filters lets each output sample pick the one for its own fractional position, whatever the ratio.

Two different things go wrong, depending on the direction:

• Pitching up is decimating. Reading twice as fast doubles every frequency in the recording. Harmonics that end up above the output’s Nyquist frequency (half its sample rate, 22.05 kHz here) can’t be represented, and fold back down as aliases. That’s why they move downwards as the pitch rises. A straight line between samples does nothing to stop them, so the windowed sinc lowers its cutoff in step with the pitch: at +12 semitones it cuts off at half the usual frequency, which takes a filter twice as long, and twice the work per sample.
• Pitching down is interpolating. The output needs samples between the stored ones, and a staircase or straight lines leave the spectral images from the resampling page’s zero-stuffing section. They’re heard as a metallic fizz on low notes.

For both notes, the sinc keeps both below −98 dB at every setting of the slider. On the sparse tone, drop-sample never does better than −10 dB, and linear never better than −16 dB. Even on the dense note, they never get past −33 and −42 dB. Real samplers also have cheaper tricks. A multisample library records a note every few semitones, so nothing is pitched far. Copies of a sound can be stored already filtered, an octave apart, like the band-limited wavetables on the sampling page, and the player picks one by pitch. Some early samplers avoided the maths altogether by giving each voice its own converter, running at a variable clock rate.

Speeding a recording up raises its pitch, but it also does two other things.

The sound gets shorter. That’s harmless for a single synth note. It’s not acceptable for a melody, whose rhythm changes, or for a song, whose tempo changes.

A voice changes character. Your voice starts as a buzz from the vocal folds, rich in harmonics. It then passes through the throat, mouth and nose, which resonate at a few frequencies set by their shape: the formants. The formants are what make an “ah” an “ah” and an “oo” an “oo”, and they’re part of what makes a voice sound like a particular person. They depend on the shape of the vocal tract, not on the pitch. Sing “ah” on a low note and a high note, and the harmonics move but the formants stay. Speed the recording up, though, and everything moves.

This is why sample libraries for pianos and voices record nearly every note rather than stretching a few, and it sets the plan for the rest of the page. Suppose we can make a sound longer without changing its pitch. Then we can shift the pitch without changing the length, in two steps:

So the next four sections are about time stretching. Formants are dealt with in sections 5 and 7.

Here’s the simplest possible idea. Cut the sound into short pieces, called grains. To make it 1.5 times longer, lay them down 1.5 times further apart. Each grain is a perfectly good copy of a short stretch of the original, with its own pitch, so the pitch should be unchanged.

The grains are cut every $H_a$ samples from the input (the analysis hop), and laid down every $H_s = H_a \times \text{stretch}$ samples in the output (the synthesis hop).

Done literally, with grains butted end to end, every join is a jump in the waveform, and jumps click. The fix is the one used on the FIR and MP3 pages: windows. Each grain fades in and out with a Hann window, and grains overlap by half, so that the windows add up to exactly 1 and each join is a crossfade. That’s overlap-add (OLA).

To judge the result, the figures from here on use a measure that only works on a steady sound whose contents we know exactly. The sung “ah” contains only the harmonics of D3, plus a little breath noise. The chord contains only the harmonics of its three notes. A perfect stretch would still contain exactly those frequencies, so energy anywhere else is damage. The readout gives that energy relative to the energy at the notes. The original “ah” measures −28.6 dB, which is its breath noise. The chord measures −102.7 dB.

The trouble is that the grains are cut at arbitrary points in the waveform’s cycle. In the original, the grain that followed this one started exactly one hop later, so its cycles continued seamlessly. After stretching, the next grain is cut from a point that’s further on in the input but laid down at a point that isn’t. So its cycles start partway through, out of step with what’s already there.

The fix: don’t cut each grain from exactly where the timetable says. Look nearby (within a few milliseconds) for the place where the input looks most like what should come next, and cut it from there instead.

What should come next is easy to say. It’s whatever followed the previous grain in the input, its natural continuation, because that’s what would join on seamlessly. So, for every candidate position in the search range, compare the candidate with the natural continuation by multiplying them sample by sample and adding up: the correlation from the Fourier page, and the same idea as autocorrelation pitch detection. Then take the best match. This is WSOLA, waveform-similarity overlap-add.

WSOLA and its relatives are simple, cheap and good for speech and single instruments, which makes them a common choice for playing speech faster or slower. For chords and full mixes, we need something that can treat each frequency separately. That’s the phase vocoder, in section 6. First, though, there’s a way to use the grain idea to change the pitch directly, and keep the formants where they are.

A voiced sound is a series of pulses: each puff of air through the vocal folds sets the vocal tract ringing, and the ring dies away before (or soon after) the next puff. The ring’s shape is the formants. The spacing of the puffs is the pitch.

So, cut the voice into grains one pulse at a time. Each grain is two periods long, centred on a pulse, with a Hann window, so it holds one complete ring. Then:

• Lay the grains down closer together, and there are more pulses per second: the pitch goes up. Further apart, and it goes down.
• Each grain keeps its own shape, so the ring and its resonances are untouched: the formants stay put.
• To change the duration, use some grains twice, or skip some, while keeping the new spacing.

That’s PSOLA, pitch-synchronous overlap-add. It needs to know where every pulse is: the pitch marks. They come from the pitch detection page. YIN’s pitch track says how long each period is. The first mark of a voiced stretch goes on the biggest peak of its first cycle. Each later mark goes about one period on, wherever the cycle around it best matches the cycle around the previous mark (searching a quarter of a period either way). That keeps every mark at the same point of its cycle, even when the peaks are flat or there are two of similar height. Where the sound is unvoiced (“s”, breath), there are no pulses, and the grains are just copied at a fixed 10 ms spacing.

PSOLA has been a standard voice tool since the late 1980s, when it was developed for speech synthesis. Its weaknesses come from its assumptions:

• It needs one clear pitch, so it can’t handle chords.
• A misplaced pitch mark gives a rough, jittery sound, which makes it only as good as the pitch detection.
• Copying the same noise grains to stretch an “s” can leave a faint buzz at the copying rate.
• Very large shifts sound unnatural, because a real voice’s pulses also change shape with pitch.

Try your own voice. A clearly voiced, steady recording works best.

The phase vocoder works on the spectrum instead of on the waveform. Cut the sound into short, overlapping, windowed frames, as before, and take the FFT of each. That’s a short-time Fourier transform (STFT), and it’s what a spectrogram shows. Here, frames are 2048 samples (46 ms) long, every 256 samples.

Each FFT bin is a spinning arrow: its length is how much of that frequency is in the frame, and its angle (phase) is where that sinusoid is in its cycle. To stretch, rebuild the sound from the frames laid down further apart: inverse FFT each one, window it again, and overlap-add.

Step 1 of the figure further down does exactly that, and the result is a mess: +6.1 dB away from the harmonics on the “ah”. Each frame’s arrows are at the angles they had in the input, and the input moved on by one analysis hop between frames. The output moves on by a longer hop, so every sinusoid has turned too little for the time that has passed, and the joins don’t fit. It’s the same problem OLA had, now one frequency at a time. The fix is to work out how far each arrow should turn over the longer hop. That needs each component’s true frequency, and the bins don’t give it directly.

FFT bins are $f_s/N$ apart: 21.5 Hz here. A sinusoid at 1050 Hz falls between bins 48 (1033.6 Hz) and 49 (1055.1 Hz). Its magnitude shows up in both, and the magnitude alone can’t say exactly where it is. The phase can. Between two frames $H$ samples apart, a sinusoid at exactly a bin’s centre frequency would turn that bin’s arrow by a predictable angle. A sinusoid slightly off-centre turns it by a little more or a little less, and the difference gives its true frequency:

where $f_k$ is the bin’s centre frequency, and $\Delta\phi$ is how much further the arrow turned than $f_k$ alone would have turned it (brought into the range −180° to +180°).

The catch is in “brought into the range”. An angle can’t tell one turn from two, so a bin only gives the right answer if its arrow’s extra turn is less than half a cycle either way. The further a bin is from the true frequency, and the longer the hop, the bigger that extra turn. It’s aliasing again, this time of the phase. That’s why phase vocoders use hops of a quarter of a frame or less: here, an eighth.

Now each output frame can get the right phases. Each bin’s arrow is advanced from where it was in the previous output frame by its true frequency × the synthesis hop. Every component then keeps turning at its own speed across the joins. That’s step 2.

Plain propagation has two known artefacts. Bins near the same peak are each advanced on their own, so they drift out of their original relationship, which sounds “phasey” and distant. And a sharp attack, a drum hit, is spread across the frames that contain it. Phase locking (Laroche and Dolson, 1999) fixes part of this. Only the bins at spectral peaks are advanced on their own, and the bins around each peak keep the same phase offsets from it that they had in the input. That’s step 3.

Commercial time-stretchers combine these ideas. A common approach is to detect attacks and treat them separately: reset the phases there, or copy the attack across unstretched. Others mix in WSOLA-style alignment.

The phase vocoder stretches without changing pitch, so with a resampler after it, it shifts pitch without changing duration, as planned in section 2. But resampling still moves the formants, so on its own this gives the chipmunk again, just at the right length.

The fix works one frame at a time. Split each frame’s spectrum into two parts. The envelope is the smooth shape, and is the formants. The fine structure is the harmonics. Then reshape the envelope before resampling, so that the resampling moves it back to where it belongs.

The cepstrum separates the two. Keeping only its low-quefrency end (liftering) gives the envelope. One refinement turned out to matter. A plain cepstral envelope follows the average of the log spectrum, and that includes the noise in the valleys between harmonics. On the “ah”, it dragged the envelope down to a flat line above about 1.5 kHz. So, first, each point of the log spectrum is raised to the highest value within half a harmonic spacing either side. That fills in the valleys, and the smoothed envelope then runs along the tops of the harmonics, which is where the formants really are. (The “true envelope” method in the further reading does this more carefully.)

If the envelope is $E(f)$ and the pitch is to be shifted by $p$, every frequency is about to be multiplied by $p$. To end up with the formants moved by $q$ instead (with $q = 1$ to keep them in place), each frame’s spectrum is multiplied by $E(fp/q) \,/\, E(f)$ before resampling.

The same split, a smooth filter and a source of buzz or hiss, is the basis of how phones code speech. The voice-coder page (coming next) will find the envelope a different way, with linear prediction.

Pitch correction puts the pitch detection page and this one together:

1. Detect the pitch (YIN).
2. Work out how far each moment is from the nearest note.
3. Shift it there (PSOLA).

The retune speed sets how quickly the correction catches up. Slow, and the singer’s scoops into notes and natural vibrato survive. Instant, and every slide snaps from note to note. That’s the robotic, stepped effect heard on Cher’s “Believe” (1998), which made the Auto-Tune plug-in famous.

The same building blocks show up in many places:

• Harmonisers add shifted copies of a voice, a third or a fifth above.
• Key lock on a DJ mixer keeps a track’s pitch while its tempo is changed to match another.
• Speed controls in podcast and video players keep voices natural at 1.5× or 2×.
• Voice changers move formants on their own, to change apparent age or size.

Which method to use is a trade-off:

• A sampler reads a stored sound faster or slower, by $r = 2^{n/12}$ for $n$ semitones. Reading between samples is a resampling problem. A windowed sinc whose cutoff follows the pitch keeps aliases (pitching up) and images (pitching down) below −98 dB, where drop-sample and linear interpolation never do better than −33 and −42 dB, or −10 and −16 dB on a tone with sparse, loud harmonics.
• Resampling also changes the duration, and moves the formants (the chipmunk voice). The plan: stretch the duration without changing the pitch, then resample.
• OLA stretches by spacing out windowed grains, but misaligned cycles partly cancel. WSOLA searches for the best-matching position, which is good for one voice and poor for chords.
• PSOLA uses one grain per pitch period, re-spaced: pitch and duration change separately, and the formants stay put. It needs good pitch marks.
• The phase vocoder measures each bin’s true frequency from its phase advance, and advances it over the new hop. It handles chords. Phase locking reduces phasiness and smearing.
• Formant preservation reshapes each frame’s envelope (from the cepstrum) before resampling. Pitch correction combines detection, snapping to notes, and PSOLA.

• J. L. Flanagan and R. M. Golden, “Phase vocoder”, Bell System Technical Journal 45 (1966): where it started.
• E. Moulines and F. Charpentier, “Pitch-synchronous waveform processing techniques for text-to-speech synthesis using diphones”, Speech Communication 9 (1990): PSOLA.
• W. Verhelst and M. Roelands, “An overlap-add technique based on waveform similarity (WSOLA) for high quality time-scale modification of speech”, ICASSP 1993.
• J. Laroche and M. Dolson, “Improved phase vocoder time-scale modification of audio”, IEEE Transactions on Speech and Audio Processing 7 (1999): phase locking.
• A. Röbel and X. Rodet, “Efficient spectral envelope estimation and its application to pitch shifting and envelope preservation”, DAFx 2005: the “true envelope”.
• J. O. Smith, Digital Audio Resampling Home Page (online): the sinc-table interpolation used by the sampler in section 1.