Mercurial > hg > match-vamp
changeset 0:640f92242cc1
* initial import
| author | cannam |
|---|---|
| date | Wed, 24 Oct 2007 12:13:43 +0000 |
| parents | |
| children | de792b8c2801 |
| files | COPYING Finder.cpp Finder.h Makefile MatchFeeder.cpp MatchFeeder.h MatchVampPlugin.cpp MatchVampPlugin.h Matcher.cpp Matcher.h Path.cpp Path.h README match-vamp-plugin.cat |
| diffstat | 14 files changed, 2383 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/COPYING Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,340 @@ + GNU GENERAL PUBLIC LICENSE + Version 2, June 1991 + + Copyright (C) 1989, 1991 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +License is intended to guarantee your freedom to share and change free +software--to make sure the software is free for all its users. This +General Public License applies to most of the Free Software +Foundation's software and to any other program whose authors commit to +using it. (Some other Free Software Foundation software is covered by +the GNU Library General Public License instead.) You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. + + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if you +distribute copies of the software, or if you modify it. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must give the recipients all the rights that +you have. You must make sure that they, too, receive or can get the +source code. And you must show them these terms so they know their +rights. + + We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + + Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, we +want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that redistributors of a free +program will individually obtain patent licenses, in effect making the +program proprietary. To prevent this, we have made it clear that any +patent must be licensed for everyone's free use or not licensed at all. + + The precise terms and conditions for copying, distribution and +modification follow. + + GNU GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License applies to any program or other work which contains +a notice placed by the copyright holder saying it may be distributed +under the terms of this General Public License. The "Program", below, +refers to any such program or work, and a "work based on the Program" +means either the Program or any derivative work under copyright law: +that is to say, a work containing the Program or a portion of it, +either verbatim or with modifications and/or translated into another +language. (Hereinafter, translation is included without limitation in +the term "modification".) Each licensee is addressed as "you". + +Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running the Program is not restricted, and the output from the Program +is covered only if its contents constitute a work based on the +Program (independent of having been made by running the Program). +Whether that is true depends on what the Program does. + + 1. You may copy and distribute verbatim copies of the Program's +source code as you receive it, in any medium, provided that you +conspicuously and appropriately publish on each copy an appropriate +copyright notice and disclaimer of warranty; keep intact all the +notices that refer to this License and to the absence of any warranty; +and give any other recipients of the Program a copy of this License +along with the Program. + +You may charge a fee for the physical act of transferring a copy, and +you may at your option offer warranty protection in exchange for a fee. + + 2. You may modify your copy or copies of the Program or any portion +of it, thus forming a work based on the Program, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) You must cause the modified files to carry prominent notices + stating that you changed the files and the date of any change. + + b) You must cause any work that you distribute or publish, that in + whole or in part contains or is derived from the Program or any + part thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + + c) If the modified program normally reads commands interactively + when run, you must cause it, when started running for such + interactive use in the most ordinary way, to print or display an + announcement including an appropriate copyright notice and a + notice that there is no warranty (or else, saying that you provide + a warranty) and that users may redistribute the program under + these conditions, and telling the user how to view a copy of this + License. (Exception: if the Program itself is interactive but + does not normally print such an announcement, your work based on + the Program is not required to print an announcement.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Program, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Program, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Program. + +In addition, mere aggregation of another work not based on the Program +with the Program (or with a work based on the Program) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may copy and distribute the Program (or a work based on it, +under Section 2) in object code or executable form under the terms of +Sections 1 and 2 above provided that you also do one of the following: + + a) Accompany it with the complete corresponding machine-readable + source code, which must be distributed under the terms of Sections + 1 and 2 above on a medium customarily used for software interchange; or, + + b) Accompany it with a written offer, valid for at least three + years, to give any third party, for a charge no more than your + cost of physically performing source distribution, a complete + machine-readable copy of the corresponding source code, to be + distributed under the terms of Sections 1 and 2 above on a medium + customarily used for software interchange; or, + + c) Accompany it with the information you received as to the offer + to distribute corresponding source code. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form with such + an offer, in accord with Subsection b above.) + +The source code for a work means the preferred form of the work for +making modifications to it. For an executable work, complete source +code means all the source code for all modules it contains, plus any +associated interface definition files, plus the scripts used to +control compilation and installation of the executable. However, as a +special exception, the source code distributed need not include +anything that is normally distributed (in either source or binary +form) with the major components (compiler, kernel, and so on) of the +operating system on which the executable runs, unless that component +itself accompanies the executable. + +If distribution of executable or object code is made by offering +access to copy from a designated place, then offering equivalent +access to copy the source code from the same place counts as +distribution of the source code, even though third parties are not +compelled to copy the source along with the object code. + + 4. You may not copy, modify, sublicense, or distribute the Program +except as expressly provided under this License. Any attempt +otherwise to copy, modify, sublicense or distribute the Program is +void, and will automatically terminate your rights under this License. +However, parties who have received copies, or rights, from you under +this License will not have their licenses terminated so long as such +parties remain in full compliance. + + 5. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Program or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Program (or any work based on the +Program), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Program or works based on it. + + 6. Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the +original licensor to copy, distribute or modify the Program subject to +these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties to +this License. + + 7. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Program at all. For example, if a patent +license would not permit royalty-free redistribution of the Program by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Program. + +If any portion of this section is held invalid or unenforceable under +any particular circumstance, the balance of the section is intended to +apply and the section as a whole is intended to apply in other +circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system, which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 8. If the distribution and/or use of the Program is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Program under this License +may add an explicit geographical distribution limitation excluding +those countries, so that distribution is permitted only in or among +countries not thus excluded. In such case, this License incorporates +the limitation as if written in the body of this License. + + 9. The Free Software Foundation may publish revised and/or new versions +of the General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of this License which applies to it and "any +later version", you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number of +this License, you may choose any version ever published by the Free Software +Foundation. + + 10. If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we sometimes +make exceptions for this. Our decision will be guided by the two goals +of preserving the free status of all derivatives of our free software and +of promoting the sharing and reuse of software generally. + + NO WARRANTY + + 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY +FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN +OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES +PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED +OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS +TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE +PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, +REPAIR OR CORRECTION. + + 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR +REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING +OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED +TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY +YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER +PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE +POSSIBILITY OF SUCH DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + <one line to give the program's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + 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. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + +Also add information on how to contact you by electronic and paper mail. + +If the program is interactive, make it output a short notice like this +when it starts in an interactive mode: + + Gnomovision version 69, Copyright (C) year name of author + Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, the commands you use may +be called something other than `show w' and `show c'; they could even be +mouse-clicks or menu items--whatever suits your program. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the program, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the program + `Gnomovision' (which makes passes at compilers) written by James Hacker. + + <signature of Ty Coon>, 1 April 1989 + Ty Coon, President of Vice + +This General Public License does not permit incorporating your program into +proprietary programs. If your program is a subroutine library, you may +consider it more useful to permit linking proprietary applications with the +library. If this is what you want to do, use the GNU Library General +Public License instead of this License.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Finder.cpp Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,243 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 "Finder.h" + + +Finder::Finder(Matcher *p1, Matcher *p2) +{ + if (!p1->firstPM) + std::cerr << "Warning: wrong args in Finder()" << std::endl; + pm1 = p1; + pm2 = p2; + index1 = 0; + index2 = 0; + rowRange = new int[2]; + colRange = new int[2]; +} // constructor + +Finder::~Finder() +{ + delete[] rowRange; + delete[] colRange; +} + +bool +Finder::find(int i1, int i2) +{ + if (i1 >= 0) { + index1 = i1; + index2 = i2 - pm1->first[i1]; + } + return (i1 >= 0) && (i2 >= pm1->first[i1]) && (i2 < pm1->last[i1]); +} // find() + +void +Finder::getColRange(int row, int *range) +{ + range[0] = pm1->first[row]; + range[1] = pm1->last[row]; +} // getColRange() + +void +Finder::getRowRange(int col, int *range) +{ + range[0] = pm2->first[col]; + range[1] = pm2->last[col]; +} // getRowRange() + +int +Finder::getExpandDirection(int row, int col) +{ + return getExpandDirection(row, col, false); +} // getExpandDirection() + +int +Finder::getExpandDirection(int row, int col, bool check) +{ + int min = getPathCost(row, col); + bestRow = row; + bestCol = col; + getRowRange(col, rowRange); + if (rowRange[1] > row+1) + rowRange[1] = row+1; // don't cheat by looking at future :) + for (int index = rowRange[0]; index < rowRange[1]; index++) { + int tmp = getPathCost(index, col); + if (tmp < min) { + min = tmp; + bestRow = index; + } + } + getColRange(row, colRange); + if (colRange[1] > col+1) + colRange[1] = col+1; // don't cheat by looking at future :) + for (int index = colRange[0]; index < colRange[1]; index++) { + int tmp = getPathCost(row, index); + if (tmp < min) { + min = tmp; + bestCol = index; + bestRow = row; + } + } + // System.err.print(" BEST: " + bestRow + " " + bestCol + " " + check); + // 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; + } + return ((bestRow==row)? ADVANCE_THIS: 0) | + ((bestCol==col)? ADVANCE_OTHER: 0); + +} // getExpandDirection() + +unsigned char +Finder::getDistance(int row, int col) +{ + if (find(row, col)) { + return pm1->distance[row][col - pm1->first[row]]; + } + std::cerr << "getDistance(" << row << "," << col << "): out of bounds" << std::endl; + throw "getDistance index out of bounds"; +} // getDistance()/2 + +void +Finder::setDistance(int row, int col, unsigned char b) +{ + if (find(row, col)) { + pm1->distance[row][col - pm1->first[row]] = b; + return; + } + std::cerr << "setDistance(" << row << "," << col << "," << b << "): out of bounds" << std::endl; + throw "setDistance index out of bounds"; +} // setDistance() + +int +Finder::getPathCost(int row, int col) +{ + if (find(row, col)) // "1" avoids div by 0 below + return pm1->bestPathCost[row][col - pm1->first[row]]*100/ (1+row+col); + std::cerr << "getPathCost(" << row << "," << col << "): out of bounds" << std::endl; + throw "getPathCost index out of bounds"; +} // getPathCost() + +int +Finder::getRawPathCost(int row, int col) +{ + if (find(row, col)) + return pm1->bestPathCost[row][col - pm1->first[row]]; + std::cerr << "getRawPathCost(" << row << "," << col << "): out of bounds" << std::endl; + throw "getRawPathCost index out of bounds"; +} // getRawPathCost() + +void +Finder::setPathCost(int row, int col, int i) +{ + if (find(row, col)) { + pm1->bestPathCost[row][col - pm1->first[row]] = i; + return; + } + std::cerr << "setPathCost(" << row << "," << col << "," << i << "): out of bounds" << std::endl; + throw "setPathCost index out of bounds"; +} // setPathCost() + +unsigned char +Finder::getDistance() +{ + return pm1->distance[index1][index2]; +} // getDistance()/0 + +void +Finder::setDistance(int b) +{ + pm1->distance[index1][index2] = (unsigned char)b; +} // setDistance() + +int +Finder::getPathCost() +{ + return pm1->bestPathCost[index1][index2]; +} // getPathCost() + +void +Finder::setPathCost(int i) +{ + pm1->bestPathCost[index1][index2] = i; +} // setPathCost() + +void +Finder::recalculatePathCostMatrix(int r1, int c1, int r2, int c2) +{ + if (!find(r1,c1)) { + std::cerr << "recalculatePathCostMatrix(" << r1 << "," << c1 << "): out of bounds" << std::endl; + throw "recalculatePathCostMatrix index out of bounds"; + } + int thisRowStart, c; + int prevRowStart = 0, prevRowStop = 0; + for (int r = r1; r <= r2; r++) { + thisRowStart = pm1->first[r]; + if (thisRowStart < c1) + thisRowStart = c1; + for (c = thisRowStart; c <= c2; c++) { + if (find(r,c)) { + int i2 = index2; + int newCost = pm1->distance[r][i2]; + int dir = 0; + if (r > r1) { // not first row + int min = -1; + if ((c > prevRowStart) && (c <= prevRowStop)) { + // diagonal from (r-1,c-1) + min = pm1->bestPathCost[r-1][c-pm1->first[r-1]-1] + + newCost * 2; + dir = ADVANCE_BOTH; + } + if ((c >= prevRowStart) && (c < prevRowStop)) { + // vertical from (r-1,c) + int cost = pm1->bestPathCost[r-1][c-pm1->first[r-1]] + + newCost; + if ((min == -1) || (cost < min)) { + min = cost; + dir = ADVANCE_THIS; + } + } + if (c > thisRowStart) { + // horizontal from (r,c-1) + int cost =pm1->bestPathCost[r][i2-1]+newCost; + if ((min == -1) || (cost < min)) { + min = cost; + dir = ADVANCE_OTHER; + } + } + pm1->bestPathCost[r][i2] = min; + } else if (c > thisRowStart) { // first row + // horizontal from (r,c-1) + pm1->bestPathCost[r][i2] = pm1->bestPathCost[r][i2-1] + + newCost; + dir = ADVANCE_OTHER; + } + if ((r != r1) || (c != c1)) { + pm1->distance[r][i2] = (unsigned char) + ((pm1->distance[r][i2] & MASK) | dir); + } + } else + break; // end of row + } + prevRowStart = thisRowStart; + prevRowStop = c; + } +} // recalculatePathCostMatrix()
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Finder.h Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,91 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 _FINDER_H_ +#define _FINDER_H_ + +#include <vector> +#include <iostream> + +#include "Matcher.h" + +/** Maps cost matrix coordinates into an efficient + * (linear instead of quadratic space) representation. + * Stores result of most recent mapping for fast + * sequential access. + */ +class Finder { + +protected: + Matcher *pm1, *pm2; + int index1, index2, bestRow, bestCol; + int *rowRange; + int *colRange; + +public: + Finder(Matcher *p1, Matcher *p2); + + ~Finder(); + + /** Sets up the instance variables to point to the given + * coordinate in the distance matrix. + * + * @param i1 frameNumber in the first Matcher + * @param i2 frameNumber in the second Matcher + * @return true iff the point (i2,i1) is represented in the distance matrix + */ + bool find(int i1, int i2); + + /** Returns the range [lo,hi) of legal column indices for the + * given row. */ + void getColRange(int row, int *range); + + /** Returns the range [lo,hi) of legal row indices for the given + * column. */ + void getRowRange(int col, int *range); + + int getExpandDirection(int row, int col); + int getExpandDirection(int row, int col, bool check); + + unsigned char getDistance(int row, int col); + void setDistance(int row, int col, unsigned char b); + + int getPathCost(int row, int col); + int getRawPathCost(int row, int col); + void setPathCost(int row, int col, int i); + + unsigned char getDistance(); + void setDistance(int b); + + int getPathCost(); + void setPathCost(int i); + + /** Calculates a rectangle of the path cost matrix so that the + * minimum cost path between the bottom left and top right + * corners can be computed. Caches previous values to avoid + * calling find() multiple times, and is several times faster as + * a result. + * + * @param r1 the bottom of the rectangle to be calculated + * @param c1 the left side of the rectangle to be calculated + * @param r2 the top of the rectangle to be calculated + * @param c2 the right side of the rectangle to be calculated + */ + void recalculatePathCostMatrix(int r1, int c1, int r2, int c2); + +}; // class Finder + +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Makefile Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,18 @@ + +CXXFLAGS := -I../vamp-plugin-sdk -O3 -Wall +#CXXFLAGS := -I../vamp-plugin-sdk -g -Wall -march=pentium4 -msse -msse2 -ffast-math +#CXXFLAGS := -I../vamp-plugin-sdk -O3 -Wall -march=pentium4 -msse -msse2 -fomit-frame-pointer -ffast-math + +match-vamp-plugin.so: Finder.o Matcher.o MatchFeeder.o MatchVampPlugin.o Path.o + g++ -shared $^ -o $@ -L../vamp-plugin-sdk/vamp-sdk -Wl,-Bstatic -lvamp-sdk -Wl,-Bdynamic -lpthread + +clean: + rm *.o + +# DO NOT DELETE + +Finder.o: Finder.h Matcher.h +Matcher.o: Matcher.h Finder.h +MatchFeeder.o: MatchFeeder.h Matcher.h Finder.h +MatchVampPlugin.o: MatchVampPlugin.h Matcher.h MatchFeeder.h Finder.h Path.h +Path.o: Path.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/MatchFeeder.cpp Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,139 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 "MatchFeeder.h" + +MatchFeeder::MatchFeeder(Matcher *m1, Matcher *m2) : + pm1(m1), pm2(m2) +{ + fftSize = m1->fftSize; + finder = new Finder(m1, m2); + reBuffer = new double[fftSize/2+1]; + imBuffer = new double[fftSize/2+1]; +} + +MatchFeeder::~MatchFeeder() +{ + delete[] imBuffer; + delete[] reBuffer; + while (!q1.empty()) { + delete[] q1.front(); + q1.pop(); + } + while (!q2.empty()) { + delete[] q2.front(); + q2.pop(); + } + delete finder; +} + +void +MatchFeeder::feed(const float *const *input) +{ + // We maintain two FIFO queues of audio data frame block pointers, + // one per input stream. When the match-feeder function is + // entered, it knows that it has at least one block in each queue. + // It loops, processing up to one block per matcher, until a queue + // is empty. Then it returns, to be called again with more data. + + float *block = new float[fftSize+2]; + for (size_t i = 0; i < fftSize+2; ++i) { + block[i] = input[0][i]; + } + q1.push(block); + + block = new float[fftSize+2]; + for (size_t i = 0; i < fftSize+2; ++i) { + block[i] = input[1][i]; + } + q2.push(block); + + while (!q1.empty() && !q2.empty()) { +// std::cerr << "MatchFeeder::feed: q1 " << q1.size() << " q2 " << q2.size() << std::endl; + feedBlock(); + } +} + +void +MatchFeeder::feedBlock() +{ + if (pm1->frameCount < pm1->blockSize) { // fill initial block +// std::cerr << "feeding initial block" << std::endl; + feed1(); + feed2(); + } +//!!! } else if (pm1->atEnd) { +// feed2(); +//!!! } else if (pm2->atEnd) +// feed1(); + else if (pm1->runCount >= Matcher::MAX_RUN_COUNT) { // slope constraints +// std::cerr << "pm1 too slopey" << std::endl; + feed2(); + } else if (pm2->runCount >= Matcher::MAX_RUN_COUNT) { +// std::cerr << "pm2 too slopey" << std::endl; + feed1(); + } else { + switch (finder->getExpandDirection + (pm1->frameCount-1, pm2->frameCount-1)) { + case ADVANCE_THIS: +// std::cerr << "finder says ADVANCE_THIS" << std::endl; + feed1(); + break; + case ADVANCE_OTHER: +// std::cerr << "finder says ADVANCE_OTHER" << std::endl; + feed2(); + break; + case ADVANCE_BOTH: +// std::cerr << "finder says ADVANCE_BOTH" << std::endl; + feed1(); + feed2(); + break; + } + } +} + +void +MatchFeeder::feed1() +{ +// std::cerr << "feed1" << std::endl; + float *block = q1.front(); + q1.pop(); + for (size_t i = 0; i <= fftSize/2; ++i) { + reBuffer[i] = block[i*2]; + } + for (size_t i = 0; i <= fftSize/2; ++i) { + imBuffer[i] = block[i*2+1]; + } + delete[] block; + pm1->processFrame(reBuffer, imBuffer); +} + +void +MatchFeeder::feed2() +{ +// std::cerr << "feed2" << std::endl; + float *block = q2.front(); + q2.pop(); + for (size_t i = 0; i <= fftSize/2; ++i) { + reBuffer[i] = block[i*2]; + } + for (size_t i = 0; i <= fftSize/2; ++i) { + imBuffer[i] = block[i*2+1]; + } + delete[] block; + pm2->processFrame(reBuffer, imBuffer); +} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/MatchFeeder.h Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,51 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 _MATCH_FEEDER_H_ +#define _MATCH_FEEDER_H_ + +#include "Matcher.h" +#include "Finder.h" + +#include <queue> + +class MatchFeeder +{ +public: + MatchFeeder(Matcher *m1, Matcher *m2); + ~MatchFeeder(); + + void feed(const float *const *input); + + Finder *getFinder() { return finder; } + +protected: + void feedBlock(); + void feed1(); + void feed2(); + + Finder *finder; + Matcher *pm1; + Matcher *pm2; + + size_t fftSize; + double *reBuffer; + double *imBuffer; + + std::queue<float *> q1; + std::queue<float *> q2; +}; + +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/MatchVampPlugin.cpp Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,454 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 "MatchVampPlugin.h" + +#include "Matcher.h" +#include "MatchFeeder.h" +#include "Path.h" + +#include <vamp/vamp.h> +#include <vamp-sdk/PluginAdapter.h> +#include <vamp-sdk/RealTime.h> + +#include <vector> +#include <algorithm> + +//static int extant = 0; + +#ifdef _WIN32 +HANDLE +MatchVampPlugin::m_serialisingMutex; +#else +pthread_mutex_t +MatchVampPlugin::m_serialisingMutex; +#endif + +bool +MatchVampPlugin::m_serialisingMutexInitialised = false; + +MatchVampPlugin::MatchVampPlugin(float inputSampleRate) : + Plugin(inputSampleRate), + m_serialise(false), + m_begin(true), + m_locked(false) +{ + if (!m_serialisingMutexInitialised) { + m_serialisingMutexInitialised = true; +#ifdef _WIN32 + m_serialisingMutex = CreateMutex(NULL, FALSE, NULL); +#else + pthread_mutex_init(&m_serialisingMutex, 0); +#endif + } + + pm1 = 0; + pm2 = 0; + feeder = 0; +// std::cerr << "MatchVampPlugin::MatchVampPlugin(" << this << "): extant = " << ++extant << std::endl; +} + +MatchVampPlugin::~MatchVampPlugin() +{ +// std::cerr << "MatchVampPlugin::~MatchVampPlugin(" << this << "): extant = " << --extant << std::endl; + + delete feeder; + delete pm1; + delete pm2; + + if (m_locked) { +#ifdef _WIN32 + ReleaseMutex(m_serialisingMutex); +#else + pthread_mutex_unlock(&m_serialisingMutex); +#endif + m_locked = false; + } +} + +string +MatchVampPlugin::getIdentifier() const +{ + return "match"; +} + +string +MatchVampPlugin::getName() const +{ + return "Match Performance Aligner"; +} + +string +MatchVampPlugin::getDescription() const +{ + return "Calculate alignment between two performances in separate channel inputs"; +} + +string +MatchVampPlugin::getMaker() const +{ + return "Simon Dixon (plugin by Chris Cannam)"; +} + +int +MatchVampPlugin::getPluginVersion() const +{ + return 1; +} + +string +MatchVampPlugin::getCopyright() const +{ + return "GPL"; +} + +MatchVampPlugin::ParameterList +MatchVampPlugin::getParameterDescriptors() const +{ + ParameterList list; + + ParameterDescriptor desc; + desc.identifier = "serialise"; + desc.name = "Serialise Plugin Invocations"; + desc.description = "Reduce potential memory load at the expense of multiprocessor performance by serialising multi-threaded plugin runs"; + desc.minValue = 0; + desc.maxValue = 1; + desc.defaultValue = 0; + desc.isQuantized = true; + desc.quantizeStep = 1; + list.push_back(desc); + + return list; +} + +float +MatchVampPlugin::getParameter(std::string name) const +{ + if (name == "serialise") { + return m_serialise ? 1.0 : 0.0; + } + return 0.0; +} + +void +MatchVampPlugin::setParameter(std::string name, float value) +{ + if (name == "serialise") { + m_serialise = (value > 0.5); + std::cerr << "MatchVampPlugin::setParameter: set serialise to " << m_serialise << std::endl; + } +} + +size_t +MatchVampPlugin::getPreferredStepSize() const +{ + if (!pm1) createMatchers(); + return pm1->getHopSize(); +} + +size_t +MatchVampPlugin::getPreferredBlockSize() const +{ + if (!pm1) createMatchers(); + return pm1->getFFTSize(); +} + +void +MatchVampPlugin::createMatchers() const +{ + pm1 = new Matcher(m_inputSampleRate, 0); + pm2 = new Matcher(m_inputSampleRate, pm1); + pm1->setOtherMatcher(pm2); + feeder = new MatchFeeder(pm1, pm2); +} + +bool +MatchVampPlugin::initialise(size_t channels, size_t stepSize, size_t blockSize) +{ + if (!pm1) createMatchers(); + if (channels < getMinChannelCount() || + channels > getMaxChannelCount()) return false; + if (stepSize != getPreferredStepSize() || + blockSize != getPreferredBlockSize()) return false; + m_begin = true; + m_locked = false; + return true; +} + +void +MatchVampPlugin::reset() +{ + //!!!??? +} + +MatchVampPlugin::OutputList +MatchVampPlugin::getOutputDescriptors() const +{ + OutputList list; + + float outRate = 1.0 / 0.020; //!!! this is the default value of hopTime in Matcher + + OutputDescriptor desc; + desc.identifier = "path"; + desc.name = "Path"; + desc.description = "Alignment path"; + desc.unit = ""; + desc.hasFixedBinCount = true; + desc.binCount = 1; + desc.hasKnownExtents = false; + desc.isQuantized = true; + desc.quantizeStep = 1; + desc.sampleType = OutputDescriptor::VariableSampleRate; + desc.sampleRate = outRate; + list.push_back(desc); + + desc.identifier = "a_b"; + desc.name = "A-B Timeline"; + desc.description = "Timing in performance B corresponding to moments in performance A"; + desc.unit = "sec"; + desc.hasFixedBinCount = true; + desc.binCount = 1; + desc.hasKnownExtents = false; + desc.isQuantized = false; + desc.sampleType = OutputDescriptor::VariableSampleRate; + desc.sampleRate = outRate; + list.push_back(desc); + + desc.identifier = "b_a"; + desc.name = "B-A Timeline"; + desc.description = "Timing in performance A corresponding to moments in performance B"; + desc.unit = "sec"; + desc.hasFixedBinCount = true; + desc.binCount = 1; + desc.hasKnownExtents = false; + desc.isQuantized = false; + desc.sampleType = OutputDescriptor::VariableSampleRate; + desc.sampleRate = outRate; + list.push_back(desc); + + desc.identifier = "a_b_divergence"; + desc.name = "A-B Divergence"; + desc.description = "Difference between timings in performances A and B"; + desc.unit = "sec"; + desc.hasFixedBinCount = true; + desc.binCount = 1; + desc.hasKnownExtents = false; + desc.isQuantized = false; + desc.sampleType = OutputDescriptor::VariableSampleRate; + desc.sampleRate = outRate; + list.push_back(desc); + + desc.identifier = "a_b_temporatio"; + desc.name = "A-B Tempo Ratio"; + desc.description = "Ratio of tempi between performances A and B"; + desc.unit = ""; + desc.hasFixedBinCount = true; + desc.binCount = 1; + desc.hasKnownExtents = false; + desc.isQuantized = false; + desc.sampleType = OutputDescriptor::VariableSampleRate; + desc.sampleRate = outRate; + list.push_back(desc); + + return list; +} + +MatchVampPlugin::FeatureSet +MatchVampPlugin::process(const float *const *inputBuffers, + Vamp::RealTime timestamp) +{ + if (m_begin) { + if (!m_locked && m_serialise) { + m_locked = true; +#ifdef _WIN32 + WaitForSingleObject(m_serialisingMutex, INFINITE); +#else + pthread_mutex_lock(&m_serialisingMutex); +#endif + } + m_begin = false; + } + +// std::cerr << timestamp.toString(); + + feeder->feed(inputBuffers); + +// std::cerr << "."; +// std::cerr << std::endl; + + return FeatureSet(); +} + +MatchVampPlugin::FeatureSet +MatchVampPlugin::getRemainingFeatures() +{ + int x = pm2->getFrameCount() - 1; + int y = pm1->getFrameCount() - 1; + + Finder *finder = feeder->getFinder(); + + std::vector<int> pathx; + std::vector<int> pathy; + +// std::cerr << "initial x,y = " << x << std::endl; + + while (finder->find(y, x) && ((x > 0) || (y > 0))) { + + pathx.push_back(x); + pathy.push_back(y); + +// std::cerr << pathx.size() << ": (" << x << "," << y << ")" << std::endl; + + switch (finder->getDistance() & ADVANCE_BOTH){ + case ADVANCE_THIS: y--; break; + case ADVANCE_OTHER: x--; break; + case ADVANCE_BOTH: x--; y--; break; + default: // this would indicate a bug, but we wouldn't want to hang + std::cerr << "WARNING: MatchVampPlugin::getRemainingFeatures: Neither matcher advanced in path backtrack at (" << x << "," << y << ")" << std::endl; + if (x > y) x--; else y--; break; + } + } + + std::reverse(pathx.begin(), pathx.end()); + std::reverse(pathy.begin(), pathy.end()); + + int smoothedLen = Path().smooth(pathx, pathy, pathx.size()); + + FeatureSet returnFeatures; + + int prevx = 0; + int prevy = 0; + + for (int i = 0; i < smoothedLen; ++i) { + + int x = pathx[i]; + int y = pathy[i]; + + Vamp::RealTime xt = Vamp::RealTime::frame2RealTime + (x * pm1->getHopSize(), lrintf(m_inputSampleRate)); + Vamp::RealTime yt = Vamp::RealTime::frame2RealTime + (y * pm2->getHopSize(), lrintf(m_inputSampleRate)); + + Feature feature; + feature.hasTimestamp = true; + feature.timestamp = xt; + feature.values.clear(); + feature.values.push_back(yt.sec + double(yt.nsec)/1.0e9); + returnFeatures[0].push_back(feature); + + if (x != prevx) { + + feature.hasTimestamp = true; + feature.timestamp = xt; + feature.values.clear(); + feature.values.push_back(yt.sec + yt.msec()/1000.0); + returnFeatures[1].push_back(feature); + + Vamp::RealTime diff = yt - xt; + feature.values.clear(); + feature.values.push_back(diff.sec + diff.msec()/1000.0); + returnFeatures[3].push_back(feature); + + if (i > 0) { + int lookback = 100; //!!! arbitrary + if (lookback > i) lookback = i; + int xdiff = x - pathx[i-lookback]; + int ydiff = y - pathy[i-lookback]; + if (xdiff != 0 && ydiff != 0) { + float ratio = float(ydiff)/float(xdiff); + if (ratio < 8 && ratio > (1.0/8)) { //!!! just for now, since we aren't dealing properly with silence yet + feature.values.clear(); + feature.values.push_back(ratio); + returnFeatures[4].push_back(feature); + } + } + } + } + + if (y != prevy) { + feature.hasTimestamp = true; + feature.timestamp = yt; + feature.values.clear(); + feature.values.push_back(xt.sec + xt.msec()/1000.0); + returnFeatures[2].push_back(feature); + } + + prevx = x; + prevy = y; + } + + delete feeder; + delete pm1; + delete pm2; + feeder = 0; + pm1 = 0; + pm2 = 0; + + if (m_locked) { +#ifdef _WIN32 + ReleaseMutex(m_serialisingMutex); +#else + pthread_mutex_unlock(&m_serialisingMutex); +#endif + m_locked = false; + } + + return returnFeatures; + + +/* + for (int i = 0; i < smoothedLen; ++i) { + std::cerr << i << ": [" << pathx[i] << "," << pathy[i] << "]" << std::endl; + } + + std::cerr << std::endl; + std::cerr << "File: A" << std::endl; + std::cerr << "Marks: -1" << std::endl; + std::cerr << "FixedPoints: true 0" << std::endl; + std::cerr << "0" << std::endl; + std::cerr << "0" << std::endl; + std::cerr << "0" << std::endl; + std::cerr << "0" << std::endl; + std::cerr << "File: B" << std::endl; + std::cerr << "Marks: 0" << std::endl; + std::cerr << "FixedPoints: true 0" << std::endl; + std::cerr << "0.02" << std::endl; + std::cerr << "0.02" << std::endl; + + std::cerr << smoothedLen << std::endl; + for (int i = 0; i < smoothedLen; ++i) { + std::cerr << pathx[i] << std::endl; + } + + std::cerr << smoothedLen << std::endl; + for (int i = 0; i < smoothedLen; ++i) { + std::cerr << pathy[i] << std::endl; + } +*/ +} + +static Vamp::PluginAdapter<MatchVampPlugin> mvpAdapter; + +const VampPluginDescriptor *vampGetPluginDescriptor(unsigned int version, + unsigned int index) +{ + if (version < 1) return 0; + + switch (index) { + case 0: return mvpAdapter.getDescriptor(); + default: return 0; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/MatchVampPlugin.h Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,85 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 _MATCH_VAMP_PLUGIN_H_ +#define _MATCH_VAMP_PLUGIN_H_ + +#include <vamp-sdk/Plugin.h> + +#ifdef _WIN32 +#include <windows.h> +#else +#include <pthread.h> +#endif + +class Matcher; +class MatchFeeder; + +class MatchVampPlugin : public Vamp::Plugin +{ +public: + MatchVampPlugin(float inputSampleRate); + virtual ~MatchVampPlugin(); + + bool initialise(size_t channels, size_t stepSize, size_t blockSize); + void reset(); + + InputDomain getInputDomain() const { return FrequencyDomain; } + + size_t getPreferredStepSize() const; + size_t getPreferredBlockSize() const; + + size_t getMinChannelCount() const { return 2; } + size_t getMaxChannelCount() const { return 2; } + + std::string getIdentifier() const; + std::string getName() const; + std::string getDescription() const; + std::string getMaker() const; + int getPluginVersion() const; + std::string getCopyright() const; + + ParameterList getParameterDescriptors() const; + float getParameter(std::string) const; + void setParameter(std::string, float); + + OutputList getOutputDescriptors() const; + + FeatureSet process(const float *const *inputBuffers, + Vamp::RealTime timestamp); + + FeatureSet getRemainingFeatures(); + +protected: + void createMatchers() const; + mutable Matcher *pm1; + mutable Matcher *pm2; + mutable MatchFeeder *feeder; + bool m_serialise; + bool m_begin; + bool m_locked; + +#ifdef _WIN32 + static HANDLE m_serialisingMutex; +#else + static pthread_mutex_t m_serialisingMutex; +#endif + + static bool m_serialisingMutexInitialised; +}; + + +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Matcher.cpp Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,484 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 "Matcher.h" +#include "Finder.h" + +#include <iostream> + +bool Matcher::silent = true; + +Matcher::Matcher(float rate, Matcher *p) +{ + std::cerr << "Matcher::Matcher(" << rate << ", " << p << ")" << std::endl; + + sampleRate = rate; + otherMatcher = p; // the first matcher will need this to be set later + firstPM = (!p); + matchFileOffset = 0; + ltAverage = 0; + frameCount = 0; + runCount = 0; + paused = false; + hopSize = 0; + fftSize = 0; + blockSize = 0; + hopTime = 0.020; // DEFAULT, overridden with -h //!!! + fftTime = 0.04644; // DEFAULT, overridden with -f + blockTime = 10.0; // DEFAULT, overridden with -c + normalise1 = true; + normalise2 = false; + normalise3 = false; + normalise4 = true; + useSpectralDifference = true; + useChromaFrequencyMap = false; + scale = 90; + maxFrames = 0; // stop at EOF + + hopSize = lrint(sampleRate * hopTime); + fftSize = lrint(pow(2, lrint(log(fftTime * sampleRate) / log(2)))); + blockSize = lrint(blockTime / hopTime); + + distance = 0; + bestPathCost = 0; + distYSizes = 0; + distXSize = 0; + + initialised = false; + +} // default constructor + +Matcher::~Matcher() +{ + std::cerr << "Matcher(" << this << ")::~Matcher()" << std::endl; + + if (initialised) { + + for (int i = 0; i < distXSize; ++i) { + if (distance[i]) { + free(distance[i]); + free(bestPathCost[i]); + } + } + free(distance); + free(bestPathCost); + + free(first); + free(last); + + free(distYSizes); + } +} + +void +Matcher::print() +{ + cerr << toString() << endl; +} // print() + +string +Matcher::toString() +{ + std::stringstream os; + os << "Matcher " << this << ": (" << sampleRate + << "kHz)" + << "\n\tHop size: " << hopSize + << "\n\tFFT size: " << fftSize + << "\n\tBlock size: " << blockSize; + return os.str(); +} // toString() + +void +Matcher::init() +{ + if (initialised) return; + + initialised = true; + + makeFreqMap(fftSize, sampleRate); + + initVector<double>(prevFrame, freqMapSize); + initVector<double>(newFrame, freqMapSize); + initMatrix<double>(frames, blockSize, freqMapSize + 1); + + int distSize = (MAX_RUN_COUNT + 1) * blockSize; + + distXSize = blockSize * 2; + +// std::cerr << "Matcher::init: distXSize = " << distXSize << std::endl; + + distance = (unsigned char **)malloc(distXSize * sizeof(unsigned char *)); + bestPathCost = (int **)malloc(distXSize * sizeof(int *)); + distYSizes = (int *)malloc(distXSize * sizeof(int)); + + for (int i = 0; i < blockSize; ++i) { + distance[i] = (unsigned char *)malloc(distSize * sizeof(unsigned char)); + bestPathCost[i] = (int *)malloc(distSize * sizeof(int)); + distYSizes[i] = distSize; + } + for (int i = blockSize; i < distXSize; ++i) { + distance[i] = 0; + } + + first = (int *)malloc(distXSize * sizeof(int)); + last = (int *)malloc(distXSize * sizeof(int)); + + frameCount = 0; + runCount = 0; +// frameRMS = 0; + ltAverage = 0; + + if (!silent) print(); +} // init + +void +Matcher::makeFreqMap(int fftSize, float sampleRate) +{ + initVector<int>(freqMap, fftSize/2 + 1); + if (useChromaFrequencyMap) + makeChromaFrequencyMap(fftSize, sampleRate); + else + makeStandardFrequencyMap(fftSize, sampleRate); +} // makeFreqMap() + +void +Matcher::makeStandardFrequencyMap(int fftSize, float sampleRate) +{ + double binWidth = sampleRate / fftSize; + int crossoverBin = (int)(2 / (pow(2, 1/12.0) - 1)); + int crossoverMidi = lrint(log(crossoverBin*binWidth/440)/ + log(2) * 12 + 69); + // freq = 440 * Math.pow(2, (midi-69)/12.0) / binWidth; + int i = 0; + while (i <= crossoverBin) { + freqMap[i] = i; + ++i; + } + while (i <= fftSize/2) { + double midi = log(i*binWidth/440) / log(2) * 12 + 69; + if (midi > 127) + midi = 127; + freqMap[i++] = crossoverBin + lrint(midi) - crossoverMidi; + } + freqMapSize = freqMap[i-1] + 1; + if (!silent) { + cerr << "Standard map size: " << freqMapSize + << "; Crossover at: " << crossoverBin << endl; +//!!! for (i = 0; i < fftSize / 2; i++) +// cerr << "freqMap[" << i << "] = " << freqMap[i] << endl; + } +} // makeStandardFrequencyMap() + +void +Matcher::makeChromaFrequencyMap(int fftSize, float sampleRate) +{ + double binWidth = sampleRate / fftSize; + int crossoverBin = (int)(1 / (pow(2, 1/12.0) - 1)); + // freq = 440 * Math.pow(2, (midi-69)/12.0) / binWidth; + int i = 0; + while (i <= crossoverBin) + freqMap[i++] = 0; + while (i <= fftSize/2) { + double midi = log(i*binWidth/440) / log(2) * 12 + 69; + freqMap[i++] = (lrint(midi)) % 12 + 1; + } + freqMapSize = 13; + if (!silent) { + cerr << "Chroma map size: " << freqMapSize + << "; Crossover at: " << crossoverBin << endl; + for (i = 0; i < fftSize / 2; i++) + cerr << "freqMap[" << i << "] = " << freqMap[i] << endl; + } +} // makeChromaFrequencyMap() + +void +Matcher::processFrame(double *reBuffer, double *imBuffer) +{ + if (!initialised) init(); + + for (int i = 0; i < (int)newFrame.size(); ++i) { + newFrame[i] = 0; + } + double rms = 0; + for (int i = 0; i <= fftSize/2; i++) { + double mag = reBuffer[i] * reBuffer[i] + + imBuffer[i] * imBuffer[i]; + rms += mag; + newFrame[freqMap[i]] += mag; + } + rms = sqrt(rms / (fftSize/2)); + + int frameIndex = frameCount % blockSize; + + if (frameCount >= distXSize) { +// std::cerr << "Resizing " << distXSize << " -> " << distXSize * 2 << std::endl; + distXSize *= 2; + distance = (unsigned char **)realloc(distance, distXSize * sizeof(unsigned char *)); + bestPathCost = (int **)realloc(bestPathCost, distXSize * sizeof(int *)); + distYSizes = (int *)realloc(distYSizes, distXSize * sizeof(int)); + first = (int *)realloc(first, distXSize * sizeof(int)); + last = (int *)realloc(last, distXSize * sizeof(int)); + + for (int i = distXSize/2; i < distXSize; ++i) { + distance[i] = 0; + } + } + + if (firstPM && (frameCount >= blockSize)) { + + int len = last[frameCount - blockSize] - + first[frameCount - blockSize]; + + // We need to copy distance[frameCount-blockSize] to + // distance[frameCount], and then truncate + // distance[frameCount-blockSize] to its first len elements. + // Same for bestPathCost. +/* + std::cerr << "moving " << distYSizes[frameCount - blockSize] << " from " << frameCount - blockSize << " to " + << frameCount << ", allocating " << len << " for " + << frameCount - blockSize << std::endl; +*/ + distance[frameCount] = distance[frameCount - blockSize]; + + distance[frameCount - blockSize] = (unsigned char *) + malloc(len * sizeof(unsigned char)); + for (int i = 0; i < len; ++i) { + distance[frameCount - blockSize][i] = + distance[frameCount][i]; + } + + bestPathCost[frameCount] = bestPathCost[frameCount - blockSize]; + + bestPathCost[frameCount - blockSize] = (int *) + malloc(len * sizeof(int)); + for (int i = 0; i < len; ++i) { + bestPathCost[frameCount - blockSize][i] = + bestPathCost[frameCount][i]; + } + + distYSizes[frameCount] = distYSizes[frameCount - blockSize]; + distYSizes[frameCount - blockSize] = len; + } + + double totalEnergy = 0; + if (useSpectralDifference) { + for (int i = 0; i < freqMapSize; i++) { + totalEnergy += newFrame[i]; + if (newFrame[i] > prevFrame[i]) { + frames[frameIndex][i] = newFrame[i] - prevFrame[i]; + } else { + frames[frameIndex][i] = 0; + } + } + } else { + for (int i = 0; i < freqMapSize; i++) { + frames[frameIndex][i] = newFrame[i]; + totalEnergy += frames[frameIndex][i]; + } + } + frames[frameIndex][freqMapSize] = totalEnergy; + + double decay = frameCount >= 200 ? 0.99: + (frameCount < 100? 0: (frameCount - 100) / 100.0); + + if (ltAverage == 0) + ltAverage = totalEnergy; + else + ltAverage = ltAverage * decay + totalEnergy * (1.0 - decay); + +// System.err.println(Format.d(ltAverage,4) + " " + +// Format.d(totalEnergy) + " " + +// Format.d(frameRMS)); + +// std::cerr << "ltAverage: " << ltAverage << ", totalEnergy: " << totalEnergy << ", frameRMS: " << rms << std::endl; + + if (rms <= 0.01) //!!! silenceThreshold) + for (int i = 0; i < freqMapSize; i++) + frames[frameIndex][i] = 0; + else if (normalise1) + for (int i = 0; i < freqMapSize; i++) + frames[frameIndex][i] /= totalEnergy; + else if (normalise3) + for (int i = 0; i < freqMapSize; i++) + frames[frameIndex][i] /= ltAverage; + + int stop = otherMatcher->frameCount; + int index = stop - blockSize; + if (index < 0) + index = 0; + first[frameCount] = index; + last[frameCount] = stop; + + bool overflow = false; + int mn= -1; + int mx= -1; + for ( ; index < stop; index++) { + int dMN = calcDistance(frames[frameIndex], + otherMatcher->frames[index % blockSize]); + if (mx<0) + mx = mn = dMN; + else if (dMN > mx) + mx = dMN; + else if (dMN < mn) + mn = dMN; + if (dMN >= 255) { + overflow = true; + dMN = 255; + } + if ((frameCount == 0) && (index == 0)) // first element + setValue(0, 0, 0, 0, dMN); + else if (frameCount == 0) // first row + setValue(0, index, ADVANCE_OTHER, + getValue(0, index-1, true), dMN); + else if (index == 0) // first column + setValue(frameCount, index, ADVANCE_THIS, + getValue(frameCount - 1, 0, true), dMN); + else if (index == otherMatcher->frameCount - blockSize) { + // missing value(s) due to cutoff + // - no previous value in current row (resp. column) + // - no diagonal value if prev. dir. == curr. dirn + int min2 = getValue(frameCount - 1, index, true); + // if ((firstPM && (first[frameCount - 1] == index)) || + // (!firstPM && (last[index-1] < frameCount))) + if (first[frameCount - 1] == index) + setValue(frameCount, index, ADVANCE_THIS, min2, dMN); + else { + int min1 = getValue(frameCount - 1, index - 1, true); + if (min1 + dMN <= min2) + setValue(frameCount, index, ADVANCE_BOTH, min1,dMN); + else + setValue(frameCount, index, ADVANCE_THIS, min2,dMN); + } + } else { + int min1 = getValue(frameCount, index-1, true); + int min2 = getValue(frameCount - 1, index, true); + int min3 = getValue(frameCount - 1, index-1, true); + if (min1 <= min2) { + if (min3 + dMN <= min1) + setValue(frameCount, index, ADVANCE_BOTH, min3,dMN); + else + setValue(frameCount, index, ADVANCE_OTHER,min1,dMN); + } else { + if (min3 + dMN <= min2) + setValue(frameCount, index, ADVANCE_BOTH, min3,dMN); + else + setValue(frameCount, index, ADVANCE_THIS, min2,dMN); + } + } + otherMatcher->last[index]++; + } // loop for row (resp. column) + + vector<double> tmp = prevFrame; + prevFrame = newFrame; + newFrame = tmp; + + frameCount++; + runCount++; + + otherMatcher->runCount = 0; + + if (overflow && !silent) + cerr << "WARNING: overflow in distance metric: " + << "frame " << frameCount << ", val = " << mx << endl; + + if (!silent) + std::cerr << "Frame " << frameCount << ", d = " << (mx-mn) << std::endl; + + if ((frameCount % 100) == 0) { + if (!silent) { + cerr << "Progress:" << frameCount << " " << ltAverage << endl; +// Profile.report(); + } + } +//!!! if (frameCount == maxFrames) +// closeStreams(); +// } +} // processFrame() + +int +Matcher::calcDistance(const vector<double> &f1, const vector<double> &f2) +{ + double d = 0; + double sum = 0; + for (int i = 0; i < freqMapSize; i++) { + d += fabs(f1[i] - f2[i]); + sum += f1[i] + f2[i]; + } + // System.err.print(" " + Format.d(d,3)); + if (sum == 0) + return 0; + if (normalise2) + return (int)(scale * d / sum); // 0 <= d/sum <= 2 + if (!normalise4) + return (int)(scale * d); + // double weight = (5 + Math.log(f1[freqMapSize] + f2[freqMapSize]))/10.0; + double weight = (8 + log(sum)) / 10.0; + // if (weight < mins) { + // mins = weight; + // System.err.println(Format.d(mins,3) + " " + Format.d(maxs)); + // } + // if (weight > maxs) { + // maxs = weight; + // System.err.println(Format.d(mins,3) + " " + Format.d(maxs)); + // } + if (weight < 0) + weight = 0; + else if (weight > 1) + weight = 1; + return (int)(scale * d / sum * weight); +} // calcDistance() + +int +Matcher::getValue(int i, int j, bool firstAttempt) +{ + if (firstPM) + return bestPathCost[i][j - first[i]]; + else + return otherMatcher->bestPathCost[j][i - otherMatcher->first[j]]; +} // getValue() + +void +Matcher::setValue(int i, int j, int dir, int value, int dMN) +{ + if (firstPM) { + distance[i][j - first[i]] = (unsigned char)((dMN & MASK) | dir); + bestPathCost[i][j - first[i]] = + (value + (dir==ADVANCE_BOTH? dMN*2: dMN)); + } else { + if (dir == ADVANCE_THIS) + dir = ADVANCE_OTHER; + else if (dir == ADVANCE_OTHER) + dir = ADVANCE_THIS; + int idx = i - otherMatcher->first[j]; + if (idx == (int)otherMatcher->distYSizes[j]) { + // This should never happen, but if we allow arbitrary + // pauses in either direction, and arbitrary lengths at + // end, it is better than a segmentation fault. + std::cerr << "Emergency resize: " << idx << " -> " << idx * 2 << std::endl; + otherMatcher->distYSizes[j] = idx * 2; + otherMatcher->bestPathCost[j] = + (int *)realloc(otherMatcher->bestPathCost[j], + idx * 2 * sizeof(int)); + otherMatcher->distance[j] = + (unsigned char *)realloc(otherMatcher->distance[j], + idx * 2 * sizeof(unsigned char)); + } + otherMatcher->distance[j][idx] = (unsigned char)((dMN & MASK) | dir); + otherMatcher->bestPathCost[j][idx] = + (value + (dir==ADVANCE_BOTH? dMN*2: dMN)); + } +} // setValue() +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Matcher.h Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,341 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 _MATCHER_H_ +#define _MATCHER_H_ + +#include <vector> +#include <iostream> +#include <sstream> +#include <cmath> + +#define ADVANCE_THIS 1 +#define ADVANCE_OTHER 2 +#define ADVANCE_BOTH 3 +#define MASK 0xfc + + +using std::vector; +using std::string; +using std::cerr; +using std::endl; + +/** 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. + */ + +class Matcher +{ +protected: + /** Points to the other performance with which this one is being + * compared. The data for the distance metric and the dynamic + * time warping is shared between the two matchers. In the + * original version, only one of the two performance matchers + * contained the distance metric. (See <code>first</code>) + */ + Matcher *otherMatcher; + + /** Indicates which performance is considered primary (the + * score). This is the performance shown on the vertical axis, + * and referred to as "this" in the codes for the direction of + * DTW steps. */ + bool firstPM; + + /** Sample rate of audio */ + float sampleRate; + + /** Onset time of the first note in the audio file, in order to + * establish synchronisation between the match file and the audio + * data. */ + double matchFileOffset; + + /** Flag indicating whether or not each frame of audio should be + * normalised to have a sum of 1. (Default = false). */ + bool normalise1; + + /** Flag indicating whether or not the distance metric for pairs + * of audio frames should be normalised by the sum of the two + * frames. (Default = false). */ + bool normalise2; + + /** Flag indicating whether or not each frame of audio should be + * normalised by the long term average of the summed energy. + * (Default = false; assumes normalise1 == false). */ + bool normalise3; + + /** Flag indicating whether or not the distance metric for pairs + * of audio frames should be normalised by the log of the sum of + * the frames. (Default = false; assumes normalise2 == + * false). */ + bool normalise4; + + /** Flag indicating whether or not the half-wave rectified + * spectral difference should be used in calculating the distance + * metric for pairs of audio frames, instead of the straight + * spectrum values. (Default = true). */ + bool useSpectralDifference; + + bool useChromaFrequencyMap; + + /** Scaling factor for distance metric; must guarantee that the + * final value fits in the data type used, that is, unsigned + * char. (Default = 16). + */ + double scale; + + /** Spacing of audio frames (determines the amount of overlap or + * skip between frames). This value is expressed in + * seconds. (Default = 0.020s) */ + double hopTime; + + /** The size of an FFT frame in seconds. (Default = 0.04644s). + * Note that the value is not taken to be precise; it is adjusted + * so that <code>fftSize</code> is always power of 2. */ + double fftTime; + + /** The width of the search band (error margin) around the current + * match position, measured in seconds. Strictly speaking the + * width is measured backwards from the current point, since the + * algorithm has to work causally. + */ + double blockTime; + + /** Spacing of audio frames in samples (see <code>hopTime</code>) */ + int hopSize; + + /** The size of an FFT frame in samples (see <code>fftTime</code>) */ + int fftSize; + + /** Width of the search band in FFT frames (see <code>blockTime</code>) */ + int blockSize; + + /** The number of frames of audio data which have been read. */ + int frameCount; + + /** RMS amplitude of the current frame. */ +// double frameRMS; + + /** Long term average frame energy (in frequency domain + * representation). */ + double ltAverage; + + /** The number of frames sequentially processed by this matcher, + * without a frame of the other matcher being processed. + */ + int runCount; + + /** Interactive control of the matching process allows pausing + * computation of the cost matrices in one direction. + */ + bool paused; + + /** The total number of frames of audio data to be read. */ + int maxFrames; + + /** A mapping function for mapping FFT bins to final frequency + * bins. The mapping is linear (1-1) until the resolution + * reaches 2 points per semitone, then logarithmic with a + * semitone resolution. e.g. for 44.1kHz sampling rate and + * fftSize of 2048 (46ms), bin spacing is 21.5Hz, which is mapped + * linearly for bins 0-34 (0 to 732Hz), and logarithmically for + * the remaining bins (midi notes 79 to 127, bins 35 to 83), + * where all energy above note 127 is mapped into the final + * bin. */ + vector<int> freqMap; + + /** The number of entries in <code>freqMap</code>. Note that the + * length of the array is greater, because its size is not known + * at creation time. */ + int freqMapSize; + + /** The most recent frame; used for calculating the frame to frame + * spectral difference. */ + vector<double> prevFrame; + vector<double> newFrame; + + /** A block of previously seen frames are stored in this structure + * for calculation of the distance matrix as the new frames are + * read in. One can think of the structure of the array as a + * circular buffer of vectors. The last element of each vector + * stores the total energy. */ + vector<vector<double> > frames; + + /** The best path cost matrix. */ + int **bestPathCost; + + /** The distance matrix. */ + unsigned char **distance; + + /** The bounds of each row of data in the distance and path cost matrices.*/ + int *first; + int *last; + + /** Height of each column in distance and bestPathCost matrices */ + int *distYSizes; + + /** Width of distance and bestPathCost matrices and first and last vectors */ + int distXSize; + + /** Total number of audio frames, or -1 for live or compressed input. */ + long fileLength; + + bool initialised; + +//!!! bool atEnd; //!!! + + /** Disable or enable debugging output */ + static bool silent; + + static const double decay = 0.99; + static const double silenceThreshold = 0.0004; + static const int MAX_RUN_COUNT = 3; + + friend class Finder; //!!! + +public: + /** Constructor for Matcher. + * + * @param p The Matcher representing the performance with which + * this one is going to be matched. Some information is shared + * between the two matchers (currently one possesses the distance + * matrix and optimal path matrix). + */ + Matcher(float rate, Matcher *p); + + ~Matcher(); + + /** For debugging, outputs information about the Matcher to + * standard error. + */ + void print(); + + /** Gives some basic `header' information about the Matcher. */ + string toString(); + + /** Adds a link to the Matcher object representing the performance + * which is going to be matched to this one. + * + * @param p the Matcher representing the other performance + */ + void setOtherMatcher(Matcher *p) { + otherMatcher = p; + } // setOtherMatcher() + + int getFFTSize() { + return fftSize; + } + + int getHopSize() { + return hopSize; + } + + int getFrameCount() { + return frameCount; + } + +protected: + template <typename T> + void initVector(vector<T> &vec, int sz, T dflt = 0) { + std::cerr << "initVector: " << sz << " * " << sizeof(T) << " = " + << sz * sizeof(T) << std::endl; + vec.clear(); + while ((int)vec.size() < sz) vec.push_back(dflt); + } + + template <typename T> + void initMatrix(vector<vector<T> > &mat, int hsz, int vsz, + T dflt = 0, int fillTo = -1) { + std::cerr << "initMatrix: " << hsz << " * " << vsz << " * " + << sizeof(T) << " = " + << hsz * vsz * sizeof(T) << std::endl; + mat.clear(); + if (fillTo < 0) fillTo = hsz; + for (int i = 0; i < hsz; ++i) { + mat.push_back(vector<T>()); + if (i < fillTo) { + while ((int)mat[i].size() < vsz) { + mat[i].push_back(dflt); + } + } + } + } + + void init(); + + void makeFreqMap(int fftSize, float sampleRate); + + /** Creates a map of FFT frequency bins to comparison bins. Where + * the spacing of FFT bins is less than 0.5 semitones, the + * mapping is one to one. Where the spacing is greater than 0.5 + * semitones, the FFT energy is mapped into semitone-wide + * bins. No scaling is performed; that is the energy is summed + * into the comparison bins. See also processFrame() + */ + void makeStandardFrequencyMap(int fftSize, float sampleRate); + + void makeChromaFrequencyMap(int fftSize, float sampleRate); + + /** Processes a frame of audio data by first computing the STFT + * with a Hamming window, then mapping the frequency bins into a + * part-linear part-logarithmic array, then (optionally) + * computing the half-wave rectified spectral difference from the + * previous frame, then (optionally) normalising to a sum of 1, + * then calculating the distance to all frames stored in the + * otherMatcher and storing them in the distance matrix, and + * finally updating the optimal path matrix using the dynamic + * time warping algorithm. + */ + void processFrame(double *reBuffer, double *imBuffer); + + /** 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 + * @return the distance, scaled and truncated to an integer + */ + int calcDistance(const vector<double> &f1, const vector<double> &f2); + + /** Retrieves values from the minimum cost matrix. + * + * @param i the frame number of this Matcher + * @param j the frame number of the other Matcher + * @return the cost of the minimum cost path to this location + */ + int getValue(int i, int j, bool firstAttempt); + + /** Stores entries in the distance matrix and the optimal path matrix. + * + * @param i the frame number of this Matcher + * @param j the frame number of the other Matcher + * @param dir the direction from which this position is reached with + * minimum cost + * @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); + + friend class MatchFeeder; + +}; // class Matcher + +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Path.cpp Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,76 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 "Path.h" + +int +Path::smooth(std::vector<int> &x, std::vector<int> &y, int length) +{ + if (length == 0) + return 0; + while (val.size() < length) { + val.push_back(0); + len.push_back(0); + } + int p = 0; + val[0] = len[0] = 0; + for (int i = 1; i < length; i++) { // H = 1; V = 2; D = 3 + int current = x[i] - x[i-1] + 2 * (y[i] - y[i-1]); + if (current == val[p]) { + len[p]++; + } else if ((current == 3) || (val[p] == 0)) { + val[++p] = current; + len[p] = 1; + } else if (val[p] + current == 3) { // 1 + 2 + if (--len[p] == 0) + p--; + if (val[p] == 3) + len[p]++; + else { + val[++p] = 3; + len[p] = 1; + } + } else { // val[p] == 3 && current != 3 + if ((val[p-1] == current) || + (val[p-1] == 0) || + (len[p] > MAX_RUN_LENGTH)) { + val[++p] = current; + len[p] = 1; + } else { + if (--len[p-1] == 0) { + val[p-1] = val[p]; + len[p-1] = len[p]; + p--; + if (val[p-1] == 3) { + len[p-1] += len[p]; + p--; + } + } + len[p]++; + } + } + } + int i = 1; + for (int pp = 1; pp <= p; pp++) { + int dx = val[pp] & 1; + int dy = val[pp] >> 1; + for (int j = len[pp]; j > 0; j--, i++) { + x[i] = x[i-1] + dx; + y[i] = y[i-1] + dy; + } + } + return i; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Path.h Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,46 @@ +/* -*- 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. + This file copyright 2007 Simon Dixon, Chris Cannam and QMUL. + + 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 _PATH_H_ +#define _PATH_H_ + +#include <vector> + +class Path +{ +public: + Path() { } + + /** Smooths an alignment path.<BR> + * Consider the path as a sequence of horizontal (H), vertical (V) and + * diagonal (D) steps. The smoothing consists of 2 rewrite rules:<BR> + * HnDmVn / Dm+n (where m is less than MAX_RUN_LENGTH)<BR> + * VnDmHn / Dm+n (where m is less than MAX_RUN_LENGTH)<BR> + * The new path is written over the old path. Note that the end points of + * each application of a rewrite rule do not change. + * @return the length of the new path + */ + int smooth(std::vector<int> &x, std::vector<int> &y, int length); + +protected: + static const int MAX_RUN_LENGTH = 50; + + std::vector<int> val; + std::vector<int> len; +}; + +#endif +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/README Wed Oct 24 12:13:43 2007 +0000 @@ -0,0 +1,14 @@ + +MATCH Vamp plugin +================= + +This is a Vamp plugin implementation of the MATCH audio alignment +algorithm: + + http://www.elec.qmul.ac.uk/people/simond/match/index.html + +This plugin is Copyright (c) 2007 Simon Dixon and Chris Cannam, +distributed under the GNU General Public License. See the file +COPYING for details. + +