cannam@0: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
cannam@0: 
cannam@0: /*
cannam@0:     Vamp feature extraction plugin using the MATCH audio alignment
cannam@0:     algorithm.
cannam@0: 
cannam@0:     Centre for Digital Music, Queen Mary, University of London.
cannam@0:     This file copyright 2007 Simon Dixon, Chris Cannam and QMUL.
cannam@0:     
cannam@0:     This program is free software; you can redistribute it and/or
cannam@0:     modify it under the terms of the GNU General Public License as
cannam@0:     published by the Free Software Foundation; either version 2 of the
cannam@0:     License, or (at your option) any later version.  See the file
cannam@0:     COPYING included with this distribution for more information.
cannam@0: */
cannam@0: 
cannam@0: #include "Matcher.h"
cannam@0: 
cannam@0: #include <iostream>
cannam@0: 
cannam@4: #include <cstdlib>
Chris@16: #include <cassert>
cannam@4: 
Chris@10: //#define DEBUG_MATCHER 1
Chris@10: 
Chris@38: Matcher::Matcher(Parameters parameters,
Chris@38:                  FeatureExtractor::Parameters feParams,
Chris@38:                  Matcher *p) :
Chris@43:     m_params(parameters),
Chris@43:     m_featureExtractor(feParams),
Chris@43:     m_metric(parameters.distanceNorm)
cannam@0: {
Chris@10: #ifdef DEBUG_MATCHER
Chris@43:     cerr << "Matcher::Matcher(" << m_params.sampleRate << ", " << p << ")" << endl;
Chris@10: #endif
cannam@0: 
Chris@43:     m_otherMatcher = p;	// the first matcher will need this to be set later
Chris@43:     m_firstPM = (!p);
Chris@43:     m_frameCount = 0;
Chris@43:     m_runCount = 0;
Chris@43:     m_featureSize = m_featureExtractor.getFeatureSize();
Chris@43:     m_blockSize = 0;
Chris@23: 
Chris@43:     m_blockSize = lrint(m_params.blockTime / m_params.hopTime);
Chris@23: #ifdef DEBUG_MATCHER
Chris@43:     cerr << "Matcher: m_blockSize = " << m_blockSize << endl;
Chris@23: #endif
Chris@23: 
Chris@43:     m_initialised = false;
Chris@23: }
Chris@23: 
Chris@43: Matcher::Matcher(Parameters parameters, Matcher *p, int m_featureSize_) :
Chris@43:     m_params(parameters),
Chris@43:     m_featureSize(m_featureSize_),
Chris@43:     m_featureExtractor(FeatureExtractor::Parameters(m_params.sampleRate, m_params.fftSize)), // unused default config
Chris@43:     m_metric(parameters.distanceNorm)
Chris@23: {
Chris@23: #ifdef DEBUG_MATCHER
Chris@43:     cerr << "Matcher::Matcher(" << m_params.sampleRate << ", " << p << ", " << m_featureSize << ")" << endl;
Chris@23: #endif
Chris@23: 
Chris@43:     m_otherMatcher = p;	// the first matcher will need this to be set later
Chris@43:     m_firstPM = (!p);
Chris@43:     m_frameCount = 0;
Chris@43:     m_runCount = 0;
Chris@43:     m_blockSize = 0;
cannam@0: 
Chris@43:     m_blockSize = lrint(m_params.blockTime / m_params.hopTime);
Chris@15: #ifdef DEBUG_MATCHER
Chris@43:     cerr << "Matcher: m_blockSize = " << m_blockSize << endl;
Chris@15: #endif
cannam@0: 
Chris@43:     m_initialised = false;
Chris@23: } 
cannam@0: 
cannam@0: Matcher::~Matcher()
cannam@0: {
Chris@10: #ifdef DEBUG_MATCHER
Chris@15:     cerr << "Matcher(" << this << ")::~Matcher()" << endl;
Chris@10: #endif
cannam@0: }
cannam@0: 
cannam@0: void
cannam@0: Matcher::init()
cannam@0: {
Chris@43:     if (m_initialised) return;
cannam@0: 
Chris@43:     m_frames = vector<vector<double> >
Chris@43:         (m_blockSize, vector<double>(m_featureSize, 0));
cannam@0: 
Chris@43:     m_distXSize = m_blockSize * 2;
Chris@45: 
Chris@41:     size();
cannam@0: 
Chris@43:     m_frameCount = 0;
Chris@43:     m_runCount = 0;
Chris@38:     
Chris@43:     m_initialised = true;
Chris@16: }
Chris@16: 
cannam@0: void
Chris@41: Matcher::size()
cannam@0: {
Chris@43:     int distSize = (m_params.maxRunCount + 1) * m_blockSize;
Chris@45:     m_bestPathCost.resize(m_distXSize, vector<float>(distSize, 0));
Chris@45:     m_distance.resize(m_distXSize, vector<float>(distSize, 0));
Chris@45:     m_advance.resize(m_distXSize, vector<Advance>(distSize, AdvanceNone));
Chris@43:     m_distYSizes.resize(m_distXSize, distSize);
Chris@43:     m_first.resize(m_distXSize, 0);
Chris@43:     m_last.resize(m_distXSize, 0);
Chris@38: }
cannam@0: 
Chris@14: vector<double>
Chris@21: Matcher::consumeFrame(double *reBuffer, double *imBuffer)
cannam@0: {
Chris@43:     if (!m_initialised) init();
cannam@0: 
Chris@43:     vector<double> real(reBuffer, reBuffer + m_params.fftSize/2 + 1);
Chris@43:     vector<double> imag(imBuffer, imBuffer + m_params.fftSize/2 + 1);
Chris@43:     vector<double> feature = m_featureExtractor.process(real, imag);
Chris@43:     int frameIndex = m_frameCount % m_blockSize;
Chris@43:     m_frames[frameIndex] = feature;
Chris@21:     calcAdvance();
Chris@21: 
Chris@38:     return feature;
Chris@23: }
Chris@21: 
Chris@23: void
Chris@23: Matcher::consumeFeatureVector(std::vector<double> feature)
Chris@23: {
Chris@43:     if (!m_initialised) init();
Chris@43:     int frameIndex = m_frameCount % m_blockSize; 
Chris@43:     m_frames[frameIndex] = feature;
Chris@23:     calcAdvance();
Chris@21: }
Chris@21: 
Chris@21: void
Chris@21: Matcher::calcAdvance()
Chris@21: {
Chris@43:     int frameIndex = m_frameCount % m_blockSize;
Chris@21: 
Chris@43:     if (m_frameCount >= m_distXSize) {
Chris@43:         m_distXSize *= 2;
Chris@41:         size();
cannam@0:     }
cannam@0: 
Chris@43:     if (m_firstPM && (m_frameCount >= m_blockSize)) {
cannam@0: 
Chris@43:         int len = m_last[m_frameCount - m_blockSize] -
Chris@43:                  m_first[m_frameCount - m_blockSize];
cannam@0: 
Chris@43:         // We need to copy distance[m_frameCount-m_blockSize] to
Chris@43:         // distance[m_frameCount], and then truncate
Chris@43:         // distance[m_frameCount-m_blockSize] to its first len elements.
cannam@0:         // Same for bestPathCost.
cannam@0: /*
Chris@43:         std::cerr << "Matcher(" << this << "): moving " << distYSizes[m_frameCount - m_blockSize] << " from " << m_frameCount - m_blockSize << " to "
Chris@43:                   << m_frameCount << ", allocating " << len << " for "
Chris@43:                   << m_frameCount - m_blockSize << std::endl;
cannam@0: */
Chris@43:         m_distance[m_frameCount] = m_distance[m_frameCount - m_blockSize];
Chris@43:         m_distance[m_frameCount - m_blockSize].resize(len, 0);
cannam@0: 
Chris@43:         m_bestPathCost[m_frameCount] = m_bestPathCost[m_frameCount - m_blockSize];
Chris@43:         m_bestPathCost[m_frameCount - m_blockSize].resize(len, 0);
cannam@0: 
Chris@45:         m_advance[m_frameCount] = m_advance[m_frameCount - m_blockSize];
Chris@45:         m_advance[m_frameCount - m_blockSize].resize(len);
Chris@45:         
Chris@43:         m_distYSizes[m_frameCount] = m_distYSizes[m_frameCount - m_blockSize];
Chris@43:         m_distYSizes[m_frameCount - m_blockSize] = len;
cannam@0:     }
cannam@0: 
Chris@43:     int stop = m_otherMatcher->m_frameCount;
Chris@43:     int index = stop - m_blockSize;
cannam@0:     if (index < 0)
cannam@0:         index = 0;
Chris@43:     m_first[m_frameCount] = index;
Chris@43:     m_last[m_frameCount] = stop;
cannam@0: 
cannam@0:     bool overflow = false;
cannam@0:     int mn= -1;
cannam@0:     int mx= -1;
cannam@0:     for ( ; index < stop; index++) {
Chris@26: 
Chris@45:         float dMN = m_metric.calcDistance
Chris@43:             (m_frames[frameIndex],
Chris@45:              m_otherMatcher->m_frames[index % m_blockSize]);
Chris@26:         
cannam@0:         if (mx<0)
cannam@0:             mx = mn = dMN;
cannam@0:         else if (dMN > mx)
cannam@0:             mx = dMN;
cannam@0:         else if (dMN < mn)
cannam@0:             mn = dMN;
cannam@0:         if (dMN >= 255) {
cannam@0:             overflow = true;
cannam@0:             dMN = 255;
cannam@0:         }
Chris@26: 
Chris@43:         if ((m_frameCount == 0) && (index == 0))    // first element
Chris@45:             setValue(0, 0, AdvanceNone, 0, dMN);
Chris@43:         else if (m_frameCount == 0)                 // first row
Chris@45:             setValue(0, index, AdvanceOther,
cannam@0:                      getValue(0, index-1, true), dMN);
cannam@0:         else if (index == 0)                      // first column
Chris@45:             setValue(m_frameCount, index, AdvanceThis,
Chris@43:                      getValue(m_frameCount - 1, 0, true), dMN);
Chris@43:         else if (index == m_otherMatcher->m_frameCount - m_blockSize) {
cannam@0:             // missing value(s) due to cutoff
cannam@0:             //  - no previous value in current row (resp. column)
cannam@0:             //  - no diagonal value if prev. dir. == curr. dirn
Chris@43:             int min2 = getValue(m_frameCount - 1, index, true);
Chris@43:             //	if ((m_firstPM && (first[m_frameCount - 1] == index)) ||
Chris@43:             //			(!m_firstPM && (m_last[index-1] < m_frameCount)))
Chris@43:             if (m_first[m_frameCount - 1] == index)
Chris@45:                 setValue(m_frameCount, index, AdvanceThis, min2, dMN);
cannam@0:             else {
Chris@43:                 int min1 = getValue(m_frameCount - 1, index - 1, true);
cannam@0:                 if (min1 + dMN <= min2)
Chris@45:                     setValue(m_frameCount, index, AdvanceBoth, min1,dMN);
cannam@0:                 else
Chris@45:                     setValue(m_frameCount, index, AdvanceThis, min2,dMN);
cannam@0:             }
cannam@0:         } else {
Chris@43:             int min1 = getValue(m_frameCount, index-1, true);
Chris@43:             int min2 = getValue(m_frameCount - 1, index, true);
Chris@43:             int min3 = getValue(m_frameCount - 1, index-1, true);
cannam@0:             if (min1 <= min2) {
cannam@0:                 if (min3 + dMN <= min1)
Chris@45:                     setValue(m_frameCount, index, AdvanceBoth, min3,dMN);
cannam@0:                 else
Chris@45:                     setValue(m_frameCount, index, AdvanceOther,min1,dMN);
cannam@0:             } else {
cannam@0:                 if (min3 + dMN <= min2)
Chris@45:                     setValue(m_frameCount, index, AdvanceBoth, min3,dMN);
cannam@0:                 else
Chris@45:                     setValue(m_frameCount, index, AdvanceThis, min2,dMN);
cannam@0:             }
cannam@0:         }
Chris@43:         m_otherMatcher->m_last[index]++;
cannam@0:     } // loop for row (resp. column)
cannam@0: 
Chris@43:     m_frameCount++;
Chris@43:     m_runCount++;
cannam@0: 
Chris@43:     m_otherMatcher->m_runCount = 0;
cannam@0: 
Chris@43:     if (overflow) {
cannam@0:         cerr << "WARNING: overflow in distance metric: "
Chris@43:              << "frame " << m_frameCount << ", val = " << mx << endl;
Chris@43:     }
Chris@21: }
cannam@0: 
cannam@0: int
cannam@0: Matcher::getValue(int i, int j, bool firstAttempt)
cannam@0: {
Chris@43:     if (m_firstPM)
Chris@43:         return m_bestPathCost[i][j - m_first[i]];
cannam@0:     else
Chris@43:         return m_otherMatcher->m_bestPathCost[j][i - m_otherMatcher->m_first[j]];
cannam@0: } // getValue()
cannam@0: 
cannam@0: void
Chris@45: Matcher::setValue(int i, int j, Advance dir, float value, float dMN)
cannam@0: {
Chris@43:     if (m_firstPM) {
Chris@45: 
Chris@45:         int jdx = j - m_first[i];
Chris@45:         m_distance[i][jdx] = dMN;
Chris@45:         m_advance[i][jdx] = dir;
Chris@45:         m_bestPathCost[i][jdx] =
Chris@45:             (value + (dir == AdvanceBoth ? dMN*2: dMN));
Chris@45: 
cannam@0:     } else {
Chris@45: 
Chris@45:         if (dir == AdvanceThis) {
Chris@45:             dir = AdvanceOther;
Chris@45:         } else if (dir == AdvanceOther) {
Chris@45:             dir = AdvanceThis;
Chris@45:         }
Chris@45: 
Chris@43:         int idx = i - m_otherMatcher->m_first[j];
Chris@45:         
Chris@43:         if (idx == (int)m_otherMatcher->m_distYSizes[j]) {
cannam@0:             // This should never happen, but if we allow arbitrary
cannam@0:             // pauses in either direction, and arbitrary lengths at
cannam@0:             // end, it is better than a segmentation fault.
cannam@0:             std::cerr << "Emergency resize: " << idx << " -> " << idx * 2 << std::endl;
Chris@43:             m_otherMatcher->m_distYSizes[j] = idx * 2;
Chris@43:             m_otherMatcher->m_bestPathCost[j].resize(idx * 2, 0);
Chris@43:             m_otherMatcher->m_distance[j].resize(idx * 2, 0);
cannam@0:         }
Chris@45: 
Chris@45:         m_otherMatcher->m_distance[j][idx] = dMN;
Chris@45:         m_otherMatcher->m_advance[j][idx] = dir;
Chris@43:         m_otherMatcher->m_bestPathCost[j][idx] =
Chris@45:             (value + (dir == AdvanceBoth ? dMN*2: dMN));
cannam@0:     }
cannam@0: } // setValue()
cannam@0: