Skip to main content

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}