Chris@235: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
Chris@235: 
Chris@235: /*
Chris@235:     Vamp feature extraction plugin using the MATCH audio alignment
Chris@235:     algorithm.
Chris@235: 
Chris@235:     Centre for Digital Music, Queen Mary, University of London.
Chris@235:     Copyright (c) 2007-2020 Simon Dixon, Chris Cannam, and Queen Mary
Chris@235:     University of London, Copyright (c) 2014-2015 Tido GmbH.
Chris@235:     
Chris@235:     This program is free software; you can redistribute it and/or
Chris@235:     modify it under the terms of the GNU General Public License as
Chris@235:     published by the Free Software Foundation; either version 2 of the
Chris@235:     License, or (at your option) any later version.  See the file
Chris@235:     COPYING included with this distribution for more information.
Chris@235: */
Chris@235: 
Chris@235: #ifndef FULL_DTW_H
Chris@235: #define FULL_DTW_H
Chris@235: 
Chris@235: #include <vector>
Chris@235: #include <functional>
Chris@235: 
Chris@235: #include "DistanceMetric.h"
Chris@235: #include "MatchTypes.h"
Chris@235: 
Chris@235: /** Represents a full-matrix dynamic time warping aligner. Unlike the
Chris@235:  *  combination of Matcher and Finder, which implement a "live" online
Chris@235:  *  DTW that stores only a part of the matrix, FullDTW works offline,
Chris@235:  *  requiring all features up-front and storing the whole cost
Chris@235:  *  matrix. This is far simpler than Matcher/Finder, can calculate
Chris@235:  *  subsequence matches, and always returns the optimal path, but it
Chris@235:  *  is also much more expensive - O(mn) rather than O(m+n) in both
Chris@235:  *  time and space.
Chris@235:  */
Chris@235: class FullDTW
Chris@235: {
Chris@235: public:
Chris@235:     struct Parameters {
Chris@235: 
Chris@235:         Parameters(double hopTime_) :
Chris@235:             hopTime(hopTime_),
Chris@235:             diagonalWeight(1.0),
Chris@235:             subsequence(false)
Chris@235:         {}
Chris@235: 
Chris@235:         /** Spacing of audio frames (determines the amount of overlap
Chris@235:          *  or skip between frames). This value is expressed in
Chris@235:          *  seconds.
Chris@235:          */
Chris@235:         double hopTime;
Chris@235: 
Chris@235:         /** Weight applied to cost of diagonal step relative to
Chris@235:          *  horizontal or vertical step. The default of 1.0 is normal
Chris@235:          *  for cases that are not expected to differ wildly in speed.
Chris@235:          */
Chris@235:         double diagonalWeight;
Chris@235: 
Chris@235:         /** Whether this is a subsequence matcher. The FullDTW aligns
Chris@235:          *  two sequences, and by default it assumes that they are
Chris@235:          *  anchored to one another at both ends (i.e. they both span
Chris@235:          *  the same material). If subsequence is true, then it
Chris@235:          *  instead assumes that the second sequence is intended to
Chris@235:          *  match some subsequence of the first, and it returns a
Chris@235:          *  match against the best-matching subsequence rather than
Chris@235:          *  the whole of the first sequence.
Chris@235:          */
Chris@235:         bool subsequence;
Chris@235:     };
Chris@235:     
Chris@235:     /** Constructor for FullDTW.
Chris@235:      * 
Chris@235:      *  A FullDTW expects to be provided with two sequences of feature
Chris@235:      *  vectors calculated by some external code (for example, a
Chris@235:      *  FeatureExtractor) which it will align.
Chris@235:      */
Chris@235:     FullDTW(Parameters params, DistanceMetric::Parameters dparams);
Chris@235: 
Chris@235:     /**
Chris@235:      * Align the sequence s2 against the sequence s1, returning the
Chris@235:      * index into s1 for each element in s2. If the subsequence
Chris@235:      * parameter was set on construction, then the alignment is
Chris@235:      * against the best-matching subsequence of s1; otherwise it is
Chris@235:      * against the whole of s1.
Chris@235:      */
Chris@235:     std::vector<size_t> align(const featureseq_t &s1,
Chris@235:                               const featureseq_t &s2);
Chris@235: 
Chris@235: private:
Chris@235:     Parameters m_params;
Chris@235:     DistanceMetric m_metric;
Chris@235: 
Chris@235:     struct CostOption {
Chris@235:         bool present;
Chris@235:         pathcost_t cost;
Chris@235:     };
Chris@235: 
Chris@235:     pathcost_t choose(CostOption x, CostOption y, CostOption d);
Chris@235:     pathcostmat_t costSequences(const featureseq_t &s1, const featureseq_t &s2);
Chris@235: };
Chris@235: 
Chris@235: #endif