Mercurial > hg > match-vamp
changeset 45:a1b7df871496 refactors
Replace char dist (inc dir in masked section) with float dist + separate dir
| author | Chris Cannam |
|---|---|
| date | Thu, 13 Nov 2014 14:43:03 +0000 |
| parents | c1112adfd270 |
| children | b0ebc3e2c016 |
| files | src/DistanceMetric.cpp src/DistanceMetric.h src/Finder.cpp src/Finder.h src/MatchFeatureFeeder.cpp src/MatchFeeder.cpp src/Matcher.cpp src/Matcher.h |
| diffstat | 8 files changed, 141 insertions(+), 134 deletions(-) [+] |
line wrap: on
line diff
--- a/src/DistanceMetric.cpp Thu Nov 13 13:59:41 2014 +0000 +++ b/src/DistanceMetric.cpp Thu Nov 13 14:43:03 2014 +0000 @@ -56,12 +56,3 @@ return d / sum * weight; } -int -DistanceMetric::calcDistanceScaled(const vector<double> &f1, - const vector<double> &f2, - double scale) -{ - double distance = calcDistance(f1, f2); - return int(distance * scale); -} -
--- a/src/DistanceMetric.h Thu Nov 13 13:59:41 2014 +0000 +++ b/src/DistanceMetric.h Thu Nov 13 14:43:03 2014 +0000 @@ -51,21 +51,6 @@ double calcDistance(const std::vector<double> &f1, const std::vector<double> &f2); - /** Calculates the Manhattan distance between two vectors, with an - * optional normalisation by the combined values in the - * vectors. Since the vectors contain energy, this could be - * considered as a squared Euclidean distance metric. Note that - * normalisation assumes the values are all non-negative. - * - * @param f1 one of the vectors involved in the distance calculation - * @param f2 one of the vectors involved in the distance calculation - * @param scale the scaling factor to place the result in integer range - * @return the distance, scaled by scale and truncated to an integer - */ - int calcDistanceScaled(const std::vector<double> &f1, - const std::vector<double> &f2, - double scale); - private: DistanceNormalisation m_norm; };
--- a/src/Finder.cpp Thu Nov 13 13:59:41 2014 +0000 +++ b/src/Finder.cpp Thu Nov 13 14:43:03 2014 +0000 @@ -63,13 +63,13 @@ range[1] = pm2->m_last[col]; } // getRowRange() -int +Matcher::Advance Finder::getExpandDirection(int row, int col) { return getExpandDirection(row, col, false); } // getExpandDirection() -int +Matcher::Advance Finder::getExpandDirection(int row, int col, bool check) { int min = getPathCost(row, col); @@ -100,17 +100,28 @@ // System.err.println(" " + pm1->frameCount + " " + pm2->frameCount); if (check) { // System.err.println(find(row+1, col) + " " + find(row, col+1)); - if (!find(row, col+1)) - return ADVANCE_THIS; - if (!find(row+1, col)) - return ADVANCE_OTHER; + if (!find(row, col+1)) { + return Matcher::AdvanceThis; + } else if (!find(row+1, col)) { + return Matcher::AdvanceOther; + } } - return ((bestRow==row)? ADVANCE_THIS: 0) | - ((bestCol==col)? ADVANCE_OTHER: 0); + + if (bestRow == row) { + if (bestCol == col) { + return Matcher::AdvanceBoth; + } else { + return Matcher::AdvanceThis; + } + } else if (bestCol == col) { + return Matcher::AdvanceOther; + } else { + return Matcher::AdvanceBoth; + } } // getExpandDirection() -unsigned char +float Finder::getDistance(int row, int col) { if (find(row, col)) { @@ -121,7 +132,7 @@ } // getDistance()/2 void -Finder::setDistance(int row, int col, unsigned char b) +Finder::setDistance(int row, int col, float b) { if (find(row, col)) { pm1->m_distance[row][col - pm1->m_first[row]] = b; @@ -131,16 +142,16 @@ throw "setDistance index out of bounds"; } // setDistance() -int +float Finder::getPathCost(int row, int col) { if (find(row, col)) // "1" avoids div by 0 below - return pm1->m_bestPathCost[row][col - pm1->m_first[row]]*100/ (1+row+col); + return pm1->m_bestPathCost[row][col - pm1->m_first[row]] / float(1+row+col); std::cerr << "getPathCost(" << row << "," << col << "): out of bounds" << std::endl; throw "getPathCost index out of bounds"; } // getPathCost() -int +float Finder::getRawPathCost(int row, int col) { if (find(row, col)) @@ -150,38 +161,50 @@ } // getRawPathCost() void -Finder::setPathCost(int row, int col, int i) +Finder::setPathCost(int row, int col, float cost) { if (find(row, col)) { - pm1->m_bestPathCost[row][col - pm1->m_first[row]] = i; + pm1->m_bestPathCost[row][col - pm1->m_first[row]] = cost; return; } - std::cerr << "setPathCost(" << row << "," << col << "," << i << "): out of bounds" << std::endl; + std::cerr << "setPathCost(" << row << "," << col << "," << cost << "): out of bounds" << std::endl; throw "setPathCost index out of bounds"; } // setPathCost() -unsigned char +Matcher::Advance +Finder::getAdvance() +{ + return pm1->m_advance[index1][index2]; +} + +void +Finder::setAdvance(Matcher::Advance a) +{ + pm1->m_advance[index1][index2] = a; +} + +float Finder::getDistance() { return pm1->m_distance[index1][index2]; } // getDistance()/0 void -Finder::setDistance(int b) +Finder::setDistance(float b) { - pm1->m_distance[index1][index2] = (unsigned char)b; + pm1->m_distance[index1][index2] = b; } // setDistance() -int +float Finder::getPathCost() { return pm1->m_bestPathCost[index1][index2]; } // getPathCost() void -Finder::setPathCost(int i) +Finder::setPathCost(float cost) { - pm1->m_bestPathCost[index1][index2] = i; + pm1->m_bestPathCost[index1][index2] = cost; } // setPathCost() void @@ -201,14 +224,14 @@ if (find(r,c)) { int i2 = index2; int newCost = pm1->m_distance[r][i2]; - int dir = 0; + Matcher::Advance dir = Matcher::AdvanceNone; if (r > r1) { // not first row int min = -1; if ((c > prevRowStart) && (c <= prevRowStop)) { // diagonal from (r-1,c-1) min = pm1->m_bestPathCost[r-1][c-pm1->m_first[r-1]-1] + newCost * 2; - dir = ADVANCE_BOTH; + dir = Matcher::AdvanceBoth; } if ((c >= prevRowStart) && (c < prevRowStop)) { // vertical from (r-1,c) @@ -216,7 +239,7 @@ newCost; if ((min == -1) || (cost < min)) { min = cost; - dir = ADVANCE_THIS; + dir = Matcher::AdvanceThis; } } if (c > thisRowStart) { @@ -224,7 +247,7 @@ int cost =pm1->m_bestPathCost[r][i2-1]+newCost; if ((min == -1) || (cost < min)) { min = cost; - dir = ADVANCE_OTHER; + dir = Matcher::AdvanceOther; } } pm1->m_bestPathCost[r][i2] = min; @@ -232,12 +255,9 @@ // horizontal from (r,c-1) pm1->m_bestPathCost[r][i2] = pm1->m_bestPathCost[r][i2-1] + newCost; - dir = ADVANCE_OTHER; + dir = Matcher::AdvanceOther; } - if ((r != r1) || (c != c1)) { - pm1->m_distance[r][i2] = (unsigned char) - ((pm1->m_distance[r][i2] & MASK) | dir); - } + pm1->m_advance[r][i2] = dir; } else break; // end of row } @@ -262,21 +282,21 @@ pathx.push_back(x); pathy.push_back(y); - switch (getDistance() & ADVANCE_BOTH) { - case ADVANCE_THIS: + switch (getAdvance()) { + case Matcher::AdvanceThis: // cerr << ", going down (dist = " << (int)getDistance() << ")" << endl; y--; break; - case ADVANCE_OTHER: + case Matcher::AdvanceOther: // cerr << ", going left (dist = " << (int)getDistance() << ")" << endl; x--; break; - case ADVANCE_BOTH: + case Matcher::AdvanceBoth: // cerr << ", going diag (dist = " << (int)getDistance() << ")" << endl; x--; y--; break; - default: // this would indicate a bug, but we wouldn't want to hang + case Matcher::AdvanceNone: // this would indicate a bug, but we wouldn't want to hang // cerr << "WARNING: Neither matcher advanced in path backtrack at (" << x << "," << y << ")" << endl; if (x > y) { x--;
--- a/src/Finder.h Thu Nov 13 13:59:41 2014 +0000 +++ b/src/Finder.h Thu Nov 13 14:43:03 2014 +0000 @@ -57,21 +57,24 @@ * column. */ void getRowRange(int col, int *range); - int getExpandDirection(int row, int col); - int getExpandDirection(int row, int col, bool check); + Matcher::Advance getExpandDirection(int row, int col); + Matcher::Advance getExpandDirection(int row, int col, bool check); - unsigned char getDistance(int row, int col); - void setDistance(int row, int col, unsigned char b); + float getDistance(int row, int col); + void setDistance(int row, int col, float b); - int getPathCost(int row, int col); - int getRawPathCost(int row, int col); - void setPathCost(int row, int col, int i); + float getPathCost(int row, int col); + float getRawPathCost(int row, int col); //!!!??? + void setPathCost(int row, int col, float i); - unsigned char getDistance(); - void setDistance(int b); + Matcher::Advance getAdvance(); + void setAdvance(Matcher::Advance a); + + float getDistance(); + void setDistance(float b); - int getPathCost(); - void setPathCost(int i); + float getPathCost(); + void setPathCost(float i); /** Calculates a rectangle of the path cost matrix so that the * minimum cost path between the bottom left and top right
--- a/src/MatchFeatureFeeder.cpp Thu Nov 13 13:59:41 2014 +0000 +++ b/src/MatchFeatureFeeder.cpp Thu Nov 13 14:43:03 2014 +0000 @@ -54,16 +54,19 @@ } else { switch (finder->getExpandDirection (pm1->m_frameCount-1, pm2->m_frameCount-1)) { - case ADVANCE_THIS: + case Matcher::AdvanceThis: feed1(); break; - case ADVANCE_OTHER: + case Matcher::AdvanceOther: feed2(); break; - case ADVANCE_BOTH: + case Matcher::AdvanceBoth: feed1(); feed2(); break; + case Matcher::AdvanceNone: + cerr << "finder says AdvanceNone!" << endl; + break; } } }
--- a/src/MatchFeeder.cpp Thu Nov 13 13:59:41 2014 +0000 +++ b/src/MatchFeeder.cpp Thu Nov 13 14:43:03 2014 +0000 @@ -115,19 +115,19 @@ } else { switch (finder->getExpandDirection (pm1->m_frameCount-1, pm2->m_frameCount-1)) { - case ADVANCE_THIS: -// std::cerr << "finder says ADVANCE_THIS" << std::endl; + case Matcher::AdvanceThis: f1 = feed1(); break; - case ADVANCE_OTHER: -// std::cerr << "finder says ADVANCE_OTHER" << std::endl; + case Matcher::AdvanceOther: f2 = feed2(); break; - case ADVANCE_BOTH: -// std::cerr << "finder says ADVANCE_BOTH" << std::endl; + case Matcher::AdvanceBoth: f1 = feed1(); f2 = feed2(); break; + case Matcher::AdvanceNone: + cerr << "finder says AdvanceNone!" << endl; + break; } }
--- a/src/Matcher.cpp Thu Nov 13 13:59:41 2014 +0000 +++ b/src/Matcher.cpp Thu Nov 13 14:43:03 2014 +0000 @@ -89,6 +89,7 @@ (m_blockSize, vector<double>(m_featureSize, 0)); m_distXSize = m_blockSize * 2; + size(); m_frameCount = 0; @@ -101,8 +102,9 @@ Matcher::size() { int distSize = (m_params.maxRunCount + 1) * m_blockSize; - m_bestPathCost.resize(m_distXSize, vector<int>(distSize, 0)); - m_distance.resize(m_distXSize, vector<unsigned char>(distSize, 0)); + m_bestPathCost.resize(m_distXSize, vector<float>(distSize, 0)); + m_distance.resize(m_distXSize, vector<float>(distSize, 0)); + m_advance.resize(m_distXSize, vector<Advance>(distSize, AdvanceNone)); m_distYSizes.resize(m_distXSize, distSize); m_first.resize(m_distXSize, 0); m_last.resize(m_distXSize, 0); @@ -158,18 +160,13 @@ */ m_distance[m_frameCount] = m_distance[m_frameCount - m_blockSize]; m_distance[m_frameCount - m_blockSize].resize(len, 0); - for (int i = 0; i < len; ++i) { - m_distance[m_frameCount - m_blockSize][i] = - m_distance[m_frameCount][i]; - } m_bestPathCost[m_frameCount] = m_bestPathCost[m_frameCount - m_blockSize]; m_bestPathCost[m_frameCount - m_blockSize].resize(len, 0); - for (int i = 0; i < len; ++i) { - m_bestPathCost[m_frameCount - m_blockSize][i] = - m_bestPathCost[m_frameCount][i]; - } + m_advance[m_frameCount] = m_advance[m_frameCount - m_blockSize]; + m_advance[m_frameCount - m_blockSize].resize(len); + m_distYSizes[m_frameCount] = m_distYSizes[m_frameCount - m_blockSize]; m_distYSizes[m_frameCount - m_blockSize] = len; } @@ -186,10 +183,9 @@ int mx= -1; for ( ; index < stop; index++) { - int dMN = m_metric.calcDistanceScaled + float dMN = m_metric.calcDistance (m_frames[frameIndex], - m_otherMatcher->m_frames[index % m_blockSize], - m_params.distanceScale); + m_otherMatcher->m_frames[index % m_blockSize]); if (mx<0) mx = mn = dMN; @@ -203,12 +199,12 @@ } if ((m_frameCount == 0) && (index == 0)) // first element - setValue(0, 0, 0, 0, dMN); + setValue(0, 0, AdvanceNone, 0, dMN); else if (m_frameCount == 0) // first row - setValue(0, index, ADVANCE_OTHER, + setValue(0, index, AdvanceOther, getValue(0, index-1, true), dMN); else if (index == 0) // first column - setValue(m_frameCount, index, ADVANCE_THIS, + setValue(m_frameCount, index, AdvanceThis, getValue(m_frameCount - 1, 0, true), dMN); else if (index == m_otherMatcher->m_frameCount - m_blockSize) { // missing value(s) due to cutoff @@ -218,13 +214,13 @@ // if ((m_firstPM && (first[m_frameCount - 1] == index)) || // (!m_firstPM && (m_last[index-1] < m_frameCount))) if (m_first[m_frameCount - 1] == index) - setValue(m_frameCount, index, ADVANCE_THIS, min2, dMN); + setValue(m_frameCount, index, AdvanceThis, min2, dMN); else { int min1 = getValue(m_frameCount - 1, index - 1, true); if (min1 + dMN <= min2) - setValue(m_frameCount, index, ADVANCE_BOTH, min1,dMN); + setValue(m_frameCount, index, AdvanceBoth, min1,dMN); else - setValue(m_frameCount, index, ADVANCE_THIS, min2,dMN); + setValue(m_frameCount, index, AdvanceThis, min2,dMN); } } else { int min1 = getValue(m_frameCount, index-1, true); @@ -232,14 +228,14 @@ int min3 = getValue(m_frameCount - 1, index-1, true); if (min1 <= min2) { if (min3 + dMN <= min1) - setValue(m_frameCount, index, ADVANCE_BOTH, min3,dMN); + setValue(m_frameCount, index, AdvanceBoth, min3,dMN); else - setValue(m_frameCount, index, ADVANCE_OTHER,min1,dMN); + setValue(m_frameCount, index, AdvanceOther,min1,dMN); } else { if (min3 + dMN <= min2) - setValue(m_frameCount, index, ADVANCE_BOTH, min3,dMN); + setValue(m_frameCount, index, AdvanceBoth, min3,dMN); else - setValue(m_frameCount, index, ADVANCE_THIS, min2,dMN); + setValue(m_frameCount, index, AdvanceThis, min2,dMN); } } m_otherMatcher->m_last[index]++; @@ -266,18 +262,26 @@ } // getValue() void -Matcher::setValue(int i, int j, int dir, int value, int dMN) +Matcher::setValue(int i, int j, Advance dir, float value, float dMN) { if (m_firstPM) { - m_distance[i][j - m_first[i]] = (unsigned char)((dMN & MASK) | dir); - m_bestPathCost[i][j - m_first[i]] = - (value + (dir==ADVANCE_BOTH? dMN*2: dMN)); + + int jdx = j - m_first[i]; + m_distance[i][jdx] = dMN; + m_advance[i][jdx] = dir; + m_bestPathCost[i][jdx] = + (value + (dir == AdvanceBoth ? dMN*2: dMN)); + } else { - if (dir == ADVANCE_THIS) - dir = ADVANCE_OTHER; - else if (dir == ADVANCE_OTHER) - dir = ADVANCE_THIS; + + if (dir == AdvanceThis) { + dir = AdvanceOther; + } else if (dir == AdvanceOther) { + dir = AdvanceThis; + } + int idx = i - m_otherMatcher->m_first[j]; + if (idx == (int)m_otherMatcher->m_distYSizes[j]) { // This should never happen, but if we allow arbitrary // pauses in either direction, and arbitrary lengths at @@ -287,9 +291,11 @@ m_otherMatcher->m_bestPathCost[j].resize(idx * 2, 0); m_otherMatcher->m_distance[j].resize(idx * 2, 0); } - m_otherMatcher->m_distance[j][idx] = (unsigned char)((dMN & MASK) | dir); + + m_otherMatcher->m_distance[j][idx] = dMN; + m_otherMatcher->m_advance[j][idx] = dir; m_otherMatcher->m_bestPathCost[j][idx] = - (value + (dir==ADVANCE_BOTH? dMN*2: dMN)); + (value + (dir == AdvanceBoth ? dMN*2: dMN)); } } // setValue()
--- a/src/Matcher.h Thu Nov 13 13:59:41 2014 +0000 +++ b/src/Matcher.h Thu Nov 13 14:43:03 2014 +0000 @@ -22,11 +22,6 @@ #include <sstream> #include <cmath> -#define ADVANCE_THIS 1 -#define ADVANCE_OTHER 2 -#define ADVANCE_BOTH 3 -#define MASK 0xfc - #include "DistanceMetric.h" #include "FeatureExtractor.h" @@ -37,19 +32,23 @@ /** Represents an audio stream that can be matched to another audio * stream of the same piece of music. The matching algorithm uses - * dynamic time warping. The distance metric is a Euclidean metric - * on the FFT data with the higher frequencies mapped onto a linear - * scale. + * dynamic time warping. */ class Matcher { public: + enum Advance { + AdvanceNone, + AdvanceBoth, + AdvanceThis, + AdvanceOther + }; + struct Parameters { Parameters(float rate_, double hopTime_, int fftSize_) : sampleRate(rate_), distanceNorm(DistanceMetric::NormaliseDistanceToLogSum), - distanceScale(90.0), hopTime(hopTime_), fftSize(fftSize_), blockTime(10.0), @@ -62,12 +61,6 @@ /** Type of distance metric normalisation */ DistanceMetric::DistanceNormalisation distanceNorm; - /** Scaling factor for distance metric; must guarantee that the - * final value fits in the data type used, that is, unsigned - * char. - */ - double distanceScale; - /** Spacing of audio frames (determines the amount of overlap or * skip between frames). This value is expressed in * seconds. */ @@ -186,7 +179,7 @@ * @param value the cost of the minimum path except the current step * @param dMN the distance cost between the two frames */ - void setValue(int i, int j, int dir, int value, int dMN); + void setValue(int i, int j, Advance dir, float value, float dMN); void calcAdvance(); @@ -231,19 +224,25 @@ vector<vector<double> > m_frames; /** The best path cost matrix. */ - vector<vector<int> > m_bestPathCost; + vector<vector<float> > m_bestPathCost; /** The distance matrix. */ - vector<vector<unsigned char> > m_distance; + vector<vector<float> > m_distance; - /** The bounds of each row of data in the distance and path cost matrices.*/ + /** The advance direction matrix. */ + vector<vector<Advance> > m_advance; + + /** The bounds of each row of data in the distance, path cost, and + * advance direction matrices.*/ vector<int> m_first; vector<int> m_last; - /** Height of each column in distance and bestPathCost matrices */ + /** Height of each column in distance, path cost, and advance + * direction matrices. */ vector<int> m_distYSizes; - /** Width of distance and bestPathCost matrices and first and last vectors */ + /** Width of distance, path cost, and advance direction matrices + * and first and last vectors */ int m_distXSize; bool m_initialised;