Speech Communication 43 (2004) 311–329
www.elsevier.com/locate/specom

A real-time music-scene-description system:
predominant-F0 estimation for detecting melody and basslines in real-world audio signals q
Masataka Goto *National Institute of Advanced Industrial Science and Technology (AIST), 1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan
Received 22 May 2002; received in revised form 9 May 2003; accepted 13 March 2004

Abstract
In this paper, we describe the concept of music scene description and address the problem of detecting melody andbass lines in real-world audio signals containing the sounds of various instruments. Most previous pitch-estimation
methods have had diﬃculty dealing with such complex music signals because these methods were designed to deal with
mixtures of only a few sounds. To enable estimation of the fundamental frequency (F0) of the melody and bass lines, we
propose a predominant-F0 estimation method called PreFEst that does not rely on the unreliable fundamental component and obtains the most predominant F0 supported by harmonics within an intentionally limited frequency range.
This method estimates the relative dominance of every possible F0 (represented as a probability density function of
the F0) by using MAP (maximum a posteriori probability) estimation and considers the F0Õs temporal continuity byusing a multiple-agent architecture. Experimental results with a set of ten music excerpts from compact-disc recordings
showed that a real-time system implementing this method was able to detect melody and bass lines about 80% of thetime these existed.
 2004 Elsevier B.V. All rights reserved.
Keywords: F0 estimation; MAP estimation; EM algorithm; Music understanding; Computational auditory scene analysis; Music
information retrieval

1. Introductionq

Supported by ‘‘Information and Human Activity’’, Precursory Research for Embryonic Science and Technology(PRESTO), Japan Science and Technology Corporation (JST).
*
Corresponding author. Tel.: +81 29 861 5898; fax: +81 29
861 3313.
E-mail address: m.goto@aist.go.jp

A typical research approach to computational
auditory scene analysis (CASA) (Bregman, 1990;
Brown, 1992; Cooke and Brown, 1993; Rosenthal
and Okuno, 1995; Okuno and Cooke, 1997;

0167-6393/$ - see front matter  2004 Elsevier B.V. All rights reserved.
doi:10.1016/j.specom.2004.07.001

312

M. Goto / Speech Communication 43 (2004) 311–329

Rosenthal and Okuno, 1998) is sound source segregation: the extraction of the audio signal corresponding to each auditory stream in a soundmixture. Human listeners can obviously understand various properties of the sound mixtures they
hear in a real-world environment and this suggeststhat they detect the existence of certain auditory
objects in sound mixtures and obtain a descriptionof them. This understanding, however, is not necessarily evidence that the human auditory system extracts the individual audio signal corresponding toeach auditory stream. This is because segregation is
not a necessary condition for understanding: even
if a mixture of two objects cannot be segregated,that the mixture includes the two objects can beunderstood from their salient features. In developing a computational model of monaural or binaural sound source segregation, we might be dealing
with a problem which is not solved by any mechanism in this world, not even by the human brain,
although sound source segregation is valuable fromthe viewpoint of engineering.
In the context of CASA, we therefore consider
it essential to build a computational model thatcan obtain a certain description of the auditory
scene from sound mixtures. To emphasize its difference from sound source segregation and restoration, we call this approach auditory scene
description. Kashino (1994) discussed the auditory
scene analysis problem from a standpoint similar
to ours by pointing out that the extraction of symbolic representation is more natural and essential
than the restoration of a target signal wave froma sound mixture; he did not, however, address
the issue of subsymbolic description which we deal
with below.
In modeling the auditory scene description, it isimportant that we discuss what constitutes anappropriate description of audio signals. An easy
way of specifying the description is to borrowthe terminology of existing discrete symbol systems, such as musical scores consisting of musicalnotes or speech transcriptions consisting of text
characters. Those symbols, however, fail to express
non-symbolic properties such as the expressivenessof a musical performance and the prosody of spontaneous speech. To take such properties into account, we need to introduce a subsymbolic

description represented as continuous quantitativevalues. At the same time, we need to choose anappropriate level of abstraction for the description, because even though descriptions such as
raw waveforms and spectra have continuous values they are too concrete. The appropriateness of
the abstraction level will depend, of course, on
the purpose of the description and on the use towhich it will be put.
The focus of this paper is on the problem ofmusic scene description––that is, auditory scene
description in music––for monaural complex
real-world audio signals such as those recordedon commercially distributed compact discs. The
audio signals are thus assumed to contain simultaneous sounds of various instruments. This
real-world-oriented approach with realistic assumptions is important to address the scaling-up problem 1 and facilitate the implementation of practicalapplications (Goto and Muraoka, 1996, 1998;
Goto, 2001).
The main contribution of this paper is to propose a predominant-F0 estimation method thatmakes it possible to detect the melody and basslines in such audio signals. On the basis of thismethod, a real-time system estimating the fundamental frequencies (F0s) of these lines has been
implemented as a subsystem of our music-scenedescription system. In the following sections, we
discuss the description used in the music-scenedescription system and the diﬃculties encounteredin detecting the melody and bass lines. We then describe the algorithm of the predominant-F0 estimation method that is a core part of our system.
Finally, we show experimental results obtainedusing our system.

2. Music-scene-description problem
Here, we explain the entire music-scene-description problem. We also explain the main diﬃculties

1
As known from the scaling-up problem (Kitano, 1993) inthe domain of artiﬁcial intelligence, it is hard to scale-up asystem whose preliminary implementation works only in laboratory (toy-world) environments with unrealistic assumptions.

M. Goto / Speech Communication 43 (2004) 311–329

in detecting the melody and bass lines––the subproblem that we deal with in this paper.

313

Musicalaudio signals
time

2.1. Problem speciﬁcation
Music scene description is deﬁned as a processthat obtains a description representing the input
musical audio signal. Since various levels of
description are possible, we must decide whichlevel is an appropriate ﬁrst step toward the ultimate description in human brains. We think thatthe music score is inadequate for this because, as
pointed out (Goto and Muraoka, 1999), an untrained listener understands music to some extent
without mentally representing audio signals asmusical scores. Music transcription, identifying
the names (symbols) of musical notes and chords,
is in fact a skill mastered only by trained musicians. We think that an appropriate description
should be:• An intuitive description that can be easily
obtained by untrained listeners.
• A basic description that trained musicians
can use as a basis for higher-level music
understanding.
• A useful description facilitating the development of various practical applications.
According to these requirements, we propose adescription (Fig. 1) consisting of ﬁve subsymbolic
representations:(1) Hierarchical beat structure
Represents the fundamental temporal structure of music and comprises the quarter-note
and measure levels––i.e., the positions ofquarter-note beats and bar-lines.
(2) Chord change possibility
Represents the possibilities of chord changes
and indicates how much change there is in
the dominant frequency components included
in chord tones and their harmonic overtones.
(3) Drum pattern
Represents temporal patterns of how two
principal drums, a bass drum and a snare
drum, are played. This representation is not
used for music without drums.

Hierarchicalbeat structure
Chord change
possibility
Drum pattern

Snare
drum
Bass
drum

Melody line
Bass lin e

Fig. 1. Description in our music-scene-description system.

(4) Melody line
Represents the temporal trajectory of the melody, which is a series of single tones and isheard more distinctly than the rest. Note that
this is not a series of musical notes; it is a continuous representation of frequency andpower transitions.
(5) Bass line
Represents the temporal trajectory of thebass, which is a series of single tones and is
the lowest part in polyphonic music. This isa continuous representation of frequency
and power transitions.
The idea behind these representations camefrom introspective observation of how untrained
listeners listen to music. A description consistingof the ﬁrst three representations and the methods
for obtaining them were described previously(Goto and Muraoka, 1994, 1996, 1998, 1999;
Goto, 1998, 2001) from the viewpoint of beattracking. 2
In this paper we deal with the last two representations, the melody line and bass line. The detection
2
Although the basic concept of music scene description is
independent of music genres, some subsymbolic representationsin Fig. 1 depend on genres in our current implementation. The
hierarchical beat structure, chord change possibility, and drum
pattern are obtained under the assumption that an input song is
popular music and its time-signature is 4/4. On the other hand,
the melody and bass lines are obtained for music, in any genre,
having single-tone melody and bass lines.

314

M. Goto / Speech Communication 43 (2004) 311–329

of the melody and bass lines is important because
the melody forms the core of Western music andis very inﬂuential in the identity of a musical pieceand the bass is closely related to the tonality. Theselines are fundamental to the perception of music byboth trained and untrained listeners. They are also
useful in various applications such as automatictranscription, automatic music indexing for information retrieval (e.g., searching for a song by singing a melody), computer participation in live
human performances, musical performance analysis
of outstanding recorded performances, and automatic production of accompaniment tracks for
Karaoke or Music Minus One using compact discs.
In short, we solve the problem of obtaining adescription of the melody line Sm(t) and the bassline Sb(t) given byS m ðtÞ ¼ fF m ðtÞ; Am ðtÞg;ð1Þ

S b ðtÞ ¼ fF b ðtÞ; Ab ðtÞg;ð2Þ

where Fi(t) (i = m, b) denotes the fundamental frequency (F0) at time t and Ai(t) denotes the power
at t.
2.2. Problems in detecting the melody and bass lines
It has been considered diﬃcult to estimate theF0 of a particular instrument or voice in the monaural audio signal of an ensemble performed bymore than three musical instruments. Most previous F0 estimation methods (Noll, 1967; Schroeder,
1968; Rabiner et al., 1976; Nehorai and Porat,
1986; Charpentier, 1986; Ohmura, 1994; Abeet al., 1996; Kawahara et al., 1999) have beenpremised upon the input audio signal containing
just a single-pitch sound with aperiodic noise.
Although several methods for dealing with multiple-pitch mixtures have been proposed (Parsons,
1976; Chafe and Jaﬀe, 1986; Katayose and Inokuchi, 1989; de Cheveigné, 1993; Brown and Cooke,
1994; Nakatani et al., 1995; Kashino and Murase,
1997; Kashino et al., 1998; de Cheveigné and
Kawahara, 1999; Tolonen and Karjalainen, 2000;
Klapuri, 2001), these required that the number ofsimultaneous sounds be assumed and had diﬃculty estimating the F0 in complex audio signals
sampled from compact discs.

The main reason F0 estimation in sound mixtures is diﬃcult is that in the time–frequency domain the frequency components of one soundoften overlap the frequency components of simultaneous sounds. In popular music, for example,
part of the voiceÕs harmonic structure is often
overlapped by harmonics of the keyboard instrument or guitar, by higher harmonics of the bass
guitar, and by noisy inharmonic frequency components of the snare drum. A simple method of
locally tracing a frequency component is therefore
neither reliable nor stable. Moreover, sophisticated F0 estimation methods relying on the existence of the F0Õs frequency component (thefrequency component corresponding to the F0)
not only cannot handle the missing fundamental,
but are also unreliable when the F0Õs frequency
component is smeared by the harmonics of simultaneous sounds.
Taking the above into account, the main problems in detecting the melody and bass lines can besummarized as:(i) How to decide which F0 belongs to the melody and bass lines in polyphonic music.
(ii) How to estimate the F0 in complex soundmixtures where the number of sound sources
is unknown.
(iii) How to select the appropriate F0 when several ambiguous F0 candidates are found.

3. Predominant-F0 estimation method: PreFEst
We propose a method called PreFEst (predominant-F0 estimation method) which makes it possible to detect the melody and bass lines inreal-world sound mixtures. In solving the above
problems, we make three assumptions:• The melody and bass sounds have a harmonic
structure. However, we do not care about theexistence of the F0Õs frequency component.
• The melody line has the most predominant(strongest) harmonic structure in middle- andhigh-frequency regions and the bass line has
the most predominant harmonic structure in a
low-frequency region.

M. Goto / Speech Communication 43 (2004) 311–329• The melody and bass lines tend to have temporally continuous trajectories: the F0 is likely tocontinue at close to the previous F0 for its duration (i.e., during a musical note).
These assumptions ﬁt a large class of music withsingle-tone melody and bass lines.
PreFEst basically estimates the F0 of the most
predominant harmonic structure within a limited
frequency range of a sound mixture. Our solutions
to the three problems mentioned above are outlined as follows: 3

dominant and stable trajectory of the F0 as
the output. For this sequential F0 tracking,we introduce a multiple-agent architecture inwhich agents track diﬀerent temporal trajectories of the F0.
While we do not intend to build a psychoacoustical model of human perception, certain psychoacoustical results may have some relevanceconcerning our strategy: Ritsma (1967) reported
that the ear uses a rather limited spectral regionin achieving 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 second and higher
harmonics rather than by the fundamental. Note,however, that those results do not directly support
our strategy since they were obtained by using thepitch of a single sound.
PreFEst consists of three components, the PreFEst-front-end for frequency analysis, the PreFEstcore to estimate the predominant F0, and thePreFEst-back-end to evaluate the temporal continuity of the F0. Fig. 2 shows an overview of
PreFEst. The PreFEst-front-end ﬁrst calculates

Audio signals

Extracting frequency components

Limiting frequency regions
BPF for melody line

BPF for bass line

Forming F0's probability density function

Agent
Salience
detector

Int

Agent

era

cti

on

Agent

Melody line

Detecting melody line

F0's probability density function

PreFEst-core PreFEst-back-end

Frequency components

Most predominant F0 trajectory3
In this paper, we do not deal with the problem of detecting
the absence (activity) of melody and bass lines. PreFEst simply
estimates the predominant F0 without discriminating between
the sound sources.

PreFEst-front-end

Instantaneous frequency calculation

Detecting bass line(i) The method intentionally limits the frequency
range to middle- and high-frequency regions
for the melody line and to a low frequency
region for the bass line, and ﬁnds the F0
whose harmonics are most predominant inthose ranges. In other words, whether theF0 is within the limited range or not, PreFEst
tries to estimate the F0 which is supported by
predominant harmonic frequency components within that range.
(ii) The method regards the observed frequency
components as a weighted mixture of all possible harmonic-structure tone models without
assuming the number of sound sources. It
estimates their weights by using the Expectation-Maximization (EM) algorithm (Dempster et al., 1977), which is an iterativetechnique for computing maximum likelihood
estimates and MAP (maximum a posteriori
probability) estimates from incomplete data.
The method then considers the maximumweight model as the most predominant harmonic structure and obtains its F0. Since theabove processing does not rely on the existence of the F0Õs frequency component, it candeal with the missing fundamental.
(iii) Because multiple F0 candidates are found in
an ambiguous situation, the method considers
their temporal continuity and selects the most315

Bass line

Fig. 2. Overview of PreFEst (predominant-F0 estimation
method).

316

M. Goto / Speech Communication 43 (2004) 311–329

signal phase, of ﬁlter-bank outputs. It uses an eﬃcient calculation method (Flanagan and Golden,1966) based on the short-time Fourier transform(STFT) whose output can be interpreted as a collection of uniform-ﬁlter outputs. When the STFT
of a signal x(t) with a window function h(t) is deﬁned as
Z 1
X ðx; tÞ ¼
xðsÞhðs  tÞejxs ds
ð3Þ

instantaneous frequencies by using multirate signal
processing techniques and extracts frequency components on the basis of an instantaneous-frequency-related measure. By using two bandpass
ﬁlters (BPFs), it limits the frequency range of thesecomponents to middle and high regions for the
melody line and to a low region for the bass line.
The PreFEst-core then forms a probability density
function (PDF) for the F0 which represents the relative dominance of every possible harmonic structure. To form the F0Õs PDF, it regards each set ofﬁltered frequency components as a weighted mixture of all possible harmonic-structure tone models
and then estimates their weights which can beinterpreted as the F0Õs PDF; the maximum-weightmodel corresponds to the most predominant harmonic structure. This estimation is carried out
using MAP estimation and the EM algorithm. Finally, in the PreFEst-back-end, multiple agents
track the temporal trajectories of promising salient
peaks in the F0Õs PDF and the output F0 is determined on the basis of the most dominant and stable trajectory.

1¼ a þ jb;ð4Þ

the instantaneous frequency k(x, t) is given by
kðx; tÞ ¼ x þa ob
 b oaotot
a2 þ b2:

ð5Þ

The PreFEst-front-end uses a multirate ﬁlter
bank to obtain adequate time and frequency resolution and extracts frequency components by using
an instantaneous-frequency-related measure. It
obtains two sets of bandpass-ﬁltered frequency
components, one for the melody line and the otherfor the bass line.

To obtain adequate time–frequency resolution
under the real-time constraint, we designed an
STFT-based multirate ﬁlter bank (Fig. 3). At eachlevel of the binary branches, the audio signal isdown-sampled by a decimator that consists of ananti-aliasing ﬁlter (an FIR lowpass ﬁlter (LPF))
and a 1/2 down-sampler. The cut-oﬀ frequency of
the LPF in each decimator is 0.45 fs, where fs isthe sampling rate at that branch. In our current
implementation, the input signal is digitized at 16bit/16 kHz and is ﬁnally down-sampled to 1 kHz.
Then the STFT, whose window size is 512 samples,is calculated at each leaf by using the Fast Fourier
Transform (FFT) while compensating for the timedelays of the diﬀerent multirate layers. Since at 16
kHz the FFT frame is shifted by 160 samples, thediscrete time step (1 frame-time) is 10 ms. This
paper uses time t for the time measured in unitsof frame-time.

3.1.1. Instantaneous frequency calculation
The PreFEst-front-end ﬁrst calculates theinstantaneous frequency (Flanagan and Golden,
1966; Boashash, 1992), the rate of change of the

3.1.2. Extracting frequency components
The extraction of frequency components isbased on the mapping from the center frequency
x of an STFT ﬁlter to the instantaneous frequency

3.1. PreFEst-front-end: forming the observed probability density functions

Audio signals

FFT
FFT
FFT
FFT

16 kHz

Decimator
2

8 kHz

Decimator

4 kHz

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

2 kHz

Decimator

3.6-7.2
kHz

1.8-3.6kHz

0.9-1.8
kHz

0.45-0.9
kHz

1kHz

Fig. 3. Structure of the multirate ﬁlter bank.

FFT

0-0.45kHz

M. Goto / Speech Communication 43 (2004) 311–329

k(x, t) of its output (Charpentier, 1986; Abe et al.,
1996; Kawahara et al., 1999). If there is a frequency component at frequency w, that frequency
is placed at the ﬁxed point of the mapping andthe instantaneous frequencies around w stayalmost constant in the mapping (Kawahara et al.,ðtÞ1999). Therefore, a set Wf of instantaneous frequencies of the frequency components can beextracted by using the equation (Abe et al., 1997)


o
ðtÞ
ðkðw; tÞ  wÞ < 0 :Wf ¼ w j kðw; tÞ  w ¼ 0;ow
ð6ÞBy calculating the power of those frequencies,ðtÞwhich is given by the STFT spectrum at Wf , wecan deﬁne the power distribution functionWðtÞp ðxÞ as(ðtÞj X ðx; tÞ j if x 2 Wf ;WðtÞð7Þ
p ðxÞ ¼0otherwise:
3.1.3. Limiting frequency regions
The frequency range is intentionally limited byusing the two BPFs whose frequency responses
are shown in Fig. 4. The BPF for the melody line
is designed so that it covers most of the dominantharmonics of typical melody lines and deemphasizes the crowded frequency region around theF0: it does not matter if the F0 is not within the
passband. The BPF for the bass line is designed
so that it covers most of the dominant harmonics
of typical bass lines and deemphasizes a frequency
region where other parts tend to become more
dominant than the bass line.
The ﬁltered frequency components can be
represented as BPF i ðxÞW0ðtÞ
p ðxÞ, where BPFi(x)(i = m,b) is the BPFÕs frequency response for the
melody line (i = m) and the bass line (i = b), andBPF for detecting bass line

317

x is the log-scale frequency denoted in units ofcents (a musical-interval measurement). Frequency
fHz in Hertz is converted to frequency fcent in cents
as follows:
fcent ¼ 1200log2

fHz
440

3

2125

ð8Þ

:

There are 100 cents to a tempered semitone and1200 to an octave. The power distribution
ðtÞ
W0ðtÞ
p ðxÞ is the same as Wp ðxÞ except that the frequency unit is the cent.
To enable the application of statistical methods,
we represent each of the bandpass-ﬁltered frequency components as a probability density funcðtÞ
tion (PDF), called an observed PDF, pW ðxÞ:ðtÞpW ðxÞ ¼ R 1

BPF i ðxÞW0ðtÞ
p ðxÞ

1

BPF i ðxÞW0ðtÞ
p ðxÞdx:

ð9Þ

3.2. PreFEst-core: estimating the F0Õs probability
density function
For each set of ﬁltered frequency componentsðtÞ
represented as an observed PDF pW ðxÞ, the PreFEst-core forms a probability density function ofðtÞthe F0, called the F0Õs PDF, pF0 ðF Þ, where F isthe log-scale frequency in cents. We consider eachobserved PDF to have been generated from aweighted-mixture model of the tone models of all
the possible F0s; a tone model is the PDF corresponding to a typical harmonic structure and indicates where the harmonics of the F0 tend to occur.
Because the weights of tone models represent therelative dominance of every possible harmonic
structure, we can regard these weights as the F0Õs
PDF: the more dominant a tone model is in the
mixture, the higher the probability of the F0 of
its model.

BPF for detecting melody line

1

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

Fig. 4. Frequency responses of bandpass ﬁlters (BPFs).

318

M. Goto / Speech Communication 43 (2004) 311–329

Table 1
List of symbols
SymbolDescription

t
x
i
ðtÞ
pW ðxÞFp(xjF, m, l(t)(F, m))l(t)(F, m)c(t)(hjF, m)Mi
Hi
Wip(xjh(t))h(t)w(t)(F, m)Fli, FhiðtÞ
pF0 ðF Þ
p0i(h(t))
p0i(w(t))
p0i(l(t))

Time
Log-scale frequency in centsThe melody line (i = m) or the bass line (i = b)
Observed PDF (bandpass-ﬁltered frequency components) (Eq. (9))
Fundamental frequency (F0) in cents
PDF of the mth tone model for each F0 F (Eq. (10))
Shape of tone model (l(t)(F, m) = {c(t)(hjF, m)}) (Eq. (12))
Relative amplitude of the hth harmonic component (shape of tone model)
The number of tone models
The number of harmonic components for tone modelStandard deviation of the Gaussian distribution for harmonic components
Weighted-mixture model (weighted mixture of tone models) (Eq. (15))
Model parameter of p(xjh(t)) (Eq. (16))
Weight of tone model p(xjF, m, l(t)(F, m))Lower and upper limits of the possible (allowable) F0 range
F0Õs PDF (Eq. (20))
Prior distribution of the model parameter h(t) (Eq. (21))
Prior distribution of the weight of tone model (Eq. (22))
Prior distribution of the tone-model shapes (Eq. (23))ðtÞ

w0i ðF ; mÞMost probable parameter of w(t)(F, m) (for p0i(w(t)))ðtÞðtÞl0i ðF ; mÞ ðc0i ðh j F ; mÞÞ
ðtÞ
bwi
ðtÞ
bli ðF ; mÞ0 (t)0 (t) 0 (t)Most probable parameter of l(t)(F, m) (for p0i(l(t)))ðtÞParameter determining how much emphasis is put on w0i

ðtÞParameter determining how much emphasis is put on l0i ðF ; mÞh = {w , l }hðtÞ ¼ fwðtÞ ; lðtÞ g

Old parameter estimate for each iteration of the EM algorithm
New parameter estimate for each iteration of the EM algorithm

The main symbols used in this section are listed
in Table 1.
3.2.1. Weighted mixture of adaptive tone models
To deal with diversity of the harmonic structure, the PreFEst-core can use several types ofharmonic-structure tone models. The PDF ofthe mth tone model for each F0 F is denoted byp(x j F, m, l(t)(F, m)) (Fig. 5), where the model
parameter l(t)(F, m) represents the shape of thetone model. The number of tone models is Mi
Tone Model (m=2)
p(x | F,2,µ(t)(F,2))p(x,1 | F,2,µ(t)(F,2))c(t)(1|F,2)c(t)(2|F,2)

Tone Model (m=1)
p(x | F,1,µ(t)(F,1))c(t)(3|F,2)(t)c (1|F,1)
F(t)c (3|F,1)c(t)(4|F,1)
F+1902
F+2400pðx j F ; m; lðtÞ ðF ; mÞÞ ¼

Hi
X

p

h¼1

ðx; h j F ; m; lðtÞ ðF ; mÞÞ;ð10Þ

pðx; h j F ; m; lðtÞ ðF ; mÞÞ ¼ cðtÞ ðh j F ; mÞGðx; F
þ 1200log2 h; Wi Þ;

ð11ÞlðtÞ ðF ; mÞ ¼ fcðtÞ ðh j F ; mÞ j h ¼ 1; . . . ; Hi g;"#
1
ðx  x0 Þ2Gðx; x0 ; rÞ ¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ exp 
;
2r2
2pr2

ð12Þ
ð13Þ

c(t)(4|F,2)c(t)(2|F,1)
fundamental
frequency F+1200(1 6 m 6 Mi) where i denotes the melody line
(i = m) or the bass line (i = b). Each tone model
is deﬁned byx [cent]x [cent]

Fig. 5. Model parameters of multiple adaptive tone models.

where Hi is the number of harmonics considered,
Wi is the standard deviation r of the Gaussian distribution G(x; x0, r), and c(t)(hjF, m) determines therelative amplitude of the hth harmonic component(the shape of the tone model) and satisﬁes

M. Goto / Speech Communication 43 (2004) 311–329
HiXcðtÞ ðh j F ; mÞ ¼ 1:

ð14Þ

h¼1

In short, this tone model places a weighted
Gaussian distribution at the position of each harmonic component. 4
ðtÞWe then consider the observed PDF pW ðxÞ tohave been generated from the following modelp(xjh(t)), which is a weighted mixture of all possible
tone models p(xjF, m, l(t)(F, m)):Z Fhi XMiðtÞwðtÞ ðF ; mÞpðx j h Þ ¼
Fli

m¼1
ðtÞ

pðx j F ; m; l ðF ; mÞÞdF ;hðtÞ ¼ fwðtÞ ; lðtÞ g;
ðtÞ

w

ðtÞ

¼ fw ðF ; mÞ j Fli 6 F 6 Fhi ;m ¼ 1; . . . ; Mi g;

ð17ÞlðtÞ ¼ flðtÞ ðF ; mÞ j Fli 6 F 6 Fhi ;m ¼ 1; . . . ; Mi g;

ð18Þ

where Fli and Fhi denote the lower and upper limits of the possible (allowable) F0 range andw(t)(F, m) is the weight of a tone modelp(xjF, m, l(t)(F, m)) that satisﬁes
Z Fhi X
MiwðtÞ ðF ; mÞdF ¼ 1:
ð19Þ
Fli

m¼1

Because we cannot know a priori the number ofsound sources in real-world audio signals, it isimportant that we simultaneously take into consideration all F0 possibilities as expressed in Eq.
(15). If we can estimate the model parameter h(t)ðtÞsuch that the observed PDF pW ðxÞ is likely to havebeen generated from the model p(xjh(t)), the weightw(t)(F, m) can be interpreted as the F0Õs PDFðtÞ
pF0 ðF Þ:ðtÞ

pF0 ðF Þ ¼

MiXwðtÞ ðF ; mÞðFli 6 F 6 Fhi Þ:

3.2.2. Introducing a prior distribution
To use prior knowledge about F0 estimates andthe tone-model shapes, we deﬁne a prior distribution p0i(h(t)) of h(t) as follows:
p0i ðhðtÞ Þ ¼ p0i ðwðtÞ Þp0i ðlðtÞ Þ;
h
i
1
ðtÞ
ðtÞ
exp bwi
Dw ðw0i ; wðtÞ Þ ;
Zw
" Z
Mi
Fhi X
1
ðtÞ
p0i ðl Þ ¼
exp 
bðtÞ
li ðF ; mÞ
Zl
Fli
m¼1
#
p0i ðwðtÞ Þ ¼

ðtÞ

ð15Þ
ð16Þ

ð20Þ

m¼1

319

Dl ðl0i ðF ; mÞ; lðtÞ ðF ; mÞÞdF :

ð21Þ
ð22Þ

ð23Þ

Here p0i(w(t)) and p0i(l(t)) are unimodal distributions: p0i(w(t)) takes its maximum value atðtÞ
w0i ðF ; mÞ and p0i(l(t)) takes its maximum value
ðtÞ
ðtÞ
ðtÞ
at l0i ðF ; mÞ, where w0i ðF ; mÞ and l0i ðF ; mÞðtÞðc0i ðh j F ; mÞÞ are the most probable parameters.
Zw and Zl are normalization factors, and bðtÞwi
and bðtÞ
li ðF ; mÞ are parameters determining how
much emphasis is put on the maximum value.
The prior distribution is not informative (i.e., itðtÞ
is uniform) when bðtÞwi and bli ðF ; mÞ are 0, corresponding to the case when no prior knowledge isðtÞavailable. In Eqs. (22) and (23), Dw ðw0i ; wðtÞ Þ andðtÞ
Dl ðl0i ðF ; mÞ; lðtÞ ðF ; mÞÞ are the following Kullback–Leibler information: 5
Z Fhi XMiðtÞðtÞ
Dw ðw0i ; wðtÞ Þ ¼
w0i ðF ; mÞ
Fli

m¼1
ðtÞ

log

w0i ðF ; mÞdF ;wðtÞ ðF ; mÞ

ð24Þ

ðtÞ

Dl ðl0i ðF ; mÞ; lðtÞ ðF ; mÞÞ
¼

ðtÞ
Hi
X
c ðh j F ; mÞðtÞ:c0i ðh j F ; mÞ log 0icðtÞ ðh j F ; mÞ
h¼1
ðtÞ

ð25Þ
ðtÞ

Dw ðw0i ; wðtÞ Þ represents the closeness between w0i
ðtÞand w(t) and Dl ðl0i ðF ; mÞ; lðtÞ ðF ; mÞÞ representsðtÞ
the closeness between l0i ðF ; mÞ and l(t)(F, m).

4

Although we deal with only harmonic-structure tonemodels in this paper, we can also support inharmonic-structure
tone models as discussed later.

5
We use Eqs. (24) and (25) because they are intuitive andare also convenient in the derivations that follow.

320

M. Goto / Speech Communication 43 (2004) 311–329

3.2.3. MAP estimation using the EM algorithm
The problem to be solved is to estimate themodel parameter h(t), taking into account the priorðtÞdistribution p0i(h(t)), when we observe pW ðxÞ. The
MAP (maximum a posteriori probability) estimator of h(t) is obtained by maximizing
Z 1

ðtÞ

pW ðxÞðlog pðx j hðtÞ Þ þ log p0i ðhðtÞ ÞÞdx:

ð26Þ

1

Because this maximization problem is too diﬃcult to solve analytically, we use the EM (Expectation-Maximization) algorithm to estimate h(t).
While the EM algorithm is usually used for computing maximum likelihood estimates from incomplete observed data, it can also be used forcomputing MAP estimates as described in (Dempster et al., 1977). In the maximum likelihood estimation, the EM algorithm iteratively applies two
steps, the expectation step (E-step) to computethe conditional expectation of the mean log-likelihood and the maximization step (M-step) to maximize its expectation. On the other hand, in the
MAP estimation, the algorithm iteratively applies
the E-step to compute the sum of the conditional
expectation and the log prior distribution and
the M-step to maximize it. With respect to h(t),each iteration updates the old estimate h 0 (t) ={w 0 (t), l 0 (t)} to obtain the new (improved) estimateðtÞ¼ fwðtÞ ; lðtÞ g. For each frame t, w 0 (t) is initial-hized with the ﬁnal estimate wðt1Þ after iterations
at the previous frame t  1; l 0 (t) is initialized withðtÞthe most probable parameter l0i in our current
implementation.
By introducing the hidden (unobservable) variables F, m, and h, which, respectively, describe
which F0, which tone model, and which harmoniccomponent were responsible for generating eachobserved frequency component at x, we can specify the two steps as follows:QðhðtÞ j h0ðtÞ Þ
Z 1
ðtÞ
¼
pW ðxÞEF ;m;h ½log pðx;F ;m;h j hðtÞ Þ j x;h0ðtÞ dx;
1

ð28Þ
where Q(h(t)jh 0 (t)) is the conditional expectation of
the mean log-likelihood for the maximum likelihood estimation. EF,m,h[ajb] denotes the conditional expectation of a with respect to the hidden
variables F, m, and h with the probability distribution determined by condition b.
(2) (M-step)
Maximize QMAP(h(t)jh 0 (t)) as a function of h(t) toobtain the updated (improved) estimate hðtÞ :hðtÞ ¼ argmax QMAP ðhðtÞ j h0ðtÞ Þ:

ð29Þ

hðtÞ

In the E-step, Q(h(t)jh 0 (t)) is expressed asQðhðtÞ j h0ðtÞ Þ ¼

Z 1 Z Fhi X
Mi X
Hi
1

Fli

ðtÞ

pW ðxÞpðF ; m; h j x; h0ðtÞ Þ

m¼1 h¼1

log pðx; F ; m; h j hðtÞ ÞdF dx;

ð30Þ

where the complete-data log-likelihood is given bylog pðx; F ; m; h j hðtÞ Þ¼ logðwðtÞ ðF ; mÞpðx; h j F ; m; lðtÞ ðF ; mÞÞÞ:ð31Þ

From Eq. (21), the log prior distribution is givenbylog p0i ðhðtÞ Þ
Z Fhi XMiðtÞ

w0i ðF ;mÞ
wðtÞ ðF ;mÞ
Fli
m¼1
!
ðtÞ
Hi
X
c0i ðh j F ;mÞðtÞðtÞc0i ðh j F ; mÞ log ðtÞþbli ðF ;mÞ
dF :c ðh j F ;mÞ
h¼1¼  log Z w Z l 

ðtÞ

ðtÞ

bwi w0i ðF ;mÞ log

ð32Þ(1) (E-step)Compute the following QMAP(h(t)jh 0 (t)) for the
MAP estimation:
QMAP ðhðtÞ j h0ðtÞ Þ ¼ QðhðtÞ j h0ðtÞ Þ þ log p0i ðhðtÞ Þ;
ð27Þ

Regarding the M-step, Eq. (29) is a conditional
problem of variation, where the conditions are
given by Eqs. (14) and (19). This problem can besolved by using the following Euler-Lagrange differential equations with Lagrange multipliers kw
and kl:M. Goto / Speech Communication 43 (2004) 311–329

Z 1X
Hi

o
owðtÞ

ðtÞ

pW ðxÞpðF ;m;h j x; h0ðtÞ Þðlog wðtÞ ðF ;mÞ

pðF ; m j x; h0ðtÞ Þ1 h¼1¼

w0ðtÞ ðF ; mÞpðx j F ; m; l0ðtÞ ðF ; mÞÞpðx j h0ðtÞ ÞðtÞþ log pðx;h j F ; m;l ðF ;mÞÞÞdx


kw
o
ocðtÞ

w0i ðF ;mÞ
wðtÞ ðF ;mÞ

1w ðF ; mÞ 
Mi ðFhi  Fli Þ
ðtÞ

Z 1

!

ðtÞ

¼ 0;

ð33Þ

ðtÞ
pW ðxÞpðF ; m; h j x; h0ðtÞ Þðlog wðtÞ ðF ; mÞ1wðtÞ ðF ; mÞ ¼ðtÞwML ðF ; mÞ þ bðtÞwi w0i ðF ; mÞ1 þ bðtÞ
wi

ðtÞ

ðtÞ

ðtÞ

ðtÞ

wML ðF ;mÞ þ bðtÞli ðF ;mÞ1
kl cðtÞ ðh j F ; mÞ 
¼ 0:
Hi

ðtÞ
ðtÞ
wML ðF ; mÞ and cML ðh j F ; mÞ

ð34Þ



þbðtÞ
wi w0i ðF ; mÞ ;

ðtÞ

m¼1

ð43Þ



:

ðtÞ

cML ðh j F ;mÞ ¼

kw ¼ 1 þ bðtÞ
wi ;
kl ¼

ðtÞ

pW ðxÞpðF ; m j x; h0ðtÞ Þdx

1þ bðtÞ
li ðF ; mÞ:ð38Þ

According to BayesÕ theorem, p(F, m, hjx, h 0 (t)) andp(F, mjx, h 0 (t)) are given bypðF ; m; h j x; h0ðtÞ Þ¼

w0ðtÞ ðF ; mÞpðx; h j F ; m; l0ðtÞ ðF ; mÞÞpðx j h0ðtÞ Þ

;

ð39Þ

ðtÞ
wML ðF ;mÞ

ðtÞ

pW ðxÞ

1w ðF ;mÞpðx;h j F ;m;l0ðtÞ ðF ;mÞÞdx:
MiR Fhi P
0ðtÞ ðg;mÞpðx j g;m;l0ðtÞ ðF ;mÞÞdg
w
Fli

ð36Þ

ð37Þ

Z 1

1
0ðtÞ

In these equations, kw and kl are determined from
Eqs. (14) and (19) as

Z 1

ðtÞ

pW ðxÞ

w0ðtÞ ðF ; mÞpðx j F ; m; l0ðtÞ ðF ; mÞÞdx;
MiR Fhi P
0ðtÞ ðg; mÞpðx j g; m; l0ðtÞ ðF ; mÞÞdg
w
Fli

ð35Þ

ðtÞ

ðtÞ
þbðtÞ
li ðF ; mÞc0i ðh j F ; mÞZ 1
1pW ðxÞpðF ; m; h j x; h0ðtÞ Þdx

1

where
are, when anon-informative prior distribution (bðtÞwi ¼ 0 and
bðtÞ
ðF
;
mÞ
¼
0)
is
given,
thefollowing
maximumlilikelihood estimates:wML ðF ; mÞ ¼

From these equations we get
Z 1
1
ðtÞ
pW ðxÞpðF ; m j x; h0ðtÞ ÞdxwðtÞ ðF ; mÞ ¼
kw
1

1
kl

;

ð42Þ

ðtÞ
c0i ðh j F ; mÞ
ðtÞ
bðtÞ
ðF
;
mÞc
ðh
j
F
;
mÞ
log
0i
li
cðtÞ ðh j F ; mÞcðtÞ ðh j F ; mÞ ¼

ð41Þ

ðtÞ
wML ðF ;mÞcML ðh j F ;mÞ þ bli
ðF ; mÞc0i ðh j F ; mÞþ1200log2 h; Wi ÞÞdx

Z 1

;

cðtÞ ðh j F ;mÞ
¼

þ log cðtÞ ðh j F ; mÞ þ log Gðx; F

ðtÞ

ð40Þ

:

Finally, we obtain the new parameter estimateswðtÞ ðF ; mÞ and cðtÞ ðhjF ; mÞ:

ðtÞ

ðtÞ

bðtÞ
wi w0i ðF ;mÞ log

321

m¼1

ð44Þ
For an intuitive explanation of Eq. (43), we callw0ðtÞ ðF ; mÞpðx j F ; m; l0ðtÞ ðF ; mÞÞMi
R Fhi P
w0ðtÞ ðg; mÞpðx j g; m; l0ðtÞ ðF ; mÞÞdg
Fli
m¼1

the decomposition ﬁlter. For the integrand on theright-hand side of Eq. (43), we can consider that,ðtÞ
by this ﬁlter, the value of pW ðxÞ at frequency x is
decomposed into (is distributed among) all possible
tone models p(xjF, m, l 0 (t)(F, m)) (Fli 6 F 6 Fhi,
1 6 m 6 Mi) in proportion to the numerator ofthe decomposition ﬁlter at x. The higher the weight322

M. Goto / Speech Communication 43 (2004) 311–329

w 0 (t)(F, m), the larger the decomposed value given
to the corresponding tone model. Note that theðtÞvalue of pW ðxÞ at diﬀerent x is also decomposed
according to a diﬀerent ratio in proportion to thenumerator of the decomposition ﬁlter at that x. FiðtÞ
nally, the updated weight wML ðF ; mÞ is obtained byintegrating all the decomposed values given to thecorresponding mth tone model for the F0 F.
We think that this decomposition behavior is theadvantage of PreFEst in comparison to previous
comb-ﬁlter-based or autocorrelation-based methods (de Cheveigné, 1993; de Cheveigné and Kawahara, 1999; Tolonen and Karjalainen, 2000). Thisis because those previous methods cannot easily
support the decomposition of an overlapping frequency component (overtone) shared by several
simultaneous tones and tend to have diﬃculty distinguishing sounds with overlapping overtones. In
addition, PreFEst can simultaneously estimate allðtÞ
the weights wML ðF ; mÞ (for all the range of F) so thatthese weights can be optimally balanced: it does notdetermine the weight at F after determining theweight at another F. We think this simultaneous
estimation of all the weights is an advantage of PreFEst compared to previous recursive-subtractionbased methods (de Cheveigné, 1993; Klapuri,2001) where components of the most dominant harmonic structure identiﬁed are subtracted from a
mixture and then this is recursively done again starting from the residue of the previous subtraction. In
those methods, once inappropriate identiﬁcation or
subtraction occurs, the following recursions startingfrom the wrong residue become unreliable.
After the above iterative computation of Eqs.
ðtÞ(41)–(44), the F0Õs PDF pF0 ðF Þ estimated by considering the prior distribution can be obtained fromw(t)(F, m) according to Eq. (20). We can also obtainthe tone-model shape c(t)(hjF, m), which is the relative amplitude of each harmonic component of all
types of tone models p(xjF, m, l(t)(F, m)).
A simple way to determine the frequency Fi(t)of the most predominant F0 is to ﬁnd the freðtÞ
quency that maximizes the F0Õs PDF pF0 ðF Þ:ðtÞF i ðtÞ ¼ argmax pF0 ðF Þ:

ð45Þ

F

This result is not always stable, however, because
peaks corresponding to the F0s of simultaneous

tones sometimes compete in the F0Õs PDF for a
moment and are transiently selected, one after another, as the maximum of the F0Õs PDF. Therefore, we have to consider the global temporalcontinuity of the F0 peak. This is addressed in
the next section.
3.3. PreFEst-back-end: sequential F0 tracking witha multiple-agent architecture
The PreFEst-back-end sequentially tracks peak
trajectories in the temporal transition of the F0ÕsPDF to select the most dominant and stable F0
trajectory from the viewpoint of global F0 estimation. 6 To make this possible, we introduced amultiple-agent architecture that enables dynamic
and ﬂexible control of the tracking process. In an
earlier multiple-agent architecture (Goto and Muraoka, 1996) the number of agents was ﬁxed during
the processing. In contrast, our new architecture
generates and terminates agents dynamically byusing a mechanism similar to one in the residuedriven architecture (Nakatani et al., 1995).
Our architecture consists of a salience detector
and multiple agents (Fig. 6). The salience detector
picks up promising salient peaks in the F0Õs PDF,
and the agents driven by those peaks track theirtrajectories. They behave at each frame as follows(the ﬁrst three steps correspond to the numbers in
Fig. 6):(1) After forming the F0Õs PDF at each frame, thesalience detector picks out several salient
peaks that are higher than a dynamic threshold that is adjusted according to the maximum peak. The detector then evaluates how
promising each salient peak is by tracking
its trajectory in the near future (at most 50ms) taking into consideration the total powertransition. For the real-time implementation,
this can be done by regarding the present timeas the near-future time.
6

Because the F0Õs PDF is obtained without needing toassume the number of sounds contained, our method can, byusing an appropriate sound-source discrimination method, be
extended to the problem of tracking multiple simultaneous
sounds.

M. Goto / Speech Communication 43 (2004) 311–329(2) selective allocation(1) Salienceoragent generation

detector

Agent Interaction Agent

F0's PDF

track Agent
track(3) killedetimfrequencyFig. 6. Sequential F0 tracking with the multiple-agent
architecture.

(2) If there are generated agents, they interact to
exclusively allocate the salient peaks to agentsaccording to the criterion of peak closenessbetween the peak frequency and the agenttracking frequency. If more than one agent
claims the same peak, the peak is allocatedto the most reliable agent. If the most salient
peak has not been allocated, a new agent for
tracking its peak is generated.
(3) Each agent has an accumulated penalty. The
penalty of an agent to which a salient peakhas been allocated is reset. An agent to whicha salient peak has not been allocated is penalized a certain value and the agent tries to ﬁnd
its next peak in the F0Õs PDF directly. Whenthe agent cannot ﬁnd the peak even in the
F0Õs PDF, it is further penalized a certain
value. An agent whose accumulated penalty
exceeds a certain threshold is terminated.
(4) Each agent evaluates its own reliability byusing the reliability at the previous frame
and the degree of the peakÕs salience at thecurrent frame.
(5) The output F0 Fi(t) is determined on the basisof which agent has the highest reliability andgreatest total power along the trajectory of
the peak it is tracking. The power Ai(t) is
obtained as the total power of the harmonics
of the F0 Fi(t).

4. System implementation
PreFEst has been implemented in a real-timesystem that takes a musical audio signal as input

323

and 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 audio-synchronizedgraphics output (Fig. 7) shows a window representing the scrolling F0 trajectories on a time–frequency plane (Fig. 7(b)), and adjacent interlocking
windows representing the frequency components(Fig. 7(a)) and the F0Õs PDF for the melody andbass lines (Fig. 7(c) and (d)). The output audio signals are generated by sinusoidal synthesis on thebasis of the harmonics tracked along the estimatedF0.
Our current implementation for experiments
uses two adaptive tone models with the parametervalues listed in Table 2. Since we cannot assume
perfect harmonicity in real-world audio signals,
the standard deviation of the Gaussian distribution, Wm and Wb, is eﬀective to take care of any
inharmonicity of the harmonic components andits value was set according to psychoacousticalexperiments (Kashino and Tanaka, 1994) on theauditory segregation of sounds with a mistuned
harmonic. For the prior distribution of the tonemodel shapes l(t), we useðtÞ

c0i ðh j F ; mÞ ¼ ai;m gm;h Gðh; 1; Ui Þ;

ð46Þ

where m is 1 or 2, ai,m is a normalization factor,
gm,h is 2/3 (when m = 2 and h is even) or 1 (otherwise), Um = 5.5, and Ub = 2.7. Fig. 8 shows thesetone-model shapes which are invariable for all F0
ranges and for all the time. We did not use theprior distribution of w(t) (prior knowledge regarding rough F0 estimates). For the parameters bðtÞwi
and bðtÞ
li ðF ; mÞ, we usebðtÞ
wi ¼ 0;" 
2 , #
F

Fl
i
bðtÞ
0:2 ;
li ðF ; mÞ ¼ Bi exp 
Fhi  Fli

ð47Þ
ð48Þ

where Bm = 15 and Bb = 10.
The system has been implemented using a distributed-processing technique so that diﬀerent system functions––such as audio input and output (I/O), main calculation, and intermediate-state andoutput visualization––are performed by diﬀerent

324

M. Goto / Speech Communication 43 (2004) 311–329

Fig. 7. Scrolling-window snapshots for a popular-music excerpt with drum sounds: (a) frequency components, (b) the corresponding
melody and bass lines detected (ﬁnal output), (c) the corresponding F0Õs PDF estimated when detecting the melody line, and (d) the
corresponding F0Õs PDF estimated when detecting the bass line. These interlocking windows have the same vertical axis of log-scalefrequency.

Table 2
Parameter values
Fhm = 8400 cent (2093 Hz)
Flm = 3600 cent (130.8 Hz)
Mm = 2
Hm = 16
Wm = 17 cent

Fhb = 4800 cent (261.6 Hz)
Flb = 1000 cent (29.14 Hz)
Mb = 2
Hb = 6
Wb = 17 centprocesses distributed over a LAN (Ethernet). To
facilitate system expansion and application devel-

opment, those processes were 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 et al., 1997). The main signal
processing was done on a workstation with two
Alpha21264 750-MHz CPUs (Linux 2.2), and theaudio I/O and visualization processing was doneon a workstation, the SGI Octane, with two
R12000 300-MHz CPUs (Irix 6.5).

M. Goto / Speech Communication 43 (2004) 311–329
x 10

4

–3

4

3

3

2

2

1

1

0

4000

5000

(a)

8

x 10

6000
7000
frequency [cent]

8000

9000

0

–3

8
6

4

4

2

2

2000

(c)

2500

3000

3500 4000 4500
frequency [cent]

–3

4000

5000

(b)

6

0

x 10

5000

5500

6000

0

325

x 10

6000
7000
frequency [cent]

8000

3500 4000 4500
frequency [cent]

5000

9000

–3

2000

(d)

2500

3000

5500

6000

ðtÞ

Fig. 8. Prior distribution of the tone-model shapes pðx j F ; m; l0i ðF ; mÞÞ in our experiments: (a) for melody line (i = m, m = 1, F = 4000
cent), (b) for melody line (i = m, m = 2, F = 4000 cent), (c) for base line (i = b, m = 1, F = 2000 cent), (d) for base line (i = b, m = 2,
F = 2000 cent).

5. Experimental results
The system was tested on excerpts from 10
musical pieces in the popular, jazz, and orchestralgenres (Table 3). The 20-s-long input monaural
audio signals––each containing a single-tone mel-ody and the sounds of several instruments––weresampled from compact discs. We evaluated thedetection rates by comparing the estimated F0s
with the correct F0s that were hand-labeled using
an F0 editor program we developed. This F0 editor program enables a user to determine, at each

Table 3Detection rates for the melody and bass lines
Title

Genre

Detection rates [%]MelodyBass

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 Con. in D, Op. 35 (Tchaikovsky)

PopularPopularPopularPopularPopularPopular
Jazz
Jazz
Jazz
Classical

90.8
76.6
94.2
91.6
90.1
91.7
95.3
82.2
92.9
78.7

91.2
87.3
85.4
73.1
76.4
72.1
65.8
82.0
80.8
84.8

88.4

79.9

Average326

M. Goto / Speech Communication 43 (2004) 311–329

frame, the correct F0 values of the melody andbass lines while listening to the audio playbackof the original as well as the harmonic structureof the currently labeled F0 while also watching
their frequency components. If the F0 error (frequency diﬀerence) of a frame was less than 50
cents, the estimated F0 at that frame was judged
to be correct.
The detection rates thus obtained are listed inTable 3. The system correctly detected, for mostparts of each audio sample, the melody lines provided by a voice or a single-tone mid-range instrument and the bass lines provided by a bass guitar
or a contrabass: the average detection rate was
88.4% for the melody line and 79.9% for the bass
line. In the absence of a melody or bass line, thesystem detected the F0 of a dominant accompaniment part because the method simply estimates the
predominant F0 trajectory every moment and does
not distinguish between the sound sources. The
evaluation was therefore made during periods
when a hand-labeled melody or bass line waspresent.
Typical errors were half-F0 or double-F0 errors, errors where the detected line switched fromthe target part to another obbligato part for awhile even as the previously tracked target partcontinued, and errors where a short-term trajectory near the onset of the target part was missing
because of switching delay from another part tothe target part. These errors were essentially due
to the absence of a source-discrimination mechanism for selecting just the target part from among
several simultaneous streams on the basis of soundsource consistency; we plan to address this issue ina future implementation.

6. Discussion
PreFEst has great potential that we have yet to
fully exploit. We discuss its future prospects withrespect to the following points.
• Incorporating prior knowledge about the tonemodel shapes
While simple tone models (Fig. 8) were used forthe prior distribution and were eﬀective enoughas shown by the experimental results, PreFEst
allows the use of richer tone models. Many different tone models, for example, could be prepared by analyzing various kinds of harmonic
structure that appear in music. Future work will
also include the use of machine learning techniques to learn these tone models.
• Using more general (inharmonic structure) tonemodelsAlthough we deal with only harmonic-structure
tone models in this paper, PreFEst can be applied to any weighted mixture of arbitrary tonemodels (even if their components are inharmonic) by simply replacing Eq. (11) with
pðx; h j F ; m; lðtÞ ðF ; mÞÞ¼ cðtÞ ðh j F ; mÞparbitrary ðx; F ; h; mÞ;

ð49Þ

where parbitrary(x; F, h, m) is an arbitrary PDF (his merely the component number in this case).
Even with this general tone model, in theory
we can estimate the F0Õs PDF by using the same
Eqs. (41)–(44). Both the harmonic-structure
tone models (Eq. (11)) and any inharmonicstructure tone models (Eq. (49)) can also be
used together.
• Modeling attacks of sounds, consonants, anddrum sounds
By introducing F0-independent tone models
having arbitrary PDFs in addition to Eq. (49),
we can extend PreFEst to deal with various
F0-independent inharmonic-structure sounds––
such as attacks of musical-instrument sounds,
consonants in the singing voice, and drumsounds––that real-world sound mixtures usuallycontain. In our current implementation with
only harmonic-structure tone models, the estimated F0Õs PDF is sometimes smeared at theframes with such short sounds. Future work will
include the modeling and detection of theseinharmonic-structure sounds to more precisely
estimate the F0Õs PDF and obtain a richer
description using the detection results.
• Incorporating prior knowledge regarding roughF0 estimates of the melody and bass lines
Although prior knowledge about rough F0 estimates can be incorporated into the estimation,
it was not used in our experiments. This will

M. Goto / Speech Communication 43 (2004) 311–329

be useful for some practical applications, suchas the analysis of expression in a recorded performance, where a more precise F0 with fewer
errors is required.
• Tracking multiple sound sources with soundsource identiﬁcation
Although multiple peaks in the F0Õs PDF, eachcorresponding to a diﬀerent sound source, aretracked by multiple agents in the PreFEstback-end, we did not fully exploit them. If they
could be tracked while considering their soundsource consistency by using a sound source
identiﬁcation method, we can investigate othersimultaneous sound sources as well as the melody and bass lines. A study of integrating asound source identiﬁcation method with tonemodel shapes in PreFEst will be necessary.

327

rithm, a probability density function of the F0
which represents the relative dominance of every
possible harmonic structure. This approach naturally does not require the existence of the F0Õs frequency component and can handle the missing
fundamental that often occurs in musical audio
signals. In addition, the multiple-agent architecture makes it possible to determine the most dominant and stable F0 trajectory from the viewpointof global temporal continuity of the F0.
In the future, we plan to work on the various
extensions discussed in Section 6. While PreFEst
was developed for music audio signals, it––especially the PreFEst-core––can also be applied to
non-music audio signals. In fact, Masuda-Katsuse(Masuda-Katsuse, 2001; Masuda-Katsuse andSugano, 2001) has extended it and demonstrated
its eﬀectiveness for speech recognition in realistic
noisy environments.

7. Conclusion
We have described the problem of musicscene description––auditory scene description inmusic––and have addressed the problems regarding the detection of the melody and bass lines incomplex real-world audio signals. The predominant-F0 estimation method PreFEst makes it possible to detect these lines by estimating the most
predominant F0 trajectory. Experimental results
showed that our system implementing PreFEst
can estimate, in real time, the predominant F0sof the melody and bass lines in audio signals sampled from compact discs.
Our research shows that the pitch-related properties of real-world musical audio signals––like themelody and bass lines––as well as temporal properties like the hierarchical beat structure, can be
described without segregating sound sources. Taking a hint from the observation that human listeners can easily listen to the melody and bass lines,
we developed PreFEst to detect these lines separately by using only partial information within
intentionally limited frequency ranges. Because itis generally impossible to know a priori the number of sound sources in a real-world environment,
PreFEst considers all possibilities of the F0 at thesame time and estimates, by using the EM algo-

Acknowledgments
I thank Shotaro Akaho and Hideki Asoh (National Institute of Advanced Industrial Scienceand Technology) for their valuable discussions. I
also thank the anonymous reviewers for their helpful comments and suggestions.

References
Abe, T., Kobayashi, T., Imai, S., 1996. Robust pitch estimation
with harmonics enhancement in noisy environments basedon instantaneous frequency. In: Proc. Internat. Conf. on
Spoken Language Processing (ICSLP 96), pp. 1277–1280.
Abe, T., Kobayashi, T., Imai, S., 1997. The IF spectrogram: a
new spectral representation. In: Proc. Internat. Sympos. on
Simulation, Visualization and Auralization for Acoustic
Research and Education (ASVA 97), pp. 423–430.
Boashash, B., 1992. Estimating and interpreting the instantaneous frequency of a signal. Proc. IEEE 80 (4), 520–568.
Bregman, A.S., 1990. Auditory Scene Analysis: The Perceptual
Organization of Sound. The MIT Press.
Brown, G.J., 1992. Computational auditory scene analysis: arepresentational approach. Ph.D. thesis, University ofSheﬃeld.
Brown, G.J., Cooke, M., 1994. Perceptual grouping of musicalsounds: a computational model. J. New Music Res. 23, 107–
132.

328

M. Goto / Speech Communication 43 (2004) 311–329

Chafe, C., Jaﬀe, D., 1986. Source separation and note identiﬁcation in polyphonic music. In: Proc. IEEE Internat. Conf.
on Acoustics, Speech, and Signal Processing (ICASSP 86),
pp. 1289–1292.
Charpentier, F.J., 1986. Pitch detection using the short-term
phase spectrum. In: Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Processing (ICASSP 86), pp. 113–
116.
Cooke, M., Brown, G., 1993. Computational auditory scene
analysis: exploiting principles of perceived continuity.
Speech Comm. 13, 391–399.
de Cheveigné, A., 1993. Separation of concurrent harmonicsounds: fundamental frequency estimation and a timedomain cancellation model of auditory processing. J.
Acoust. Soc. Amer. 93 (6), 3271–3290.
de Cheveigné, A., Kawahara, H., 1999. Multiple period
estimation and pitch perception model. Speech Comm. 27(3–4), 175–185.
Dempster, A.P., Laird, N.M., Rubin, D.B., 1977. Maximum
likelihood from incomplete data via the EM algorithm. J.
Roy. Statist. Soc. B 39 (1), 1–38.
Flanagan, J.L., Golden, R.M., 1966. Phase vocoder. Bell
System Tech. J. 45, 1493–1509.
Goto, M., 1998. A study of real-time beat tracking for musicalaudio signals. Ph.D. thesis, Waseda University (inJapanese).
Goto, M., 2001. An audio-based real-time beat tracking system
for music with or without drum-sounds. J. New Music Res.
30 (2), 159–171.
Goto, M., Muraoka, Y., 1994. A beat tracking system foracoustic signals of music. In: Proc. 2nd ACM Internat.
Conf. on Multimedia (ACM Multimedia 94), pp. 365–372.
Goto, M., Muraoka, Y., 1996. Beat tracking based on multipleagent architecture––a real-time beat tracking system foraudio signals. In: Proc. 2nd Internat. Conf. on Multiagent
Systems (ICMAS-96), pp. 103–110.
Goto, M., Muraoka, Y., 1998. Music understanding at the beatlevel––real-time beat tracking for audio signals. In: Computational Auditory Scene Analysis. Lawrence Erlbaum
Associates, pp. 157–176.
Goto, M., Muraoka, Y., 1999. Real-time beat tracking for
drumless audio signals: chord change detection for musicaldecisions. Speech Comm. 27 (3–4), 311–335.
Goto, M., Neyama, R., Muraoka, Y., 1997. RMCP: remotemusic control protocol––design and applications. In: Proc.
1997 Internat. Computer Music Conference (ICMC 97),
pp. 446–449.
Kashino, K., 1994. Computational auditory scene analysis formusic signals. Ph.D. thesis, University of Tokyo (inJapanese).
Kashino, K., Murase, H., 1997. A music stream segregation
system based on adaptive multi-agents. In: Proc. Internat.
Joint Conf. on Artiﬁcial Intelligence (IJCAI-97), pp. 1126–
1131.

Kashino, K., Tanaka, H., 1994. A computational model ofsegregation of two frequency components––evaluation andintegration of multiple cues. Electron. Comm. Jpn. (PartIII) 77 (7), 35–47.
Kashino, K., Nakadai, K., Kinoshita, T., Tanaka, H., 1998.
Application of the Bayesian probability network to musicscene analysis. In: Computational Auditory Scene Analysis.
Lawrence Erlbaum Associates, pp. 115–137.
Katayose, H., Inokuchi, S., 1989. The kansei music system.
Comput. Music J. 13 (4), 72–77.
Kawahara, H., Katayose, H., de Cheveigné, A., Patterson,
R.D., 1999. Fixed point analysis of frequency to instantaneous frequency mapping for accurate estimation of F0
and periodicity. In: Proc. European Conf. on SpeechCommunication and Technology (Eurospeech 99), pp.
2781–2784.
Kitano, H., 1993. Challenges of massive parallelism. In: Proc.
Internat. Joint Conf. on Artiﬁcial Intelligence (IJCAI-93),
pp. 813–834.
Klapuri, A.P., 2001. Multipitch estimation and sound separation by the spectral smoothness principle. In: Proc. IEEE
Internat. Conf. on Acoustics, Speech, and Signal Processing(ICASSP 2001).
Masuda-Katsuse, I., 2001. A new method for speech recognition in the presence of non-stationary, unpredictable andhigh-level noise. In: Proc. European Conf. on SpeechCommunication and Technology (Eurospeech 2001), pp.
1119–1122.
Masuda-Katsuse, I., Sugano, Y., 2001. Speech estimationbiased by phonemic expectation in the presence of nonstationary and unpredictable noise. In: Proc. Workshop on
Consistent & Reliable Acoustic Cues for Sound Analysis(CRAC workshop).
Nakatani, T., Okuno, H.G., Kawabata, T., 1995. Residuedriven architecture for computational auditory scene analysis. In: Proc. Internat. Joint Conf. on Artiﬁcial Intelligence(IJCAI-95), pp. 165–172.
Nehorai, A., Porat, B., 1986. Adaptive comb ﬁltering forharmonic signal enhancement. IEEE Trans. ASSP ASSP-34(5), 1124–1138.
Noll, A.M., 1967. Cepstrum pitch determination. J. Acoust.
Soc. Amer. 41 (2), 293–309.
Ohmura, H., 1994. Fine pitch contour extraction by voice
fundamental wave ﬁltering method. In: Proc. IEEE Internat. Conf. on Acoustics, Speech, and Signal Processing(ICASSP 94), pp. II–189–192.
Okuno, H.G., Cooke, M.P. (Eds.), 1997. Working Notes of the
IJCAI-97 Workshop on Computational Auditory Scene
Analysis.
Parsons, T.W., 1976. Separation of speech from interferingspeech by means of harmonic selection. J. Acoust. Soc.
Amer. 60 (4), 911–918.
Plomp, R., 1967. Pitch of complex tones. J. Acoust. Soc. Amer.
41 (6), 1526–1533.

M. Goto / Speech Communication 43 (2004) 311–329
Rabiner, L.R., Cheng, M.J., Rosenberg, A.E., McGonegal,
C.A., 1976. A comparative performance study of several
pitch detection algorithms. IEEE Trans. ASSP ASSP-24 (5),399–418.
Ritsma, R.J., 1967. Frequencies dominant in the perception of thepitch of complex sounds. J. Acoust. Soc. Amer. 42 (1), 191–198.
Rosenthal, D., Okuno, H.G. (Eds.), 1995. Working Notes of
the IJCAI-95 Workshop on Computational Auditory Scene
Analysis.

329

Rosenthal, D.F., Okuno, H.G. (Eds.), 1998. Computational Auditory Scene Analysis. Lawrence Erlbaum
Associates.
Schroeder, M.R., 1968. Period histogram and product spectrum: new methods for fundamental-frequency measurement. J. Acoust. Soc. Amer. 43 (4), 829–834.
Tolonen, T., Karjalainen, M., 2000. A computationally eﬃcient
multipitch analysis model. IEEE Trans. Speech Audio
Process. 8 (6), 708–716.