SPB Git

Repository Public

Tempo.swift 20.9 KB 457 lines swift

1// =============================================================================2//                  SP BOUCHER | SOFTWARE & RESEARCH3//             ARTIFICIAL INTELLIGENCE • FINANCE • ENGINEERING4// =============================================================================5//6// PROJECT METADATA7// -----------------------------------------------------------------------------8// Project          : ORIX DJ9// File             : Packages/ORIXDJCore/Sources/ORIXAnalysis/Tempo.swift10// Description      : Tempo (autocorrelation comb + Fourier refinement + octave11//                    resolution), beat phase, downbeat and tempo stability.12// Module           : ORIXAnalysis13// Repository       : https://git.spboucher.ai/orix-dj14// Created          : 2026-11-2115// Last Modified    : 2026-11-2116//17// =============================================================================18// AUTHOR & PROFESSIONAL AFFILIATION19// =============================================================================20//21// Author           : Simon-Pierre Boucher22// Position         : Professor of Finance23// Institution      : Université du Québec en Outaouais (UQO)24// Department       : Département des sciences administratives25// Organization     : SP Boucher26//27// Website          : https://spboucher.ai28// Git              : https://git.spboucher.ai29//30// =============================================================================31// OFFICIAL CONTACT DIRECTORY32// =============================================================================33//34// General          : info@spboucher.ai35// Professional     : contact@spboucher.ai36// Direct           : simon@spboucher.ai37// Research         : research@spboucher.ai38// Development      : dev@spboucher.ai39// Support          : support@spboucher.ai40// Security/Admin   : admin@spboucher.ai41// Notifications    : notifications@spboucher.ai42//43// Preferred Contact: support@spboucher.ai44//45// =============================================================================46// COPYRIGHT & INTELLECTUAL PROPERTY47// =============================================================================48//49// Copyright (c) 202650// Simon-Pierre Boucher51//52// All rights reserved where applicable.53//54// This file is governed by the applicable project license,55// copyright notices, institutional agreements and relevant law.56//57// Unless expressly authorized by the applicable license or58// rights holder, copying, redistribution, sublicensing,59// publication and commercial exploitation are not permitted.60//61// Existing third-party rights and notices remain unaffected.62//63// =============================================================================64// CONFIDENTIALITY & SECURITY65// =============================================================================66//67// Classification   : Public68// Distribution     : Public repository; use is governed by the project license69// Security Contact : admin@spboucher.ai70//71// Access to this source does not independently grant permission72// to redistribute or disclose confidential materials.73//74// Do not embed credentials, private keys, access tokens,75// certificates or confidential personal information.76//77// =============================================================================78// LICENSE & MAINTENANCE79// =============================================================================80//81// License          : None specified (no license file in this repository)82// Maintainer       : Simon-Pierre Boucher83// Technical Contact: dev@spboucher.ai84//85// =============================================================================86// END OF SP BOUCHER SOURCE HEADER87// =============================================================================8889import Accelerate9091struct TempoEstimate {92    var grid: BeatGrid93    var bpmConfidence: Double94    var tempoStability: Double95    var downbeatConfidence: Double96}9798enum TempoEstimator {99    /// Minimum comb salience (mean normalised autocorrelation at the beat lags) below which no grid is reported.100    static let minimumSalience = 0.05101    /// A faster metrical level is preferred when its pulse alignment reaches this fraction of the best one.102    static let octaveThreshold = 0.85103104    static func estimate(features f: OnsetFeatures, detrended o: [Float], duration: Double, range: ClosedRange<Double>,105                         check: () throws -> Void) throws -> TempoEstimate? {106        let n = f.count107        let fr = f.frameRate108        let lo = min(max(range.lowerBound, 30), 300)109        let hi = max(lo + 1, min(range.upperBound, 320))110        guard n >= Int(3 * fr), o.count == n else { return nil }111112        // Zero-mean detrended envelope.113        var mean: Float = 0114        vDSP_meanv(o, 1, &mean, vDSP_Length(n))115        guard mean > 1e-6 else { return nil }116        // Smoothed over 50 ms so that autocorrelation peaks survive sampling at fractional lags.117        var z = [Float](repeating: 0, count: n)118        let kernel: [Float] = [1.0 / 9, 2.0 / 9, 3.0 / 9, 2.0 / 9, 1.0 / 9]119        for i in 0..<n {120            var v: Float = 0121            for k in 0..<5 {122                let j = i + k - 2123                if j >= 0 && j < n { v += kernel[k] * o[j] }124            }125            z[i] = v - mean126        }127128        // Unbiased, normalised autocorrelation up to four beats of the slowest tempo.129        let maxLag = min(n - 2, Int(4 * 60 * fr / lo) + 2)130        let size = nextPowerOfTwo(n + maxLag + 1)131        var padded = [Float](repeating: 0, count: size)132        padded.replaceSubrange(0..<n, with: z)133        var raw = [Float](repeating: 0, count: size)134        RealFFT(size: max(8, size)).autocorrelation(padded, into: &raw)135        guard raw[0] > 0 else { return nil }136        var r = [Float](repeating: 0, count: maxLag + 1)137        let zeroLag = raw[0] / Float(n)138        for lag in 0...maxLag { r[lag] = raw[lag] / Float(n - lag) / zeroLag }139        try check()140141        func comb(_ bpm: Double) -> Double {142            let period = 60 * fr / bpm143            var sum = 0.0144            var terms = 0145            for multiple in 1...4 {146                let x = period * Double(multiple)147                if x > Double(maxLag) - 1 || x > Double(n) / 2 { break }148                sum += Double(interpolate(r, x))149                terms += 1150            }151            return terms > 0 ? sum / Double(terms) : 0152        }153154        // Coarse scan.155        var coarse = lo156        var coarseScore = -Double.infinity157        var bpm = lo158        while bpm <= hi + 1e-9 {159            let s = comb(bpm)160            if s > coarseScore { coarseScore = s; coarse = bpm }161            bpm += 0.25162        }163        guard comb(coarse) >= minimumSalience else { return nil }164165        // Refine on the harmonic sum of the envelope's zero-padded spectrum (whole-track coherence).166        let refined = refine(z, frameRate: fr, bpm: coarse)167        try check()168169        // Octave resolution: T/2, T, 2T inside the range, judged on the drum (low + mid) pulse alignment.170        let drums = weightedEnvelope(f, low: 1, mid: 1, high: 0)171        var candidates: [(bpm: Double, score: Double)] = []172        for multiplier in [0.5, 1.0, 2.0] {173            let c = refined * multiplier174            if c >= lo * 0.985 && c <= hi * 1.015 {175                let alignment = foldPeak(drums, period: 60 * fr / c).mean176                candidates.append((c, alignment))177            }178        }179        var tempo = refined180        if let best = candidates.map(\.score).max(), best > 0 {181            let acceptable = candidates.filter { $0.score >= octaveThreshold * best }182            if let fastest = acceptable.map(\.bpm).max() { tempo = fastest }183        }184        let salience = comb(tempo)185186        // Beat phase: pulse train on a kick-weighted envelope, then alignment on the attacks at 0.5 ms resolution.187        let phaseEnvelope = weightedEnvelope(f, low: 1, mid: 0.5, high: 0.15)188        let period = 60 * fr / tempo189        let phaseFrames = foldPeak(phaseEnvelope, period: period).phase190        var beatSeconds = 60 / tempo191        var anchor = phaseFrames / fr + f.latency192        if let fine = alignFine(rise: f.fineRise, rate: f.fineRate, beat: beatSeconds, anchor: anchor, duration: duration) {193            beatSeconds = fine.beat194            anchor = fine.anchor195        }196        tempo = 60 / beatSeconds197        var first = anchor.truncatingRemainder(dividingBy: beatSeconds)198        if first < 0 { first += beatSeconds }199        if first >= beatSeconds { first = 0 }200        try check()201202        let downbeat = downbeat(f, firstBeat: first, beatSeconds: beatSeconds, duration: duration)203        let stability = stability(o, frameRate: fr, period: 60 * fr / tempo)204        let grid = BeatGrid(bpm: tempo, firstBeatSeconds: first, downbeatIndex: downbeat.index)205        return TempoEstimate(grid: grid,206                             bpmConfidence: min(1, max(0, salience)).squareRoot(),207                             tempoStability: stability,208                             downbeatConfidence: downbeat.confidence)209    }210211    /// Sum of band envelopes, each normalised by its mean; bands that carry almost nothing are ignored.212    static func weightedEnvelope(_ f: OnsetFeatures, low: Float, mid: Float, high: Float) -> [Float] {213        let n = f.count214        var out = [Float](repeating: 0, count: n)215        var fullMean: Float = 0216        vDSP_meanv(f.full, 1, &fullMean, vDSP_Length(n))217        guard fullMean > 0 else { return out }218        var used = false219        for (band, weight) in [(f.low, low), (f.mid, mid), (f.high, high)] where weight > 0 {220            var m: Float = 0221            vDSP_meanv(band, 1, &m, vDSP_Length(n))222            guard m > fullMean * 0.01 else { continue }223            var gain = weight / m224            vDSP_vsma(band, 1, &gain, out, 1, &out, 1, vDSP_Length(n))225            used = true226        }227        return used ? out : f.full228    }229230    /// Folds `x` at `period` frames; returns the phase (frames, 0..<period) of the strongest pulse and its mean value per period.231    static func foldPeak(_ x: [Float], period: Double) -> (phase: Double, mean: Double) {232        guard period >= 2, !x.isEmpty else { return (0, 0) }233        let smooth = foldProfile(x, period: period)234        let bins = smooth.count235        let scale = Double(bins) / period236        var best = 0237        for k in 1..<bins where smooth[k] > smooth[best] { best = k }238        let d = parabolicOffset(smooth[(best + bins - 1) % bins], smooth[best], smooth[(best + 1) % bins])239        var phase = (Double(best) + d) / scale240        if phase < 0 { phase += period }241        if phase >= period { phase -= period }242        let periods = max(1, Double(x.count) / period)243        return (phase, smooth[best] / periods)244    }245246    /// `x` accumulated by phase modulo `period` (half-frame bins, circularly smoothed).247    static func foldProfile(_ x: [Float], period: Double) -> [Double] {248        let bins = max(4, Int((period * 2).rounded()))249        var acc = [Double](repeating: 0, count: bins)250        let scale = Double(bins) / period251        for i in 0..<x.count where x[i] != 0 {252            let p = Double(i).truncatingRemainder(dividingBy: period) * scale253            let i0 = Int(p)254            let frac = p - Double(i0)255            let v = Double(x[i])256            acc[i0 % bins] += v * (1 - frac)257            acc[(i0 + 1) % bins] += v * frac258        }259        // Triangular smoothing over ±2 frames: an onset between two frames must count as much as one on a frame.260        var smooth = [Double](repeating: 0, count: bins)261        let reach = min(4, (bins - 1) / 2)262        for k in 0..<bins {263            var v = 0.0264            for d in -reach...reach {265                v += acc[((k + d) % bins + bins) % bins] * Double(reach + 1 - abs(d))266            }267            smooth[k] = v / Double(reach + 1)268        }269        return smooth270    }271272    /// Maximises the harmonic sum of the envelope spectrum around `bpm` (±2.5 %).273    static func refine(_ z: [Float], frameRate: Double, bpm: Double) -> Double {274        let n = z.count275        let size = min(1 << 21, max(1 << 15, nextPowerOfTwo(16 * n)))276        guard n <= size else { return bpm }277        var padded = [Float](repeating: 0, count: size)278        padded.replaceSubrange(0..<n, with: z)279        var mags = [Float](repeating: 0, count: size / 2)280        RealFFT(size: size).magnitudes(padded, into: &mags)281        let binsPerBPM = Double(size) / (60 * frameRate)282        let centre = bpm * binsPerBPM283        let weights: [Double] = [1, 1, 0.5, 0.5]284        func harmonicSum(_ k: Double) -> Double {285            var s = 0.0286            for (h, w) in weights.enumerated() {287                let x = k * Double(h + 1)288                if x < Double(size / 2 - 2) { s += w * Double(interpolate(mags, x)) }289            }290            return s291        }292        let step = 0.5293        let span = Int((centre * 0.025 / step).rounded(.up))294        var bestIndex = 0295        var bestValue = -1.0296        for i in -span...span {297            let v = harmonicSum(centre + Double(i) * step)298            if v > bestValue { bestValue = v; bestIndex = i }299        }300        let k = centre + Double(bestIndex) * step301        let d = parabolicOffset(harmonicSum(k - step), bestValue, harmonicSum(k + step))302        return (k + d * step) / binsPerBPM303    }304305    /// Joint micro-refinement of tempo and phase: maximises the sharpness of the attack envelope folded at the beat period.306    static func alignFine(rise: [Float], rate: Double, beat: Double, anchor: Double, duration: Double) -> (beat: Double, anchor: Double)? {307        let reach = Int(0.02 * rate)308        let width = 2 * reach + 1309        let firstIndex = Int((-anchor / beat).rounded(.up))310        let lastIndex = Int(((duration - anchor) / beat).rounded(.down))311        let beats = lastIndex - firstIndex + 1312        guard beats >= 4, rise.count > width else { return nil }313        let centreIndex = (firstIndex + lastIndex) / 2314        let centreTime = anchor + Double(centreIndex) * beat315        let steps = 40316        let spread = min(0.003, 0.04 / max(1, duration))317318        var bestValue = -1.0, bestShift = 0.0, bestBeat = beat, bestMean = 0.0319        var profile = [Float](repeating: 0, count: width)320        rise.withUnsafeBufferPointer { r in321            for step in -steps...steps {322                let candidate = beat / (1 + spread * Double(step) / Double(steps))323                vDSP_vclr(&profile, 1, vDSP_Length(width))324                for j in firstIndex...lastIndex {325                    let t = centreTime + Double(j - centreIndex) * candidate326                    let index = Int((t * rate - 0.5).rounded())327                    if index - reach >= 0 && index + reach < r.count {328                        vDSP_vadd(profile, 1, r.baseAddress! + (index - reach), 1, &profile, 1, vDSP_Length(width))329                    }330                }331                var peak = 0.0332                var peakAt = 0333                var total = 0.0334                for k in 1..<(width - 1) {335                    let v = 0.25 * Double(profile[k - 1]) + 0.5 * Double(profile[k]) + 0.25 * Double(profile[k + 1])336                    total += v337                    if v > peak { peak = v; peakAt = k }338                }339                if peak > bestValue {340                    bestValue = peak341                    bestBeat = candidate342                    bestMean = total / Double(width - 2)343                    var d = 0.0344                    if peakAt > 1 && peakAt < width - 2 {345                        func s(_ k: Int) -> Double { 0.25 * Double(profile[k - 1]) + 0.5 * Double(profile[k]) + 0.25 * Double(profile[k + 1]) }346                        d = parabolicOffset(s(peakAt - 1), s(peakAt), s(peakAt + 1))347                    }348                    bestShift = (Double(peakAt - reach) + d) / rate349                }350            }351        }352        guard bestValue > 0, bestValue >= 2.5 * bestMean else { return nil }353        let newCentre = centreTime + bestShift354        return (bestBeat, newCentre - Double(centreIndex) * bestBeat)355    }356357    /// Bar phase from the low-frequency accent and the beat-to-beat spectral change, as a contrast statistic over the four phases.358    static func downbeat(_ f: OnsetFeatures, firstBeat: Double, beatSeconds: Double, duration: Double) -> (index: Int, confidence: Double) {359        let fr = f.frameRate360        let n = f.count361        let beats = Int(((duration - firstBeat) / beatSeconds).rounded(.down))362        guard beats >= 8, n > 0 else { return (0, 0) }363        let bands = f.bandCount364        var accent = [Double](repeating: 0, count: beats)365        var novelty = [Double](repeating: 0, count: beats)366        var previous = [Float](repeating: 0, count: bands)367        var current = [Float](repeating: 0, count: bands)368        let periodFrames = beatSeconds * fr369        f.bandSpectrum.withUnsafeBufferPointer { spectrum in370            for j in 0..<beats {371                let centre = (firstBeat + Double(j) * beatSeconds - f.latency) * fr372                let c = Int(centre.rounded())373                var a: Float = 0374                let firstFrame = min(n - 1, max(0, c - 2))375                for k in firstFrame...max(firstFrame, min(n - 1, c + 2)) where f.low[k] > a { a = f.low[k] }376                accent[j] = Double(a)377                let from = min(n - 1, max(0, Int(centre + 0.1 * periodFrames)))378                let to = min(n, max(from + 1, Int(centre + 0.9 * periodFrames)))379                for b in 0..<bands {380                    var m: Float = 0381                    vDSP_meanv(spectrum.baseAddress! + from * bands + b, vDSP_Stride(bands), &m, vDSP_Length(to - from))382                    current[b] = m383                }384                if j > 0 {385                    var d = 0.0386                    for b in 0..<bands { d += Double(abs(current[b] - previous[b])) }387                    novelty[j] = d388                }389                swap(&current, &previous)390            }391        }392        novelty[0] = novelty[1...].reduce(0, +) / Double(beats - 1)393394        func contrast(_ x: [Double]) -> [Double] {395            let mean = x.reduce(0, +) / Double(x.count)396            let variance = x.reduce(0) { $0 + ($1 - mean) * ($1 - mean) } / Double(x.count)397            guard variance > 1e-12 else { return [0, 0, 0, 0] }398            var sums = [Double](repeating: 0, count: 4), counts = [Double](repeating: 0, count: 4)399            for (j, v) in x.enumerated() { sums[j % 4] += v; counts[j % 4] += 1 }400            let means = (0..<4).map { sums[$0] / max(1, counts[$0]) }401            return (0..<4).map { p in402                let others = (means.reduce(0, +) - means[p]) / 3403                return (means[p] - others) / (variance / max(1, counts[p])).squareRoot()404            }405        }406        let a = contrast(accent), b = contrast(novelty)407        let score = (0..<4).map { a[$0] + b[$0] }408        let order = (0..<4).sorted { score[$0] > score[$1] }409        let margin = max(0, score[order[0]] - score[order[1]])410        return (order[0], 1 - exp(-margin / 4))411    }412413    /// Agreement of local tempo estimates (10 s windows) with the global one, weighted by onset energy.414    static func stability(_ o: [Float], frameRate: Double, period: Double) -> Double {415        let n = o.count416        let window = min(Int(10 * frameRate), n / 2)417        guard window > Int(4 * period) else { return 0 }418        var multiple = 4.0419        while multiple > 1 && period * multiple * 1.1 > Double(window) / 2 { multiple /= 2 }420        let target = period * multiple421        let tolerance = 0.08422        let minLag = max(1, Int(target * (1 - tolerance)))423        let maxLag = min(window - 2, Int((target * (1 + tolerance)).rounded(.up)))424        guard maxLag > minLag + 2 else { return 0 }425        var weighted = 0.0, weights = 0.0426        var values = [Double](repeating: 0, count: maxLag - minLag + 1)427        o.withUnsafeBufferPointer { p in428            var start = 0429            while start + window <= n {430                let base = p.baseAddress! + start431                var energy: Float = 0432                vDSP_dotpr(base, 1, base, 1, &energy, vDSP_Length(window))433                if energy > 0 {434                    for lag in minLag...maxLag {435                        var v: Float = 0436                        vDSP_dotpr(base, 1, base + lag, 1, &v, vDSP_Length(window - lag))437                        values[lag - minLag] = Double(v) / Double(window - lag)438                    }439                    var best = 0440                    for k in 1..<values.count where values[k] > values[best] { best = k }441                    var deviation = tolerance442                    let normalised = values[best] / (Double(energy) / Double(window))443                    if best > 0 && best < values.count - 1 && normalised > 0.05 {444                        let d = parabolicOffset(values[best - 1], values[best], values[best + 1])445                        deviation = abs((Double(minLag + best) + d) / target - 1)446                    }447                    let agreement = max(0, 1 - deviation / 0.04)448                    weighted += Double(energy) * agreement449                    weights += Double(energy)450                }451                start += max(1, window / 2)452            }453        }454        return weights > 0 ? min(1, max(0, weighted / weights)) : 0455    }456}457
Files main
Menu

Theme