# Algorithm for testing input sound for multiple expected notes?

** originally I asked this question on stack exchange and was pointed to dsp.stackexchange **

I need to determine when the correct musical notes (from a piano) such as in a chord are being played. While detecting single notes is a no brainer, and full music transcription seems to still be considered a research problem, I'm hoping that since my program knows which combination of notes to expect and only needs to classify the played notes (maximum of six) as correct/incorrect that the task will fall somewhere in between.

Can anyone point me towards an efficient algorithm (I need to implement it in JavaScript) that should be able to achieve this with minimal false negatives (incorrectly telling the user they hit the wrong note)?

My current idea is to test that the signal has better correlation with the target frequency than the nearest semitone above and below for each expected note.

• I hate to tell you, but JavaScript is really one of the worst programming languages you could chose for such a problem. – Marcus Müller Sep 8 '15 at 7:26
• it is what it is :) ... but still have all the processing power of the host to make up for any inefficiencies - so should still be able to run anything that would be passable in an embedded situation. – norlesh Sep 8 '15 at 7:30
• but still have all the processing power of the host to make up for any inefficiencies I'd call that an exaggeration. This actually strongly restricts the options you have; for example, a natively implemented 1024 FFT happens in microseconds on a modern CPU, and can be heavily multithreaded (especially if the FFT size is larger); on JavaScript, you're inherently single-threaded, and the available FFT implementations are either mathematically bad (DSP.js) or still about 10000 to 100000 times slower than native (JSFFT), making approaches that incorporate overlapping FFTs practically impossible. – Marcus Müller Sep 8 '15 at 7:57
• The same goes for things like linear algebra routines -- Implementing an efficient Matrix decomposition is impossible in JavaScript, because the majority of time is spent interpreting the language and handling indirection, and only a fraction is spent doing numerical math; this together with a lack of syntactic sugar and interoperability with native numerical libraries rule out algorithms with depend on things like singular value decomposition. I'd love to be proven wrong, but I just don't see how you could implement such things which JavaScript in a manner that's acceptably fast. – Marcus Müller Sep 8 '15 at 8:00
• Thank's for your input Marcus - shoehorning this into the JavaScript VM (a constraint of the project) may well be very difficult, but that's a separate matter. At the moment my concern and the subject of the question is what algorithms could produce the required output? – norlesh Sep 8 '15 at 8:33

I'd like to point out two things beforehand:

1. this is a complex question, and
2. as soon as you have figured out how to do this algorithmically, you'll have to write a lot of signal processing functionality in JS that other languages would already have access to (e.g. python through scipy/numpy, C/C++/Fortran through LAPACK/BLAS/FFTW etc)

so this will become a very complex project, and if you have the chance to influence the expectations for fast results, I'd recommend not promising a working prototype too soon.

Now, for a start, this looks like a linear algebra problem. That's because LA is kind of the sonic screw driver of DSP; give a man a sonic screwdriver, and everything looks like... wait, that metaphor doesn't work.

So, anyways, what you want to do is find a vector representation of your signal under test and map it to coordinates in a space spanned by the possible musical notes. Mathematically, you want to

1. Find a set of base vectors representing your notes,
2. Find a suitable base in which you can represent both these vectors and your signal
3. Project the signal vector onto your note vector; the magnitude of the coefficients gives you the "amount" of the respective notes being represented in the signal.

As an example, the discrete Fourier transform takes signals that are represented in a time sampling base (every base vector is $(0,\ldots,0,1,0,\ldots,0)$, with the 1 representing the the sample time) and transforms it to a base system of orthogonal oscillations (The nth base vector of that base is $( e^{j2\pi nt})_{t\in (0,\ldots, N)}$). That is such a base transform.

You could simply record fixed lengths of your tones, normalize them in power (important!) and do a dot product with each of these, and find the ones that are above a certain threshold. Do that again with the piece of your signal starting one sample later, and find the notes that have been present with enough energy for enough time. What you end up with is a FIR filter bank.

Now, with a proper language and libraries, that would be a few lines of code, and one could do everything in frequency domain rather than time domain, reducing the effort of the convolution above to a multiplication and two FFTs, but since there is (I don't think there can be, due to architectural restrictions) no FFT in JavaScript, this is probably not easy to optimize. It might be that for reliable results, your algorithm might become too slow to process the audio signal in real time.

• developer.mozilla.org/en/docs/Web/API/AnalyserNode does an FFT in native code behind the scenes and exposes the result in JavaScript – norlesh Sep 8 '15 at 9:35
• @norlesh: woah! But I thought you needed something in pure JavaScript? Well, in that case, do a sufficiently fine FFT, and find the max(abs) bin, moving median, compare with should-be bin – Marcus Müller Sep 8 '15 at 13:45

The feature you should be looking for is chroma (Harmonic Pitch Class Profile). It maps the FFT to the 12 notes of music. It also wraps notes across octaves. Now, based on the peaks in these 12 notes, you'll need to train a classifier to identify different chords. You'll find quite a lot of matlab/python/cpp implementations online, not sure for JS. Also check answers in these posts 1) https://stackoverflow.com/questions/4337487/chord-detection-algorithms 2) https://stackoverflow.com/questions/4033083/guitar-chord-recognition-algorithm

One possibility is to just look at the ratios of the frequencies present. For example, let's assume you are playing a chord on the piano and that each key is roughly just a sinusoid.

If you play a major triad, the ratios of the frequencies will always be the same, regardless of what the root note is. If equal-tempered tuning is used, the ratios of the higher frequencies to the root would be $2^{4/12}$ and $2^{7/12}$.

In the case of other harmonics being present, you could use a threshold that discriminates against frequencies that are below a certain amplitude.

What you are trying to do is actually not that straight forward. As other people have suggested the FFT can be used to determine the frequency representation of each note. Unfortunately, a direct application of the FFT will not work for your case unless you use enough samples.

The FFT has a frequency resolution of: $$\frac{1}{T}$$ Where $T$ is the length of your window size i.e. the amount of signal you take the FFT of. On the low end of the frequency spectrum you will need to distinguish between notes that are 1Hz apart. This means you need $T=1$ i.e. your latency is at least 1s.

Your other problem is windowing. Your samples will have certain bandwidth in the frequency domain. This means that your A4 note will have frequency components in the neighboring notes. If you have high enough resolution, you should be able to find the maximum, which will correspond to your note frequency.

If you need real time responsiveness you would probably need to look into parametric methods.