cannam@198: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
cannam@198: 
cannam@198: /*
cannam@198:     Vamp
cannam@198: 
cannam@198:     An API for audio analysis and feature extraction plugins.
cannam@198: 
cannam@198:     Centre for Digital Music, Queen Mary, University of London.
cannam@198:     Copyright 2006-2008 Chris Cannam and QMUL.
cannam@198:   
cannam@198:     Permission is hereby granted, free of charge, to any person
cannam@198:     obtaining a copy of this software and associated documentation
cannam@198:     files (the "Software"), to deal in the Software without
cannam@198:     restriction, including without limitation the rights to use, copy,
cannam@198:     modify, merge, publish, distribute, sublicense, and/or sell copies
cannam@198:     of the Software, and to permit persons to whom the Software is
cannam@198:     furnished to do so, subject to the following conditions:
cannam@198: 
cannam@198:     The above copyright notice and this permission notice shall be
cannam@198:     included in all copies or substantial portions of the Software.
cannam@198: 
cannam@198:     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
cannam@198:     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
cannam@198:     MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
cannam@198:     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR
cannam@198:     ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
cannam@198:     CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
cannam@198:     WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
cannam@198: 
cannam@198:     Except as contained in this notice, the names of the Centre for
cannam@198:     Digital Music; Queen Mary, University of London; and Chris Cannam
cannam@198:     shall not be used in advertising or otherwise to promote the sale,
cannam@198:     use or other dealings in this Software without prior written
cannam@198:     authorization.
cannam@198: */
cannam@198: 
cannam@198: #include "FixedTempoEstimator.h"
cannam@198: 
cannam@198: using std::string;
cannam@198: using std::vector;
cannam@198: using std::cerr;
cannam@198: using std::endl;
cannam@198: 
cannam@198: using Vamp::RealTime;
cannam@198: 
cannam@198: #include <cmath>
cannam@198: 
cannam@198: 
cannam@198: FixedTempoEstimator::FixedTempoEstimator(float inputSampleRate) :
cannam@198:     Plugin(inputSampleRate),
cannam@198:     m_stepSize(0),
cannam@198:     m_blockSize(0),
cannam@198:     m_priorMagnitudes(0),
cannam@200:     m_df(0),
cannam@200:     m_r(0),
cannam@200:     m_fr(0),
cannam@204:     m_t(0),
cannam@200:     m_n(0)
cannam@198: {
cannam@198: }
cannam@198: 
cannam@198: FixedTempoEstimator::~FixedTempoEstimator()
cannam@198: {
cannam@198:     delete[] m_priorMagnitudes;
cannam@198:     delete[] m_df;
cannam@200:     delete[] m_r;
cannam@200:     delete[] m_fr;
cannam@204:     delete[] m_t;
cannam@198: }
cannam@198: 
cannam@198: string
cannam@198: FixedTempoEstimator::getIdentifier() const
cannam@198: {
cannam@198:     return "fixedtempo";
cannam@198: }
cannam@198: 
cannam@198: string
cannam@198: FixedTempoEstimator::getName() const
cannam@198: {
cannam@198:     return "Simple Fixed Tempo Estimator";
cannam@198: }
cannam@198: 
cannam@198: string
cannam@198: FixedTempoEstimator::getDescription() const
cannam@198: {
cannam@198:     return "Study a short section of audio and estimate its tempo, assuming the tempo is constant";
cannam@198: }
cannam@198: 
cannam@198: string
cannam@198: FixedTempoEstimator::getMaker() const
cannam@198: {
cannam@198:     return "Vamp SDK Example Plugins";
cannam@198: }
cannam@198: 
cannam@198: int
cannam@198: FixedTempoEstimator::getPluginVersion() const
cannam@198: {
cannam@198:     return 1;
cannam@198: }
cannam@198: 
cannam@198: string
cannam@198: FixedTempoEstimator::getCopyright() const
cannam@198: {
cannam@198:     return "Code copyright 2008 Queen Mary, University of London.  Freely redistributable (BSD license)";
cannam@198: }
cannam@198: 
cannam@198: size_t
cannam@198: FixedTempoEstimator::getPreferredStepSize() const
cannam@198: {
cannam@198:     return 0;
cannam@198: }
cannam@198: 
cannam@198: size_t
cannam@198: FixedTempoEstimator::getPreferredBlockSize() const
cannam@198: {
cannam@202:     return 128;
cannam@198: }
cannam@198: 
cannam@198: bool
cannam@198: FixedTempoEstimator::initialise(size_t channels, size_t stepSize, size_t blockSize)
cannam@198: {
cannam@198:     if (channels < getMinChannelCount() ||
cannam@198: 	channels > getMaxChannelCount()) return false;
cannam@198: 
cannam@198:     m_stepSize = stepSize;
cannam@198:     m_blockSize = blockSize;
cannam@198: 
cannam@198:     float dfLengthSecs = 8.f;
cannam@198:     m_dfsize = (dfLengthSecs * m_inputSampleRate) / m_stepSize;
cannam@198: 
cannam@198:     m_priorMagnitudes = new float[m_blockSize/2];
cannam@198:     m_df = new float[m_dfsize];
cannam@198: 
cannam@198:     for (size_t i = 0; i < m_blockSize/2; ++i) {
cannam@198:         m_priorMagnitudes[i] = 0.f;
cannam@198:     }
cannam@198:     for (size_t i = 0; i < m_dfsize; ++i) {
cannam@198:         m_df[i] = 0.f;
cannam@198:     }
cannam@198: 
cannam@198:     m_n = 0;
cannam@198: 
cannam@198:     return true;
cannam@198: }
cannam@198: 
cannam@198: void
cannam@198: FixedTempoEstimator::reset()
cannam@198: {
cannam@198:     std::cerr << "FixedTempoEstimator: reset called" << std::endl;
cannam@198: 
cannam@198:     if (!m_priorMagnitudes) return;
cannam@198: 
cannam@198:     std::cerr << "FixedTempoEstimator: resetting" << std::endl;
cannam@198: 
cannam@198:     for (size_t i = 0; i < m_blockSize/2; ++i) {
cannam@198:         m_priorMagnitudes[i] = 0.f;
cannam@198:     }
cannam@198:     for (size_t i = 0; i < m_dfsize; ++i) {
cannam@198:         m_df[i] = 0.f;
cannam@198:     }
cannam@198: 
cannam@200:     delete[] m_r;
cannam@200:     m_r = 0;
cannam@200: 
cannam@200:     delete[] m_fr; 
cannam@200:     m_fr = 0;
cannam@200: 
cannam@204:     delete[] m_t; 
cannam@204:     m_t = 0;
cannam@204: 
cannam@198:     m_n = 0;
cannam@198: 
cannam@198:     m_start = RealTime::zeroTime;
cannam@198:     m_lasttime = RealTime::zeroTime;
cannam@198: }
cannam@198: 
cannam@198: FixedTempoEstimator::ParameterList
cannam@198: FixedTempoEstimator::getParameterDescriptors() const
cannam@198: {
cannam@198:     ParameterList list;
cannam@198:     return list;
cannam@198: }
cannam@198: 
cannam@198: float
cannam@198: FixedTempoEstimator::getParameter(std::string id) const
cannam@198: {
cannam@198:     return 0.f;
cannam@198: }
cannam@198: 
cannam@198: void
cannam@198: FixedTempoEstimator::setParameter(std::string id, float value)
cannam@198: {
cannam@198: }
cannam@198: 
cannam@200: static int TempoOutput = 0;
cannam@200: static int CandidatesOutput = 1;
cannam@200: static int DFOutput = 2;
cannam@200: static int ACFOutput = 3;
cannam@200: static int FilteredACFOutput = 4;
cannam@200: 
cannam@198: FixedTempoEstimator::OutputList
cannam@198: FixedTempoEstimator::getOutputDescriptors() const
cannam@198: {
cannam@198:     OutputList list;
cannam@198: 
cannam@198:     OutputDescriptor d;
cannam@198:     d.identifier = "tempo";
cannam@198:     d.name = "Tempo";
cannam@198:     d.description = "Estimated tempo";
cannam@198:     d.unit = "bpm";
cannam@198:     d.hasFixedBinCount = true;
cannam@198:     d.binCount = 1;
cannam@198:     d.hasKnownExtents = false;
cannam@198:     d.isQuantized = false;
cannam@198:     d.sampleType = OutputDescriptor::VariableSampleRate;
cannam@198:     d.sampleRate = m_inputSampleRate;
cannam@198:     d.hasDuration = true; // our returned tempo spans a certain range
cannam@198:     list.push_back(d);
cannam@198: 
cannam@200:     d.identifier = "candidates";
cannam@200:     d.name = "Tempo candidates";
cannam@200:     d.description = "Possible tempo estimates, one per bin with the most likely in the first bin";
cannam@200:     d.unit = "bpm";
cannam@200:     d.hasFixedBinCount = false;
cannam@200:     list.push_back(d);
cannam@200: 
cannam@198:     d.identifier = "detectionfunction";
cannam@198:     d.name = "Detection Function";
cannam@198:     d.description = "Onset detection function";
cannam@198:     d.unit = "";
cannam@198:     d.hasFixedBinCount = 1;
cannam@198:     d.binCount = 1;
cannam@198:     d.hasKnownExtents = true;
cannam@198:     d.minValue = 0.0;
cannam@198:     d.maxValue = 1.0;
cannam@198:     d.isQuantized = false;
cannam@198:     d.quantizeStep = 0.0;
cannam@198:     d.sampleType = OutputDescriptor::FixedSampleRate;
cannam@198:     if (m_stepSize) {
cannam@198:         d.sampleRate = m_inputSampleRate / m_stepSize;
cannam@198:     } else {
cannam@198:         d.sampleRate = m_inputSampleRate / (getPreferredBlockSize()/2);
cannam@198:     }
cannam@198:     d.hasDuration = false;
cannam@198:     list.push_back(d);
cannam@198: 
cannam@198:     d.identifier = "acf";
cannam@198:     d.name = "Autocorrelation Function";
cannam@198:     d.description = "Autocorrelation of onset detection function";
cannam@198:     d.hasKnownExtents = false;
cannam@201:     d.unit = "r";
cannam@198:     list.push_back(d);
cannam@198: 
cannam@198:     d.identifier = "filtered_acf";
cannam@198:     d.name = "Filtered Autocorrelation";
cannam@198:     d.description = "Filtered autocorrelation of onset detection function";
cannam@201:     d.unit = "r";
cannam@198:     list.push_back(d);
cannam@198: 
cannam@198:     return list;
cannam@198: }
cannam@198: 
cannam@198: FixedTempoEstimator::FeatureSet
cannam@198: FixedTempoEstimator::process(const float *const *inputBuffers, RealTime ts)
cannam@198: {
cannam@198:     FeatureSet fs;
cannam@198: 
cannam@198:     if (m_stepSize == 0) {
cannam@198: 	cerr << "ERROR: FixedTempoEstimator::process: "
cannam@198: 	     << "FixedTempoEstimator has not been initialised"
cannam@198: 	     << endl;
cannam@198: 	return fs;
cannam@198:     }
cannam@198: 
cannam@200: //    if (m_n < m_dfsize) std::cerr << "m_n = " << m_n << std::endl;
cannam@198: 
cannam@198:     if (m_n == 0) m_start = ts;
cannam@198:     m_lasttime = ts;
cannam@198: 
cannam@198:     if (m_n == m_dfsize) {
cannam@200:         calculate();
cannam@200:         fs = assembleFeatures();
cannam@198:         ++m_n;
cannam@198:         return fs;
cannam@198:     }
cannam@198: 
cannam@198:     if (m_n > m_dfsize) return FeatureSet();
cannam@198: 
cannam@198:     int count = 0;
cannam@198: 
cannam@198:     for (size_t i = 1; i < m_blockSize/2; ++i) {
cannam@198: 
cannam@198:         float real = inputBuffers[0][i*2];
cannam@198:         float imag = inputBuffers[0][i*2 + 1];
cannam@198: 
cannam@198:         float sqrmag = real * real + imag * imag;
cannam@198: 
cannam@198:         if (m_priorMagnitudes[i] > 0.f) {
cannam@198:             float diff = 10.f * log10f(sqrmag / m_priorMagnitudes[i]);
cannam@198:             if (diff >= 3.f) ++count;
cannam@198:         }
cannam@198: 
cannam@198:         m_priorMagnitudes[i] = sqrmag;
cannam@198:     }
cannam@198: 
cannam@198:     m_df[m_n] = float(count) / float(m_blockSize/2);
cannam@198:     ++m_n;
cannam@198:     return fs;
cannam@198: }
cannam@198: 
cannam@198: FixedTempoEstimator::FeatureSet
cannam@198: FixedTempoEstimator::getRemainingFeatures()
cannam@198: {
cannam@198:     FeatureSet fs;
cannam@198:     if (m_n > m_dfsize) return fs;
cannam@200:     calculate();
cannam@200:     fs = assembleFeatures();
cannam@198:     ++m_n;
cannam@198:     return fs;
cannam@198: }
cannam@198: 
cannam@198: float
cannam@199: FixedTempoEstimator::lag2tempo(int lag)
cannam@199: {
cannam@198:     return 60.f / ((lag * m_stepSize) / m_inputSampleRate);
cannam@198: }
cannam@198: 
cannam@200: void
cannam@200: FixedTempoEstimator::calculate()
cannam@200: {    
cannam@200:     std::cerr << "FixedTempoEstimator::calculate: m_n = " << m_n << std::endl;
cannam@200:     
cannam@200:     if (m_r) {
cannam@200:         std::cerr << "FixedTempoEstimator::calculate: calculation already happened?" << std::endl;
cannam@200:         return;
cannam@200:     }
cannam@200: 
cannam@200:     if (m_n < m_dfsize / 6) {
cannam@200:         std::cerr << "FixedTempoEstimator::calculate: Not enough data to go on (have " << m_n << ", want at least " << m_dfsize/4 << ")" << std::endl;
cannam@200:         return; // not enough data (perhaps we should return the duration of the input as the "estimated" beat length?)
cannam@200:     }
cannam@200: 
cannam@200:     int n = m_n;
cannam@200: 
cannam@200:     m_r = new float[n/2];
cannam@200:     m_fr = new float[n/2];
cannam@204:     m_t = new float[n/2];
cannam@200: 
cannam@200:     for (int i = 0; i < n/2; ++i) {
cannam@200:         m_r[i] = 0.f;
cannam@200:         m_fr[i] = 0.f;
cannam@204:         m_t[i] = 0.f;
cannam@200:     }
cannam@200: 
cannam@200:     for (int i = 0; i < n/2; ++i) {
cannam@200: 
cannam@200:         for (int j = i; j < n-1; ++j) {
cannam@200:             m_r[i] += m_df[j] * m_df[j - i];
cannam@200:         }
cannam@200: 
cannam@200:         m_r[i] /= n - i - 1;
cannam@200:     }
cannam@200: 
cannam@200:     for (int i = 1; i < n/2; ++i) {
cannam@200: 
cannam@204:         float weight = 1.f - fabsf(128.f - lag2tempo(i)) * 0.005;
cannam@204:         if (weight < 0.f) weight = 0.f;
cannam@204:         weight = weight * weight;
cannam@204:         std::cerr << "i = " << i << ": tempo = " << lag2tempo(i) << ", weight = " << weight << std::endl;
cannam@204: 
cannam@204: //        m_fr[i] = m_r[i];
cannam@204:         m_fr[i] = 0;
cannam@204: 
cannam@204:         m_fr[i] = m_r[i] * (1 + weight/20.f);
cannam@204:     }
cannam@204: 
cannam@204:     float related[4] = { 1.5, 0.66666667, 0.5 };
cannam@204: 
cannam@204:     for (int i = 1; i < n/2 - 1; ++i) {
cannam@204: 
cannam@204:         if (!(m_fr[i] > m_fr[i-1] &&
cannam@204:               m_fr[i] >= m_fr[i+1])) {
cannam@204:             continue;
cannam@204:         }
cannam@204: 
cannam@204:         m_t[i] = lag2tempo(i);
cannam@200: 
cannam@200:         int div = 1;
cannam@200: 
cannam@204:         for (int j = 0; j < sizeof(related)/sizeof(related[0]); ++j) {
cannam@204: 
cannam@204:             int k0 = i / related[j];
cannam@204:             
cannam@204:             if (k0 > 1 && k0 < n/2 - 2) {
cannam@204: 
cannam@204:                 for (int k = k0 - 1; k <= k0 + 1; ++k) {
cannam@204: 
cannam@204:                     if (m_r[k] > m_r[k-1] &&
cannam@204:                         m_r[k] >= m_r[k+1]) {
cannam@204: 
cannam@204:                         std::cerr << "peak at " << i << " (val " << m_r[i] << ", tempo " << lag2tempo(i) << ") has sympathetic peak at " << k << " (val " << m_r[k] << " for relative tempo " << lag2tempo(k) / related[j] << ")" << std::endl;
cannam@204: 
cannam@204:                         m_t[i] = m_t[i] + lag2tempo(k) / related[j];
cannam@204:                         ++div;
cannam@204:                     }
cannam@204:                 }
cannam@204:             }
cannam@204:         }
cannam@204: 
cannam@204:         m_t[i] /= div;
cannam@204:         
cannam@204:         if (div > 1) {
cannam@204:             std::cerr << "adjusting tempo from " << lag2tempo(i) << " to "
cannam@204:                       << m_t[i] << std::endl;
cannam@204:         }
cannam@204:     }
cannam@204: /*
cannam@204:     for (int i = 1; i < n/2; ++i) {
cannam@204: 
cannam@204: //        int div = 1;
cannam@204:         int j = i * 2;
cannam@200:         
cannam@200:         while (j < n/2) {
cannam@204:             m_fr[i] += m_fr[j] * 0.1;
cannam@200:             j *= 2;
cannam@204: //            ++div;
cannam@200:         }
cannam@204: 
cannam@204: //        m_fr[i] /= div;
cannam@204:     }
cannam@204: 
cannam@202: //        std::cerr << "i = " << i << ", (n/2 - 1)/i = " << (n/2 - 1)/i << ", sum = " << m_fr[i] << ", div = " << div << ", val = " << m_fr[i] / div << ", t = " << lag2tempo(i) << std::endl;
cannam@200: 
cannam@200: 
cannam@204: //    }
cannam@204: */
cannam@200:     std::cerr << "FixedTempoEstimator::calculate done" << std::endl;
cannam@200: }
cannam@200:     
cannam@200: 
cannam@198: FixedTempoEstimator::FeatureSet
cannam@200: FixedTempoEstimator::assembleFeatures()
cannam@198: {
cannam@198:     FeatureSet fs;
cannam@200:     if (!m_r) return fs; // No results
cannam@200: 
cannam@198:     Feature feature;
cannam@198:     feature.hasTimestamp = true;
cannam@198:     feature.hasDuration = false;
cannam@198:     feature.label = "";
cannam@198:     feature.values.clear();
cannam@198:     feature.values.push_back(0.f);
cannam@198: 
cannam@200:     char buffer[40];
cannam@198: 
cannam@198:     int n = m_n;
cannam@198: 
cannam@198:     for (int i = 0; i < n; ++i) {
cannam@198:         feature.timestamp = RealTime::frame2RealTime(i * m_stepSize,
cannam@198:                                                      m_inputSampleRate);
cannam@200:         feature.values[0] = m_df[i];
cannam@198:         feature.label = "";
cannam@200:         fs[DFOutput].push_back(feature);
cannam@198:     }
cannam@198: 
cannam@199:     for (int i = 1; i < n/2; ++i) {
cannam@198:         feature.timestamp = RealTime::frame2RealTime(i * m_stepSize,
cannam@198:                                                      m_inputSampleRate);
cannam@200:         feature.values[0] = m_r[i];
cannam@199:         sprintf(buffer, "%.1f bpm", lag2tempo(i));
cannam@200:         if (i == n/2-1) feature.label = "";
cannam@200:         else feature.label = buffer;
cannam@200:         fs[ACFOutput].push_back(feature);
cannam@198:     }
cannam@198: 
cannam@198:     float t0 = 60.f;
cannam@198:     float t1 = 180.f;
cannam@198: 
cannam@198:     int p0 = ((60.f / t1) * m_inputSampleRate) / m_stepSize;
cannam@198:     int p1 = ((60.f / t0) * m_inputSampleRate) / m_stepSize;
cannam@198: 
cannam@200: //    std::cerr << "p0 = " << p0 << ", p1 = " << p1 << std::endl;
cannam@198: 
cannam@198:     int pc = p1 - p0 + 1;
cannam@200: //    std::cerr << "pc = " << pc << std::endl;
cannam@198: 
cannam@200: //    int maxpi = 0;
cannam@200: //    float maxp = 0.f;
cannam@198: 
cannam@200:     std::map<float, int> candidates;
cannam@198: 
cannam@200:     for (int i = p0; i <= p1 && i < n/2-1; ++i) {
cannam@198: 
cannam@200:         // Only candidates here are those that were peaks in the
cannam@200:         // original acf
cannam@200: //        if (r[i] > r[i-1] && r[i] > r[i+1]) {
cannam@200: //            candidates[filtered] = i;
cannam@200: //        }
cannam@198: 
cannam@200:         candidates[m_fr[i]] = i;
cannam@198: 
cannam@198:         feature.timestamp = RealTime::frame2RealTime(i * m_stepSize,
cannam@198:                                                      m_inputSampleRate);
cannam@200:         feature.values[0] = m_fr[i];
cannam@199:         sprintf(buffer, "%.1f bpm", lag2tempo(i));
cannam@200:         if (i == p1 || i == n/2-2) feature.label = "";
cannam@200:         else feature.label = buffer;
cannam@200:         fs[FilteredACFOutput].push_back(feature);
cannam@198:     }
cannam@198: 
cannam@200: //    std::cerr << "maxpi = " << maxpi << " for tempo " << lag2tempo(maxpi) << " (value = " << maxp << ")" << std::endl;
cannam@198: 
cannam@200:     if (candidates.empty()) {
cannam@200:         std::cerr << "No tempo candidates!" << std::endl;
cannam@200:         return fs;
cannam@200:     }
cannam@198: 
cannam@198:     feature.hasTimestamp = true;
cannam@198:     feature.timestamp = m_start;
cannam@198:     
cannam@198:     feature.hasDuration = true;
cannam@198:     feature.duration = m_lasttime - m_start;
cannam@198: 
cannam@200:     std::map<float, int>::const_iterator ci = candidates.end();
cannam@200:     --ci;
cannam@200:     int maxpi = ci->second;
cannam@198: 
cannam@204:     if (m_t[maxpi] > 0) {
cannam@204:         feature.values[0] = m_t[maxpi];
cannam@204:     } else {
cannam@204:         // shouldn't happen -- it would imply that this high value was not a peak!
cannam@204:         feature.values[0] = lag2tempo(maxpi);
cannam@204:         std::cerr << "WARNING: No stored tempo for index " << maxpi << std::endl;
cannam@204:     }
cannam@204: 
cannam@204:     sprintf(buffer, "%.1f bpm", feature.values[0]);
cannam@199:     feature.label = buffer;
cannam@199: 
cannam@200:     fs[TempoOutput].push_back(feature);
cannam@198: 
cannam@200:     feature.values.clear();
cannam@200:     feature.label = "";
cannam@200: 
cannam@200:     while (feature.values.size() < 8) {
cannam@204:         feature.values.push_back(lag2tempo(ci->second)); //!!!??? use m_t?
cannam@200:         if (ci == candidates.begin()) break;
cannam@200:         --ci;
cannam@200:     }
cannam@200: 
cannam@200:     fs[CandidatesOutput].push_back(feature);
cannam@200:     
cannam@198:     return fs;
cannam@198: }