Robust temporal and spectral modeling for query By melody.
Query by melody is the problem of retrieving musical performances from melodies. Retrieval of real performances is complicated due to the large number of variations in performing a melody and the presence of colored accompaniment noise. We describe a simple yet effective probabilistic model for this task. We describe a generative model that is rich enough to capture the spectral and temporal variations of musical performances and allows for tractable melody retrieval. While most of previous studies on music retrieval from melodies were performed with either symbolic (e.g. MIDI) data or with monophonic (single instrument) performances, we performed experiments in retrieving live and studio recordings of operas that contain a leading vocalist and rich instrumental accompaniment. Our results show that the probabilistic approach we propose is effective and can be scaled to massive datasets.
INTRODUCTION
A natural way for searching a musical audio database for
a song is to look for a short audio segment containing a
melody from the song. Most of the existing systems are
based on textual information, such as the title of the song
and the name of the composer. However, people often do
not remember the name of the composer and the song's title
but can easily recall fragments from the soloist's melody.
The task of query by melody attempts to automate the
music retrieval task. It was rst discussed in the context
of query by humming [11, 13, 14]. These works focus on
converting hummed melodies into symbolic MIDI format
(MIDI is an acronym for Musical Instrument Digital Inter-
face. It is a symbolic format for representing music). Once
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
SIGIR'02, August 11-15, 2002, Tampere, Finland.
the query is converted into a symbolic format the challenge
is to search for musical performances that approximately
match the query. Most of the research so far has been conducted
with music stored in MIDI format [12] or in monophonic
(i.e. single vocal or instrument) recordings (see for
instance [9, 7] and the references therein). In this paper,
we suggest a method for query by melody where the query
is posed in symbolic form as a monophonic melody and the
database consists of real polyphonic recordings.
When dealing with real polyphonic recordings we need to
address several complicating factors. Ideally melodies can
be represented as sequences of notes, each is a pair of frequency
and temporal duration. In real recordings two major
sources of di-culty arise. The rst is the high variability of
the actual durations of notes. A melody can be performed
faster or slower than the one dictated by the musical score.
This type of variation is often referred to as tempo vari-
ability. Furthermore, the tempo can vary within a single
performance. For instance, a performance can start with a
slow tempo which gradually increases. The second complicating
factor is the high variability of the spectrum due to
many factors such as dierences in tone colors (timbre) of
dierent singers/instruments, the intentional variation by
the leading vocalists (e.g. vibrato and dynamics) and by
\spectral masking" of the leading vocal by the accompanying
vocals and orchestra.
We propose to tackle these di-culties by using a generative
probabilistic approach that models the temporal and
spectral variations. We associate each note with a hidden
tempo variable. The tempo variables capture the temporal
variations in the durations of notes. To enable e-cient com-
putation, the hidden tempo sequence is modeled as a rst
order Markov process. In addition, we also describe a simple
probabilistic spectral distribution model that is robust
to the masking noise of the accompanying instruments and
singers. This spectral distribution model is a variant of the
harmonic likelihood model for pitch detection [16]. Combining
the temporal and spectral probabilistic components, we
obtain a joint model which can be thought of as a dynamic
Bayesian network [8]. This representation enables e-cient
alignment and retrieval using dynamic programming.
This probabilistic approach is related to several recent
works that employ Hidden Markov Models (HMM) for music
processing. Raphael [15] uses melody information (pitches
and durations of notes) in building an HMM for a score
following application. A similar approach is taken by Durey
and Clements [9] who use the pitch information of notes
for building HMMs for melody retrieval. However, both
approaches were designed for and evaluated on monophonic
music databases. Most work on polyphonic music processing
addressed tasks such as music segmentation into textures [6],
polyphonic pitch tracking [18], and genre classication [17,
10]. We believe that the approach we describe in this paper
is a step toward an eective retrieval procedure for massive
musical datasets.
2. PROBLEM SETTING
In our setting, we are given a melody and our task is
to retrieve musical performances containing the requested
melody and to nd its location within the retrieved perfor-
mances. A melody is a sequence of notes where each note
is a pair of a pitch value and a duration value. Our goal
is to retrieve melodies from audio signals representing real
performances.
Formally, let R+ denote the positive real numbers. Let
be frequency values (in Hz) and let [f l ; fh ] be a
diapason. A diapason of a singer (or an instrument) is the
range of pitch frequencies that are in use by the singer (or
by the instrument). For instance, a tenor singer typically
employs a diapason of [110Hz; 530Hz]. Let  denote the
set of all possible frequencies of notes. In the well-tempered
Western music tuning system,
the possible pitches of notes in the diapason. A melody is
described formally by a sequence of pitches, p 2 k , and a
sequence of durations, d 2 R+ k , in a predened time units
(e.g. seconds or samples).
A performance of a melody is a discrete time sampled audio
performance is formally entirely
dened given the melody: play or sing using pitch p1 for the
rst d1 seconds, then play or sing pitch p2 for the next d2
seconds, and so on and so forth. In reality, a melody does
not impose a rigid framework. The actual frequency content
of a given note varies with the type of instrument that
is played and by the performer. Examples for such variations
are the vibrato and timbre eects. The accompaniment also
greatly in
uences the spectral distribution. While playing a
note using pitch p, we are likely to see a local concentration
of energy close to multiples of the frequency p in the power
spectrum of the signal. However, there may be other spectral
regions with high levels of energy. We will address this
problem later on in this section. Another source of variation
is local scaling of the durations of notes as instructed by the
melody. The performer typically uses a tempo that scales
the duration and moves from one tempo to another, thus
using a dierent time scale to play the notes. Therefore,
we also need to model the variation in the tempo which we
describe now.
A tempo sequence is a sequence of scaling factors, m 2
. The actual duration of note i, denoted e
d i is d i scaled
by
Seemingly, allowing dierent scaling
factors for the dierent notes adds a degree of freedom that
makes the melody duration values redundant. However, a
typical tempo sequence does not change rapidly and thus
re
ects most of the information of the original durations
(up to a scaling factor). Table 1 shows two examples of
sequences. A pitch{duration{tempo triplet (p; d; m)
generates an actual pitch{duration pair (p; e d) .
Rallentando 1.2 1.2 1.25 1.3 1.3

Table

1: Examples of scaling factor sequences: In
the rst sequence the scaling factors are gradually
increasing and thus the tempo is decreasing
("Rallentando"). In the second example the scaling
factors are decreasing and the tempo is increasing
(\Accelerando").
In order to describe the generation of the actual performance
audio signal o from (p; e d) we introduce one more vari-
able, s 2 R+ k where s i is the starting time (sample number)
of note i in the performance. We dene s
e
d j for
consecutive blocks of signal
samples. Let
be the block of samples
generated by note i.
The power spectrum of varies signicantly from performance
to performance, according to various factors such as
the spectral envelope of the soloist and pitches of accompaniment
instruments. Since our goal is to locate and retrieve
a melody from a dataset that may contain thousands of per-
formances, we resort to a very simple spectral model and do
not explicitly model these variables. We use an approximation
to the likelihood of a block spectrum given its pitch.
3. FROM MELODY TO SIGNAL:
A GENERATIVE MODEL
To pose the problem in a probabilistic framework, we need
to describe the likelihood of a performance given the melody,
We cast the tempo sequence m as a hidden random
variable, thus the likelihood can be written as,
For simplicity, we assume that the tempo sequence does not
depend on the melody. While this assumption, naturally,
does not always hold, we found empirically that these types
of correlations can be ingnored in short pieces of perfor-
mances. With this assumption and the identity e
Equ. (1) can be rewritten as,
d)
We now need to specify the prior distribution over the tempo,
(m), and the posterior distribution of the signal given the
pitches and the actual durations of the notes P (ojp; e d).
3.1 modeling
We chose to model the tempo sequence as a rst order
Markov process. As we see in the sequel this choice on one
hand allows an e-cient alignment and retrieval, and on the
other hand, was found empirically to be rich enough. There-
fore, the likelihood of m is given by,
Y
We use the log-normal distribution to model the conditional
probability
where  is a scaling parameter of the variance. The prior
distribution of the rst scaling factor P (m1) is also assumed
to be log-normal around zero with variance , log 2 (m i )
N (0; ). In our experiments, the parameter  was determined
manually according to musical knowledge. This parameter
can also be learned from MIDI les.
3.2 Spectral Distribution Model
In this section we describe our spectral distribution model.
There exist quite a few models for the spectral distribution
of singing voices and harmonic instruments. However, most
of these models are rather general. These models typically
assume that the musical signal is contaminated with white
noise whose energy is statistically independent of the signal.
See for instance [16] and the references therein. In contrast,
we assume that there is a leading instrument, or soloist, that
is accompanied by an orchestra or a chorus. The energy of
the accompaniment is typically highly correlated with the
energy of the soloist. Put another way, the dynamics of the
accompaniment matches the dynamics of the soloist. For
instance, when the soloist sings pianissimo the chorus follows
her with pianissimo voices. We therefore developed a
simple model whose parameters can be e-ciently estimated
that copes with the correlation in energy between the leading
soloist and the accompaniment. In Fig. 1 we show the
spectrum of one frame of a performance signal from our
database. The harmonics are designated by dashed lines. It
is clear from the gure that there is a large concentration
of energy at the designated harmonics. The residual en-
ergy, outside the harmonics, is certainly non-negligible but
is clearly lower than the energy of the harmonics. Thus, our
assumptions, although simplistic, seem to capture to a large
extent the characteristics of the spectrum of singing with
accompaniment.
Using the denition of a block o i from Sec. 2, the likelihood
of the signal given the sequences of pitches and durations
can be decomposed into a product of likelihood values
of the individual blocks,
Y
Therefore, the core of our modeling approach is a probabilistic
model for the spectral distribution of a whole block given
the underlying pitch frequency of the soloist. Our starting
point is similar to the model presented in [16]. We assume
that a note with pitch p i attains high energy at frequencies
which are multiples of p i , namely at p i h for integer h.
These frequencies are often referred to as harmonics. Since
our signal is band limited, we only need to consider a nite
set of harmonics h, h 2 f1; 2; :::; Hg. For practical purposes
we set H to be 20 which enables a fast parameter estimation
procedure. Let F (!) denote the observed energy of the
block at frequency !. Let S(!) denote the energy of the
soloist at frequency !. The harmonic model assumes that

Figure

1: The spectrum of a single frame along with
an impulse train designating the harmonics of the
soloist.
S() is bursts of energy centered at the harmonics of the
pitch frequency, p i h, and we model it as a weighted sum of
where A(h) is the volume gain for the harmonic whose index
is h. The residual of the spectrum at frequency ! is
denoted N(!) and is equal to
now describe a probabilistic model that leads to the following
log-likelihood score,
log
denotes the '2-norm.
To derive the above equation we assume that the spectrum
of the ith block, F , is comprised of two components. The
rst component is the energy of the soloist, S(!) as dened
in Equ. (2). The second component is a general masking
noise that encompasses the signal's energy due to the accompaniment
and aects the entire spectrum. We denote
the noise energy at frequency ! as (!). The energy of the
spectrum at frequency ! is therefore modeled as,
We now impose another simplifying assumption by setting
the noise  to be a multivariate normal random variable and
further assuming that the noise values at each frequency !
are statistically independent with equal variance. Thus, the
noise density function is
where v is the variance and L is the number of spectral
points computed by the discrete Fourier transform. (We
chose to get a good spectral resolution.) Taking the
log of the above density function we get,
log
The gain values A(h) are free parameters which we need to
estimate from the spectrum. Assuming that the noise level
is relatively small compared to the bursts of energy at the
harmonics of the pitch frequency, we set the value of A(h)
to be F (p i h). We also do not know the noise variance v. For
parameter we use the simple maximum likelihood
(ML) estimate which can be easily found as follows. The
maximum likelihood estimate of v is found by taking the
derivative of log f(jv) with respect to v,
@ log f(jv)
Rearranging Equ. (4), the noise value at frequency !, (!),
can be written as,
By using above equation for (!) along with values set for
A(h) and the maximum likelihood estimate v  in Equ. (6)
we get,
log
log
Since the stochastic ingredient of our spectral model is the
accompanying noise, the noise likelihood above also constitute
the likelihood of the spectrum.
To summarize, we now overview our approach for retrieval.
We are given a melody (p; d) and we want to nd an audio
signal which represents a performance of this melody.
Using our probabilistic framework, we cast the problem as
the problem of nding a signal portion whose likelihood
given the melody, P (ojp; d), is high. Our search strategy
is as follows. We nd the best alignment of the signal to
the melody as we describe in the next section. The score
of the alignment procedure we devise is also our means for
retrieval. We then rank the segments of signals in accordance
with their likelihood scores and return the segments
achieving high likelihoods scores.
4. ALIGNMENT AND RETRIEVAL
Alignment of a melody to a signal is performed by nd-
ing the best assignment of a tempo sequence. Formally,
we are looking for the scaling factors m  that attain the
highest likelihood score, m Although
the number of possible sequences of scaling factors
grows exponentially with the sequence length, the problem
of nding m  can be e-ciently solved using dynamic
programming, as we now describe.
the scaling factors of the
rst i notes of a melody. Let the rst
t samples of a signal. Let M be a discrete set of possible
scaling factor values. For  2 M , let M i;t; be a set of
all possible sequences of i scaling factors, m i , such that
is the scaling factor of note i and
1. Initialization
2. Recursion
(i
3. Termination

Figure

2: The alignment algorithm.
the actual ending time of note i. Let
t; ) be the joint
likelihood of
The pseudo code for computing
recursively is
shown in Fig. 2.
The most likely sequence of scaling factors m  is obtained
from the algorithm by saving the intermediate values that
maximize each expression in the recursion step. The complexity
of the algorithm is O(kT jM j 2 D), where k is the number
of notes, T is the number of samples in the digital signal,
jM j is the number of all possible tempo values and D is the
maximal duration of a note. Using a pre-computation of
the likelihood values we can reduced the time complexity
by a factor of D and thus the run time of the algorithm reduces
to O(kT jM j 2 ). It is important to clarify that the pre-computation
does not completely determine a single pitch
value for a frame. It calculates the probability of the frame
given each possible pitch in the diapason.
As mentioned above, our primary goal is to retrieve the
segments of signals representing the melody given by the
query. Theoretically, we need to assign a segment its likelihood
score,
d). However, this
marginal probability is rather expensive to compute. We
thus approximate this probability with the joint probability
of the signal and most likely sequence of scaling factors,
d) . That is, we use the likelihood score of the
alignment procedure as a retrieval score.
5. EXPERIMENTAL RESULTS
To evaluate our algorithm we collected 50 dierent melodies
from famous opera arias, and queried these melodies in a
database of real recordings. The recordings consist of 832
performances of opera arias performed by more then 40
dierent tenor singers with full orchestral accompaniment.
Each performance is one minute. The data was extracted
from seven audio CDs [2, 3, 5, 1, 4], and saved in wav for-
mat. Most of the performances (about 90 percent) are digital
recordings (DDD/ADD). Yet, some performances are
digital remastering of old analog recordings (AAD). This
Spectral Distribution Model
HSN HIN
AvgP Cov Oerr AvgP Cov Oerr
Melody
length

Table

2: Retrieval results
introduced additional complexity to the retrieval task due
to varying level of noise.
The melodies for the experiments were extracted from
MIDI les. About half of the MIDI les were downloaded
from the Internet 1 and the rest of the MIDI les were performed
on a MIDI keyboard and saved as MIDI les.
We compared three dierent tempo-based approaches for
retrieval. The rst method simply uses the original durations
given in the query without any scaling. We refer to
this simplistic approach as the Fixed Tempo (FT) model.
The second approach uses a single scaling factor for all the
durations of a given melody. However, this scaling factor is
determined independently for each signal so as to maximize
the signals likelihood. We refer to this model as the Locally
Fixed Tempo (LFT) model. The third retrieval method is
our variable tempo model that we introduced in this paper.
We therefore refer to this method as the Variable Tempo
model. By taking a prex subset of each melody used
in a query we evaluated three dierent lengths of melodies:
5 seconds, 15 seconds, and 25 seconds.
To assess the quality of the spectral distribution model
described in Sec. 3.2, we implemented the spectral distribution
model described in [16]. This model assumes that the
harmonics of the signal are contaminated with noise whose
mean energy is independent of the energy of the harmonics.
We refer to our model as the Harmonics with Scaled Noise
(HSN) model and to the model from [16] as the Harmonics
with Independent Noise (HIN) model.
To evaluate the performances of the methods we used
three evaluation measures: one-error, coverage and average
precision. To explain these measures we introduce the
following notation. Let N be the number of performances
in our database and let M be the number of melodies that
we search for. (As mentioned above, in our experiments
50.) For a melody index i we denote
by Y i the set of the performances containing melody i. The
probabilistic modeling we discussed in this paper induces a
natural ordering over the performances for each melody. Let
R i (j) denote the ranking of the performance indexed j with
respect to melody i. Based on the above denitions we now
http://www.musicscore.freeserve.co.uk,
http://www.classicalmidi.gothere.uk.com
give the formal denitions of the performance measures we
used for evaluation.
One-Error. The one-error measures how many times the
top-ranked performance did not contain the melody posed
in the query. Thus, if the goal of our system is to return a
single performance that contains the melody, the one-error
measures how many times the retrieved performance did not
contain the melody. Formally, the denition of the one-error
is,
predicate  holds and 0 otherwise.
Coverage. While the one-error evaluates the performance
of a system with respect to the top-ranked performance, the
goal of the coverage measure is to assess the performance of
the system for all of the possible performances of a melody.
Informally, Coverage measures the number of excess (non-
relevant) performances we need to scan until we retrieve all
the relevant performances. Formally, Coverage is dened as,
Average Precision. The above measures do not su-ce in
evaluating the performances of retrieval systems as one can
achieve good (low) coverage but suer high one-error rates,
and vice versa. In order to assess the ranking performance
as a whole we use the frequently used average precision mea-
sure. Formally, the average precision is dened as,
In addition we also use precision versus recall graphs to illustrate
the overall performances of the dierent approaches
discussed in the paper. A precision-recall graph shows the
level of precision for dierent recall values. The graphs presented
in this paper are non-interpolated, that is, they were
calculated based on the precision and recall values achieved
at integer positions of the ranked lists.
In

Table

2 we report results with respect to the performance
measures described for the FT, LFT, and VT mod-
els. For each tempo model we conducted the experiments
with the two spectral distribution models HIN and HSN.
It is clear from the table that the Variable Tempo model
with the Harmonics with Scaled Noise spectral distribution
outperforms the rest of the models and achieves superior
results. Moreover, the performance of the Variable Tempo
model consistently improves as the duration of the queries
increases. In contrast, the Fixed Tempo does not exhibit
any improvement as the duration of the queries increases
and the Locally Fixed Tempo shows only a moderate improvement
when using fteen second long queries instead of
ve second long queries and it does not improve as the duration
grows to twenty ve seconds. A reasonable explanation
for these phenomena is that the amount of variability in a
very short query is naturally limited and thus the leverage
gained by accurate tempo modeling which takes into account
the variability in tempo is rather small. Thus, as the query
Recall
Precision
Precision
Recall
Precision

Figure

3: Precision-recall curves comparing the performance
of three tempo models for queries consisting
of ve seconds (top), fteen second (middle),
and twenty ve seconds (bottom).
Precision
Recall
Precision
Recall
Precision

Figure

4: Precision-recall curves comparing the performance
of each of the tempo models for three different
query lengths.
duration grows the power of the variable tempo model is
better exploited. The Locally Fixed Tempo can capture the
average tempo of a performance but clearly fails to capture
changes in the tempo. Since the chance of a tempo change
grows with the duration of the query the average tempo
stops from being a good approximation and we do not see
further improvement in the retrieval quality.
In Fig 3 we give precision-recall graphs that compare the
three tempo models. Each graph compares FT, LFT and
VT for dierent query durations. The VT model clearly
outperforms both the FT and LFT models. The longer the
query the wider the gap in performance. In Fig 4 we compare
the precision-recall graphs for each model as a function
of the query duration. Each graph shows the precision-recall
curves for 5, 15, and 25 seconds queries. We again see that
only the VT model consistently improves with the increase
in the query duration. Using a globally xed tempo (FT) is
clearly inadequate as it results in very poor performance {
precision is never higher than 0.35 even for low level of re-
call. The performance of the LFT model is more reasonable.
A precision of about 0.5 can be achieved for a recall value of
0.5. However, the full power of our approach is utilized only
when we use the VT model. We achieve an average precision
of 0.92 with a recall of 0.75. It seems that with the VT
model we reach an overall performance that can serve as the
basis for large scale music retrieval systems.
Lastly, as a nal sanity check of the conjecture of the robustness
of the VT model we used the VT and LFT model
with three long melody queries (one minute) and applied
the retrieval and alignment process. We then let a professional
musician listen to the segmentation and browse the
segmented spectogram. An example of a spectogram with a
segmentation of the VT model is given in Fig 5. The example
is of a performance where the energy of accompaniment
is higher than the energy of the leading tenor. Nonetheless,
a listening experiment veried that our system was able to
properly segment and align the melody posed by the query.
Although these perceptual listening tests are subjective, the
experiments indicated that the VT model also provides an
accurate alignment and segmentation.
6. DISCUSSION
In this paper we presented a robust probabilistic model
for query by melody. The proposed approach is simple
to implement and was found to work well on polyphony-
rich recordings with various types of accompaniments. The
probabilistic model that we developed focuses on two main
sources of variability. The rst is variations in the actual
durations of notes in real recordings (tempo variability) and
the second is the variability of the spectrum mainly due to
the \spectral masking" of the leading vocal by the accompanying
vocals and orchestra. In this work we assumed that
the pitch information in a query is accurate and only the
duration can be altered in the performance. This assumption
is reasonable if the queries are posed using a symbolic
input mechanism such as a MIDI keyboard. However, an
easier and more convenient mechanism is to hum or whistle
a melody. This task is often called \query by humming".
In addition to the tempo variability and spectral masking,
a query by humming system also needs to take into account
imperfections in the pitch of the hummed melody. Indeed,
Frequency
Time
Figure

5: An illustration of the alignment and segmentation
of the VT model. The pitches of the notes
in the melody are overlayed in solid lines.
much of the work on query by humming have been devoted
to music retrieval using noisy pitch information. The majority
of the work on query by humming though have focused
on search of noisy queries in symbolic databases. Since the
main thrust of this research is searches in real polyphonic
recordings, it complements the research on query by humming
and can supplement numerous systems that search in
databases. We plan to extend our algorithm so it
can be combined with a front end for hummed queries. In
addition, we have started conducting research on supervised
methods for musical genre classication. We believe that by
combining highly accurate genre classication with a robust
retrieval and alignment we will be able to provide an eec-
tive tool for searching and browsing for both professionals
and amateurs.

Acknowledgments

We would like to thank Moria Koman for her help in creating
the queries used in the experiments and Leo Kon-
torovitch for useful comments on the manuscript.
7.



--R


Best of opera.
Les 40 tenors.
nessun dorma
The young domingo.


A model for reasoning about persistent and causation.
Melody spotting using hidden Markov models.
An overview of audio information retrieval.
Query by humming: Musical information retrieval in an audio database.
Searching monophonic patterns within polyphonic sources.
The new zealand digital library melody index

Automatic segmentation of acoustic musical signals using hidden markov models.
Speech enhancement by harmonic modeling via map pitch track- ing
Audio information retrieval (air) tools.
pitch tracking using joint bayesian estimation of multiple frame parameters.
--TR
A model for reasoning about persistence and causation
Query by humming
An overview of audio information retrieval
Automatic Segmentation of Acoustic Musical Signals Using Hidden Markov Models

--CTR
Keiichiro Hoashi , Kazunori Matsumoto , Naomi Inoue, Personalization of user profiles for content-based music retrieval based on relevance feedback, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
Fang-Fei Kuo , Man-Kwan Shan, Looking for new, not known music only: music retrieval by melody style, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA
Olivier Gillet , Gal Richard, Drum loops retrieval from spoken queries, Journal of Intelligent Information Systems, v.24 n.2, p.159-177, May 2005
spectral modeling;query by melody;graphical models;music information retrieval