Skip to main content

qualia_audio/features/structure/
novelty.rs

1//! Foote novelty curve: a checkerboard kernel correlated along the SSM diagonal.
2//!
3//! Sliding a `L × L` checkerboard kernel down the main diagonal of a
4//! self-similarity matrix scores, at each frame, how much the local structure
5//! looks like the seam between two homogeneous blocks. The kernel's sign
6//! pattern is
7//!
8//! ```text
9//!   + -
10//!   - +
11//! ```
12//!
13//! so within a homogeneous region (all four quadrants equally similar) the
14//! contributions cancel to ~0, while at a boundary the two same-block quadrants
15//! (`+`) are high and the two cross-block quadrants (`-`) are low, producing a
16//! sharp positive peak.
17
18use crate::types::AudioError;
19
20/// Correlate a checkerboard kernel along the diagonal of `ssm`, producing a
21/// per-frame novelty curve.
22///
23/// `ssm` is a row-major `n_frames × n_frames` self-similarity matrix (as
24/// produced by [`super::ssm::self_similarity`]). `kernel_size` is the full width
25/// `L` of the (`L × L`) checkerboard kernel and **must be even and ≥ 2**; each
26/// half-quadrant then spans `M = L/2` frames.
27///
28/// The novelty at frame `n` is `Σ_{a,b} C(a,b) · S[n+a, n+b]` over kernel
29/// offsets `a, b ∈ [-M, M)`, where the checkerboard sign is `+1` when `a` and
30/// `b` lie on the same side of the split and `-1` otherwise. The diagonal is
31/// centred at `(n, n)`. Kernel taps that fall outside `[0, n_frames)` are
32/// treated as zero (zero-padding), so a full-length curve of `n_frames` values
33/// is produced.
34///
35/// # Caller-buffer contract (zero-heap)
36/// The `n_frames`-long result is written into the caller-provided `out`;
37/// `out.len()` must be at least `n_frames`. No heap allocation is performed.
38///
39/// # Errors
40/// - [`AudioError::InvalidParameter`] if `n_frames == 0`, `kernel_size == 0`,
41///   `kernel_size` is odd, or `ssm.len() < n_frames * n_frames`.
42/// - [`AudioError::OutputBufferTooSmall`] if `out.len() < n_frames`.
43pub fn novelty_curve(
44    ssm: &[f32],
45    n_frames: usize,
46    kernel_size: usize,
47    out: &mut [f32],
48) -> Result<(), AudioError> {
49    if n_frames == 0 || kernel_size == 0 || kernel_size % 2 != 0 {
50        return Err(AudioError::InvalidParameter);
51    }
52    let ssm_needed = n_frames
53        .checked_mul(n_frames)
54        .ok_or(AudioError::InvalidParameter)?;
55    if ssm.len() < ssm_needed {
56        return Err(AudioError::InvalidParameter);
57    }
58    if out.len() < n_frames {
59        return Err(AudioError::OutputBufferTooSmall);
60    }
61
62    let m = (kernel_size / 2) as isize;
63    let nf = n_frames as isize;
64
65    for n in 0..n_frames {
66        let center = n as isize;
67        let mut acc = 0.0f64;
68        let mut a = -m;
69        while a < m {
70            let row = center + a;
71            if row < 0 || row >= nf {
72                a += 1;
73                continue;
74            }
75            let a_neg = a < 0;
76            let mut b = -m;
77            while b < m {
78                let col = center + b;
79                if col < 0 || col >= nf {
80                    b += 1;
81                    continue;
82                }
83                let b_neg = b < 0;
84                // Checkerboard: same side of the split => +, opposite => -.
85                let sign = if a_neg == b_neg { 1.0f64 } else { -1.0f64 };
86                acc += sign * ssm[(row as usize) * n_frames + (col as usize)] as f64;
87                b += 1;
88            }
89            a += 1;
90        }
91        out[n] = acc as f32;
92    }
93    Ok(())
94}
95
96#[cfg(test)]
97mod tests {
98    use super::super::ssm::self_similarity;
99    use super::*;
100
101    fn two_section_ssm(n_frames: usize, half: usize) -> Vec<f32> {
102        let dims = 2;
103        let mut f = vec![0.0f32; n_frames * dims];
104        for frame in 0..n_frames {
105            if frame < half {
106                f[frame * dims] = 1.0;
107            } else {
108                f[frame * dims + 1] = 1.0;
109            }
110        }
111        let mut ssm = vec![0.0f32; n_frames * n_frames];
112        self_similarity(&f, n_frames, dims, &mut ssm).expect("ssm");
113        ssm
114    }
115
116    /// Golden: two orthogonal sections of 4 frames each, kernel size 4.
117    /// The novelty curve must peak at the boundary frame (index 4) with the
118    /// analytically derived value 8.0, and be ~0 in the block interior.
119    #[test]
120    fn golden_peaks_at_boundary() {
121        let n = 8;
122        let ssm = two_section_ssm(n, 4);
123        let mut nov = vec![-1.0f32; n];
124        novelty_curve(&ssm, n, 4, &mut nov).expect("novelty");
125
126        // Analytical curve derived by hand: [4, 1, 0, 2, 8, 2, 0, 1].
127        // (Edge values differ low vs high side because the zero-padded kernel
128        // overhangs asymmetrically: frame 0 sees rows {0,1}, frame 7 sees only
129        // {5,6,7}. The boundary peak at frame 4 is the strict interior maximum.)
130        let expect = [4.0f32, 1.0, 0.0, 2.0, 8.0, 2.0, 0.0, 1.0];
131        for (i, (&got, &want)) in nov.iter().zip(expect.iter()).enumerate() {
132            assert!((got - want).abs() < 1e-5, "n[{i}]={got} want {want}");
133        }
134
135        // The strict interior maximum is at the true boundary, frame 4.
136        let mut best = 0usize;
137        for i in 1..n - 1 {
138            if nov[i] > nov[best] {
139                best = i;
140            }
141        }
142        assert_eq!(best, 4, "peak frame");
143        assert!((nov[4] - 8.0).abs() < 1e-5);
144        // Homogeneous interior (frame 2) is flat.
145        assert!(nov[2].abs() < 1e-6, "interior novelty {}", nov[2]);
146    }
147
148    /// A larger split (12 frames, boundary at 6, kernel 4) still peaks exactly
149    /// on the boundary frame.
150    #[test]
151    fn peak_tracks_midpoint() {
152        let n = 12;
153        let ssm = two_section_ssm(n, 6);
154        let mut nov = vec![0.0f32; n];
155        novelty_curve(&ssm, n, 4, &mut nov).expect("novelty");
156        let mut best = 1usize;
157        for i in 1..n - 1 {
158            if nov[i] > nov[best] {
159                best = i;
160            }
161        }
162        assert_eq!(best, 6, "peak at boundary; curve={nov:?}");
163    }
164
165    #[test]
166    fn rejects_bad_params() {
167        let ssm = vec![0.0f32; 16];
168        let mut out = [0.0f32; 4];
169        assert_eq!(
170            novelty_curve(&ssm, 0, 2, &mut out),
171            Err(AudioError::InvalidParameter)
172        );
173        // odd kernel
174        assert_eq!(
175            novelty_curve(&ssm, 4, 3, &mut out),
176            Err(AudioError::InvalidParameter)
177        );
178        // zero kernel
179        assert_eq!(
180            novelty_curve(&ssm, 4, 0, &mut out),
181            Err(AudioError::InvalidParameter)
182        );
183        // ssm too small: need 4*4=16.
184        assert_eq!(
185            novelty_curve(&[0.0f32; 15], 4, 2, &mut out),
186            Err(AudioError::InvalidParameter)
187        );
188    }
189
190    #[test]
191    fn rejects_small_output() {
192        let ssm = vec![0.0f32; 16];
193        let mut out = [0.0f32; 3]; // need 4
194        assert_eq!(
195            novelty_curve(&ssm, 4, 2, &mut out),
196            Err(AudioError::OutputBufferTooSmall)
197        );
198    }
199}