[ editor's note:  this was posted to music-dsp@shoko.calarts.edu]

From: "Eric Scheirer" <eds@media.mit.edu>
Subject: Beat-tracking algorithm
Date: Mon, 3 May 1999 07:59:19 -0400


I've received a lot of requests for the source code for my beat-tracking
algorithm, and more information about how it works.  I decided to respond
on the list rather than privately to each individual.

You can hear examples of the software working at
  <http://sound.media.mit.edu/~eds/beat/results.html>

These examples were all created automatically, using the same parameter
settings for each track (no hand-tweaking).  Thus the results are a good,
fair test of the general function of the algorithm, and could be improved
if you were willing to adjust the parameters on a track by track basis.

The algorithm is in two stages.  First, subband decomposition and
rectification, and second, periodicity detection and heuristic analyis.

The only real major advance in this method compared to the "obvious"
ones is the observation that you have to do the periodicity detection
in subbands.  My implementation uses six, but more or fewer (down to,
perhaps, four) should work as well.  The technical paper [1] contains
a more involved discussion of this observation.  My implementation
uses very steep high-order filters to minimize crossover between
subbands, but I no longer feel that this is important.  Thus, this is
a place where the efficiency of the implementation can be improved.
I half-wave rectify and smooth the output of each subband filter, and
take the derivative.  I don't do any thresholding or attempt to locate
"onsets" in the signals; it seems that doing this rarely helps and
often hurts, and is very difficult to do robustly.

Using the envelope derivatives, you then figure out the periodicity in
each subband.  Autocorrelation would work, but autocorrelation loses
the phase, which tells you where the beat is (it tells you tempo, but
doesn't give you beat placements).  In my implementation, I use banks
of comb peak filters [ H(z) = 1 / (1 - z^(-n)) ] tuned to a range of
the tempi in which I'm interested, that is, for  n  corresponding to
the range 60-180 bpm.  These filters will phase-lock to a signal with
quasi-periodic energy near their resonant frequency.

At this point, we have to figure out which comb filters in which bands
are really responding, and then integrate the information across bands
in some good way.  In the current implementation, the former is
accomplished by inspecting the RMS power output of each of the filters,
and the latter by simple summation of predictions: each band generates
"predictions" for where in time it thinks the next beat will be (based
on the phase of the responsive comb filters), and a beat is actually
generated at the points in time that many predictions have lined up.

All this is described in much more detail in the paper.

The code is available at http://sound.media.mit.edu/~eds/beat/tapping.tar.gz
for research purposes only.  You're free to use the code for your
personal experiments or for research work, but if you want to incorporate
it in a product, you have to license it from MIT (this could be free,
but we'd have to go through the formality).  Please credit me if you
do follow-on work using the software.  The software ran at one time
on an Alpha workstation, but I can't guarantee that it still works
or will be easily portable.  If anyone ports it to other platforms,
I would be happy to host the ported version(s) in the same place.
There's lots of poorly-described parameters to tweak; be prepared to
spend a while figuring out what they do.

Happy beat tracking,

 -- Eric

REFERENCES

[1] Scheirer, E. D. Tempo and beat analysis of acoustic musical signals.
    J. Acoust. Soc. Am 103:1 pp 588-601 (Jan 1998).




dupswapdrop: the music-dsp mailing list and website
http://shoko.calarts.edu/~glmrboy/musicdsp/music-dsp.html