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}