dtw_cost()

template<typename T >

float MayaFlux::Kinesis::dtw_cost ( std::span< const T >  a, std::span< const T >  b, const std::function< float(const T &, const T &)> &  distance, size_t  band = 0  )

inline

Dynamic time warping cost between two sequences.

Template Parameters

T	Element type

Parameters

a	Left sequence
b	Right sequence
distance	Pointwise cost between one element of each
band	Sakoe-Chiba radius: the furthest an alignment may stray from the diagonal, in elements. Zero means unconstrained

Returns

Accumulated cost of the cheapest monotone alignment, or infinity if either sequence is empty or the band admits no complete alignment

Resampling by arc length removes speed variation from a path by discarding time entirely, which is right when only shape matters and wrong when the quantity being compared is not positional. This instead keeps both sequences and finds the cheapest correspondence between them, allowing one to stretch against the other, so two recordings of the same thing performed at different tempos align rather than disagree at every step.

The band is the difference between a bounded cost and a quadratic one, and it also encodes an assumption: a nonzero band asserts that the two sequences are roughly in step and only locally out of it. A band narrower than the genuine offset between two sequences reports infinity rather than a poor alignment, which is the honest answer given the constraint it was handed.

Definition at line 361 of file PathShape.hpp.

{
    if (a.empty() || b.empty())
        return std::numeric_limits<float>::infinity();
 
    const size_t n = a.size();
    const size_t m = b.size();
    constexpr float inf = std::numeric_limits<float>::infinity();
 
    std::vector<float> prev(m + 1, inf);
    std::vector<float> curr(m + 1, inf);
    prev[0] = 0.0F;
 
    for (size_t i = 1; i <= n; ++i) {
        std::ranges::fill(curr, inf);
 
        size_t lo = 1;
        size_t hi = m;
        if (band > 0) {
            const auto centre = static_cast<size_t>(
                (static_cast<double>(i) * static_cast<double>(m)) / static_cast<double>(n));
            lo = (centre > band) ? (centre - band) : 1;
            hi = std::min(m, centre + band);
            if (lo > hi)
                return inf;
        }
 
        for (size_t j = lo; j <= hi; ++j) {
            const float cost = distance(a[i - 1], b[j - 1]);
            const float best = std::min({ prev[j], curr[j - 1], prev[j - 1] });
            curr[j] = (best == inf) ? inf : (cost + best);
        }
        std::swap(prev, curr);
    }
 
    return prev[m];
}

References a, b, distance(), hi, and lo.

Here is the call graph for this function: