Can a Computer Feel the Beat?

A beat graph, taken from [1].

It is relatively easy for a human with a watch to listen to a piece of music and calculate the number of beats per minute (bpm). For example, one can listen for 10 seconds while counting the number of beats heard, and then multiply this number by 6. It turns out that computers find this far more difficult, and anecdotal evidence suggests the few freely-available algorithms are wrong about 25% of the time!

Automatically detecting the bpm for a recording has a number of uses. It is useful for DJs to seamlessly mix between songs (see, for example, the BpmDj software). It is also useful for runners who would like to adapt their running style to a particular number of steps per minute, by allowing them to choose songs that they can run in time to. (An incorrect number of steps per minute, or cadence, is thought to be inefficient and to lead to an increased risk of injury; 170-180 steps per minute is currently thought ideal.)

The free algorithms available use a range of techniques, including standard signal processing techniques and bespoke could-have-been-made-up-on-the-spot techniques. For example, Fourier transforms are used in some but not all algorithms. Some freely available algorithms include:

This project would investigate existing freely available algorithms for detecting bpm from audio files. This would constitute both describing and contrasting the technical details of the algorithms, and trying them out to see how well they work on a range of sample music files.

The following would be useful for the project, but are not formal prerequisites:

Familiarity with some sort of computer programming language suitable for analyzing sound files (e.g. C, C++, Python, Matlab, etc).
Familiarity with some parts of signal processing (e.g. Fourier transforms, low-pass and high-pass filters, windowing).
Familiarity with some statistical tests for time-series data (e.g. two-point correlation, covariance, etc).