changeset 235:4d0e9225c179 subsequence

Add a full-DTW implementation for subsequence experiments

--- a/Makefile.inc	Fri Jun 10 13:56:05 2016 +0100
+++ b/Makefile.inc	Thu Jul 02 16:29:39 2020 +0100
@@ -41,14 +41,13 @@
 # DO NOT DELETE
 
 src/DistanceMetric.o: src/DistanceMetric.h src/MatchTypes.h
-src/Path.o: src/Path.h
 src/FeatureConditioner.o: src/FeatureConditioner.h src/MatchTypes.h
-src/MatchFeatureFeeder.o: src/MatchFeatureFeeder.h src/Matcher.h
-src/MatchFeatureFeeder.o: src/DistanceMetric.h src/MatchTypes.h src/Finder.h
 src/FeatureExtractor.o: src/FeatureExtractor.h src/MatchTypes.h
 src/Finder.o: src/Finder.h src/Matcher.h src/DistanceMetric.h
 src/Finder.o: src/MatchTypes.h src/Path.h
 src/Matcher.o: src/Matcher.h src/DistanceMetric.h src/MatchTypes.h
+src/MatchFeatureFeeder.o: src/MatchFeatureFeeder.h src/Matcher.h
+src/MatchFeatureFeeder.o: src/DistanceMetric.h src/MatchTypes.h src/Finder.h
 src/MatchPipeline.o: src/MatchPipeline.h src/Matcher.h src/DistanceMetric.h
 src/MatchPipeline.o: src/MatchTypes.h src/Finder.h src/FeatureExtractor.h
 src/MatchPipeline.o: src/FeatureConditioner.h src/MatchFeatureFeeder.h
@@ -57,19 +56,21 @@
 src/MatchVampPlugin.o: src/Finder.h src/FeatureExtractor.h
 src/MatchVampPlugin.o: src/FeatureConditioner.h src/MatchFeatureFeeder.h
 src/MatchVampPlugin.o: src/Path.h
+src/Path.o: src/Path.h
+src/DistanceMetric.o: src/MatchTypes.h
+src/FeatureConditioner.o: src/MatchTypes.h
+src/FeatureExtractor.o: src/MatchTypes.h
+src/Finder.o: src/Matcher.h src/DistanceMetric.h src/MatchTypes.h
+src/FullDTW.o: src/DistanceMetric.h src/MatchTypes.h
+src/Matcher.o: src/DistanceMetric.h src/MatchTypes.h
 src/MatchFeatureFeeder.o: src/Matcher.h src/DistanceMetric.h src/MatchTypes.h
 src/MatchFeatureFeeder.o: src/Finder.h
-src/FeatureExtractor.o: src/MatchTypes.h
-src/Finder.o: src/Matcher.h src/DistanceMetric.h src/MatchTypes.h
-src/Matcher.o: src/DistanceMetric.h src/MatchTypes.h
 src/MatchPipeline.o: src/Matcher.h src/DistanceMetric.h src/MatchTypes.h
 src/MatchPipeline.o: src/Finder.h src/FeatureExtractor.h
 src/MatchPipeline.o: src/FeatureConditioner.h src/MatchFeatureFeeder.h
 src/MatchVampPlugin.o: src/MatchPipeline.h src/Matcher.h src/DistanceMetric.h
 src/MatchVampPlugin.o: src/MatchTypes.h src/Finder.h src/FeatureExtractor.h
 src/MatchVampPlugin.o: src/FeatureConditioner.h src/MatchFeatureFeeder.h
-src/DistanceMetric.o: src/MatchTypes.h
-src/FeatureConditioner.o: src/MatchTypes.h
+test/TestDistanceMetric.o: src/DistanceMetric.h src/MatchTypes.h
 test/TestFeatureConditioner.o: src/FeatureConditioner.h src/MatchTypes.h
-test/TestDistanceMetric.o: src/DistanceMetric.h src/MatchTypes.h
 test/TestFeatureExtractor.o: src/FeatureExtractor.h src/MatchTypes.h

--- a/README	Fri Jun 10 13:56:05 2016 +0100
+++ b/README	Thu Jul 02 16:29:39 2020 +0100
@@ -5,15 +5,11 @@
 This is a Vamp plugin implementation of the MATCH audio alignment
 algorithm:
 
-  http://www.eecs.qmul.ac.uk/~simond/match/index.html
+  https://www.eecs.qmul.ac.uk/~simond/match/index.html
 
 See plugin homepage at
 
-  http://code.soundsoftware.ac.uk/projects/match-vamp/
-
-This is version 1.0 of the plugin, which includes a number of fixes,
-efficiency improvements, and extra options not present in the prior
-0.2.1 release.
+  https://code.soundsoftware.ac.uk/projects/match-vamp/
 
 Plugin code by Chris Cannam and Simon Dixon.
 
@@ -39,7 +35,7 @@
 
 (See the CITATION file for a BibTeX reference.)
 
-Copyright (c) 2007-2015 Simon Dixon, Chris Cannam, and Queen Mary
+Copyright (c) 2007-2020 Simon Dixon, Chris Cannam, and Queen Mary
 University of London, Copyright (c) 2014-2015 Tido GmbH.
 
 Distributed under the GNU General Public License. See the file COPYING

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/FullDTW.cpp	Thu Jul 02 16:29:39 2020 +0100
@@ -0,0 +1,141 @@
+/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
+
+/*
+    Vamp feature extraction plugin using the MATCH audio alignment
+    algorithm.
+
+    Centre for Digital Music, Queen Mary, University of London.
+    Copyright (c) 2007-2015 Simon Dixon, Chris Cannam, and Queen Mary
+    University of London, Copyright (c) 2014-2015 Tido GmbH.
+    
+    This program is free software; you can redistribute it and/or
+    modify it under the terms of the GNU General Public License as
+    published by the Free Software Foundation; either version 2 of the
+    License, or (at your option) any later version.  See the file
+    COPYING included with this distribution for more information.
+*/
+
+#include "FullDTW.h"
+
+#include <stdexcept>
+
+FullDTW::FullDTW(Parameters params, DistanceMetric::Parameters dparams) :
+    m_params(params),
+    m_metric(dparams)
+{
+}
+
+pathcost_t
+FullDTW::choose(CostOption x, CostOption y, CostOption d) {
+    if (x.present && y.present) {
+        if (!d.present) {
+            throw std::logic_error("if x & y both exist, so must diagonal");
+        }
+        return std::min(std::min(x.cost, y.cost), d.cost);
+    } else if (x.present) {
+        return x.cost;
+    } else if (y.present) {
+        return y.cost;
+    } else {
+        return 0.0;
+    }
+}
+
+pathcostmat_t
+FullDTW::costSequences(const featureseq_t &s1, const featureseq_t &s2) {
+
+    pathcostmat_t costs(s1.size(), pathcostvec_t(s2.size(), 0));
+
+    for (size_t j = 0; j < s1.size(); ++j) {
+        for (size_t i = 0; i < s2.size(); ++i) {
+            distance_t dist = m_metric.calcDistance(s1[j], s2[i]);
+            if (i == 0 && m_params.subsequence) {
+                costs[j][i] = dist;
+            } else {
+                costs[j][i] = choose
+                    (
+                        { j > 0,
+                          j > 0 ? dist + costs[j-1][i] : 0
+                        },
+                        { i > 0,
+                          i > 0 ? dist + costs[j][i-1] : 0
+                        },
+                        { j > 0 && i > 0,
+                          j > 0 && i > 0 ? dist + costs[j-1][i-1] : 0
+                        });
+            }
+        }
+    }
+
+    return costs;
+}
+
+std::vector<size_t>
+FullDTW::align(const featureseq_t &s1, const featureseq_t &s2) {
+
+    // Return the index into s1 for each element in s2
+        
+    std::vector<size_t> alignment(s2.size(), 0);
+
+    if (s1.empty() || s2.empty()) {
+        return alignment;
+    }
+
+    auto costs = costSequences(s1, s2);
+
+#ifdef DEBUG_DTW
+    SVCERR << "Cost matrix:" << endl;
+    for (auto v: cost) {
+        for (auto x: v) {
+            SVCERR << x << " ";
+        }
+        SVCERR << "\n";
+    }
+#endif
+
+    size_t j = s1.size() - 1;
+    size_t i = s2.size() - 1;
+
+    if (m_params.subsequence) {
+        pathcost_t min = 0.0;
+        size_t minidx = 0;
+        for (size_t j = 0; j < s1.size(); ++j) {
+            if (j == 0 || costs[j][i] < min) {
+                min = costs[j][i];
+                minidx = j;
+            }
+        }
+        j = minidx;
+#ifdef DEBUG_DTW
+        SVCERR << "Lowest cost at end of subsequence = " << min
+               << " at index " << j << ", tracking back from there" << endl;
+#endif
+    }
+        
+    while (i > 0 && (j > 0 || m_params.subsequence)) {
+
+        alignment[i] = j;
+            
+        pathcost_t a = costs[j-1][i];
+        pathcost_t b = costs[j][i-1];
+        pathcost_t both = costs[j-1][i-1];
+
+        if (a < b) {
+            --j;
+            if (both <= a) {
+                --i;
+            }
+        } else {
+            --i;
+            if (both <= b) {
+                --j;
+            }
+        }
+    }
+
+    if (m_params.subsequence) {
+        alignment[0] = j;
+    }
+        
+    return alignment;
+}

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

--- a/src/MatchFeatureFeeder.cpp	Fri Jun 10 13:56:05 2016 +0100
+++ b/src/MatchFeatureFeeder.cpp	Thu Jul 02 16:29:39 2020 +0100
@@ -18,6 +18,8 @@
 #include "MatchFeatureFeeder.h"
 
 using std::vector;
+using std::cerr;
+using std::endl;
 
 MatchFeatureFeeder::MatchFeatureFeeder(Matcher *m1, Matcher *m2) :
     m_pm1(m1),

--- a/src/MatchFeatureFeeder.h	Fri Jun 10 13:56:05 2016 +0100
+++ b/src/MatchFeatureFeeder.h	Thu Jul 02 16:29:39 2020 +0100
@@ -14,8 +14,8 @@
     COPYING included with this distribution for more information.
 */
 
-#ifndef _MATCH_FEATURE_FEEDER_H_
-#define _MATCH_FEATURE_FEEDER_H_
+#ifndef MATCH_FEATURE_FEEDER_H
+#define MATCH_FEATURE_FEEDER_H
 
 #include "Matcher.h"
 #include "Finder.h"
@@ -82,8 +82,8 @@
     std::queue<feature_t> m_q1;
     std::queue<feature_t> m_q2;
 
-    vector<int> m_fpx;
-    vector<int> m_fpy;
+    std::vector<int> m_fpx;
+    std::vector<int> m_fpy;
 
     // not provided:
     MatchFeatureFeeder(const MatchFeatureFeeder &other);

--- a/src/MatchVampPlugin.cpp	Fri Jun 10 13:56:05 2016 +0100
+++ b/src/MatchVampPlugin.cpp	Thu Jul 02 16:29:39 2020 +0100
@@ -29,6 +29,8 @@
 #include <vector>
 #include <algorithm>
 
+using std::string;
+
 //static int extant = 0;
 
 #ifdef _WIN32

--- a/src/Matcher.h	Fri Jun 10 13:56:05 2016 +0100
+++ b/src/Matcher.h	Thu Jul 02 16:29:39 2020 +0100
@@ -26,11 +26,6 @@
 #include "DistanceMetric.h"
 #include "MatchTypes.h"
 
-using std::vector;
-using std::string;
-using std::cerr;
-using std::endl;
-
 /** Represents an audio feature stream that can be matched to another
  *  audio stream of the same piece of music.  The matching algorithm
  *  uses dynamic time warping.
@@ -38,7 +33,7 @@
 class Matcher
 {
 public:
-    static string advanceToString(advance_t a) {
+    static std::string advanceToString(advance_t a) {
         switch (a) {
         case AdvanceNone: return "AdvanceNone";
         case AdvanceBoth: return "AdvanceBoth";
@@ -57,8 +52,8 @@
             diagonalWeight(2.0)
         {}
 
-        /** Spacing of audio frames (determines the amount of overlap or
-         *  skip between frames). This value is expressed in
+        /** Spacing of audio frames (determines the amount of overlap
+         *  or skip between frames). This value is expressed in
          *  seconds.
          */
         double hopTime;
@@ -341,9 +336,9 @@
 
     /** The bounds of each row of data in the distance, path cost, and
      * advance direction matrices.*/
-    vector<int> m_first;
-    vector<int> m_last;
-
+    std::vector<int> m_first;
+    std::vector<int> m_last;
+    
     /** Width of distance, path cost, and advance direction matrices
      * and first and last vectors */
     int m_distXSize;