qualia_audio/features/contours/contour_tracking.rs
1//! Streaming pitch-contour tracker: connect per-frame salience peaks across time.
2//!
3//! Given the salient pitch candidates of each frame (as bin positions on the
4//! logarithmic salience grid), link candidates in consecutive frames that stay
5//! within a pitch-continuity tolerance into **contours** — time-connected pitch
6//! trajectories. This is the streaming stage before predominant-melody selection
7//! (`melodia`/`predominant`).
8//!
9//! Assignment is greedy one-to-one nearest-neighbour: each candidate in frame `f`
10//! extends the closest still-unclaimed contour from frame `f-1` within
11//! `pitch_tol_bins`; otherwise it begins a new contour. Peaks are processed in
12//! the order given (callers should pass them salience-descending so the strongest
13//! candidate claims first).
14//!
15//! EPISTEMIC NOTE: contours are *proposals* about pitch continuity; several
16//! coexist in polyphony. No melody is chosen here.
17//!
18//! Zero-heap hot path: the per-frame candidate bins live in a caller-owned
19//! flat buffer, and the contour id of each candidate is derived by scanning the
20//! previous frame's already-written ids — no per-call allocation.
21
22use crate::types::AudioError;
23
24/// A candidate slot that has not been assigned to a contour.
25const NO_CONTOUR: i32 = -1;
26
27/// Link per-frame salience peaks into time-continuous pitch contours.
28///
29/// `peak_bins` is a flat row-major buffer of shape `n_frames × max_peaks_per_frame`
30/// (`peak_bins[f * max_peaks_per_frame + k]`), holding the bin position of the
31/// `k`-th candidate in frame `f`; `peak_count[f]` gives how many of that frame's
32/// `max_peaks_per_frame` slots are valid (candidates occupy slots `0..count`).
33///
34/// Writes one contour id per candidate slot into `out_contour_id` (same layout as
35/// `peak_bins`): candidates sharing an id form one contour; unused slots are set
36/// to `NO_CONTOUR` (`-1`). Two candidates in consecutive frames whose bins
37/// differ by at most `pitch_tol_bins` may join the same contour.
38///
39/// Returns the number of distinct contours created.
40///
41/// # Errors
42/// - [`AudioError::InvalidParameter`] if `max_peaks_per_frame == 0`,
43/// `pitch_tol_bins` is not a finite non-negative value, or a `peak_count[f]`
44/// exceeds `max_peaks_per_frame`.
45/// - [`AudioError::OutputBufferTooSmall`] if either flat buffer is shorter than
46/// `n_frames * max_peaks_per_frame`.
47pub fn track_contours(
48 peak_bins: &[f32],
49 peak_count: &[usize],
50 n_frames: usize,
51 max_peaks_per_frame: usize,
52 pitch_tol_bins: f32,
53 out_contour_id: &mut [i32],
54) -> Result<usize, AudioError> {
55 if max_peaks_per_frame == 0
56 || !pitch_tol_bins.is_finite()
57 || pitch_tol_bins < 0.0
58 || peak_count.len() < n_frames
59 {
60 return Err(AudioError::InvalidParameter);
61 }
62 let need = n_frames.saturating_mul(max_peaks_per_frame);
63 if peak_bins.len() < need || out_contour_id.len() < need {
64 return Err(AudioError::OutputBufferTooSmall);
65 }
66 for id in out_contour_id.iter_mut().take(need) {
67 *id = NO_CONTOUR;
68 }
69 if n_frames == 0 {
70 return Ok(0);
71 }
72
73 let mut next_id: i32 = 0;
74 let base = |f: usize| f * max_peaks_per_frame;
75
76 for f in 0..n_frames {
77 let count = peak_count[f];
78 if count > max_peaks_per_frame {
79 return Err(AudioError::InvalidParameter);
80 }
81 let row = base(f);
82
83 if f == 0 {
84 for k in 0..count {
85 out_contour_id[row + k] = next_id;
86 next_id += 1;
87 }
88 continue;
89 }
90
91 let prev = base(f - 1);
92 let prev_count = peak_count[f - 1];
93 for k in 0..count {
94 let b = peak_bins[row + k];
95 // Find the nearest previous candidate within tolerance whose contour
96 // has not already been extended into this frame.
97 let mut best_j: Option<usize> = None;
98 let mut best_d = pitch_tol_bins;
99 for j in 0..prev_count {
100 let cid = out_contour_id[prev + j];
101 if cid == NO_CONTOUR {
102 continue;
103 }
104 if contour_claimed_this_frame(out_contour_id, row, k, cid) {
105 continue; // one-to-one: this contour already extended here
106 }
107 let d = (peak_bins[prev + j] - b).abs();
108 if d <= best_d {
109 best_d = d;
110 best_j = Some(j);
111 }
112 }
113 match best_j {
114 Some(j) => out_contour_id[row + k] = out_contour_id[prev + j],
115 None => {
116 out_contour_id[row + k] = next_id;
117 next_id += 1;
118 }
119 }
120 }
121 }
122 Ok(next_id as usize)
123}
124
125/// True if contour `cid` was already assigned to an earlier candidate slot
126/// (`0..k`) of the current frame — enforces one-to-one extension per frame.
127#[inline]
128fn contour_claimed_this_frame(ids: &[i32], row: usize, k: usize, cid: i32) -> bool {
129 for kk in 0..k {
130 if ids[row + kk] == cid {
131 return true;
132 }
133 }
134 false
135}
136
137#[cfg(test)]
138mod tests {
139 use super::*;
140
141 /// A single pitch drifting slowly (bins 100, 101, 102) stays one contour.
142 #[test]
143 fn continuous_pitch_one_contour() {
144 let max_p = 2usize;
145 let n = 3usize;
146 let mut bins = vec![0.0f32; n * max_p];
147 bins[0] = 100.0; // f0
148 bins[max_p] = 101.0; // f1
149 bins[2 * max_p] = 102.0; // f2
150 let counts = [1usize, 1, 1];
151 let mut ids = vec![0i32; n * max_p];
152 let n_contours = track_contours(&bins, &counts, n, max_p, 3.0, &mut ids).expect("track");
153 assert_eq!(n_contours, 1);
154 assert_eq!(ids[0], 0);
155 assert_eq!(ids[max_p], 0);
156 assert_eq!(ids[2 * max_p], 0);
157 }
158
159 /// A jump beyond tolerance breaks the contour (new id after the gap).
160 #[test]
161 fn discontinuity_starts_new_contour() {
162 let max_p = 1usize;
163 let n = 3usize;
164 let bins = [100.0f32, 200.0, 201.0]; // big jump at frame 1
165 let counts = [1usize, 1, 1];
166 let mut ids = vec![0i32; n];
167 let n_contours = track_contours(&bins, &counts, n, max_p, 3.0, &mut ids).expect("track");
168 assert_eq!(n_contours, 2);
169 assert_eq!(ids[0], 0);
170 assert_eq!(ids[1], 1);
171 assert_eq!(ids[2], 1, "202≈201 continues the second contour");
172 }
173
174 /// Two simultaneous voices track as two parallel contours.
175 #[test]
176 fn two_voices_two_contours() {
177 let max_p = 2usize;
178 let n = 3usize;
179 // Voice A ≈ bin 100, Voice B ≈ bin 160, both present every frame.
180 let mut bins = vec![0.0f32; n * max_p];
181 for f in 0..n {
182 bins[f * max_p] = 100.0 + f as f32; // A drifts up slightly
183 bins[f * max_p + 1] = 160.0 - f as f32; // B drifts down slightly
184 }
185 let counts = [2usize, 2, 2];
186 let mut ids = vec![0i32; n * max_p];
187 let n_contours = track_contours(&bins, &counts, n, max_p, 3.0, &mut ids).expect("track");
188 assert_eq!(n_contours, 2);
189 // Each voice keeps a stable contour id across frames.
190 assert_eq!(ids[0], ids[max_p]);
191 assert_eq!(ids[0], ids[2 * max_p]);
192 assert_eq!(ids[1], ids[max_p + 1]);
193 assert_ne!(ids[0], ids[1]);
194 }
195
196 #[test]
197 fn rejects_bad_params() {
198 let bins = [0.0f32; 4];
199 let counts = [1usize, 1];
200 let mut ids = [0i32; 4];
201 assert_eq!(
202 track_contours(&bins, &counts, 2, 0, 3.0, &mut ids),
203 Err(AudioError::InvalidParameter)
204 );
205 assert_eq!(
206 track_contours(&bins, &counts, 2, 2, f32::NAN, &mut ids),
207 Err(AudioError::InvalidParameter)
208 );
209 }
210}