qualia_audio/features/structure/ssm.rs
1//! Self-similarity matrix (SSM) from a per-frame feature matrix.
2//!
3//! An SSM is the frames×frames Gram-like matrix `S[i,j] = sim(x_i, x_j)` where
4//! `x_i` is the feature vector of frame `i`. Homogeneous musical sections form
5//! high-similarity square blocks on the diagonal; section boundaries appear as
6//! the seams between blocks. This is the substrate the novelty curve then reads
7//! (contrast the energy-hysteresis heuristic previously in `music.rs`).
8
9use crate::types::AudioError;
10
11/// Compute the cosine self-similarity matrix of a per-frame feature matrix.
12///
13/// `features` is a row-major `n_frames × n_dims` matrix: frame `i` occupies
14/// `features[i*n_dims .. i*n_dims + n_dims]`. These frames are provided by the
15/// caller (e.g. from [`crate::features::mel::mfcc()`] or chroma / tonal features)
16/// — this function never recomputes features.
17///
18/// The similarity is the cosine of the angle between two feature vectors,
19/// `S[i,j] = (x_i · x_j) / (‖x_i‖ ‖x_j‖)`, in `[-1, 1]` (clamped against
20/// floating-point overshoot). When either frame has zero norm its similarity to
21/// every other frame is defined as `0.0`. The matrix is symmetric with a unit
22/// diagonal for non-zero frames.
23///
24/// # Caller-buffer contract (zero internal frames² allocation)
25/// The full `n_frames × n_frames` result is written, row-major, into the
26/// caller-provided `out` buffer (`out[i*n_frames + j] = S[i,j]`). This function
27/// performs **no** heap allocation — the inherently O(frames²) storage is the
28/// caller's `out`, and the O(frames²·dims) compute uses only scalar locals.
29/// `out.len()` must be at least `n_frames * n_frames`.
30///
31/// # Errors
32/// - [`AudioError::InvalidParameter`] if `n_frames == 0`, `n_dims == 0`, or
33/// `features.len() < n_frames * n_dims`.
34/// - [`AudioError::OutputBufferTooSmall`] if `out.len() < n_frames * n_frames`.
35pub fn self_similarity(
36 features: &[f32],
37 n_frames: usize,
38 n_dims: usize,
39 out: &mut [f32],
40) -> Result<(), AudioError> {
41 if n_frames == 0 || n_dims == 0 {
42 return Err(AudioError::InvalidParameter);
43 }
44 let feat_needed = n_frames
45 .checked_mul(n_dims)
46 .ok_or(AudioError::InvalidParameter)?;
47 if features.len() < feat_needed {
48 return Err(AudioError::InvalidParameter);
49 }
50 let out_needed = n_frames
51 .checked_mul(n_frames)
52 .ok_or(AudioError::InvalidParameter)?;
53 if out.len() < out_needed {
54 return Err(AudioError::OutputBufferTooSmall);
55 }
56
57 // Symmetric: compute the upper triangle (j >= i) and mirror it. Norms are
58 // recomputed per pair rather than cached, keeping the path strictly
59 // zero-heap (a per-frame norm cache would be an O(frames) allocation).
60 for i in 0..n_frames {
61 let row_i = &features[i * n_dims..i * n_dims + n_dims];
62 let norm_i = l2_norm(row_i);
63 for j in i..n_frames {
64 let sim = if norm_i == 0.0 {
65 0.0f32
66 } else {
67 let row_j = &features[j * n_dims..j * n_dims + n_dims];
68 let norm_j = l2_norm(row_j);
69 if norm_j == 0.0 {
70 0.0
71 } else {
72 let mut dot = 0.0f64;
73 for (a, b) in row_i.iter().zip(row_j.iter()) {
74 dot += (*a as f64) * (*b as f64);
75 }
76 (dot / (norm_i * norm_j)).clamp(-1.0, 1.0) as f32
77 }
78 };
79 out[i * n_frames + j] = sim;
80 out[j * n_frames + i] = sim;
81 }
82 }
83 Ok(())
84}
85
86/// L2 norm of a feature row (f64 accumulation for stability).
87#[inline]
88fn l2_norm(row: &[f32]) -> f64 {
89 let mut acc = 0.0f64;
90 for v in row {
91 acc += (*v as f64) * (*v as f64);
92 }
93 acc.sqrt()
94}
95
96#[cfg(test)]
97mod tests {
98 use super::*;
99
100 /// Build a two-section feature matrix: first `half` frames are vector A,
101 /// the remainder are the orthogonal vector B.
102 fn two_section(n_frames: usize, half: usize) -> (Vec<f32>, usize) {
103 let n_dims = 2;
104 let mut f = vec![0.0f32; n_frames * n_dims];
105 for frame in 0..n_frames {
106 if frame < half {
107 f[frame * n_dims] = 1.0; // A = (1, 0)
108 } else {
109 f[frame * n_dims + 1] = 1.0; // B = (0, 1)
110 }
111 }
112 (f, n_dims)
113 }
114
115 /// Golden: two orthogonal sections give unit within-block similarity and
116 /// zero cross-block similarity, with a unit diagonal.
117 #[test]
118 fn golden_two_blocks() {
119 let n = 8;
120 let half = 4;
121 let (feat, dims) = two_section(n, half);
122 let mut ssm = vec![-9.0f32; n * n];
123 self_similarity(&feat, n, dims, &mut ssm).expect("ssm");
124
125 // Diagonal is 1.
126 for i in 0..n {
127 assert!(
128 (ssm[i * n + i] - 1.0).abs() < 1e-6,
129 "diag {i}={}",
130 ssm[i * n + i]
131 );
132 }
133 // Within block A (0..4) and within block B (4..8): similarity 1.
134 for i in 0..half {
135 for j in 0..half {
136 assert!((ssm[i * n + j] - 1.0).abs() < 1e-6, "A[{i},{j}]");
137 }
138 }
139 for i in half..n {
140 for j in half..n {
141 assert!((ssm[i * n + j] - 1.0).abs() < 1e-6, "B[{i},{j}]");
142 }
143 }
144 // Across blocks: similarity 0.
145 for i in 0..half {
146 for j in half..n {
147 assert!(
148 ssm[i * n + j].abs() < 1e-6,
149 "cross[{i},{j}]={}",
150 ssm[i * n + j]
151 );
152 assert!(ssm[j * n + i].abs() < 1e-6, "cross[{j},{i}]");
153 }
154 }
155 }
156
157 /// Symmetry holds for an arbitrary (non-orthogonal) matrix.
158 #[test]
159 fn symmetric_and_diagonal_unit() {
160 let n = 5;
161 let dims = 3;
162 // Distinct, non-zero rows.
163 let feat: Vec<f32> = (0..n * dims)
164 .map(|k| (k as f32 * 0.37).sin() + 1.5)
165 .collect();
166 let mut ssm = vec![0.0f32; n * n];
167 self_similarity(&feat, n, dims, &mut ssm).expect("ssm");
168 for i in 0..n {
169 assert!((ssm[i * n + i] - 1.0).abs() < 1e-5, "diag {i}");
170 for j in 0..n {
171 assert!(
172 (ssm[i * n + j] - ssm[j * n + i]).abs() < 1e-6,
173 "asym at {i},{j}"
174 );
175 assert!(ssm[i * n + j] <= 1.0 + 1e-6 && ssm[i * n + j] >= -1.0 - 1e-6);
176 }
177 }
178 }
179
180 /// A zero-norm frame is similar to nothing (defined as 0).
181 #[test]
182 fn zero_frame_similarity_is_zero() {
183 let n = 3;
184 let dims = 2;
185 // frame 1 is the zero vector.
186 let feat = [1.0f32, 0.0, 0.0, 0.0, 0.0, 1.0];
187 let mut ssm = vec![9.0f32; n * n];
188 self_similarity(&feat, n, dims, &mut ssm).expect("ssm");
189 for j in 0..n {
190 assert!(ssm[1 * n + j].abs() < 1e-6, "row1 col{j}");
191 assert!(ssm[j * n + 1].abs() < 1e-6, "col1 row{j}");
192 }
193 }
194
195 #[test]
196 fn rejects_bad_params() {
197 let mut out = [0.0f32; 4];
198 assert_eq!(
199 self_similarity(&[1.0, 2.0], 0, 2, &mut out),
200 Err(AudioError::InvalidParameter)
201 );
202 assert_eq!(
203 self_similarity(&[1.0, 2.0], 2, 0, &mut out),
204 Err(AudioError::InvalidParameter)
205 );
206 // features too short: need 2*2=4, have 3.
207 assert_eq!(
208 self_similarity(&[1.0, 2.0, 3.0], 2, 2, &mut out),
209 Err(AudioError::InvalidParameter)
210 );
211 }
212
213 #[test]
214 fn rejects_small_output() {
215 let feat = [1.0f32, 0.0, 0.0, 1.0];
216 let mut out = [0.0f32; 3]; // need 2*2 = 4
217 assert_eq!(
218 self_similarity(&feat, 2, 2, &mut out),
219 Err(AudioError::OutputBufferTooSmall)
220 );
221 }
222}