IJCAI-97 Workshop on Computational Auditory Scene Analysis

Real-time Rhythm Tracking for Drumless Audio Signals| Chord Change Detection for Musical Decisions |Masataka Goto and Yoichi Muraoka
School of Science and Engineering, Waseda University
3-4-1 Ohkubo Shinjuku-ku, Tokyo 169, JAPAN.
fgoto, muraokag@muraoka.info.waseda.ac.jp

Abstract

even for human beings to acquire.
On the other hand, an untrained listener understands

This paper presents a real-time rhythm track-

music to some extent without mentally representing au-

ing system that recognizes a rhythmic structure

dio signals as musical scores. For example, even a listenerin musical audio signals without drum-sounds.

who cannot identify chord names can sense harmony andMost previous systems dealt with MIDI sig-

chord changes. A listener who cannot completely segre-

nals and had diculty in processing, in realgate and identify every musical note can neverthelesstime, audio signals containing sounds of vari-

track musical beats and keep time to music by hand-

ous instruments and in tracking rhythm above
the quarter-note level.

clapping or foot-tapping. We therefore think that it is

Our system not only

important totracks beats at the quarter-note level but also
recognizes rhythmic structure at the half-note

without relying on transcription, and then extend theand measure levels. To make musical decisions

system so that it can understand music the way musi-

about the audio signals, we propose a method

cians do.

of detecting chord changes that does not rely

Our approach is to build a real-time rhythm-tracking

on chord name identi cation. The method en-system that recognizes a hierarchical musical structure

ables the system to understand music at di erent rhythmic levels | for example, torst build a computer system that can un-derstand music the way untrained human listeners do,of three rhythmic levels in real-world audio signals, suchnd theas those sampled from popular compact discs. Rhythm

beginnings of half notes and measures | andtracking is an important part of the computational mod-to select the best of various hypotheses abouteling of music understanding because rhythm is funda-

beat positions. Experimental results show thatmental, for both trained and untrained listeners, to the

our system is robust enough to handle audio

perception of Western music.

signals sampled from compact discs of popular

Our system can under-

stand music at the three rhythmic levels: the quarter-

music.

note level, the half-note level, and the measure (bar)

1 Introduction

1 It not only

level.

nds the pulse sequence correspond-

ing to the beats at the quarter-note level but also

Although a great deal of music-related research has been
undertaken, it is still dicult to build a computer systemthat can understand music. In terms of computational
auditory scene analysis, one of the goals is to implement
a computational model that can understand musical audio signals in a human-like fashion. A popular approachto this goal is to build an automatic music transcription
system or a sound source separation system, which typically transforms audio signals into a symbolic representation such as a musical score or MIDI data. Althoughsuch detailed-transcription technologies are important,they have diculty in dealing with compact disc audio
signals in general. Because only a trained listener canidentify musical notes and chord names, we can inferthat musical transcription is an advanced skill dicultnds

the beginnings of half notes and measures under the assumption that the time-signature is 4/4.
Most previous rhythm-tracking related systems [Dannenberg and Mont-Reynaud, 1987; Desain and Honing, 1989; 1994; 1995; Allen and Dannenberg, 1990;
Driesse, 1991; Rosenthal, 1992a; 1992b; Rowe, 1993;
Large, 1995; Smith, 1996] have dealt with MIDI signals or used onset times as their input.

Since it isquite dicult to obtain complete MIDI representations
from audio data, MIDI-based systems are limited in

Although our system does not rely on score representation, for convenience here we use score-representing terminology like [Rosenthal, 1992a; 1992b]. The quarter-note levelindicates the temporal basic unit that a human feels in music
and that usually corresponds to a quarter note in scores.

0135 01

their application. Although some systems [Schloss, 1985;
Katayose et al., 1989; Vercoe, 1994; Todd, 1994; Todd
and Lee, 1994; Scheirer, 1996] dealt with audio signals,

Musicalacoustic
signals

they either did not consider higher-level musical structure such as the half-note and measure levels or did notprocess, in real time, popular music sampled from com-time
Measure level(measure times)

pact discs. We developed a real-time beat-tracking system for audio signals [Goto and Muraoka, 1994; 1995a;

Beginning

MiddleBeginning

Half-note level(half-note times)

1995b], but it assumed that the input contained drum-

Strongsounds (a bass drum and a snare drum) and was not

Quarter-note level

generally able to track beats in audio signals without(beat times)

Weak

StrongWeak

StrongWeakdrum-sounds. Moreover, it did not recognize rhythmic
Figure 1: Rhythm tracking problem.

structure at the measure level.
In the following sections we describe how we extended
our previous system so that it can deal with drumlessaudio signals and recognize the higher-level rhythmic
structure.

To make musical decisions about the audio

signals, we propose a method of detecting chord changes.
Because our method does not rely on identifying chord
names, it can detect chord changes in audio signals sampled from compact discs, where chord identi cation is
generally dicult.

2 Rhythm Tracking Problem

Acoustic Rhythm-Tracking Issues

The diculties of tracking the rhythm in real-world musical acoustic signals can be summarized as (1) detecting rhythm-tracking cues in audio signals, (2) examining
multiple hypotheses about beat positions, and (3) making musical decisions.
In detecting tracking cues, it is necessary to detect
several cues for di erent purposes:

In this section we specify the rhythm tracking problem
that we are dealing with and present the main dicultiesof tracking rhythm.

nding beat times

and recognizing the higher-level rhythmic structure. Our
previous system [Goto and Muraoka, 1995b] addressedtherst purpose by detecting onset times using fre-quency analysis and then obtaining beat times using au-

2.1 Problem Speci cation

tocorrelation and cross-correlation of the onset times.

In our formulation, rhythm tracking is de ned as aprocess that organizes music into a hierarchical musi-the quarternote level, the half-note level, and the measure levelcal structure with three levels of rhythm:(Figure 1). The

2.2

rst step in solving our rhythm track-ing problem is thus obtaining an appropriate sequence ofbeat times in an input musical audio signal. Beat times

The tracking cues for the higher-level rhythmic structure of drumless audio signals, however, were not dealt
with.
The multiple-hypothesis issue was addressed in ourprevious system [Goto and Muraoka, 1994; 1995a; 1996]
by managing multiple agents that examined parallel hypotheses according to di erent strategies.

are temporal positions of almost regularly spaced beats

With regard to the musical-decision issue, our previ-

corresponding to quarter notes and the sequence of beatous system [Goto and Muraoka, 1995a; 1995b] made use

times is called the quarter-note level. We then addressof prestored drum patterns, which were matched withthe problem of

the currently detected drum pattern of the input. Al-

measures.

nding the beginnings of half notes and

The sequence of half-notetimes (temporal2
positions of strong beats ) is obtained by determining

though this method was e ective for audio signals with
drum-sounds, it cannot be applied to the drumless audio

whether a beat is strong or weak (half-note-level type).

signals we are considering here.

The sequence of measure times (temporal positions ofIn this paper we address the main issue in extend-

the beginnings of measures) is obtained by determining

ing the previous system to drumless audio signals andwhether a half note is the beginning or the middle of ahigher-level rhythm understanding.

The issue is thatmeasure (measure-level type). The sequence of half-note

higher-level processing using musical knowledge in ad-

times is called the half-note level and the sequence ofdition to lower-level signal processing is indispensable

measure times is called the measure level.

for recognizing the higher-level rhythmic structure andBoth half-note-level and measure-level types are called thetypes.

beattions in an ambiguous situation. Musical knowledge that

Under the assumption that the time-signature of an input
song is 4/4, in this paper a strong beat is either the rst or
third quarter note in a measure; a weak beat is the second or
fourth.
2

evaluating which is the best interpretation of beat posiis useful for analyzing musical scores or MIDI signals,
however, cannot immediately be applied to raw audio
signals because of the diculty of obtaining MIDI-like
representations of those signals.

0136 03 Chord Change Detection for Musical
Decisions

where

On the other hand, in preparation for evaluating

Cen , theSen at theeighth-note times T en interpolated from T qn :Sen = fp(t; f )g; Ten  t < T en+1
(2)
8< T q(n mod 2 = 0)
n=2
T en = : (T q(n01)=2 + T q(n+1)=2)=2(3)(n mod 2 = 1)

To address the above-mentioned higher-level processing

the eighth-note chord change possibility

issue, we propose a method for making musical decisions
based on chord changes.

spectrum is sliced into spectrum strips

In the following sections, we

rst describe a method of detecting chord changes for obtaining rhythm-tracking cues for the higher-level rhythmic structure (Section 3.1), and then explain a way ofmaking semantic decisions with heuristic musical knowledge based on the detected chord changes (Section 3.2).

3.1 Chord Change Detection

Tqn is the n-th beat time and p(t; f ) is thef at time t.4

power of the spectrum of frequency

2.

Forming histograms

By making use of provisional beat times obtained on

The system forms histograms

the basis of onset times (i.e., making use of top-down(after

this,

we

will

use

Hqn (f ) and Hen (f )abbreviations

such

as

Hin (f ) (i = q; e)) summed up along the time axis
in the corresponding strip Sqn and Sen :information from a beat-position hypothesis), this detection method examines possibilities of chord changes
in a frequency spectrum without identifying any musicalHin (f ) =notes or chord names. The idea for this method camefrom the observation that a listener who cannot identify
chord names can nevertheless sense chord changes.
where

When all frequency components which are included in

3 are consid-X

T in+1 0Gin

t=T in +Ginp(t; f )(4)

Gin (equal to (T in+1 0 Tin )=5 in our current

chord tones and their harmonic overtones

implementation) is a margin to avoid in uences of

ered, they are found to tend to change signi cantly whennoises and unstable frequency components arounda chord is changed and to be relatively stable when athe note onset.

chord is not changed. Although it is generally dicult to
extract all frequency components from audio signals cor-3.

Detecting dominant frequencies

Kin (f ) along the frequency axis in
Hin (f ) are given by
8< Hin(f ) if Hin (f ) 
Hin (f 6 1)
(5)
Kin (f ) = :First, peaks

rectly and completely, dominant frequency components
during a certain period of time can be estimated roughly
by using a histogram of frequency components.
This method therefore calculates two kinds of possi-

0bilities of chord changes, at the quarter-note level andat the eighth-note level, by slicing the frequency spec-

otherwise

Our current implementation considers only peaks

trum into strips at the provisional beat times (top-down

whose frequency is between 10 Hz and 1 kHz. These

information). We call the former the quarter-note chordpeaks can be considered the dominant tones' fre-change possibility and the latter the eighth-note chord
change possibility. The quarter-note and eighth-note

quencies in each strip and tend to correspond tofrequency components of a chord or a melody.

chord change possibilities respectively represent how a

These peaks are then transformed in order to avoid

chord is likely to change on each quarter-note position

detecting unnecessary noise peaks during a silent

and on each eighth-note position under the current beat-period such as a rest and to consider that the previ-

position hypothesis. As described in Section 3.2, theseous chord continues during its period. Considering

possibilities are used for di erent purposes.

min of Kin (f ),Qin (f ) asQin (f ) = clip(9Kin (f ) = Min )(6)
Min = 8max(min ; 8Min01 )(7)< 0 (x < 0)clip(x) =(8): x1 (0(1 < xx) 1)

temporal transition of the maximum

These possibilities are calculated as follows:

we can express the transformed peaks

1. Slicing the frequency spectrum into spectrum strips
The frequency spectrum (power spectrum) is calculated using the Fast Fourier Transform of the digitized audio signal (Section 4.1). In preparation forevaluating the quarter-note chord change possibility

Cqn , the frequency spectrum is sliced into spectrum
strips Sqn at the quarter-note times (beat times):
Sqn = fp(t; f )g; T qn  t < T qn+1
(1)
3
In the case of actual songs, frequency components of a
melody and other parts are also considered. These components tend to be in harmony with chord tones.

where 9 (= 5) and 8 (= 0.99) are constant values.

P in (f ) in each strip are4f and t are integers, and 1f and 1t are respectively equal
to the frequency resolution (10.77 Hz) and the discrete time
step (11.61 ms).

0137 0

Finally the desired peaks

calculated so that the previous peaks

Pin01(f ) canbe regarded as continuing during a relatively silent
period in which the sum of

Qin (f ) is low:

8 Qi (f ) if P Qi (f ) 
< n
fP n
2
Pin (f ) = :f Pin01 (f )Pin01 (f ) otherwise

where 2 (= 0.1) is a constant value.

(9)This makes

it possible to prevent the chord change possibilities
from increasing rapidly after every silent period.
4. Comparing frequencies between adjacent strips(a) Examining quarter-note chord change possibility

The chord change possibilities are calculated by

P in01 (f )P in (f ). When a chord is changed at the boundary time Tin between those strips, di erent peaks
tend to occur in Pin (f ) compared with P in01 (f ).

comparing peaks between adjacent strips:
andConsidering temporal transition of positive di er-

cin , we can express the quarter-note chord
Cqn and the eighth-note chord
change possibility Cen as
Cin = cin =din
(10)X
cin = clip(P in (f ) 0 Pin01 (f )) (11)enceschange possibility(b) Examining eighth-note chord change possibilityfdin = max(cin ; 8 din01 )(12)

Figure 2 shows examples of two kinds of chord change
possibilities.

Figure 2: Examples of peaks in sliced frequency spectrum and of chord change possibilities.

The thin vertical lines represent the

T qn in (a) and the eighth-note times
Ten in (b). The beginning of measure occurs at every

Chords are more likely to change on beats (quarter

quarter-note times

notes) than on other positions between two succes-

four quarter-note times from the extreme left in (a), andsive correct beats. In other words, the eighth-note

the beat occurs at every two eighth-note times from thechord change possibility tends to be higher on beats

extreme left in (b). In each of (a) and (b), the horizontal

than on eighth-note displacement positions.

lines above represent the peaks

Pin (f ) in each strip andthe thick vertical lines below represent the chord change
possibility

Cin .

rst calculates

Uhn which represents a past tendency of every four

By utilizing the two kinds of chord change possibilities,
the system recognizes the higher-level rhythmic structure (i.e., determines the half-note times and the measure times) and selects the best hypothesis from variousForthese purposes, we introduce the following two kinds ofheuristic musical knowledge.
(1) Quarter-note-level knowledge
Chords are more likely to change at the beginningsof measures than at other positions. In other words,
the quarter-note chord change possibility tends toquarter-note chord change possibility:

Uqn = 1 Uqn02 + 2 Cqn(13)
Uhn = 1 Uhn04 + 2 Cqn(14)
where 1 (= 0.99) and 2 (= 0.2) are constant values.
If Uqn 0 Uqn01 > q , it then judges that the position of a half-note time is T qn , where q (= 0.3) isa constant threshold. If Tqn is a half-note time andUhn 0 Uhn02 > h, it judges that the position of a measure time is T qn , where h (= 0.2) is a constant threshold. The reliabilities of these judgements are de ned as

Lqn = clip(Uqn 0 Uqn01)
Lhn = clip(Uhn 0 Uhn02 )be higher on a strong beat than on a weak beat andhigher on the strong beat at the beginning of a measure than on the other strong beat in the measure.
(2) Eighth-note-level knowledge

Uqn which represents a past tendency of

every other quarter-note chord change possibility and3.2 Musical Decisions

agent-generated hypotheses about beat positions.

To recognize the higher-level rhythmic structure, thesystem utilizes the quarter-note-level knowledge (1). It

(15)
(16)

Based on the previous position of a half-note time anda measure time, the following beat types (half-note-

0138 0level type and measure-level type) are determined un-

61 M.M. (Malzel's Metronome: the number of quarter

der the assumptions that strong and weak alternate on

notes per minute) and 120 M.M., and is roughly con-beat times and that beginning and middle alternate on
half-note times.
To select the best hypothesis, the system utilizes
the eighth-note-level knowledge (2).
Section 4.2, thestant. The system maintains, as the real-time output, adescription called beat information (BI) that consists ofthe beat time, its beat types, and the current tempo.

As described innal output is determined on the ba-

Figure 3 shows an overview of our rhythm tracking
system.

The system

rst digitizes an input audio sig-

A/D Conversion stage.

sis of the appropriate hypothesis that has the highest

nal in thereliability.

Analysis stage, multiple onset-time

To evaluate the reliability of a hypothesis,

Len , which is the reliability of the
T qn (= T e2n ) is the position of a beat:
Len = 1 Len01 + 2 (Ce2n 0 Ce2n+1 )(17)

In theFrequencynders detect onset

the system calculates

times in di erent ranges of the frequency spectrum, andjudgement thatthose results are transformed into vectorial representa-

If

Len becomes higher (i.e., the eighth-note chord changetion (called onset-time vectors) by onset-time vectoriz-ers.

In the Beat Prediction stage, the system manages

multiple agents that, according to di erent strategies,

possibility keeps on being higher on beats than on othermake parallel hypotheses based on those onset-time vec-

positions), the reliability is increased so that the system

tors. Each agent

can select the hypothesis under which the appropriate(the temporal di erence between two successive beats)

Cen is obtained. The reliability is also evaluated by
di erent viewpoints as described in Section 4.2.

rst calculates the inter-beat interval

and predicts the next beat time. By communicating witha chord change checker, it then determines its beat types

4 System Description

and evaluates the reliability of its own hypothesis. A hy-

5sounds assumes that the time-signature of an input songone. Finally, in the BI Transmission stage, the system

potheses manager gathers all hypotheses and then deter-

The system for musical audio signals without drumis 4/4 and that its tempo is constrained to be between

A detailed description of our beat-tracking system foraudio signals that include drum-sounds is presented in [Gotoand Muraoka, 1995a; 1995b].
5

mines thenal output on the basis of the most reliabletransmits BI to other application programs via a computer network.

4.1

Frequency Analysis

In the Frequency Analysis stage, the frequency spectrum
and several sequences of N-dimensional onset-time vec-

Musical Audio Signals

Time-signature: 4 / 4
Tempo: 61-120 M.M.

frequency band is split into several frequency ranges, andeach dimension of the onset-time vectors corresponds to

A/D Conversion

Fast Fourier Transform

tors are obtained for later processing (Figure 4). The full

Frequency
Analysis

Extracting onset components
Onset-time vectorizers
Onset-time finders
onset-time
vectors

AgentsChord change
checkers

hypotheses

Manager

Beat
Prediction

most reliable hypothesis
Beat Information
Transmission
Beat Information

Beat time, Beat types,
Current tempo

Figure 4:
Figure 3: Overview of our rhythm tracking system.

Example of a frequency spectrum and an

onset-time vector sequence.

0139 0a di erent frequency range. This representation makes

Onset-time
vectorizers Parameterit possible to consider onset times of all the frequency

Frequency focus type

ranges at the same time.

Fast Fourier Transform (FFT)Agents

The frequency spectrum is calculated with the FFT using the Hanning window. Each time the FFT is applied
to the input signal, the window is shifted to the next

Chord change
checkers

Parameters
Frequency focus type
Autocorrelation period
Inter-beat interval range
Initial peak selection

frame.
In our current implementation, the input signal is digitized at 16 bit / 22.05 kHz, and two kinds of FFT are
calculated. One FFT, for extracting onset components

Hypothesisin the Frequency Analysis stage, is calculated with a window size of 1024 samples, and the window is shifted by
256 samples. The frequency resolution is consequently

6

21.53 Hz and the discrete time step (1 frame-time ) is
11.61 ms. The other FFT, for examining chord changes
in the Beat Prediction stage, is simultaneously calcu-

Hypothesis

Next beat time
Beat types
Inter-beat interval
Figure 5:

Next beat time
Beat types
Inter-beat interval

Relations between onset-time vectorizers,

agents, and chord change checkers.

lated in audio down-sampled at 16 bit / 11.025 kHz witha window size of 1024 samples, and the window is shifted

Agent 1-1

by 128 samples. The frequency resolution and the time
step are consequently 10.77 Hz and 1 frame-time.

pair

Extracting Onset Components
The frequency component p(t; f ) that ful lls Condi-tion (18) is extracted as an onset component.

time

p t; f ); p(t + 1; f )) > pp(18)
pp = max(p(t 0 1; f ); p(t 0 1; f 6 1))(19)
Its degree of onset d(t; f ) (rapidity of increase in power)
min( (

8 max(p(t; f ); p(t + 1; f )) 0 pp<
if Condition (18) is ful lledd(t; f ) = :0
otherwise

is given by(20)

quency ranges (0-125 Hz, 125-250 Hz, 250-500 Hz, 500
Hz-1 kHz, 1-2 kHz, 2-4 kHz, and 4-11 kHz).

Each

onset time is given by the peak time found by peak-D(t) along the time axis, whereP
D(t) = f d(t; f ). D(t) is linearly smoothed with a convolution kernel before its peak time is calculated. LimitP makes it possible to nd
ing the frequency range ofpicking in the sumfonset times in the di erent frequency ranges.

eld.

three sequences of seven-dimensional onset-time vectors
with the di erent sets of frequency weights (focusing on
to agents in the Beat Prediction stage.

4.2

Beat Prediction

their own hypotheses. Each hypothesis consists of a predicted next-beat time, its beat types (half-note-level typeand measure-level type), and the current inter-beat interval (Figure 5). These hypotheses are gathered by the
manager and the most reliable one is considered theoutput.
All agents are grouped into pairs.

7

nal

Two agents inthe same pair examine the same inter-beat interval andcooperatively predict the next beat times; their two preval. For this purpose, one agent interacts with the other

Each onset-time vectorizer transforms the results of allnders into a sequence of onset-time vectors:

the same onset times in all the frequency ranges are put
together into one vector. In the current system, threevectorizers transform onset times from sevenvectors according to di erent strategies and maintain

dictions will always di er by half the inter-beat inter-

Onset-time Vectorizers

nders into

The frame-time is the unit of time used in our system,and the term time in this paper is the time measured in unitsof the frame-time.
6

Figure 6: Agent interaction through a prediction

Multiple agents interpret the sequences of onset-timenders (seven in our current imple-

mentation) detect onset times in several di erent fre-

onset-time

prediction
field

now

all/low/middle frequency ranges). These results are sent

Onset-time Finders
Multiple onset-time

inhibitAgent 1-2

agent through a prediction

eld, which is an expectancy

8 that represents the time that the next beat is ex-

curve

In our current implementation there are twelve agentsgroupedinto six agent-pairs.
8
Other systems [Desain, 1992; Desain and Honing, 1994;
Vercoe, 1994] have used a similar concept of expectancy curvefor predicting future events, but not for managing interactions between agents.

0140 07

The following describe the formation of hypotheses,

pected to occur (Figure 6). The height of each local peakin the prediction

eld can be interpreted as the proba-

bility that the next beat is at that position.

The twoagents interact with each other by inhibiting the prediction

eld in the other agent. The beat time of eachhypothesis reduces the probability of a beat in the temporally corresponding neighborhood in the other's

eld.

Each agent has the following four parameters that
determineits

strategyformakingthethe chord change checkers, and the management of hypotheses.

Beat-predicting Agents
Each agent makes a hypothesis as follows and sends it tothe one-to-one corresponding chord change checker andthe manager.
(1) Determining the inter-beat interval

hypothesis(Figure 5). Initial settings of the parameters are listed
in Table 1.

To determine the inter-beat interval, each agent receives the sequence of onset-time vectors and calculates

9 The windowed and nor-its vectorial autocorrelation.

1. frequency focus typemalized vectorial autocorrelation function

This determines which vectorizer an agent receives
onset-time vectors from. This value is chosen fromamong type-all, type-low, and type-mid, respectively

t=c0W

corresponding to vectorizers focusing on all frequency ranges, low frequency ranges, and middle
frequency ranges.
2. autocorrelation period
This determines the window size for calculating
the vectorial autocorrelation (described later) of theonset-time vector sequence. The greater this value,
the older the onset-time information considered.
3. inter-beat interval range
This controls the range of possible inter-beat intervals.

Ac( ) is de-Pc win(c 0 t; W ) (~o(t) 1 ~o(t 0  ))t=c0WAc( ) = Pcwin(c 0 t; W ) (~o(t) 1 ~o(t)) (21)ned aswhere ~
o(t) is the N-dimensional onset-time vector at timet, c is the current time, and W is the strategy parameter
autocorrelation period. The window function win(t; s)whose window size is s is given bytwin(t; s) = 1:0 0 0:5(22)s
The inter-beat interval is given by the  with the maximum height in Ac( ) within the range limited by theparameter inter-beat interval range. If the reliability of

As described later, this limits the range ofa hypothesis becomes high enough, its agent tunes thisselecting a peak in the result of the vectorial auto-parameter to narrow the range of possible inter-beat in-correlation.

tervals so that it examines only a neighborhood of thecurrent appropriate one.

4. initial peak selection(2) Predicting the next beat time

This takes a value of either primary or secondary.
When the value is primary, the largest peak in theprediction

eld is initially selected, and the peak is

considered the next beat time; when the value is sec-

ondary, the second largest peak is initially selected.
This helps generate a variety of hypotheses.

To predict the next beat time, each agent forms a prediction

eld (Figure 7). The prediction

eld is the resultof calculating the windowed cross-correlation function

Cc( ) between the sum O(t) of all dimensions of ~o(t) andBm (t) whose interval

the provisional beat time sequenceis the inter-beat interval obtained using Equation (21):

Cc( ) =Table 1: Initial settings of the strategy parameters.

pair- frequency
autointer-beat initialagent focus type correlation interval
peak
periodrange
selection
1-1
type-all
500 f.t. 43-85 f.t. primary
1-2
type-all
500 f.t. 43-85 f.t. secondary
2-1
type-all1000 f.t. 43-85 f.t. primary2-2
type-all1000 f.t. 43-85 f.t. secondary
500 f.t. 43-85 f.t. primary
3-1 type-low
500 f.t. 43-85 f.t. secondary
3-2 type-low
4-1 type-low 1000 f.t. 43-85 f.t. primary
4-2 type-low 1000 f.t. 43-85 f.t. secondary
5-1 type-mid
500 f.t. 43-85 f.t. primary
500 f.t. 43-85 f.t. secondary
5-2 type-mid
6-1 type-mid 1000 f.t. 43-85 f.t. primary
6-2 type-mid 1000 f.t. 43-85 f.t. secondary\f.t." is the abbreviation of frame-time (11.61 ms).

c
X

t=c0V

t 0 I (t)

(win(

X
m=1

c 0 t; V ) O(t)(t 0 Bm (c +  )) )

(23)

= 1)
Bm (t) = B (t) 0 I (B (t)) ((mm > 1) (24)
m01
m01

0)
(x) = 10 ((xx =
(25)
6= 0)
where I (t) is the inter-beat interval at time t, V(=
I (c)) is the window size for calculating cross-correlation, and(= 12) is a constant value.

The

9The paper [Vercoe, 1994] also proposed the use of a variant of autocorrelation for rhythmic analysis.

0141 0inter-beat interval

selected if temporarily unstable beat times split the ap-

prediction field(by autocorrelation)(by cross-correlation)

propriate dominant group, the manager repeats grouping
and selecting three times while narrowing the margin ofBeat times

beat times allowable for being classi ed into the samegroup.

time

extrapolate

evaluate
how coincide

prediction

eld is thus given by

Cc( ) where 0   

eld after theeld is inhibited byits paired agent. When the reliability of a hypothesis islow, the agent initially selects the peak in the prediction
eld according to the parameter initial peak selection,and then tries to pursue the peak close to the sum of thepreviously selected one and the inter-beat interval.
Each agent determines the beat types of the predictedbeat time according to the half-note time and the measure time. As described in Section 3.2, these times are
obtained from the quarter-note chord change possibility
received from the corresponding chord change checker.
(4) Evaluating the reliability of its own hypothesis
nally evaluates the reliability of its own

hypothesis in the following three steps.

First, the re-liability is evaluated according to how the next beattime predicted on the basis of the onset times coincides
with the time extrapolated from the past beat times(Figure 7). If they coincide, the reliability is increased;otherwise, the reliability is decreased.

Second, the re-liability is evaluated according to how appropriate theeighth-note chord change possibility is. If

Len (de ned

in Section 3.2) is higher, the reliability is increased; otherwise, the reliability is decreased. Third, the reliability
is evaluated according to how appropriate the quarternote chord change possibility is.
reliability is increased a little.

If

and

since the beat types labeled by each agent might be in-correct because of a local irregularity of chord changes
or a detection error.

5 Experiments and Results
We tested the system implemented on a distributedmemory parallel computer, the Fujitsu AP1000, consisting of 64 processing elements.

In the following,

we describe an experimental result of testing the pro-(3) Judging the beat types

Each agent

Lqn
Lhn were high compared with the recent maximum,

using only the beat types that were labeled when

Each agent then selects the next beat time from local

peaks in the prediction

Transmission stage.
The manager updates the beat types in the output

Figure 7: Predicting the next beat.

I (c) 0 1.

The reliable hypothesis in the most dominantgroup is thus selected as the output and sent to the BI

Lqn is higher, theposed method of detecting chord changes (Section 5.1)
and describe the overall recognition rates of the system(Section 5.2).

5.1

Performance Test of Chord Change
Detection

We tested the basic performance of the proposed methodof chord change detection by using a random chord progression. This chord progression consisted of one hundred chord transitions of 101 chords that were randomly
selected from sixty kinds of chords: the twelve kinds of

]

]

]

]

]

root (A, A , B, C, C , D, D , E, F, F , G, G ) with theve chord types (major triad, minor triad (m), dominant
7th chord (7), minor 7th chord (m7), major 7th chord(M7)). These chords were so selected that the adjacentchords were di erent. Using a synthesizer's piano tone,
we played them in the basic root position (close position
voicing). The fundamental frequency of the chord rootnote was between 110 Hz and 208 Hz. To examine thecase in which the chord did not change, we played eachchord twice with the duration of a quarter note (600 ms)

Chord Change Checkers

under the tempo 100 M.M.

Each chord change checker examines the two kinds ofchord change possibilities as described in Section 3.1. It
analyzes the frequency spectrum on the basis of beat

The mean, standard deviation (SD), maximum, andminimum of the quarter-note chord change possibility

Cqn and the eighth-note chord change possibility Centimes (top-down information) received from the corresponding agent, and it sends the possibilities back to
the agent (Figure 5).

Table 2: Results of testing chord change detection.

Cqn

Hypotheses Manager
The manager classi es all agent-generated hypotheses
into groups according to beat time and inter-beat interval.

Each group has an overall reliability given by

the sum of the reliabilities of the group's hypotheses.
The manager then selects the dominant group that has
the highest reliability. Since an incorrect group could be0142 0Cen
T qn (CH, NC)

T qn

CH

NC

on

mean

0.73

0.01

0.56 (0.81, 0.30)

o

0.03

SD

0.22

0.02

0.29 (0.18, 0.08)

0.05

max.

1.00

0.10

1.00 (1.00, 0.48)

0.21

min.

0.28

0.00

0.12 (0.37, 0.12)

0.00

CH: chord change.

NC: no chord change.

when the appropriate beat times were provided for slicing the frequency spectrum are listed in Table 2.

The

Cqn in Table 2 respectively mean
the Cqn when a chord was changed at Tqn and the Cqn
when a chord was not changed at T qn . The values listed
in these columns indicate that the Cqn at chord changes\CH" and \NC" of the(CH) were appropriately higher than at the others (NC).

On the other hand, the \on Tqn " and \o Tqn " of the
Cen respectively mean the Cen on beats (n mod 2 =0) and the Cen on eighth-note displacement positions(n mod 2 = 1). In the case of the \on Tqn ," because thechord-change case (CH) alternated with the no-chordchange case (NC), these cases were also analyzed separately. The values listed in these columns indicate that

Cen .
Cen of NC of \on Tqn " tended to be higher thanthe Cen of \o T qn " because the chord notes were always
chord changes were appropriately detected usingThe

played at a beat time, whereas all frequency components
on an eighth-note displacement position had lasted fromthe previous beat time.

Figure 8:

Virtual dancers synchronized with musicalbeats.
are listed in Table 3. In each song where the rhythmic
structure was eventually determined correctly, the sys-

5.2 Overall Recognition Rates

tem initially had trouble determining the beat types even

We tested the system on monaural audio signals thatwere sampled from commercial compact discs of popular
music and contained the sounds of various instruments(not including drums). The initial one or two minutes of
40 songs performed by 28 artists were used as the inputs.
The time-signature was 4/4 and the tempi ranged from
62 M.M. to 116 M.M. and were roughly constant.
In our experiment the system obtained the correct
beat time (tracked beats at the quarter-note level) in

10 and determined the cor-

35 of the 40 songs (87.5 %)rect half-note-level type (tracked beats at the half-notelevel) in 34 of the 35 songs (97.1 %) in which the correct
beat times were obtained. Moreover, it determined thecorrect measure-level type (tracked beats at the measure level) in 32 of the 34 songs (94.1 %) in which thehalf-note-level type was correct.
We evaluated how quickly the system started to track
the correct rhythm stably at each rhythmic level. The
mean, standard deviation, maximum, and minimum of
the tracking start time of all the correctly tracked songs

In evaluating the recognition accuracy of our system, we
did not count unstably tracked songs in which correct beats
were obtained just temporarily.
10though the beat time was correct.
The beat times were not obtained correctly in theve songs because onset times were very few and irregular or the tempo

uctuated temporarily. Consequently,

the chord change possibilities in those songs could not
be obtained appropriately.

The main reason why thehalf-note-level or measure-level type was incorrect in theother mistaken songs was irregularity of chord changes,
such as chords changing at every quarter-note or every
other quarter-note.
These results show that the system is robust enoughto deal with real-world musical signals and that it rec-11

ognizes the musical structure of three rhythmic levels.

We have also developed an application of our rhythmtracking system that displays real-time computer graphics dancers whose motions change in time to musicalbeats (Figure 8) and con rmed that the system is usefulin the real application.

6 Conclusion

We have described the main rhythm-tracking problem
and solution in dealing with drumless audio signals andhave described the con guration and implementation of
our real-time rhythm-tracking system. The experimental
results show that the system can track, in real time,

Table 3: Start time of tracking the correct rhythm at
the quarter-note, half-note, and measure levels.

beats at the quarter-note level, the half-note level, andthe measure level in audio signals sampled from compact
discs of popular music.

rhythmic level

Quarter-note

Half-note

MeasureWe proposed a method for detecting chord changes bymean

10.71 sec

14.70 sec

20.70 sec

analyzing the frequency spectrum sliced at provisionalSD9.05 sec

9.21 sec

9.95 secbeat times (top-down information). We think that suchmax.

35.77 sec

42.56 sec

42.56 sec

min.

0.79 sec

3.42 sec

3.42 sec

11
The rhythm-tracking results are further evaluated in[Goto and Muraoka, 1997].

0143 0an approach, without chord name identi cation, is mean-[Goto and Muraoka, 1995b] Masataka Goto and Yoichi

ingful because a person generally does not perceive music

Muraoka. A real-time beat tracking system for audio

as musical symbols. This method enabled our system tosignals.

determine the beat types in audio signals without drum-

In Proc. of the 1995 Intl. Computer Music
Conf., pages 171{174, 1995.

sounds and to select the appropriate hypothesis from

[Goto and Muraoka, 1996] Masataka Goto and Yoichi

multiple agent-generated hypotheses.

Muraoka. Beat tracking based on multiple-agent ar-

We plan to upgrade the system to generalize to otherchitecture | a real-time beat tracking system for au-musical genres, to follow tempo changes, and to makedio signals |. In Proc. of the Second Intl. Conf. on
Multiagent Systems, pages 103{110, 1996.

use of other higher-level musical structure.

Acknowledgments[Goto and Muraoka, 1997] Masataka Goto and Yoichi
Muraoka. Issues in evaluating beat tracking systems.

We thank David Rosenthal for his helpful comments on

In Working Notes of the IJCAI-97 Workshop on Is-

earlier drafts of this paper. We also thank Fujitsu Laboratories Ltd. for use of the AP1000.

sues in AI and Music, 1997 (in press).

[Katayose et al., 1989] H. Katayose, H. Kato, M. Imai,

References

and S. Inokuchi. An approach to an arti cial music
In Proc. of the 1989 Intl. Computer Music
Conf., pages 139{146, 1989.
expert.

[Allen and Dannenberg, 1990] Paul E. Allen and Roger
B. Dannenberg. Tracking musical beats in real time.
In

Proc. of the 1990 Intl. Computer Music Conf.,[Large, 1995] Edward W. Large. Beat tracking with anonlinear oscillator. In Working Notes of the IJCAI-

pages 140{143, 1990.

95 Workshop on Arti cial Intelligence and Music,[Dannenberg and Mont-Reynaud, 1987] Roger B. Dannenberg and Bernard Mont-Reynaud.

Following an

improvisation in real time. In Proc. of the 1987 Intl.

pages 24{31, 1995.
[Rosenthal, 1992a] David Rosenthal. Emulation of human rhythm perception.

Computer Music Conf., pages 241{248, 1987.

[Desain and Honing, 1989] Peter Desain and Henkjan
Honing. The quantization of musical time: A connec-

Machine Rhythm:
Computer Emulation of Human Rhythm Perception.

[Rosenthal, 1992b] David Rosenthal.

tionist approach. Computer Music Journal, 13(3):56{

PhD thesis, Massachusetts Institute of Technology,

66, 1989.
[Desain and Honing, 1994] Peter Desain and Henkjan
Honing. Advanced issues in beat induction modeling:
syncopation, tempo and timing. In Proc. of the 1994

Intl. Computer Music Conf., pages 92{94, 1994.

1992.
[Rowe, 1993] Robert Rowe.

Computational models of beat induction:

Working Notes of the
IJCAI-95 Workshop on Arti cial Intelligence and Music, pages 1{10, 1995.

the rule-based approach.

In[Desain, 1992] Peter Desain. Can computer music bene t from cognitive models of rhythm perception?

In[Scheirer, 1996] Eric D. Scheirer.
comb
1996.

On The AutomaticTranscription of Percussive Music | From Acoustic
Signal to High-Level Analysis. PhD thesis, CCRMA,
Stanford University, 1985.

[Smith, 1996] Leigh M. Smith. Modelling rhythm perception by continuous time-frequency analysis.

Real-time

tempo

tracking using rules to analyze rhythmic qualities. In

392{395, 1996.
[Todd and Lee, 1994] Neil Todd and Chris Lee.

Proc. of the 1991 Intl. Computer Music Conf., pages

Muraoka.

A beat tracking system for acoustic sig-

the 1994 Intl. Computer Music Conf., pages 88{89,1994.

[Todd, 1994] Neil P. McAngus Todd. The auditory \primal sketch": A multiscale model of rhythmic group-nals of music. In Proc. of the Second ACM Intl. Conf.

ing.

on Multimedia, pages 365{372, 1994.

[Goto and Muraoka, 1995a] Masataka Goto and Yoichi
Muraoka. Music understanding at the beat level |Anauditory-motor model of beat induction. In Proc. of578{581, 1991.
[Goto and Muraoka, 1994] Masataka Goto and YoichiIn

Proc. of the 1996 Intl. Computer Music Conf., pages

42{45, 1992.
Driesse.

Using bandpass andlters to beat-track digital audio. (unpublished),[Schloss, 1985] W. Andrew Schloss.

Proc. of the 1992 Intl. Computer Music Conf., pages[Driesse, 1991] AnthonieInteractive Music Systems.

The MIT Press, 1993.

[Desain and Honing, 1995] Peter Desain and Henkjan
Honing.

Computer Music Journal,

16(1):64{76, 1992.

Journal of New Music Research, 23(1):25{70,1994.
[Vercoe, 1994] Barry Vercoe. Perceptually-based music

real-time beat tracking for audio signals |. In Work-ing Notes of the IJCAI-95 Workshop on Computational Auditory Scene Analysis, pages 68{75, 1995.

0144 0pattern recognition and response. In Proc. of the Third

Intl. Conf. for the Perception and Cognition of Music,
pages 59{60, 1994.