Beat Tracking by Dynamic Programming

Ellis, Daniel P. W.

Beat tracking — i.e. deriving from a music audio signal a sequence of beat instants that might correspond to when a human listener would tap his foot — involves satisfying two constraints. On the one hand, the selected instants should generally correspond to moments in the audio where a beat is indicated, for instance by the onset of a note played by one of the instruments. On the other hand, the set of beats should reflect a locally-constant inter-beat-interval, since it is this regular spacing between beat times that defines musical rhythm. These dual constraints map neatly onto the two constraints optimized in dynamic programming, the local match, and the transition cost. We describe a beat tracking system which first estimates a global tempo, uses this tempo to construct a transition cost function, then uses dynamic programming to find the best-scoring set of beat times that reflect the tempo as well as corresponding to moments of high 'onset strength' in a function derived from the audio. This very simple and computationally efficient procedure is shown to perform well on the MIREX-06 beat tracking training data, achieving an average beat accuracy of just under 60% on the development data. We also examine the impact of the assumption of a fixed target tempo, and show that the system is typically able to track tempo changes in a range of ±10% of the target tempo.


Also Published In

Journal of New Music Research

More About This Work

Academic Units
Electrical Engineering
Published Here
February 13, 2012