Working Notes of the IJCAI-99 Workshop on Computational Auditory Scene Analysis, pp.31-40, August 1999.

A Real-time Music Scene Description System:
Detecting Melody and Bass Lines in Audio Signals
Masataka Goto
Satoru Hayamizu
Machine Understanding Division, Electrotechnical Laboratory
1-1-4 Umezono, Tsukuba, Ibaraki 305-8568 JAPAN.
goto@etl.go.jp
hayamizu@etl.go.jp
Abstract
This paper describes a predominant-pitch estimation method that enables us to build a realtime system detecting melody and bass lines asa subsystem of our music scene description system. The purpose of this study is to build sucha real-time system that is practical from the engineering viewpoint, that gives suggestions to
the modeling of music understanding, and thatis useful in various applications. Most previous pitch-estimation methods premised eithera single-pitch sound with aperiodic noises or a
few musical instruments and had great diﬃculty dealing with complex audio signals sampledfrom compact discs, especially discs recording
jazz or popular music with drum-sounds. Our
method can estimate the most predominant fundamental frequency (F0) in such signals
containing sounds of various instruments because it does not rely on the F0’s frequency
component, which is often overlapped by other sounds’ components, and instead estimates
the F0 by using the Expectation-Maximization
algorithm on the basis of harmonics’ frequency components within an intentionally limited
frequency range. It also uses a multiple-agent
architecture to stably track the temporal trajectory of the F0. Experimental results showthat the system is robust enough to estimate
the predominant F0s of the melody and basslines in real-world audio signals.

1

Introduction

A typical research approach to computational auditory
scene analysis is sound source segregation: the extraction, from sound mixtures such as ones people ﬁnd in
the real-world environment, of the audio signal corresponding to each auditory stream. Human listeners canobviously understand various properties of such soundmixtures, and this suggests that the listeners detect theexistence of some auditory objects in sound mixtures andobtain a description of them. The understanding, however, is not necessarily evidence that the human auditory
system extracts the individual audio signal corresponding to each auditory stream, although the sound source
segregation is valuable from the viewpoint of engineering. This is because segregation is in general not a necessary condition for understanding: even if a mixture of
two objects cannot be segregated, it can be understoodthat the two objects are included in the mixture on thebasis of salient feature points of them. In developing
a computational model of monaural or binaural soundsource segregation, there is some possibility that we are
dealing with the problem which is not solved by any
mechanism in this world, not even by a human brain.
We therefore think that it is important to ﬁrst build acomputational model that can obtain a certain description of auditory scene from sound mixtures. To emphasize this approach, we dare to call it auditory scene description. If we consider perceptual sounds1 to be the description of an auditory scene, the term auditory scene
description has the same meaning as the term auditory scene analysis utilized by Kashino [Kashino, 1994;
Kashino et al., 1998]. In fact, Kashino [1994] also discussed the auditory scene analysis problem from a standpoint similar to ours by pointing out that the extractionof symbolic representation is more natural and essential
than the restoration of a target signal wave from a soundmixture.
In modeling the auditory scene description, it is important that we discuss what an appropriate descriptionof audio signals is. An easy way of specifying the description is to borrow the terminology of existing discrete
symbol systems, such as musical scores consisting of musical notes and such as speech transcriptions consistingof text characters. Those symbols, however, represent
1
The term perceptual sound was proposed by Kashino[Kashino, 1994; Kashino et al., 1998] and means a clusterof acoustic energy which humans hear as one sound. It isdeﬁned as a symbol that corresponds to an acoustic (or auditory) entity.

−31 −only limited properties of audio signals. For example,
they discard nonsymbolic properties such as the expressiveness of music performances (the deviation of pitch,
loudness, and timing) and the prosody of spontaneous
speeches. To take such properties into account, we needto introduce a subsymbolic description represented ascontinuous quantitative values. At the same time, weneed to choose an appropriate level of abstraction forthe description, because even though descriptions suchas raw waveforms and spectra have continuous values
they are too concrete. The appropriateness of the abstraction level will of course depend on the purpose of
the description and on the use to which it will be put.
In this paper we address the problem of music scene
description, auditory scene description in music, formonaural complex real-world audio signals such as thosesampled from commercially distributed compact discs.
We deal with various musical genres, such as popular
music, jazz music, and classical works. The audio signals thus contain simultaneous sounds of various instruments (even drums). This real-world oriented approachwith realistic assumptions is important to address thescaling-up problem and facilitate the implementation ofpractical applications [Goto and Muraoka, 1996; 1998a;
1998b].
The main contribution of this paper is to propose apredominant-pitch estimation method that makes it possible to detect the melody and bass lines in such audio
signals. On the basis of the method, a real-time system
detecting those lines has been implemented as a subsystem of the entire music-scene-description system. In
the following sections, we ﬁrst discuss the description
used in our music scene description system and diﬃculties encountered in detecting the melody and bass lines.
We then describe the algorithm of the predominant-pitch
estimation method that is a core part of our system. Finally, we show experimental results obtained using oursystem.

2

Music Scene Description Problem

We ﬁrst specify the entire music-scene-description problem and present the main diﬃculties in detecting the
melody and bass lines, which is the subproblem that weare dealing with in this paper.

2.1

Problem Speciﬁcation

Music scene description is deﬁned as a process that obtains a description representing the input musical audio
signal. Since various levels of description are possible, itis necessary to decide a description that is appropriate as
the ﬁrst step toward the ultimate description in humanbrains. We think that the music score is not adequate
because, as we have already pointed out [Goto and Muraoka, 1999], an untrained listener understands music toMusicalaudio signals
time

Hierarchicalbeat structure
Chord change
possibility
Snare

drum
Drum pattern Bass
drum

Melody line
Bass line
Figure 1: Description in our music scene description system.

some extent without mentally representing audio signals as musical scores. Music transcription, identifying thenames (symbols) of musical notes and chords, is in fact askill mastered only by trained musicians. We think thatthe appropriate description should satisfy the following
requirements:
1. It is an intuitive description which can easily be obtained by untrained listeners.
2. It is a basic description which trained musicians canuse as a basis for higher-level music understanding.
3. It is a useful description facilitating the developmentof various practical applications.
According to these requirements, we propose a description consisting of the following ﬁve subsymbolic representations shown in Figure 1:(1) Hierarchical beat structureThis represents the fundamental temporal structureof music and comprises three hierarchical levels.
(2) Chord change possibility
This represents possibilities of chord changes and indicates how much dominant frequency components
included in chord tones and their harmonic overtones change.
(3) Drum patternThis represents temporal patterns of how two principal drums, a bass drum and a snare drum, areplayed.
(4) Melody line
This represents the temporal trajectory of melody,
which is a series of single tones and is more distinctly
heard than the rest. Note that this is not a series of−32 −musical notes but is a continuous representation of
frequency and amplitude transitions.
(5) Bass line
This represents the temporal trajectory of bass,
which is a series of single tones and is the lowest
part in polyphonic music.
The idea of these representations came from the observation of how untrained listeners listen to music. The
description consisting of the former three and the methods for obtaining them have already been proposed fromthe viewpoint of beat-tracking in our previous papers [Goto and Muraoka, 1994; 1996; 1998a; 1998b; 1999;
Goto, 1998].
In this paper we introduce the latter two, melody line
and bass line, into the description and address the issues of obtaining them. The detection of the melody
and bass lines is important because the melody forms
the core of Western music and is very inﬂuential in theidentity of a musical piece and the bass is closely related with the tonality. For both trained and untrained
listeners, the melody and bass lines are fundamental tothe perception of music. They are also useful in various
applications, such as automatic transcription, automatic music indexing for information retrieval like [Sonoda et al., 1998], computer participation in human live
performances, musical performance analysis of formerlyrecorded outstanding performances, and automatic production of accompaniment tracks of Karaoke or Music
Minus One by making use of compact discs.
In short, we solve the problem of obtaining the description of the melody line Dm (t) and the bass line Db (t)given byDm (t) = {Fm (t), Am (t)},Db (t) = {Fb (t), Ab (t)},

(1)
(2)

where Fi (t) (i = m, b) denotes the fundamental frequency (F0) at time t and Ai (t) denotes the amplitude att.

2.2

Katayose and Inokuchi, 1989; Brown and Cooke, 1994;
Nakatani et al., 1995; Kashino and Murase, 1997;
Kashino et al., 1998], they dealt with at most three musical instruments or voices and had great diﬃculty estimating the F0 in complex audio signals sampled fromcompact discs.
The main reason for the diﬃculty of F0 estimation
in sound mixtures is that frequency components of one
sound overlap frequency components of simultaneous
sounds in the time-frequency domain. In the case of
typical popular music performed by a voice, a keyboard
instrument (like the piano), an electric guitar, a bass
guitar, and drums, for example, a part of the voice’s
harmonic structure — especially its F0’s frequency component — is often overlapped by harmonics of the keyboard instrument and guitar, by higher harmonics of thebass guitar, and by noisy inharmonic frequency components of the snare drum. A simple method locally tracing
a frequency component therefore cannot be reliable andstable. Moreover, sophisticated F0 estimation methods
that rely on the existence of the F0’s frequency component not only cannot handle the missing fundamental
but are also unreliable when used with complex mixtures
where the F0’s component is smeared by the harmonics
of simultaneous sounds.

3

Predominant-Pitch Estimation
MethodWe propose a method for estimating the fundamental
frequency (F0) of the most predominant harmonic structure in a limited frequency region of sound mixtures.
The method makes it possible to detect the melody andbass lines because the melody line usually keeps the most
predominant harmonic structure in middle and high frequency regions and the bass line usually keeps the most
predominant harmonic structure in a low frequency region. The method has the following features that enable
the robust F0 estimation in complex sound mixtures:

Issues in Detecting Melody and Bass
Lines

It has been considered very diﬃcult to estimate theF0 of a particular instrument or voice in the monaural audio signal of an ensemble performed by more than
three musical instruments. Most previous F0 estimation methods [Noll, 1967; Schroeder, 1968; Rabiner etal., 1976; Nehorai and Porat, 1986; Charpentier, 1986;
Ohmura, 1994; Abe et al., 1996; Kawahara et al., 1998a]premised that the input audio signal contained just asingle-pitch sound or a single-pitch sound with a noisy
aperiodic sound. Although several methods for dealing with multiple-pitch mixtures were proposed in thecontext of sound source segregation and automatic music transcription [Parsons, 1976; Chafe and Jaﬀe, 1986;−33 −• While the method assumes that the target predominant sound has the harmonic structure, it does notrely on the existence of the F0’s frequency component and can deal with the missing fundamental.
In other words, it can estimate the F0 by using a
subset of the harmonic structure.
• The method dares to make use of frequency components in a limited frequency range and ﬁnds theF0 whose harmonics are predominant in that range.
In other words, whether the F0 is within that range
or not, the method tries to estimate the F0 which
is supported by predominant frequency components
as the harmonics.
• The method regards the observed frequency components as a weighted mixture of harmonic-structureAudio signals
Audio signals

Instantaneous frequency calculation

Decimator
2

Extracting candidate frequency components

Forming F0's probability density function

Agent

era

cti

on

Agent

Most predominant F0 trajectory
Melody line

Figure 2:
method.

Detecting melody lineInt

Detecting bass line

Agent

4 kHz
2 kHz

Decimator

3.6-7.2
kHz

1.8-3.6kHz

0.9-1.8
kHz

0.45-0.9
kHz

1kHz

FFT

0-0.45kHz

Figure 3: Overview of multirate ﬁlter bank.

Candidate frequency components

Salience
detector

Decimator

Decimator = LPF (0.45 fs) + 1/2 down-sampler

BPF for bass line

F0's probability density function

8 kHz

Decimator

Limiting frequency regions
BPF for melody line

FFT
FFT
FFT
FFT

16 kHzBass line

Overview of our predominant-pitch estimation

tone models and estimates their weights by using the Expectation-Maximization (EM) algorithm[Dempster et al., 1977], which is an iterative technique for computing maximum likelihood estimatesfrom incomplete data. The method then considers
the maximum-weight model as the most predominant harmonic structure and obtains its F0.
• Since the local F0 estimation is not reliable, themethod supports sequential F0 tracking on the basis of a multiple-agent architecture in which agents
track diﬀerent temporal trajectories of the F0.
In particular, it is important to deemphasize a frequency
region around the F0 in estimating the F0 of the melody
line, because its frequency region is typically very crowded with other frequency components.
The strategy of this method is related to the singing
formant, a high spectrum-envelope peak near 2.8 kHzof vowel sounds produced in male opera singing, though
the application of the method is not limited to opera
singing. Although sounds from an orchestral accompaniment tend to mask the singer’s voice around a peak(about 450 Hz) of their long-time-average spectrum, thesinging formant enables listeners to hear the voice overthe high level of sounds from the orchestra because it has
predominant frequency components in the higher limited
range [Richards, 1988]. While we do not intend to build
a psychoacoustical model of human perception, our strategy also has likely relevance to the following psychoacoustical results: Ritsma [1967] reported that theear uses a rather limited spectral region in producing

a well-deﬁned pitch perception; Plomp [1967] concluded
that for fundamental frequencies up to about 1400 Hz,
the pitch of a complex tone is determined by the secondand higher harmonics rather than by the fundamental.
We need to note, however, that those results do not directly support our strategy since they were obtained byusing the pitch of a single sound.
Figure 2 shows an overview of the method. It ﬁrst
calculates instantaneous frequencies by using multirate signal processing techniques. Candidate frequency components are then extracted on the basis of an
instantaneous-frequency-related measure. Those components are ﬁltered with two bandpass ﬁlters, one forthe melody line and the other for the bass line. Each setof the ﬁltered frequency components is utilized to forma probability density function (PDF) of the F0, and thesalient promising peaks in the F0’s PDF are sequentiallytracked by a multiple-agent architecture, where each agent forms an F0 trajectory and evaluates its reliability.
Finally, the most predominant F0 trajectory of the mostreliable agent is selected as the output.

3.1

Instantaneous Frequency Calculation

The method ﬁrst calculates the instantaneous frequency[Flanagan and Golden, 1966; Cohen, 1989; Boashash,1992], the rate of change of the phase of a signal, of ﬁlterbank outputs. Instead of calculating the phase directly,
it utilizes an eﬃcient calculation method [Flanagan andGolden, 1966] based on the short-time Fourier transform(STFT) whose output can be interpreted as a collectionof uniform-ﬁlter outputs. When the STFT of a signalx(t) is deﬁned as ∞X(ω, t) =x(τ )h(τ − t)e−jωτ dτ
(3)−∞= a + jb,(4)

the instantaneous frequency λ(ω, t) is given byλ(ω, t) = ω +∂aa ∂b∂t − b ∂t.
a2 + b2(5)

We use the STFT window function h(t) obtained byconvolving a basis function of the 2nd-order cardinal
B-spline with an isometric Gaussian window function[Kawahara et al., 1998b]. Although the importance of
the appropriate choice of h(t) is discussed in [Kawahara
et al., 1998b], our window function is not optimized to−34 −the F0 of a single tone since there may be several diﬀerent F0s within an STFT window.
Because a single STFT provides bad time-frequency
resolution for a certain frequency range, we use a multirate ﬁlter bank [Vetterli, 1987]. Since the Wavelet transform providing the minimum uncertainty is hard to be
performed in real time, we design an STFT-based ﬁlter
bank that provides an adequate time-frequency resolution compromise under the real-time constraint.
Figure 3 shows an overview of our binary-tree ﬁlter
bank. At each level of binary branches, the audio signal is down-sampled by a decimator that consists of ananti-aliasing ﬁlter (FIR lowpass ﬁlter (LPF)) and a 1/2
down-sampler. The cut-oﬀ frequency of the LPF in eachdecimator is 0.45 fs where fs is the sampling rate atthat branch. In our current implementation, the input
signal is digitized at 16 bit / 16 kHz, and it is ﬁnally
down-sampled to 1 kHz. Then the STFT whose window
size is 512 samples is calculated at each leaf by using theFast Fourier Transform (FFT) while compensating forthe diﬀerent time delays of the diﬀerent multirate layers. Since at 16 kHz the FFT frame is shifted by 160
samples, the discrete time step (1 frame-time2 ) is 10 ms.

3.2

Extracting Candidate Frequency
Components

The extraction of candidate frequency components isbased on the frequency-to-instantaneous-frequency mapping [Charpentier, 1986; Abe et al., 1996; Kawahara etal., 1998b]. We consider the mapping from the center
frequency ω of an STFT ﬁlter to the instantaneous frequency λ(ω, t) of its output. If there is a frequency component at frequency ψ, ψ is placed at the ﬁxed point of
the mapping and the instantaneous frequencies aroundψ stay almost constant in the mapping [Kawahara et al.,(t)
1998b]. Therefore a set Ψf of instantaneous frequenciesof the candidate frequency components3 can be extracted by using the following equation [Abe et al., 1997]:(t)Ψf = { ψ | λ(ψ, t) − ψ = 0,∂(λ(ψ, t) − ψ) < 0}.
∂ψ



2

(t)

| X(ω, t) | if ω ∈ Ψf0otherwise.

Figure 4: Frequency responses of bandpass ﬁlters (BPFs).

3.3

Limiting Frequency Regions

Limiting (i.e., weighting) the frequency region of frequency components is important to estimate a predominant F0. We introduce diﬀerent kinds of bandpass ﬁlters(BPFs) for the melody and bass lines. The BPF for the
melody line is designed so that it covers most dominantharmonics of typical melody lines and deemphasizes a
crowded frequency region around the F0. The BPF forthe bass line is designed so that it covers most dominantharmonics of typical bass lines and deemphasizes a frequency region where other parts tend to become more
dominant than the bass line.
In our current implementation we use BPFs whose
frequency responses are shown in Figure 4. In the restof this paper, to denote the log-scale frequency we use
the unit of cent (a musical-interval measurement). The
frequency fHz in Hz is converted to the frequency fcent
in cent as follows:fHz,
fcent = 1200 log2 REF
HzREFHz = 440 × 2

(7)

.

(8)
(9)

(t)

pΨ (x) =BP Fi (x) Ψp (x),P ow (t)(10)

where P ow (t) is the total power of the bandpass-ﬁlteredfrequency components:
 ∞(t)
BP Fi (x) Ψ(t)(11)
P ow =
p (x) dx.
−∞

3.4

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 frame-time.
3
Abe et al. [1997] called the temporal contours of thesecomponents IF attractors.

3
12 −5

There are 100 cents to a tempered semitone and 1200 toan octave.
The bandpass-ﬁltered frequency components can be(t)represented as BP Fi (x)Ψp (x) where BP Fi (x) (i =m, b) denotes the BPF’s frequency response at frequen(t)cy x (in cents) and Ψp (x) is the same as the power(t)
distribution Ψp (ω) except that the frequency unit is
the cent. In preparation for the next step, we deﬁne
the probability density function (PDF) of the bandpass(t)ﬁltered frequency components pΨ (x):(t)(t)
the power distribution function Ψp (ω) as

BPF for detecting melody line

0 cent 1200 cent 2400 cent 3600 cent 4800 cent 6000 cent 7200 cent 8400 cent 9600 cent16.35 Hz 32.70 Hz 65.41 Hz 130.8 Hz 261.6 Hz 523.3 Hz 1047 Hz 2093 Hz 4186 Hz(6)

By calculating the power of those frequencies which is(t)given by the STFT power spectrum at Ψf , we can deﬁneΨ(t)p (ω) =

BPF for detecting bass line
1

Forming the F0’s Probability Density
Function

For each set of candidate frequency components ﬁlteredby the BPF, we form a probability density function(PDF) of the F0. The basic idea is to consider that−35 −

1. (E-step)Compute the following conditional expectation of
the mean log-likelihood:the PDF of the bandpass-ﬁltered frequency components,(t)pΨ (x), was generated from a model that is a weighted
mixture of harmonic-structure tone models. When the
PDF of each tone model whose F0 is frequency F is denoted as p(x|F ), the mixture density p(x; θ(t) ) is deﬁned
as


(t)
Q(θ(t)
 |θ )∞=

Fhip(x; θ (t) ) =w(t) (F ) p(x|F ) dF,(12)

θ(t) = {w(t) (F ) | Fli ≤ F ≤ Fhi },

(13)

−∞

(t)

(17)
where EF [a|b] denotes the conditional expectationof a with respect to the hidden variable F with probability distribution determined by the condition b.

Fliwhere Fli and Fhi denote the lower and upper limitsof the possible (allowable) F0 range and w (t) (F ) is theweight of a tone model p(x|F ) which satisﬁes Fhi
w (t) (F ) dF = 1.
(14)

2. (M-step)
Maximize Q(θ(t) |θ(t) ) as a function of θ (t) in orderto obtain the updated (improved) estimate θ (t) :θ (t) = argmax Q(θ (t) |θ(t) ).

Fli

(18)

θ (t)

Note that we simultaneously take into consideration all
the possibilities of the F0 because we cannot assume thenumber of sound sources in real-world audio signals sampled from compact discs. If we can estimate the model(t)parameter θ(t) so that the observed PDF pΨ (x) is likely(t)to have been generated from the model p(x; θ (t) ), pΨ (x)is considered to be decomposed into harmonic-structure
tone models, and the weight w(t) (F ) can be interpreted
as the PDF of the F0:(t)
pF 0 (F ) = w(t) (F )pΨ (x) EF [log p(x, F ; θ(t) ) | x; θ (t) ] dx,(Fli ≤ F ≤ Fhi ).

In the E-step we haveQ(θ (t) |θ(t) ) ∞  Fhi(t)=pΨ (x)p(F |x; θ(t) ) log p(x, F ; θ (t) )dF dx,−∞ Fli(19)
where the complete-data log-likelihood is given bylog p(x, F ; θ(t) ) = log(w(t) (F ) p(x|F ))= log w(t) (F ) + log p(x|F ).

(15)

The more dominant a tone model p(x|F ) in the mixture,
the higher the probability of the F0 F of its model.
Therefore the problem to be solved is to estimate theparameter θ(t) of the model p(x; θ (t) ) when we observed(t)the PDF pΨ (x). The maximum likelihood estimator of
θ(t) is obtained by maximizing the mean log-likelihooddeﬁned as ∞(t)pΨ (x) log p(x; θ(t) ) dx.
(16)−∞

Because this maximization problem is too diﬃcult to besolved analytically, we use the Expectation-Maximization(EM) algorithm [Dempster et al., 1977], which is an iterative algorithm successively applying two steps — theexpectation step (E-step) and the maximization step (Mstep) — for computing maximum likelihood estimates(t)from incomplete observed data (in our case, pΨ (x)).
(t)
With respect to the parameter θ , each iteration updates the ‘old’ parameter estimate θ(t) to obtain the‘new’ parameter estimate θ(t) . We simply use the ﬁnal
estimate at the previous frame-time t − 1 for the initial
estimate of θ(t) .
By introducing an unobservable (hidden) variable F
describing which tone model was responsible for generating each observed frequency component at x, we canspecify the two steps of the EM algorithm as follows:(20)

As for the M-step, Equation (18) is a conditional problem of variation where the condition is Equation (14).
This problem can be solved by using the following EulerLagrange diﬀerential equation:
 ∞
∂
(t)
p (x) p(F |x; θ(t) ) (log w (t) (F ) +∂w(t) −∞ Ψ1(t)log p(x|F )) dx − λ(w (F ) − Fhi −Fli ) = 0,(21)
where λ is a Lagrange multiplier. From Equation (21),
we have
1 ∞ (t)(t)w (F ) =p (x) p(F |x; θ(t) ) dx.
(22)
λ −∞ Ψ
In this equation, λ is determined from Equation (14) tobe λ = 1 and we know from the Bayes’ theorem thatp(F |x; θ (t) ) is givenw (t) (F ) p(x|F )p(F |x; θ(t) ) =  Fhi,w (t) (η) p(x|η) dη
Fli

(23)

where w(t) (F ) is the ‘old’ parameter estimate (θ (t) ={w(t) (F )}). Finally we obtain the ‘new’ improved parameter estimate w (t) (F ): ∞w (t) (F ) p(x|F )(t)(t)
dx. (24)w (F ) =pΨ (x)  Fhi−∞w (t) (η) p(x|η) dη
Fli

−36 −

To compute Equation (24), we need to assume the
PDF of a tone model p(x|F ), which indicates where theharmonics of the F0 F tend to occur. We accordingly assume the following simple harmonic-structure tonemodels for the melody line (i = m) and the bass line
(i = b):p(x|F ) = αNiSalience
detector

selective allocationoragent generation
Agent

F0's PD

F

track

Interaction

Agent
track

Agent
track
e

tim

c(h) G(x; F + 1200 log2 h, Wi ),(25)

frequencyh=1

G(x; m, σ) = √ 1 2 e−(x−m)2
2σ 2

2πσ

,

(26)

where α is a normalization factor, Ni is the number of
harmonics considered, Wi2 is the variance of the Gaussian
distribution G(x; m, σ), and c(h) determines the amplitude of the h-th harmonic component. For c(h) we use
G(h; 0, Hi ) where Hi is a constant. Since these models
are very simple, there is a great deal of room for reﬁning
them in future implementations. This could be done, forexample, by introducing tone memories.
A simple way of determining the frequency Fi (t) of themost predominant F0 is to ﬁnd the frequency that max(t)imizes the F0’s PDF pF 0 (F ) (Equation (15)), which is
the ﬁnal estimate obtained by the iterative computationof Equation (24):Figure 5: Sequential F0 tracking by multiple-agent architecture.

picks up salient promising peaks in the F0’s PDF, andagents driven by those peaks track their trajectories(Figure 5). At the ﬁrst of the processing, no agent has
been generated and there is only the salience detector.
They then behave at each frame as follows:(1) After forming the F0’s PDF at each frame, thesalience detector picks up several salient peaks.
(2) If there are agents, they interact to allocate thesalient peaks to agents exclusively according topeak-closeness criteria.

(27)(3) If the most salient peak has not been allocated, a
new agent for tracking its peak is generated.

This result is not stable, however, because peaks corresponding to the F0s of several simultaneous tones sometimes compete in the F0’s PDF for a moment and aretransiently selected, one after another, as the maximumof the F0’s PDF. It is therefore necessary to consider
the global temporal continuity of the F0 peak. This isaddressed in the next section.

(4) Each agent has an accumulated penalty. An agent whose accumulated penalty exceeds a certain
threshold is terminated.

(t)

Fi (t) = argmax pF 0 (F ).
F

3.5

Sequential F0 Tracking by
Multiple-Agent Architecture

The method sequentially tracks peak trajectories in thetemporal transition of the F0’s PDF in order to select the most predominant and stable F0 trajectory fromthe viewpoint of global F0 estimation.4 To perform this,
we introduce a multiple-agent architecture that enables
dynamic and ﬂexible control of the tracking process. In
the multiple-agent architecture we proposed earlier [Goto and Muraoka, 1996] the number of agents was ﬁxed
during the processing. Our new architecture, however,generates and terminates agents dynamically by using amechanism similar to one in the residue-driven architecture [Nakatani et al., 1995].
The architecture consists of a salience detector andmultiple agents. At each frame the salience detector
4
Because the F0’s PDF is obtained without assuming thenumber of sounds contained, our method can, by using an appropriate sound-source discrimination method, be extended
to the problem of tracking multiple simultaneous sounds.

(5) An agent to which a salient peak has not been allocated is penalized a certain value and tries to ﬁnd
its next peak in the F0’s PDF directly. When theagent cannot ﬁnd the peak even in the F0’s PDF, it
is further penalized a certain value. Otherwise, thepenalty is reset.
(6) Each agent evaluates its own reliability by using thereliability at the previous frame and the degree ofthe peak’s salience at the current frame.
(t)(7) The output at t — the F0 f0 and its reliability(t)r0 — is determined on the basis of which agent
has the highest reliability and greatest total power
along the trajectory of the peak it is tracking.
Salience Detector(t)
The salience detector picks up salient peaks Φf of thecurrent F0’s PDF. To track peaks in the temporal transition of the F0’s PDF, we ﬁrst deﬁne the F0 peak map(t)
mF 0 (F ) considering the total power transition:

(t)
∂ (t)
pF 0 (F ) = 0,
 P ow(t) pF 0 (F ) if ∂F(t)∂ 2 (t)mF 0 (F ) =∂F 2 pF 0 (F ) < 00otherwise.
(28)

−37 −

(t)

(t)

The salient peaks Φf are then given by(t)Φf = { F|(t)mF 0 (F )≥(t)
Ths max mF 0 (F )},F

When Cfj(29)

where Ths is a constant threshold (0 ≤ Ths ≤ 1) for thejudgement of the salience.
(t)
By tracking a provisional peak trajectory of mF 0 (F )in the near future, the salience detector evaluates the(t)salience degree Φr (F ) of each peak, which represents
how promising its peak is:5


(t)
1


mF 0 (F ) G(0; 0, Ws )(Periods +1) SP ow(t)





Periods(t+τ )(t)+max φr(f ; F ) (30)Φr (F ) =|f |<2Ws


τ =1


(t)


if F ∈ Φf0otherwise,
SP ow(t) =Periods
1
P ow (t+τ ) ,Periods + 1 τ =0(31)

where Periods is the period of tracking a provisional peak
trajectory and Ws2 is the variance of the Gaussian dis(t+τ )(f ; F ) is deﬁned
tribution G(x; m, σ). The term φr
as(t+τ ))(f ; F ) = mF 0 (η (t+τ −1) (F ) + f) G(f; 0, Ws ),
φ(t+τ
r
(32)
where f is the amount of the frequency change from theprevious frame, and η (t+τ ) (F ) denotes the tracked peakfrequency at t + τ : (t+τ −1))(F ) + argmax φ(t+τ(f ; F )

r
 η
|f
|<2W
s
(t+τ)
(33)
(F ) =
ηif τ > 0Fotherwise.
(t+τ )The term φr(f ; F ) denotes a possibility indicating
how much the peak frequency is likely to change fromthe previous peak frequency η (t+τ −1) (F ).
AgentEach agent j has the following set of parameters and up(t)dates it every frame: the frequency Afj of the peak it(t)is tracking, the salience degree Adj of the peak, an ac(t)(t)
cumulated peak-not-found penalty Apj , the sum Asj(t)of SP ow since the agent was generated, and the reli(t)ability Arj .
(t)Among the salient peaks Φf , each agent ﬁnds the(t)most salient peak Cfj

than one agent claims the same peak, it is exclusively
allocated to the most predominant agent.
(t)
If the most salient peak, argmaxF Φr (F ), is not allo(t)cated, a new agent is generated and its parameter Afj(t)is set to argmaxF Φr (F ). On the other hand, an agent(t)whose penalty Apj reaches 1.0 is terminated. When
(t)

(t)

an agent cannot ﬁnd the next peak in Φf , its Apj isincreased by a positive constant Va , and when it cannot(t)(t)
ﬁnd the next peak even in mF 0 (F ), its Apj is further(t)increased by Va . Otherwise, Apj is reset to 0.0.
(t)After each agent updates the salient degree Adj

=

(t)
(t)
Φr (Afj )

(t)
(t−1)
and the power sum Asj = Asj
+
(t)
(t)
SP ow , it updates its reliability Arj as follows:
(t−1)

(t)

Arj = Ra

Asj

(t)

Asj

(t−1)

Arj

(t)

(t)

+ (1 − Ra ) SP ow
Adj ,
(t)
Asj

(35)
where Ra is a weight (0 ≤ Ra < 1) determining how
much the previous reliability is taken into account. The(t)(t)
most predominant F0 trajectory (f0 and r0 ) is then(t)determined on the basis of the parameters Afj and
(t)

Arj

of the most predominant agent whose number is
(t)

(t)

argmaxj Arj Asj .
Finally, the F0 Fi (t) and the amplitude Ai (t) of the
melody line Dm (t) (Equation (1)) and the bass line Db (t)(Equation (2)) are determined according to the harmonic structure of those lines. The harmonic structure ofeach line is estimated by tracking, in the candidate fre(t)quency components Ψp (ω), the harmonics along its F0
trajectory. The Fi (t) is ﬁnely adjusted according to thefrequencies of the harmonics and Ai (t) is obtained as thetotal power of the harmonics.

4

System Implementation andExperimental Results

Using the proposed method (the values of the parameters are listed in Table 1), we have built a real-timesystem that takes a musical audio signal as input and(34)(t+τ )In a real-time system, the mF 0 (F ) (0 ≤ τ ≤ Periods )can be accessed by regarding the actual current time as the
future time t + Periods ; the system output is consequently
delayed for a short period, at least Periods .
5— that is, when

(t)
(t−1)
| < 2Ws — the peak is allocated to agent|Cfj −Afj(t)(t)
j and its parameter Afj is updated to Cfj . If moreclosest to its previous peak fre-(t−1)
quency Afj
:
(t)
(t−1)
Cfj = argmax Φ(t), Ws ).
r (F ) G(F ; Afj
F

(t−1)

is close enough to Afj−38 −Table 1: Values of parameters.
Fhm = 9600 cent
Flm = 3600 cent
Nm = 16
Wm = 17 cent
Hm = 5.5
Ths = 0.5
Periods = 5 frame-time
Va = 0.125

Fhb = 4800 cent
Flb = 1000 cent
Nb = 6
Wb = 17 cent
Hb = 2.7
Ws = 50 cent
Ra = 0.91

Figure 6: Scrolling-window snapshots of candidate frequency components (left) and the corresponding detected melody
and bass lines (right) for a popular-music excerpt with
drum-sounds.
Table 2: Test songs sampled from compact discs.
title
My Heart Will Go On (Celine Dion)
Vision of Love (Mariah Carey)
Always (Bon Jovi)
Time Goes By (Every Little Thing)Spirit of Love (Sing Like Talking)Hoshi no Furu Oka (Misia)
Scarborough Fair (Herbie Hancock)
Autumn Leaves (Julian “Cannonball” Adderley)
On Green Dolphin Street (Miles Davis)
Violin Concerto in D, Op. 35 (Tchaikovsky)

genre
popularpopularpopularpopularpopularpopular
jazz
jazz
jazz
classical

outputs the detected melody and bass lines in several
forms: computer graphics for visualization, audio signals for auralization, and continuous quantitative values(with time stamps) for use in applications. The graphics output shows a window representing the scrolling F0
trajectories on a time-frequency plane and an adjacentinterlocking window representing the candidate frequency components (Figure 6). The output audio signals are
generated by sinusoidal synthesis on the basis of the harmonics that are tracked by a 2nd-order autoregressive
tracking model [Aikawa et al., 1996] guided by the detected Di (t).
The system has been implemented using a distributedprocessing technique so that diﬀerent system functions— such as audio input and output (I/O), main calculation, and intermediate-state and output visualization —are performed by diﬀerent processes distributed over a
LAN (Ethernet). To facilitate system expansion and application development, those processes are implemented
on the basis of a network protocol called RACP (Remote
Audio Control Protocol), which is an extension of the
RMCP (Remote Music Control Protocol) [Goto, ICMC97]. The main signal processing is performed on a personal computer with two Pentium II 450 MHz CPUs
(Linux 2.2), and the audio I/O and visualization processing is performed on a workstation, the SGI Octane
with R10000 250 MHz CPU (Irix 6.4).

We tested the system on excerpts of 10 songs in popular, jazz, and orchestral genres (Table 2). The inputmonaural audio signals were sampled from commerciallydistributed compact discs and each contained a singletone melody with sounds of several instruments.
In our experiment the system correctly detected, forthe most part of each audio sample, melody lines provided by a voice or a single-tone mid-range instrument
and bass lines provided by a bass guitar or a contrabass.
It tended to perform best on jazz music in which a wind
instrument such as a trumpet and a saxophone provided the melody line because the tones of such instruments
tended to be more dominant and salient in a jazz ensemble than in other genres. In the absence of the main vocal
part or the solo part, the system detected the F0 trajectory of a dominant accompaniment part, because ourmethod simply estimates the most predominant F0 trajectory every moment and does not discriminate soundsources.
The detected line, however, sometimes switched fromthe main vocal part to another obbligato part for a while
even when the previously tracked main vocal part continued. Furthermore, a short-term trajectory around theonset of the main vocal part was sometimes missing because of the delay in switching from another part to the
vocal part. These errors are due to the absence of amechanism for selecting just the target part from several simultaneous streams; this issue should be addressedin our future implementation. Other typical errors were
half-pitch or double-pitch errors in which the F0 was estimated as half or twice the actual F0.

5Conclusion

We have described the problem of music scene description for complex real-world audio signals and have addressed the problem of detecting the melody and basslines. Our method for estimating the most predominant
F0 trajectory in monaural audio signals does not presuppose the existence of the F0’s frequency component anduses partial information in an intentionally limited frequency range. Using the EM algorithm without assuming the number of sound sources, the method evaluates
the probability density function of the F0 which represents the relative dominance of every possible harmonic
structure. It also uses a multiple-agent architecture to
determine the most predominant and stable F0 trajectory from the viewpoint of global temporal continuity of
the F0. Experimental results show that our system implementing the method can estimate, in real time, thepredominant F0s of the melody and bass lines in audio
signals sampled from compact discs.
We plan to extend the method to track several streams
simultaneously and form more complete melody and basslines from them by using a selective-attention mechanism. That extension will also address the issues of sound−39 −source discrimination. Other future work will include
integration of the proposed pitch-estimation subsystemwith other subsystems detecting the hierarchical beatstructure, chord-change possibilities, and drum patterns
in order to build the entire music-scene-description system.

Acknowledgments
We thank Shotaro Akaho for his valuable discussions andfor his helpful comments on earlier drafts of this paper.

References[Abe et al., 1996] Toshihiko Abe, Takao Kobayashi, andSatoshi Imai. Robust pitch estimation with harmonics enhancement in noisy environments based on instantaneous
frequency. In Proc. of ICSLP 96, pages 1277–1280, 1996.
[Abe et al., 1997] Toshihiko Abe, Takao Kobayashi, andSatoshi Imai. The IF spectrogram: a new spectral representation. In Proc. of ASVA 97, pages 423–430, 1997.
[Aikawa et al., 1996] Kiyoaki Aikawa, Hideki Kawahara, andMinoru Tsuzaki. A neural matrix model for active tracking
of frequency-modulated tones. In Proc. of ICSLP 96, pages
578–581, 1996.
[Boashash, 1992] Boualem Boashash. Estimating and interpreting the instantaneous frequency of a signal. Proc. of
the IEEE, 80(4):520–568, 1992.
[Brown and Cooke, 1994] Guy J. Brown and Martin Cooke.
Perceptual grouping of musical sounds: A computationalmodel. Journal of New Music Research, 23:107–132, 1994.
[Chafe and Jaﬀe, 1986] Chris Chafe and David Jaﬀe. Source
separation and note identiﬁcation in polyphonic music. In
Proc. of ICASSP 86, pages 1289–1292, 1986.
[Charpentier, 1986] F. J. Charpentier. Pitch detection using
the short-term phase spectrum. In Proc. of ICASSP 86,
pages 113–116, 1986.
[Cohen, 1989] Leon Cohen. Time-frequency distributions —a review. Proc. of the IEEE, 77(7):941–981, 1989.
[Dempster et al., 1977] A. P. Dempster, N. M. Laird, andD. B. Rubin. Maximum likelihood from incomplete data
via the EM algorithm. J. Roy. Stat. Soc. B, 39(1):1–38,
1977.
[Flanagan and Golden, 1966] J. L. Flanagan and R. M.
Golden. Phase vocoder. The Bell System Technical Journal, 45:1493–1509, 1966.
[Goto and Muraoka, 1994] Masataka Goto and Yoichi Muraoka. A beat tracking system for acoustic signals of music. In Proc. of the Second ACM Intl. Conf. on Multimedia,
pages 365–372, 1994.
[Goto and Muraoka, 1996] Masataka Goto and Yoichi Muraoka. Beat tracking based on multiple-agent architecture— a real-time beat tracking system for audio signals —.
In Proc. of the Second Intl. Conf. on Multiagent Systems,
pages 103–110, 1996.
[Goto and Muraoka, 1998a] Masataka Goto and Yoichi Muraoka. An audio-based real-time beat tracking system andits applications. In Proc. of Intl. Computer Music Conf.,
pages 17–20, 1998.
[Goto and Muraoka, 1998b] Masataka Goto and Yoichi Muraoka. Music understanding at the beat level — real-timebeat tracking for audio signals —. In Computational Auditory Scene Analysis, pages 157–176. Lawrence Erlbaum
Associates, Publishers, 1998.
[Goto and Muraoka, 1999] Masataka Goto and Yoichi Muraoka. Real-time beat tracking for drumless audio signals:

Chord change detection for musical decisions. Speech Communication, 27(3–4):311–335, 1999.
[Goto, 1998] Masataka Goto. A Study of Real-time Beat
Tracking for Musical Audio Signals (in Japanese). PhD
thesis, Waseda University, 1998.
[Kashino and Murase, 1997] Kunio Kashino and Hiroshi
Murase. A music stream segregation system based on
adaptive multi-agents. In IJCAI-97, pages 1126–1131,
1997.
[Kashino et al., 1998] Kunio Kashino, Kazuhiro Nakadai,
Tomoyoshi Kinoshita, and Hidehiko Tanaka. Applicationof the bayesian probability network to music scene analysis. In Computational Auditory Scene Analysis, pages
115–137. Lawrence Erlbaum Associates, Publishers, 1998.
[Kashino, 1994] Kunio Kashino. Computational Auditory
Scene Analysis for Music Signals (in Japanese). PhD thesis, University of Tokyo, 1994.
[Katayose and Inokuchi, 1989] Haruhiro Katayose and Seiji
Inokuchi. The kansei music system. Computer Music Journal, 13(4):72–77, 1989.
[Kawahara et al., 1998a] Hideki Kawahara, Alain de Cheveigné, and Roy D. Patterson. An instantaneous-frequencybased pitch extraction method for high-quality speechtransformation: Revised TEMPO in the STRAIGHT suite. In Proc. of ICSLP 98, 1998.
[Kawahara et al., 1998b] Hideki Kawahara, Haruhiro Katayose, Roy D. Patterson, and Alain de Cheveigné. Highly
accurate F0 extraction using instantaneous frequencies (inJapanese). Tech. Com. Psycho. Physio., Acoust. Soc. ofJapan, H-98-116, pages 31–38, 1998.
[Nakatani et al., 1995] Tomohiro Nakatani, Hiroshi G. Okuno, and Takeshi Kawabata. Residue-driven architecture
for computational auditory scene analysis. In IJCAI-95,
pages 165–172, 1995.
[Nehorai and Porat, 1986] Arye Nehorai and Boaz Porat.
Adaptive comb ﬁltering for harmonic signal enhancement.
IEEE Trans. on ASSP, ASSP-34(5):1124–1138, 1986.
[Noll, 1967] A. Michael Noll. Cepstrum pitch determination.
J. Acoust. Soc. Am., 41(2):293–309, 1967.
[Ohmura, 1994] Hiroshi Ohmura. Fine pitch contour extraction by voice fundamental wave ﬁltering method. In Proc.
of ICASSP 94, pages II–189–192, 1994.
[Parsons, 1976] Thomas W. Parsons. Separation of speechfrom interfering speech by means of harmonic selection. J.
Acoust. Soc. Am., 60(4):911–918, 1976.
[Plomp, 1967] R. Plomp. Pitch of complex tones. J. Acoust.
Soc. Am., 41(6):1526–1533, 1967.
[Rabiner et al., 1976] Lawrence R. Rabiner, Michael J.
Cheng, Aaron E. Rosenberg, and Carol A. McGonegal. A
comparative performance study of several pitch detection
algorithms. IEEE Trans. on ASSP, ASSP-24(5):399–418,
1976.
[Richards, 1988] Whitman Richards, editor. Natural Computation. The MIT Press, 1988.
[Ritsma, 1967] Roelof J. Ritsma. Frequencies dominant in
the perception of the pitch of complex sounds. J. Acoust.
Soc. Am., 42(1):191–198, 1967.
[Schroeder, 1968] M. R. Schroeder.
Period histogramand product spectrum: New methods for fundamentalfrequency measurement. J. Acoust. Soc. Am., 43(4):829–
834, 1968.
[Sonoda et al., 1998] Tomonari Sonoda, Masataka Goto, andYoichi Muraoka. A WWW-based melody retrieval system.
In Proc. of Intl. Computer Music Conf., pages 349–352,
1998.
[Vetterli, 1987] Martin Vetterli. A theory of multirate ﬁlter
banks. IEEE Trans. on ASSP, ASSP-35(3):356–372, 1987.

−40 −