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}