Journal of New Music Research
2001, Vol. 30, No. 2, pp. 159–171

0929-8215/01/3002-159$16.00© Swets & Zeitlinger

An Audio-based Real-time Beat Tracking System for Music With
or Without Drum-sounds
Masataka Goto
National Institute of Advanced Industrial Science and Technology, Tsukuba, Ibaraki, Japan

Abstract
This paper describes a real-time beat tracking system thatrecognizes a hierarchical beat structure comprising thequarter-note, half-note, and measure levels in real-world
audio signals sampled from popular-music compact discs.
Most previous beat-tracking systems dealt with MIDI signals
and had difficulty in processing, in real time, audio signals
containing sounds of various instruments and in tracking
beats above the quarter-note level. The system described here
can process music with drums and music without drums
and can recognize the hierarchical beat structure by using
three kinds of musical knowledge: of onset times, of chord
changes, and of drum patterns. This paper also describes
several applications of beat tracking, such as beat-driven
real-time computer graphics and lighting control.

1 Introduction
The goal of this study is to build a real-time system that can
track musical beats in real-world audio signals, such as thosesampled from compact discs. I think that building such a system that even in its preliminary implementation can work inreal-world environments is an important initial step in the computational modeling of music understanding. This is because,
as known from the scaling-up problem (Kitano, 1993) in thedomain of artificial intelligence, it is hard to scale-up a system
whose preliminary implementation works only in laboratory(toy-world) environments. This real-world oriented approachalso facilitates the implementation of various practical applications in which music synchronization is necessary.
Most previous beat-tracking related systems had difficulty
working in real-world acoustic environments. Most of them(Dannenberg & Mont-Reynaud, 1987; Desain & Honing,
1989, 1994;Allen & Dannenberg, 1990; Driesse, 1991; Rosen-thal,1992a,1992b;Rowe,1993;Large,1995)usedas their input
MIDI-like representations, and their applications are limited
because it is not easy to obtain complete MIDI representations
from real-world audio signals. Some systems (Schloss, 1985;
Katayose, Kato, Imai, & Inokuchi, 1989; Vercoe, 1994; Todd,
1994; Todd & Brown, 1996; Scheirer, 1998) dealt with audio
signals, but they either did not consider the higher-level beatstructureabovethequarter-notelevelor did not process popular
music sampled from compact discs in real time. Although I
developed two beat-tracking systems for real-world audio
signals, one for music with drums (Goto & Muraoka, 1994,
1995, 1998) and the other for music without drums (Goto &Muraoka, 1996, 1999), they were separate systems and theformer was not able to recognize the measure level.
This paper describes a beat-tracking system that can deal
with the audio signals of popular-music compact discs in realtime regardless of whether or not those signals contain drumsounds. The system can recognize the hierarchical beatstructure comprising the quarter-note level (almost regularly
spaced beat times), the half-note level, and the measure level(bar-lines).1 This structure is shown in Figure 1. It assumes
that the time-signature of an input song is 4/4 and that thetempo is roughly constant and is either between 61 M.M.2 and
185 M.M. (for music with drums) or between 61 M.M. and
120 M.M. (for music without drums). These assumptions fit
a large class of popular music.

1
Although this system does not rely on score representation, for convenience this paper uses score-representing terminology like thatused by Rosenthal (1992a, 1992b). In this formulation the quarternote level indicates the temporal basic unit that a human feels inmusic and that usually corresponds to a quarter note is scores.
2
Mälzel’s Metronome: the number of quarter notes per minute.

Accepted: 9 May, 2001
Correspondence: Dr. Masataka Goto, Information Technology Research Institute, National Institute of Advanced Industrial Science andTechnology, 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, JAPAN. Tel.: +81-298-61-5898, Fax: +81-298-61-3313, E-mail: m.goto@aist.go.jp

Masataka Gotoin performers’ brains
hierarchical beat structure
time

Measure level(measure times)

Half-note level(half-note times)

Quarter-note level(beat times)

Fig. 1.

Beat-tracking problem.

The main issues in recognizing the beat structure in realworld musical acoustic signals are (1) detecting beat-tracking
cues in audio signals, (2) interpreting the cues to infer the beatstructure, and (3) dealing with the ambiguity of interpretation. First, it is necessary to develop methods for detecting
effective musical cues in audio signals. Although various cues
– such as onset times, notes, melodies, chords, and repetitivenote patterns – were used in previous score-based or MIDIbased systems (Dannenberg & Mont-Reynaud, 1987; Desain& Honing, 1989, 1994; Allen & Dannenberg, 1990; Driesse,
1991; Rosenthal, 1992a, 1992b; Rowe, 1993; Large, 1995),
most of those cues are hard to detect in complex audio signals.
Second, higher-level processing using musical knowledge is
indispensable for inferring each level of the hierarchical beatstructure from the detected cues. It is not easy, however, tomake musical decisions about audio signals, and the previous
audio-based systems (Schloss, 1985; Katayose et al., 1989;
Vercoe, 1994; Todd, 1994; Todd & Brown, 1996; Scheirer,
1998) did not use such musical-knowledge-based processing
for inferring the hierarchical beat structure. Although someof the above-mentioned MIDI-based systems used musicalknowledge, the processing they used cannot be used in audiobased systems because the available cues are different. Third,
it must be taken into account that multiple interpretations ofbeats are possible at any given time. Because there is not necessarily a single specific sound that directly indicates the beatposition, there are various ambiguous situations. Two examples are those in which several detected cues may correspondto a beat and those in which different inter-beat intervals (thedifference between the times of two successive beats) seemplausible.
The following sections introduce a new approach to thebeat-tracking problem and describe a beat-tracking model that
addresses the issues mentioned above. Experimental results
obtained with a system based on that model are then shown,and several of its beat-tracking applications are described.

Forward processes

Hierarchical beat structure

process of indicating
the beat structuremusical elements
process of producing
musical sounds
process of acoustic
transmission

Beat Tracking

Musical audio signals

Inverse problem

160

audio signals
Fig. 2.

Beat tracking as an inverse problem.

be considered the inverse problem of the following threeforward processes by music performers: the process of indicating or implying the beat structure in musical elements
when performing music, the process of producing musicalsounds (singing or playing musical instruments), and theprocess of acoustic transmission of those sounds. Although
in the brains of performers music is temporally organizedaccording to its hierarchical beat structure, this structure is
not explicitly expressed in music; it is implied in the relations among various musical elements which are not fixed
and which are dependent on musical genres or pieces. All themusical elements constituting music are then transformed
into audio signals through the processes of musical soundproduction and acoustic transmission.
The principal reason that beat tracking is intrinsically difficult is that it is the problem of inferring an original beatstructure that is not expressed explicitly. The degree of beattracking difficulty is therefore not determined simply by the
number of musical instruments performing a musical piece;
it depends on how explicitly the beat structure is expressedin the piece. For example, it is very easy to track beats in apiece that has only a regular pulse sequence with a constantinterval. The main reason that different musical genres andinstruments have different tendencies with regard to beattracking difficulty is that they have different customary tendencies with regard to the explicitness with which their beatstructure is indicated.
In audio-based beat tracking, furthermore, it is also difficult to detect the musical elements that are beat-tracking
cues. In that case, the more musical instruments played
simultaneously and the more complex the audio signal, themore difficult is the detection of those cues.

2 Beat-tracking problem (inverse problem)
In my formulation the beat-tracking problem is defined as aprocess that organizes musical audio signals into the hierarchical beat structure. As shown in Figure 2, this problem can

3 Beat-tracking model (inverse model)
To solve this inverse problem, I developed a beat-tracking
model that consists of two component models: the model ofAudio-based real-time beat tracking
inferredhierarchical beat structure
inverse model ofindicating
the beat structuregthe beat structuremusical elements

musical elements
processes of musicalsound production andacoustic transmission

model of extracting
musical elements

Beat-Tracking Modelin performers’ brains
hierarchical beat structure161

audio signals

Fig. 3.

Beat-tracking model.

extracting musical elements from audio signals, and the inverse
model of indicating the beat structure (Fig. 3). The three issues
raised in the Introduction are addressed in this beat-tracking
model as described in the following three sections.

Fig. 4. Examples of a frequency spectrum and an onset-time
vector sequence.

3.1 Model of extracting musical elements: detecting
beat-tracking cues in audio signals
In the model of extracting musical elements, the following
three kinds of musical elements are detected as the beattracking cues:p(t+1,f)p(t,f)

power

PrevPow

1. Onset times
2. Chord changes
3. Drum patterns
As described in Section 3.2, these elements are useful when
the hierarchical beat structure is inferred. In this model, onset
times are represented by an onset-time vector whose dimensions correspond to the onset times of different frequency
ranges. A chord change is represented by a chord-change possibility that indicates how much the dominant frequency components included in chord tones and their harmonic overtones
change in a frequency spectrum. A drum pattern is represented
by the temporal pattern of a bass drum and a snare drum.
These elements are extracted from the frequency spectrum calculated with the FFT (1024 samples) of the input(16 bit/22.05 kHz) using the Hanning window. Since thewindow is shifted by 256 samples, the frequency resolution
is consequently 21.53 Hz and the discrete time step (1 frametime3) is 11.61 ms. Hereafter p(t, f ) is the power of the spectrum of frequency f at time t.
3.1.1 Onset-time vector
The onset-time vectors are obtained by an onset-time vectorizer that transforms the onset times of seven frequencytimep(t+1,f)frequencyp(t,f)
PrevPow

f+1

t+1
t
t-1

f
f-1

Fig. 5.

Extracting an onset component.

ranges (0–125 Hz, 125–250 Hz, 250–500 Hz, 0.5–1 kHz, 1–
2 kHz, 2–4 kHz, and 4–11 kHz) into seven-dimensional
onset-time vectors (Fig. 4). This representation makes it possible to consider onset times of all the frequency ranges atthe same time. The onset times can be detected by a frequency analysis process that takes into account such factors
as the rapidity of an increase in power and the power present
in nearby time-frequency regions as shown in Figure 5 (Goto& Muraoka, 1999). Each onset time is given by the peak timefound by peak-picking4 in a degree-of-onset function D(t) =Sf d(t, f ) whereÏ max( p(t , f ), p(t + 1, f )) - PrevPowÔd (t , f ) = Ì(min( p(t, f ), p(t + 1, f )) > PrevPow), (1)ÔÓ 0 (otherwise),
PrevPow = max( p(t - 1, f ), p(t - 1, f ± 1)).

(2)

3

The frame-time is the unit of time used in this system, and theterm time in this paper is the time measured in units of the frametime.

4
D(t) is linearly smoothed with a convolution kernel before its peaktime is calculated.

162

Masataka Goto(a) Frequency spectrum(b) Histograms of frequency components in spectrum strips sliced at provisional beat times(c) Quarter-note chord-change possibilities
Fig. 6.

Example of obtaining a chord-change possibility on the basis of provisional beat times.

Because PrevPow considers p(t - 1, f ± 1), a false non-onset
power increase from p(t - 1, f ) to p(t, f ) is not picked up
even if there is a rising frequency component holding highpower on both p(t - 1, f - 1) and p(t, f ). The onset times inthe different frequency ranges are found by limiting the frequency range of Sf.
3.1.2 Chord-change possibility
Because it is difficult to detect chord changes when using
only a bottom-up frequency analysis, I developed a methodfor detecting them by making use of top-down information,
provisional beat times (Goto & Muraoka, 1996, 1999). The
provisional beat times are a hypothesis of the quarter-notelevel and are inferred from the onset times as described in
Section 3.2.1. Possibilities of chord changes in a frequency
spectrum are examined without identifying musical notes orchords by name. The idea for this method came from theobservation that a listener who cannot identify chord names
can nevertheless perceive chord changes. When all frequency
components included in chord tones and their harmonic overtones are considered, they are found to tend to change significantly when a chord is changed and to be relatively stable
when a chord is not changed. Although it is generally difficult to extract all frequency components from audio signals
correctly, the frequency components dominant during acertain period of time can be roughly identified by using ahistogram of frequency components. The frequency spectrum is therefore sliced into strips at the provisional beattimes and the dominant frequencies of each strip are estimated by using a histogram of frequency components in the
strip (Fig. 6). Chord-change possibilities are then obtainedby comparing dominant frequencies between adjacent strips.

Because the method takes advantage of not requiring musicalnotes to be identified, it can detect chord changes in realworld audio signals, where chord identification is generally
difficult.
For different purposes, the model uses two kinds of possibilities of chord changes, one at the quarter-note level andthe other at the eighth-note level, by slicing the frequency
spectrum into strips at the provisional beat times and byslicing it at the interpolatd eighth-note times. The one
obtained by slicing at the provisional beat times is called thequarter-note chord-change possibility and the one obtainedby slicing at the eighth-note times is called the eighth-note
chord-change possibility. They respectively represent how
likely a chord is, under the current beat-position hypothesis,to change on each quarter-note position and on each eighthnote position. The detailed equations used in this method aredescribed in a paper focusing on beat tracking for music
without drum-sounds (Goto & Muraoka, 1999).

3.1.3 Drum pattern
A drum-sound finder detects the onset time of a bass drum(BD) by using onset components and the onset time of asnare drum (SD) by using noise components. Those onset
times are then formed into the drum patterns by making useof the provisional beat times (top-down information) (Fig. 7).
[Detecting BD onset times]
Because the sound of a BD is not known in advance, thedrum-sound finder learns the characteristic frequency of a
BD by examining the extracted onset components d(t, f )Audio-based real-time beat tracking
time
Provisional
beat times
Detecteddrums

BD

SD | .
BD |O

|O
|.

|
|

o |O
|
O.| o |

represents an interpolated sixteenth note

Oo. represents the reliability of detected onsets of drums
Forming a drum pattern by making use of provisional beat(Equation (1)). For times at which onset components arefound, the finder picks peaks along the frequency axis andmakes a histogram of them (Fig. 8). The finder then judgesthat a BD has sounded at times when an onset’s peak frequency coincides with the characteristic frequency that isgiven by the lowest-frequency peak of the histogram.
[Detecting SD onset times]
Since the sound of a SD typically has noise components
widely distributed along the frequency axis, the finder needs
to detect such components. First, the noise componentsn(t, f ) are given by the following equations:Ï ( ) Ê()Ôp t, fËmin HightFreqAve , LowFreqAveÔ(3)n(t , f ) = Ì1ˆ> p(t, f ) ,
Ô
¯
2
Ô
Ó0
(otherwise),11p(t , f + 2) + Âi =-1 p(t + i, f + 1) ,4

Detecting a bass drum (BD) and a snare drum (SD).

11p(t , f - 2) + Âi =-1 p(t + i, f - 1) , (5)4()

3.2.1 Musical knowledge of onset times
To infer the quarter-note level (i.e., to determine the provisional beat times), the model uses the following heuristicknowledge:

7.5 kHz

Peak histogram(4)

Each level of the beat structure is inferred by using theinverse model of indicating the beat structure. The inverse
model is represented by the following three kinds of musicalknowledge (heuristics) corresponding to the three kinds ofmusical elements.

1 kHz

population)

3.2 Inverse model of indicating the beat structure:interpreting beat-tracking cues to infer thehierarchical beat structure

frequency

Bass drum(BD)(

where HighFreqAve and LowFreqAve respectively represent
the local averages of the power in higher and lower regionsof p(t, f ). When the surrounding High Freq Ave and Low Freq
Ave are both larger than half of p(t, f ), the component p(t, f )is not considered a peaked component but a noise component distributed almost uniformly. As shown in Figure 8, thenoise components n(t, f ) are quantized: the frequency axisof the noise components is divided into subbands (thenumber of subbands is 16) and the mean of n(t, f ) in eachsubband is calculated. The finder then calculates c(t), which
represents how widely noise components are distributed
along the frequency axis: c(t) is calculated as the product ofall quantized components within the middle frequency range(from 1.4 kHz to 7.5 kHz). Finally, the SD onset time isobtained by peak-picking of c(t) in the same way as in theonset-time finder.

frequency

20 Hz

Fig. 8.

HighFreqAve =LowFreqAve =SD

Currently detected drum patternFig. 7.
times.

163

Snare drum(SD)

1.4 kHztime
Quantized noise components

164

Masataka Gotointer-beat interval(by autocorrelation)

prediction field(by cross-correlation)

Provisional beat times

time
Fig. 9.

extrapolate

evaluatecoincidence

Predicting the next beat.

(a-1) “A frequent inter-onset interval is likely to be the interbeat interval.”(a-2) “Onset times tend to coincide with beat times (i.e.,sounds are likely to occur on beats).”
The reason the term the provisional beat times is used is thatthe sequence of beat times obtained below is just a single
hypothesis of the quarter-note level: multiple hypotheses are
considered as explained in Section 3.3.
By using autocorrelation and cross-correlation of the onsettime vectors, the model determines the inter-beat interval andpredicts the next beat time. The inter-beat interval is determined by calculating the windowed and normalized vectorial
autocorrelation function Ac(t) of the onset-time vectors:5crrwin(c - t , AcPeriod )(o(t ) ◊ o(t - t ))Â,Ac(t ) = t =cc-AcPeriodrr
Ât =c -AcPeriod win(c - t , AcPeriod )(o(t ) ◊ o(t ))(6)where oÆ(t) is the onset-time vector at time t, c is the current
time, and AcPeriod is the autocorrelation period. The windowfunction win(t, s) whose window size is s istÏÔ
1.0 - 0.5
win(t , s) = ÌsÔÓ00 £ t £ s,(7)otherwise.

According to the knowledge (a-1), the inter-beat interval isgiven by the t with the maximum height in Ac(t) within an
appropriate inter-beat interval range. To predict the next beattime by using the knowledge (a-2), the model forms a
prediction field (Fig. 9) by calculating the windowed
cross-correlation function Cc(t) between the sum O(t) of all
dimensions of oÆ(t) and a tentative beat-time sequence
Ttmp(t, m) whose interval is the inter-beat interval obtainedusing Equation (6):Ê win(c - t , CcPeriod )O(t ) ˆ
Cc(t ) =Â Á CcNumBeats d (t - T (c + t , m))˜˜ ,t =c -CcPeriod Á
tmp
Ë mÂ
¯
=1

(8)

(m = 1),Ït - I (t )Ttmp (t , m) = ÌÓTtmp (t , m - 1) - I (Ttmp (t , m - 1)) (m > 1),(9)cÏ1 (x = 0),d (x ) = ÌÓ0 (x π 0),(10)where I(t) is the inter-beat interval at time t, CcPeriod(= CcNumBeats I(c)) is the window size for calculating thecross-correlation, and CcNumBeats (= 12) is a constant factor
that determines how many previous beats are considered in
calculating the cross-correlation. The prediction field is thus
given by Cc(t) where 0 £ t £ I(c) - 1. Finally, the localmaximum peak in the prediction field is selected as the nextbeat time while considering to pursue the peak close to thesum of the previously selected one and the inter-beat interval.
The reliability of each hypothesis of the provisional beattimes is then evaluated according to how closely the next beattime predicted from the onset times coincides with the time
extrapolated from the past beat times (Fig. 9).
3.2.2 Musical knowledge of chord changes
To infer each level of the structure, the model uses the following knowledge:(b-1) “Chords are more likely to change on beat times thanon other positions.”(b-2) “Chords are more likely to change on half-note times
than on other positions of beat times.”(b-3) “Chords are more likely to change at the beginningsof measures than at other positions of half-note times.”
Figure 10 shows a sketch of how the half-note and measuretimes are inferred from the chord-change possibilities.
According to the knowledge (b-2), if the quarter-note chordchange possibility is high enough, its time is considered toindicate the position of the half-note times. According to theknowledge (b-3), if the quarter-note chord-change possibility of a half-note time is higher than that of adjacent halfnote times, its time is considered to indicate the position of
the measure times (bar-lines).
The knowledge (b-1) is used for reevaluating the reliability of the current hypothesis: if the eighth-note chord-change
possibility tends to be higher on beat times than on eighthnote displacement positions, the reliability is increased.
3.2.3 Musical knowledge of drum patterns

5
Vercoe (1994) also proposed the use of a variant of autocorrelation for rhythmic analysis.

For music with drum-sounds, eight prestored drum patterns,
like those illustrated in Figure 11, are prepared. They repre-

Audio-based real-time beat tracking
predict

provisional
beat times
timechord change
possibilities
half-notetimes
measuretimes
best-matched
drum patterns

SD
BD

SD
BD

BD

half-notetimes
Fig. 10.

Pattern 1

2

(3)
1

(4)
2

Pattern 2

1

2

3

O : 1.0
o : 0.5. : 0.0
x : -0.5
X : -1.0

4
beat: 4
SD |X...|O...|X...|O...|BD |o...|x.Xx|X.O.|x...|SD
BD

Fig. 11.

Matching weight
beat: 2
SD |X...|O...|BD |o...|X...|SD
BD

Figure 10 also shows a sketch of how the half-note times areinferred from the best-matched drum pattern: according to
the knowledge (c-1), the beginning of the best-matchedpattern is considered to indicate the position of a half-note
time. Note that the measure level cannot be determined
this way: the measure level is determined by using thequarter-note chord-change possibilities as described in
Section 3.2.2.
The knowledge (c-2) is used for reevaluating the reliability of the current hypothesis: the reliability is increased
according to how well an input drum pattern matches one ofthe prestored drum patterns.
3.2.4 Musical knowledge selection based on thepresence of drum-sounds

Knowledge-based inferring.

1

165

Examples of prestored drum patterns.

sent the ways drum-sounds are typically used in a lot of
popular music. The beginning of a pattern should be a halfnote time, and the length of the pattern is restricted to a halfnote or a measure. In the case of a half note, patterns repeated
twice are considered to form a measure.
When an input drum pattern that is currently detected in
the audio signal matches one of the prestored drum patterns
well, the model uses the following knowledge to infer thequarter-note and half-note levels:(c-1) “The beginning of the input drum pattern indicates ahalf-note time.”(c-2) “The input drum pattern has the appropriate inter-beatinterval.”

To infer the quarter-note and half-note levels, the musicalknowledge of chord changes ((b-1) and (b-2)) and themusical knowledge of drum patterns ((c-1) and (c-2)) should
be selectively applied according to the presence or absenceof drum-sounds as shown in Table 1. I therefore developed amethod for judging whether or not the input audio signal contains drum-sounds. This judgement could not be made simply
by using the detected results because the detection of thedrum-sounds is noisy. According to the fact that in popular
music a snare drum is typically played on the secondand fourth quarter notes in a measure, the method judgesthat the input audio signal contains drum-sounds only when
autocorrelation of the snare drum’s onset times is highenough.
3.3 Dealing with ambiguity of interpretation
To enable ambiguous situations to be handled when the beattracking cues are interpreted, a multiple-agent model inwhich multiple agents examine various hypotheses of thebeat structure in parallel as illustrated in Figure 12 was developed (Goto & Muraoka, 1996, 1999). Each agent uses its
own strategy and makes a hypothesis by using the inverse
model described in Section 3.2. An agent interacts withanother agent to track beats cooperatively and adapts tothe current situation by adjusting its strategy. It then evaluates the reliability of its own hypothesis according toTable 1. Musical knowledge selection for music with drum-sounds and music without drum-sounds.
Beat structure

Without drums

With drums

Measure level

quarter-note chord-change possibility(knowledge (b-3))
quarter-note chord-change possibility(knowledge (b-2))
eighth-note chord-change possibility(knowledge (b-1))

quarter-note chord-change possibility(knowledge (b-3))
drum pattern (knowledge (c-1))

Half-note level
Quarter-note level

drum pattern (knowledge (c-2))

166

Masataka Goto
Agent 1
Agent 2Compact disc

Agent 3

Drumsoundfinderyenc rumequ pectr
F sf

Agent 4Higher-level
checkers
Managert

Agent 5predicted
next-beat time

Fig. 12.

time

Multiple hypotheses maintained by multiple agents.

how well the inverse model can be applied. The final beattracking result is determined on the basis of the most reliablehypothesis.
3.4 System overview
Figure 13 shows an overview of the system based on the beattracking model. In the frequency-analysis stage, the system
detects the onset-time vectors (Section 3.1.1), detects onset
times of bass drum and snare drum sounds (Section 3.1.3),
and judges the presence or absence of drum-sounds (Section
3.2.4). In the beat-prediction stage, each agent infers thequarter-note level by using the autocorrelation and crosscorrelation of the onset-time vectors (Section 3.2.1). Eachhigher-level checker corresponding to each agent thendetects chord changes (Section 3.1.2) and drum patterns(Section 3.1.3) by using the quarter-note level as the topdown information. Using those detected results, each agent
infers the higher levels (Section 3.2.2 and Section 3.2.3)
and evaluates the reliability of its hypothesis. The agent
manager gathers all hypotheses and then determines the final
output on the basis of the most reliable one. Finally, the beattracking result is transmitted to other application programs
via a computer network.

4 Experiments and results
The system was tested on monaural audio signals sampledfrom commercial compact discs of popular music. Eighty-

Fig. 14.

Beat-structure editor program.

Musicalaudio signals

A/D conversion

Fig. 13.

Onsettimefinders

Beat information
Onsettime
vectorizers

Frequency
analysis

AgentsBeat prediction

Beat informationtransmission

Overview of the beat-tracking system.

five songs, each at least one minute long, were used as the
inputs. Forty-five of the songs had drum-sounds (32 artists,
tempo range: 67–185 M.M.) and forty did not (28 artists,
tempo range: 62–116 M.M.). Each song had the 4/4 timesignature and a roughly constant tempo.
In this experiment the system output was compared withthe hand-labeled hierarchical beat structure. To label thecorrect beat structure, I developed a beat-structure editor
program that enables a user to mark the beat positions in adigitized audio signal while listening to the audio and watching its waveform (Fig. 14). The positions can be finely
adjusted by playing back the audio with click tones at beattimes, and the half-note and measure levels can also belabeled. The recognition rates were evaluated by using thequantitative evaluation measures for analyzing the beattracking accuracy that were proposed in earlier papers (Goto& Muraoka, 1997, 1999). Unstably tracked songs (those forwhich correct beats were obtained just temporarily) were notconsidered to be tracked correctly.
4.1 Results of evaluating recognition rates
The results of evaluating the recognition rates are listed inTable 2. I also evaluated how quickly the system started to
track the correct beats stably at each level of the hierarchicalbeat structure, and the start time of tracking the correct beatAudio-based real-time beat tracking

167

Table 2. Results of evaluating recognition rates at each level ofthe beat structure.

Table 3. Start time of tracking the correct beat structure (music
without drums).

Beat structure

Without drums

With drums

Beat structure

mean

min

max

Measure level

32 of 34 songs(94.1%)
34 of 35 songs(97.1%)
35 of 40 songs(87.5%)

34 of 39 songs(87.2%)
39 of 39 songs(100%)
39 of 45 songs(86.7%)

Measure level
Half-note level
Quarter-note level

18.47 s13.74 s10.99 s3.42 s3.42 s
0.79 s

42.56 s36.75 s36.75 sHalf-note level
Quarter-note level

Table 4. Start time of tracking the correct beat structure (musicwith drums).

structure is shown in Figure 15. The horizontal axis represents the song numbers (#) arranged in order of the start timeof the quarter-note level up to song #32 (for music without
drums) and #34 (for music with drums). The mean,
minimum, and maximum of the start time of all the correctly
tracked songs are listed in Table 3 and Table 4. These results
show that in each song where the beat structure was eventually determined correctly, the system initially had trouble
determining a higher rhythmic level even though a lower
level was correct.
The following are the results of analyzing the reasons thesystem made mistakes:

Beat structure

mean

min

max

Measure level
Half-note level
Quarter-note level22.00 s17.15 s13.87 s6.32 s4.20 s0.52 s40.05 s41.89 s41.89 sporarily (during from 14 to 24 s), it sometimes got out of
position because the onset times were very few and irregular. In the other song the tracked beat times deviated too
much during a measure, although the quarter-note level was
determined correctly during most of the song.
In a song where the half-note level was wrong, the systemfailed to apply the musical knowledge of chord changes
because chords were often changed at the fourth quarter notein a measure.
In two songs where only the measure level was mistaken,
chords were often changed at every other quarter-note andthe system was not able to determine the beginnings ofmeasures.

[Music without drums]
The quarter-note level was not determined correctly in fivesongs. In one of them the system tracked eighth-note displacement positions because there were too many syncopations in the basic accompaniment rhythm. In three of theother songs, although the system tracked correct beats tem-

45

Measure level(Song #1-34)
Half-note level(Song #1-39)
Quarter-note level (Song #1-39)

Start time [sec]Start time [sec]Measure level(Song #1-32)
Half-note level(Song #1-34)
Quarter-note level (Song #1-35)

40
35
30

45
40
35
30

25

25

20

20

15

15

10

10

5

5

0

0
1

5

10

15

20

25

30

35

40

1

5

10

15

20

25

Song number(music without drums)
Fig. 15. Start time of tracking the correct beat structure.

30

35

40

Song number(music with drums)

168

Masataka Goto

The quarter-note level was not determined correctly in six
songs. In two of them the system correctly tracked beats inthe first half of the song, but the inter-beat interval became
0.75 or 1.5 times of the correct one in the middle of the song.
In two of the other songs the quarter-note level was determined correctly except that the start times were too late:
45.3 s and 51.8 s (the start time had to be less than 45 s forthe tracking to be considered correct). In the other two songs
the tracked beat times deviated too much temporarily,
although the system tracked beat times correctly during mostof the song.
The system made mistakes at the measure level in fivesongs. In one of them the system was not able to determine
the beginnings of measures because chords were oftenchanged at every quarter-note or every other quarter-note. In
two of the other songs the quarter-note chord-change possibilities were not obtained appropriately because the frequency components corresponding to the chords were too
weak. In the other two songs the system determined themeasure level correctly except that the start times were toolate: 48.3 s and 49.9 s.
The results mentioned above show that the recognition rates
at each level of the beat structure were more than 86.7
percent and that the system is robust enough to deal in realtime with real-world audio signals containing sounds ofvarious instruments.
4.2 Results of measuring rhythmic difficulty
It is important to measure the degree of beat-tracking difficulty for the songs that were used in testing the beattracking system. As discussed in Section 2, the degree ofbeat-tracking difficulty depends on how explicitly the beatstructure is expressed. It is very difficult, however, tomeasure its explicitness because it is influenced from various
aspects of the songs. In fact, most previous beat-tracking
studies have not dealt with this issue. I therefore tried, as afirst step, to evaluate the power transition of the input audio
signals. In terms of the power transition, it is more difficult
to track beats of a song in which the power tends to be lower
on beats than between adjacent beats. In other words, thelarger the number of syncopations, the greater the difficultyof tracking beats.
I thus proposed a quantitative measure of the rhythmic difficulty, called the power-difference measure,6 that considers
differences between the power on beats and the power onother positions. This measure is defined as the mean of all
the normalized power difference diffpow(n) in the song:
diffpow (n) = 0.5

powother (n) - powbeat (n)+ 0.5, (11)max( powother (n), powbeat (n))

6
The detailed equations of the power-difference measure aredescribed by Goto and Muraoka (1999).

power[Music with drums]

powbeat (n)powbeat (n-1)
powother (n-1)
powother (n)(n-1)-th beatFig. 16.

n-th beattime

Finding the local maximum of the power.

where powbeat(n) represents the local maximum power on
the n-th beat7 and powother(n) represents the local maximum
power on positions between the n-th beat and (n + 1)-thbeat (Fig. 16). The power-difference measure takes a value
between 0 (easiest) and 1 (most difficult). For a regular pulse
sequence with a constant interval, for example, this measuretakes a value of 0.
Using this power-difference measure, I evaluated therhythmic difficulty of each of the songs used in testing
the system. Figure 17 shows two histograms of the measure,
one for songs without drum-sounds and the other forsongs with drum-sounds. Comparison between these two histograms indicates that the power-difference measure tends tobe higher for songs without drum-sounds than with drumsounds. In particular, it is interesting that the measureexceeded 0.5 in more than half of the songs without drumsounds; this indicates that the power on beats is often lower
than the power on other positions in those songs. This alsosuggests that a simple idea of tracking beats by regarding
large power peaks of the input audio signal as beat positions
is not feasible.
Figure 17 also indicates the songs that were incorrectly
tracked at each level of the beat structure. While the powerdifference measure tends to be higher for the songs that wereincorrectly tracked at the quarter-note level, it’s value is notclearly related to the songs that were incorrectly tracked at
the half-note and measure levels: the influence from various
other aspects besides the power transition is dominant in
inferring the half-note and measure levels. Although thismeasure is not perfect for evaluating the rhythmic difficulty
and other aspects should be taken into consideration, it
should be a meaningful step on the road to measuring thebeat-tracking difficulty in an objective way.

5 Applications
Since beat tracking can be used to automate the timeconsuming tasks that must be completed in order tosynchronize events with music, it is useful in various applications, such as video editing, audio edition, and humancomputer improvisation. The development of applications

7

The hand-labeled correct quarter-note level is used for thisevaluation.

Audio-based real-time beat tracking
Song that was incorrectly tracked
at the measure level
Song that was incorrectly tracked
at the half-note level
Song that was incorrectly tracked
at the quarter-note level
Song that was tracked correctly

10

The number of songs

169

8
6
4
2
0
0.25

0.3

(easy)

0.35

0.4

0.45

0.5

Power-difference measure

0.55(difficult)(a) Histogram for 40 songs without drum-sounds.
Song that was incorrectly tracked
at the measure level
Song that was incorrectly tracked
at the quarter-note level
Song that was tracked correctly

The number of songs

10
8
6
4
2
0
0.25

(easy)

0.3

0.35

0.4

0.45

0.5

Power-difference measure

0.55(difficult)(b) Histogram for 45 songs with drum-sounds.
Fig. 17. Evaluating beat-tracking difficulty: histograms of the evaluated power-difference measure.

Fig. 18. Virtual dancer “Cindy”.

is facilitated by using a network protocol called RMCP
(Remote Music Control Protocol) (Goto, Neyama, &Muraoka, 1997) for sharing the beat-tracking result among
several distributed processes. RMCP is designed to sharesymbolized musical information through networks and it
supports time-scheduling using time stamps and broadcastbased information sharing without the overhead of multiple
transmission.
• Beat-driven real-time computer graphics
The beat-tracking system makes it easy to create realtime computer graphics synchronized with music and has

been used to develop a system that displays virtual dancers
and several graphic objects whose motions and positions
change in time to beats (Fig. 18). This system has several
dance sequences, each for a different mood of dance
motions. While a user selects a dance sequence manually,
the timing of each motion in the selected sequence is determined automatically on the basis of the beat-tracking
results. Such a computer graphics system is suitable forlive stage, TV program, and Karaoke uses.
• Stage-lighting control
Beat tracking facilitates the automatic synchronizationof computer-controlled stage lighting with the beats in a

170

Masataka Gotomusical performance. Various properties of lighting – suchas color, brightness, and direction – can be changed in time
to music. At the moment this application is simulated on acomputer graphics display with virtual dancers.
• Intelligent drum machine
A preliminary system that can play drum patterns in timeto input musical audio signals without drum-sounds has
been implemented. This application is potentially usefulfor automatic MIDI-audio synchronization and intelligent
computer accompaniment.
The beat-structure editor program mentioned in Section 4 isalso useful in practical applications. A user can correct oradjust the output beat structure when the system output
includes mistakes and can make the whole hierarchical beatstructure for a certain application from scratch.

6 Conclusion
This paper has described the beat-tracking problem indealing with real-world audio signals, a beat-tracking modelthat is a solution to that problem, and applications basedon a real-time beat-tracking system. Experimental results
show that the system can recognize the hierarchical beatstructure comprising the quarter-note, half-note, and measurelevels in audio signals of compact disc recordings. The
system has also been shown to be effective in practicalapplications.
The main contributions of this paper are to provide a viewin which the beat-tracking problem is regarded as an inverse
problem and to provide a new computations model that canrecognize, in real time, the hierarchical beat structure inaudio signals regardless of whether or not those signals
contain drum-sounds. The model uses sophisticatedfrequency-analysis processes based on top-down information
and uses a higher-level processing based on three kinds ofmusical knowledge that are selectively applied according
to the presence or absence of drum-sounds. These features
made it possible to overcome difficulties in making musicaldecisions about complex audio signals and to infer the hierarchical beat structure.
The system will be upgraded by enabling it to follow
tempo changes and by generalizing it to other musicalgenres. Future work will include integration of thebeat-tracking model described here and other musicunderstanding models, such as one detecting melody andbass lines (Goto, 1999, 2000).

Acknowledgments
This paper is based on my doctoral dissertation supervised
by Professor Yoichi Muraoka at Waseda University. I
thank Professor Yoichi Muraoka for his guidance and support and for providing an ideal research environment fullof freedom.

References
Allen, P.E. & Dannenberg, R.B. (1990). Tracking Musical Beatsin Real Time. In Proceedings of the 1990 International Computer Music Conference, pp. 140–143. Glasgow: ICMA.
Dannenberg, R.B. & Mont-Reynaud, B. (1987). Following
an Improvisation in Real Time. In Proceedings of the 1987
International Computer Music Conference (pp. 241–248).
Champaign/Urbana: ICMA.
Desain, P. & Honing, H. (1989). The Quantization of Musical
Time: A Connectionist Approach. Computer Music Journal,
13(3), 56–66.
Desain, P. & Honing, H. (1994). Advanced issues in beat induction modeling: syncopation, tempo and timing. In Proceedings of the 1994 International Computer Music Conference(pp. 92–94). Aarhus: ICMA.
Driesse, A. (1991). Real-Time Tempo Tracking Using Rules toAnalyze Rhythmic Qualities. In Proceedings of the 1991
International Computer Music Conference (pp. 578–581).
Montreal: ICMA.
Goto, M. (1999). A Real-time Music Scene Description System:
Detecting Melody and Bass Lines in Audio Signals. In
Working Notes of the IJCAI-99 Workshop on Computational
Auditory Scene Analysis (pp. 31–40). Stockholm: IJCAII.
Goto, M. (2000). A Robust Predominant-F0 Estimation Method
for Real-time Detection of Melody and Bass Lines in CD
Recording. In Proceedings of the 2000 IEEE International
Conference on Acoustics, Speech, and Signal Processing (pp.
II–757–760). Stanbul: IEEE.
Goto, M. & Muraoka, Y. (1994). A Beat Tracking System
for Acoustic Signals of Music. In Proceedings of theSecond ACM International Conference on Multimedia(pp. 365–372). San Francisco: ACM.
Goto, M. & Muraoka, Y. (1995). A Real-time Beat Tracking
System for Audio Signals. In Proceedings of the 1995 International Computer Music Conference (pp. 171–174). Banff:
ICMA.
Goto, M. & Muraoka, Y. (1996). Beat Tracking based on
Multiple-agent Architecture – A Real-time Beat Tracking
System for Audio Signals –. In Proceedings of the Second
International Conference on Multiagent Systems (pp.
103–110). Kyoto: AAAI Press.
Goto, M. & Muraoka, Y. (1997). Issues in Evaluating Beat
Tracking Systems. In Working Notes of the IJCAI-97 Workshop on Issues in AI and Music (pp. 9–16). Nagoya: IJCAII.
Goto, M. & Muraoka, Y. (1998). Music Understanding At The
Beat Level – Real-time Beat Tracking For Audio Signals. In
D.F. Rosenthal & H.G. Okuno (Eds.), Computational Auditory Scene Analysis (pp. 157–176). New Jersey: Lawrence
Erlbaum Associates, Publishers.
Goto, M. & Muraoka, Y. (1999). Real-time Beat Tracking forDrumlessAudioSignals:Chord Change Detection for Musical
Decisions. Speech Communication, 27(3–4), 311–335.
Goto, M., Neyama, R., & Muraoka, Y. (1997). RMCP: Remote
Music Control Protocol – Design and Applications –. In
Proceedings of the 1997 International Computer Music Conference (pp. 446–449). Thessaloniki: ICMA.

Audio-based real-time beat tracking
Katayose, H., Kato, H., Imai, M., & Inokuchi, S. (1989). “AnApproach to an Artificial Music Expert,” In Proceedingsof the 1989 International Computer Music Conference(pp. 139–146). Columbus: ICMA.
Kitano, H. (1993). “Challenges of Massive Parallelism,” In
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (pp. 813–834). Chambery:
IJCAII.
Large, E.W. (1995). Beat Tracking with a Nonlinear
Oscillator. In Working Notes of the IJCAI-95 Workshop
on Artificial Intelligence and Music (pp. 24–31). Montreal:
IJCAII.
Rosenthal, D. (1992a). “Emulation of Human Rhythm Perception,” Computer Music Journal, 16(1), 64–76.
Rosenthal, D. (1992b). Machine Rhythm: Computer Emulationof Human Rhythm Perception. Ph.D. thesis, Massachusetts
Institute of Technology.

171

Rowe, R. (1993). Interactive Music Systems. Massachusetts:
MIT Press.
Scheirer, E.D. (1998). “Tempo and beat analysis of
acoustic musical signals,” Journal of the Acoustical Society
America, 103(1), 588–601.
Schloss, W.A. (1985). On The Automatic Transcription of
Percussive Music – From Acoustic Signal to High-Level
Analysis. Ph.D. thesis, CCRMA, Stanford University.
Todd, N.P.M. (1994). “The Auditory ‘Primal Sketch”: A Multiscale Model of Rhythmic Grouping,” Journal of New Music
Research, 23(1), 25–70.
Todd, N.P.M. & Brown, G.J. (1996). “Visualization of Rhythm,
Time and Metre,” Artificial Intelligence Review, 10, 253–273.
Vercoe, B. (1994). “Perceptually-based music pattern recognition and response,” In Proceedings of the Third International
Conference for the Perception and Cognition of Music (pp.
59–60). Liège: ESCOM.