Wiki » History » Version 27

Chris Cannam, 2013-10-31 03:49 PM

1 1 Chris Cannam
h1. Wiki
2 1 Chris Cannam
3 27 Chris Cannam
{{>toc}}
4 27 Chris Cannam
5 10 Chris Cannam
h2. The method
6 10 Chris Cannam
7 14 Chris Cannam
*The method to be implemented* is that from "Anssi's Constant-Q Toolbox page":http://www.eecs.qmul.ac.uk/~anssik/cqt/.
8 1 Chris Cannam
9 1 Chris Cannam
 * The MATLAB toolbox reference implementation is "here":/projects/constant-q-toolbox.
10 1 Chris Cannam
11 16 Chris Cannam
 * The "QM-DSP":/projects/qm-dsp library also contains a Constant-Q implementation: there is a Vamp plugin of it in the "QM Vamp Plugins":/projects/qm-vamp-plugins set. I believe it is based on the method of Brown and Puckette. Our version isn't very good. Among other things, we should aim to produce an improved plugin. But this one may be useful as an extra reference.
12 4 Chris Cannam
13 8 Chris Cannam
*Has anyone already made one* corresponding directly to the Schörkhuber/Klapuri method? We don't want to duplicate effort. And if someone has, why don't I know about it? -- can we do anything to help make it more universally known?
14 9 Chris Cannam
15 9 Chris Cannam
*What other modern methods* exist in C++?
16 10 Chris Cannam
17 22 Emmanouil Benetos
Emmanouil: there is a Dec 2011 discussion on music-ir about CQT implementations. It seems that there is a C++ GNU GPL 3 code for a forwards CQT available in the Qitch plugin for SuperCollider at http://sourceforge.net/projects/sc3-plugins/ (which however implements Judith Brown's old algorithm)
18 22 Emmanouil Benetos
19 22 Emmanouil Benetos
20 10 Chris Cannam
h2. What we want it for
21 1 Chris Cannam
22 11 Chris Cannam
The immediate requirement is as the first step in implementing Emmanouil Benetos and Simon Dixon's "music transcription":http://www.mitpressjournals.org/doi/abs/10.1162/COMJ_a_00146 method for a Vamp plugin.
23 11 Chris Cannam
24 11 Chris Cannam
But the reason we aren't using the QM-DSP constant-Q implementation is that it simply isn't good enough, and that means it isn't really good enough for the rest of the world either. We should make a better one to improve upon the existing QM Vamp Plugin as well.
25 13 Chris Cannam
26 17 Chris Cannam
The method described is invertible with some signal loss -- we should implement the inversion as well.
27 17 Chris Cannam
28 13 Chris Cannam
h2. Implementation notes
29 13 Chris Cannam
30 13 Chris Cannam
The Schörkhuber/Klapuri method has (at least) three useful qualities:
31 1 Chris Cannam
32 1 Chris Cannam
 # It's mathematically diligent. Decisions such as kernel and window shape are explained and supported in the paper.
33 17 Chris Cannam
 # There is an open source MATLAB implementation available, and others have tested it.
34 17 Chris Cannam
 # It is (somewhat) invertible. 
35 17 Chris Cannam
36 18 Chris Cannam
Also the nature of the constant-Q transform is such that it should be possible to test it using relatively little data.
37 17 Chris Cannam
38 20 Chris Cannam
This makes it a good case for implementation using a unit testing or test-first regime:
39 1 Chris Cannam
40 19 Chris Cannam
 # Mathematical support will help in generating synthetic test cases
41 19 Chris Cannam
 # The existing implementation gives a reference at each step (although we need to be careful not to trust it implicitly)
42 19 Chris Cannam
 # Invertibility means we can test the forward-backward transforms.
43 21 Chris Cannam
44 21 Chris Cannam
h2. Goals
45 21 Chris Cannam
46 21 Chris Cannam
This version needs to be:
47 21 Chris Cannam
48 21 Chris Cannam
 # *Correct* -- a lot of people have looked at the output of the existing QM-DSP constant-Q transform and said "hm, that doesn't look very good" but nobody who really knows their stuff has ever taken the time to figure out what's wrong with it. This sort of review after the fact just doesn't seem to happen. We should aim to see that it's right as we go along, with a suitable testing regime.
49 21 Chris Cannam
 # *Fast* -- the method has the potential to be pretty fast, we should make the most of it
50 21 Chris Cannam
 # *Compact* -- avoiding hard-to-satisfy library dependencies so that people can apply the code easily
51 23 Chris Cannam
52 23 Chris Cannam
h2. General procedure
53 23 Chris Cannam
54 25 Chris Cannam
 # Pick apart the MATLAB and implement it in another high-level language. I'm using Yeti with "May":/projects/may, because it has very strong typing and is easy to write tests for, so it should be possible to have a high confidence of getting correct code -- and because I like it. The main thing is to target a language without the same built-in syntax as MATLAB for matrix and complex arithmetic, so that you actually have to understand how the original algorithm works. Once I have a version in another high-level language that produces the same results, I can be confident I have understood (at some level) how the toolbox code works.
55 23 Chris Cannam
 # Refactor and introduce unit tests in addition to the high-level tests that compare results against the original MATLAB.
56 1 Chris Cannam
 # Port across the test structure and reimplement the code into C++.
57 24 Chris Cannam
58 24 Chris Cannam
Is this any more efficient or effective than porting directly to C++? Not sure, let's find out -- mostly in the past I've gone straight to C++ so this is a novelty for me.
59 26 Chris Cannam
60 26 Chris Cannam
h2. Sketches and plots