Skip to main content

qualia_audio/features/multipitch/
multi_melodia.rs

1//! Multi-voice pitch-contour tracking (polyphonic extension of Melodia).
2//!
3//! Melodia's mono predominant-melody stage collapses each frame to a single F0
4//! and threads it through time. Polyphonic material has several concurrent
5//! lines, so this tracker takes the **per-frame multi-pitch estimates** (e.g.
6//! from [`super::multipitch_klapuri`], one row of F0s per analysis frame) and
7//! threads them into up to `n_voices` continuous pitch tracks by nearest-pitch
8//! continuity — the many-voices analogue of contour tracking.
9//!
10//! EPISTEMIC RULE (declared): the tracks are **proposals**. The **max-polyphony
11//! assumption** is explicit in `n_voices`: at most that many concurrent lines
12//! are posited, and when a frame offers more estimates than free voices the
13//! surplus is dropped rather than forced onto an unrelated voice. A voice with
14//! no matching estimate in a frame **abstains** for that frame (`0.0`), and is
15//! freed after [`MAX_GAP`] silent frames so a genuinely new line can reuse the
16//! slot. Zero input estimates → zero tracks.
17//!
18//! Zero-heap hot path: all per-voice / per-estimate state lives in fixed stack
19//! arrays bounded by [`MAX_VOICES`] / [`MAX_ESTIMATES`]; the caller owns the
20//! `frame_f0` input and the `out_tracks` output. Nothing is allocated.
21
22use crate::types::AudioError;
23
24/// Upper bound on concurrent voices (stack-array sizing).
25pub const MAX_VOICES: usize = 16;
26/// Upper bound on per-frame F0 estimates (stack-array sizing).
27pub const MAX_ESTIMATES: usize = 16;
28/// Consecutive unmatched frames after which a voice is freed for reuse.
29pub const MAX_GAP: usize = 3;
30
31/// Pitch distance in semitones between two positive frequencies.
32#[inline]
33fn semitone_distance(a: f32, b: f32) -> f32 {
34    12.0 * (a / b).log2().abs()
35}
36
37/// Track multiple concurrent pitch contours across frames.
38///
39/// - `frame_f0`: row-major `n_frames × max_per_frame` buffer of per-frame F0
40///   estimates in Hz; a `0.0` (or non-finite) slot means "no estimate". Rows
41///   need not be sorted, and estimates may appear in any column order from frame
42///   to frame — continuity is resolved by pitch, not by column.
43/// - `n_frames` / `max_per_frame`: shape of `frame_f0`.
44/// - `n_voices`: **declared** maximum number of concurrent voices to track
45///   (`1..=MAX_VOICES`).
46/// - `max_jump_semitones`: the largest pitch step (semitones) an estimate may be
47///   from a voice's last pitch and still continue that voice.
48/// - `out_tracks`: row-major `n_voices × n_frames` buffer; `out_tracks[v *
49///   n_frames + f]` is voice `v`'s F0 at frame `f`, or `0.0` where the voice is
50///   inactive/abstaining. Cleared on entry.
51///
52/// Returns the number of voices that were assigned at least one estimate.
53///
54/// # Errors
55/// - [`AudioError::InvalidParameter`] if `n_voices` is `0` or `> MAX_VOICES`,
56///   `max_per_frame > MAX_ESTIMATES`, `max_jump_semitones` is not positive
57///   finite, or `frame_f0.len() < n_frames * max_per_frame`.
58/// - [`AudioError::OutputBufferTooSmall`] if `out_tracks.len() < n_voices *
59///   n_frames`.
60pub fn track_multi_pitch(
61    frame_f0: &[f32],
62    n_frames: usize,
63    max_per_frame: usize,
64    n_voices: usize,
65    max_jump_semitones: f32,
66    out_tracks: &mut [f32],
67) -> Result<usize, AudioError> {
68    if n_voices == 0
69        || n_voices > MAX_VOICES
70        || max_per_frame > MAX_ESTIMATES
71        || !(max_jump_semitones.is_finite() && max_jump_semitones > 0.0)
72        || frame_f0.len() < n_frames.saturating_mul(max_per_frame)
73    {
74        return Err(AudioError::InvalidParameter);
75    }
76    if out_tracks.len() < n_voices.saturating_mul(n_frames) {
77        return Err(AudioError::OutputBufferTooSmall);
78    }
79    for v in out_tracks.iter_mut().take(n_voices * n_frames) {
80        *v = 0.0;
81    }
82    if n_frames == 0 || max_per_frame == 0 {
83        return Ok(0);
84    }
85
86    // Per-voice state: last pitch (0 = free), silent-gap counter, ever-used flag.
87    let mut last_f0 = [0.0f32; MAX_VOICES];
88    let mut gap = [0usize; MAX_VOICES];
89    let mut ever_used = [false; MAX_VOICES];
90
91    for f in 0..n_frames {
92        let row = f * max_per_frame;
93
94        // Gather this frame's valid estimates.
95        let mut est = [0.0f32; MAX_ESTIMATES];
96        let mut est_taken = [false; MAX_ESTIMATES];
97        let mut ne = 0usize;
98        for c in 0..max_per_frame {
99            let v = frame_f0[row + c];
100            if v.is_finite() && v > 0.0 {
101                est[ne] = v;
102                ne += 1;
103            }
104        }
105
106        let mut v_assigned = [false; MAX_VOICES];
107
108        // (1) Greedily continue active voices: repeatedly bind the globally
109        // closest (estimate, active-voice) pair within the jump limit.
110        loop {
111            let mut best_d = max_jump_semitones;
112            let mut best_e = usize::MAX;
113            let mut best_v = usize::MAX;
114            for e in 0..ne {
115                if est_taken[e] {
116                    continue;
117                }
118                for v in 0..n_voices {
119                    if v_assigned[v] || last_f0[v] <= 0.0 {
120                        continue;
121                    }
122                    let d = semitone_distance(est[e], last_f0[v]);
123                    if d <= best_d {
124                        best_d = d;
125                        best_e = e;
126                        best_v = v;
127                    }
128                }
129            }
130            if best_e == usize::MAX {
131                break;
132            }
133            out_tracks[best_v * n_frames + f] = est[best_e];
134            last_f0[best_v] = est[best_e];
135            gap[best_v] = 0;
136            ever_used[best_v] = true;
137            est_taken[best_e] = true;
138            v_assigned[best_v] = true;
139        }
140
141        // (2) Unmatched estimates start new voices (if a free slot exists).
142        for e in 0..ne {
143            if est_taken[e] {
144                continue;
145            }
146            let mut slot = usize::MAX;
147            for v in 0..n_voices {
148                if !v_assigned[v] && last_f0[v] <= 0.0 {
149                    slot = v;
150                    break;
151                }
152            }
153            if slot == usize::MAX {
154                continue; // more sources than declared voices → drop the surplus
155            }
156            out_tracks[slot * n_frames + f] = est[e];
157            last_f0[slot] = est[e];
158            gap[slot] = 0;
159            ever_used[slot] = true;
160            est_taken[e] = true;
161            v_assigned[slot] = true;
162        }
163
164        // (3) Active voices with no estimate abstain this frame; free after a gap.
165        for v in 0..n_voices {
166            if !v_assigned[v] && last_f0[v] > 0.0 {
167                gap[v] += 1;
168                if gap[v] > MAX_GAP {
169                    last_f0[v] = 0.0;
170                    gap[v] = 0;
171                }
172            }
173        }
174    }
175
176    let n_active = ever_used.iter().take(n_voices).filter(|&&u| u).count();
177    Ok(n_active)
178}
179
180#[cfg(test)]
181mod tests {
182    use super::*;
183
184    fn semitone_err(a: f32, b: f32) -> f32 {
185        12.0 * (a / b).log2().abs()
186    }
187
188    /// GOLDEN: two concurrent lines — a rising ~440→466 Hz voice and a steady
189    /// ~660 Hz voice — presented with the two estimates in *different column
190    /// order* each frame. The tracker recovers two continuous voices, correctly
191    /// separated by pitch continuity rather than by column.
192    #[test]
193    fn tracks_two_concurrent_voices() {
194        // frame layout (max_per_frame = 2), deliberately column-swapped:
195        //   f0: [440, 660]
196        //   f1: [660, 440]   (swapped)
197        //   f2: [466, 662]
198        let frame_f0 = [
199            440.0f32, 660.0, //
200            660.0, 440.0, //
201            466.0, 662.0, //
202        ];
203        let n_frames = 3;
204        let mut out = [0.0f32; 4 * 3];
205        let n = track_multi_pitch(&frame_f0, n_frames, 2, 4, 2.0, &mut out).expect("track");
206
207        assert_eq!(n, 2, "two concurrent lines → two voices");
208
209        // Voice 0 was seeded at 440 (frame 0 col 0), voice 1 at 660.
210        let v0 = &out[0..3];
211        let v1 = &out[3..6];
212        assert!(semitone_err(v0[0], 440.0) < 0.5, "v0f0={}", v0[0]);
213        assert!(semitone_err(v0[1], 440.0) < 0.5, "v0f1={}", v0[1]);
214        assert!(semitone_err(v0[2], 466.0) < 0.5, "v0f2={}", v0[2]);
215        assert!(semitone_err(v1[0], 660.0) < 0.5, "v1f0={}", v1[0]);
216        assert!(semitone_err(v1[1], 660.0) < 0.5, "v1f1={}", v1[1]);
217        assert!(semitone_err(v1[2], 662.0) < 0.5, "v1f2={}", v1[2]);
218
219        // Within-track pitch jumps never exceed the declared limit.
220        assert!(semitone_err(v0[1], v0[0]) <= 2.0);
221        assert!(semitone_err(v0[2], v0[1]) <= 2.0);
222    }
223
224    /// A single continuous line uses exactly one voice; a mid-line gap shorter
225    /// than MAX_GAP is tolerated and the voice resumes on the same slot.
226    #[test]
227    fn single_voice_tolerates_short_gap() {
228        // 440 → (gap) → 440 over three frames, one estimate per frame.
229        let frame_f0 = [440.0f32, 0.0, 442.0];
230        let mut out = [0.0f32; 2 * 3];
231        let n = track_multi_pitch(&frame_f0, 3, 1, 2, 2.0, &mut out).expect("track");
232        assert_eq!(n, 1, "one line → one voice across the gap");
233        assert!(semitone_err(out[0], 440.0) < 0.5);
234        assert_eq!(out[1], 0.0, "abstains during the gap frame");
235        assert!(
236            semitone_err(out[2], 442.0) < 0.5,
237            "resumes on the same voice"
238        );
239    }
240
241    /// More sources than declared voices → the surplus is dropped, not forced
242    /// onto an unrelated voice (max-polyphony assumption honoured).
243    #[test]
244    fn drops_surplus_beyond_declared_voices() {
245        let frame_f0 = [440.0f32, 660.0]; // two sources, one frame
246        let mut out = [0.0f32; 1 * 1];
247        let n = track_multi_pitch(&frame_f0, 1, 2, 1, 2.0, &mut out).expect("track");
248        assert_eq!(n, 1, "only one voice allowed");
249        assert!(
250            semitone_err(out[0], 440.0) < 0.5,
251            "keeps the first-listed source"
252        );
253    }
254
255    /// No estimates anywhere → no voices.
256    #[test]
257    fn all_silent_no_voices() {
258        let frame_f0 = [0.0f32; 6];
259        let mut out = [9.0f32; 3 * 2];
260        let n = track_multi_pitch(&frame_f0, 2, 3, 3, 2.0, &mut out).expect("track");
261        assert_eq!(n, 0);
262        assert!(
263            out.iter().all(|&v| v == 0.0),
264            "output cleared to abstention"
265        );
266    }
267
268    #[test]
269    fn rejects_bad_params() {
270        let f = [440.0f32];
271        let mut out = [0.0f32; 4];
272        assert_eq!(
273            track_multi_pitch(&f, 1, 1, 0, 2.0, &mut out),
274            Err(AudioError::InvalidParameter)
275        );
276        assert_eq!(
277            track_multi_pitch(&f, 1, 1, MAX_VOICES + 1, 2.0, &mut out),
278            Err(AudioError::InvalidParameter)
279        );
280        assert_eq!(
281            track_multi_pitch(&f, 1, 1, 2, 0.0, &mut out),
282            Err(AudioError::InvalidParameter)
283        );
284    }
285
286    #[test]
287    fn rejects_small_output() {
288        let f = [440.0f32, 0.0];
289        let mut out = [0.0f32; 1]; // needs n_voices * n_frames = 2 * 2 = 4
290        assert_eq!(
291            track_multi_pitch(&f, 2, 1, 2, 2.0, &mut out),
292            Err(AudioError::OutputBufferTooSmall)
293        );
294    }
295}