Skip to main content

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}