Music Signal Spotting Retrieval by a Humming QueryUsing Start Frame Feature Dependent Continuous
Dynamic Programming
Takuichi Nishimura

Hiroki Hashiguchi

Junko Takita

Real World Computing Partnership/ National Institute of Advanced
Industrial Science and Technology

Real World Computing Partnership

Mathematical Systems Inc.
2-4-3 Shinjuku, Shinjuku-ku, Tokyo

Tsukuba Mitsui Building 13F, 1-6-1
Takezono Tsukuba-shi, Ibaraki

305-0032, Japan+81-298-53-1668

305-0032, Japan+81-298-53-1686

hiro@rwcp.or.jp

Tsukuba Mitsui Building 13F, 1-6-1
Takezono Tsukuba-shi, Ibaraki

160-0022 Japan+81-3-3358-1701

takita@msi.co.jp

nishi@rwcp.or.jp
J. Xin Zhang
Media Drive Co.
3-195 Tsukuba, Kumagaya-shi,
Saitama, 360-0037, Japan+81-48-524-0501

chou@mediadrive.co.jp

Masataka Goto

Ryuichi Oka

Real World Computing Partnership
National Institute of Advanced
Tsukuba Mitsui Building 13F, 1-6-1
Industrial Science and Technology
Takezono Tsukuba-shi, Ibaraki/"Information and Human Activity''
PRESTO, JST
305-0032, Japan
1-1-1 Umezono, Tsukuba-shi, Ibaraki+81-298-53-1686
305-8568, Japan+81-298-61-5898

oka@rwcp.or.jp

m.goto@aist.go.jp

ABSTRACT
We have developed a music retrieval method thattakes a humming query and finds similar audio
intervals (segments) in a music audio database. Thismethod can also address a personally recorded video
database containing melodies in its audio track. Our
previous retrieving method took too much time toretrieve a segment: for example, a 60-minute databaserequired about 10-minute computation on a personal
computer. In this paper, we propose a new high-speed
retrieving method, called start frame featuredependent continuous Dynamic Programming, whichassumes that the pitch of the interval start point isaccurate. Test results show that the proposed method
reduces retrieval time to about 1/40 of present
methods.

1. INTRODUCTION
Although a large amount and variety of musical audio
signals have been available on the internet and stored

in personal hard disks at home, information retrieval
methods for those signals are still in infancy. A
typical method is a simple text-based search whichseeks property tags attached to those signals, such as
the song title, artist name, and genre. The purpose ofthis research is to enable a user to retrieve a segmentof a musical audio signal desired just by singing its
melody. Such a music retrieval method is also usefulfor retrieving video clips if those clips contain music
in audio tracks. For practical application, we think it
important that the method can be applied to an audio
database that is not segmented into musical pieces (asis often the case with broadcast recordings).
In this paper, we focus on a music retrieval systemthat takes a humming query and finds similar audio
intervals (segments) in a music audio database. If thedatabase is composed of melody scores such as MIDI,
symbols (e.g., relative pitch change or span change)
can be extracted robustly. In this case, symbol-basedretrieval [1-4] is very efficient. On the other hand,
extracted melody from an audio signal usually suffers
a lot of error and such symbol-based methods are notapplicable. Therefore, we developed the pattern-based
retrieval method [5]. Fundamentally, we find a similar
pitch sequence of a query (query pattern) in the
melody-likeness pattern on the pitch-temporal planeobtained from the database shifting the query patternalong pitch axis and warping temporally as shown in
Figure 1. The previous matching method is called
model-driven
pathContinuous
Dynamic
Programming (mpCDP) which compares thereference and all the partial intervals in the databaseand outputs similar intervals by considering multiple
possibilities of transpositions. Because the mpCDP
achieves pattern-based matching, the method can also
take whistle sound or tempo-varying humming. (In thefollowing, we use two terms, "reference pattern'' and"input pattern'': we extract a "reference pattern'' froma query and an "input pattern'' from a database inorder to feed those patterns into matching methods.)
This previous mpCDP, however, is too slow to be
used in practical applications: it needs muchcomputational cost because it accumulates local
similarities in 3-D space, which is composed frommodel-axis, input-axis, and pitch-axis.
In this paper, we propose a new quick retrieval
method, called start frame feature dependent
continuous DP (s-CDP), which searches only in 2-D
space (reference-axis and input-axis) assuming thatthe feature (pitch in this paper) of the start point of theextracted optimal interval is accurate. Our new s-CDP
is different from conventional continuous DP in therespect that we do not calculate local similarities
beforehand because the start point of the optimal
interval is obtained from bottom left to top right
successively in the 2-D space.

Figure 1. Pattern matching for humming retrieval.
Pitch shift and temporal-warp are considered.

We evaluate our new method using 20 popular music
selections comparing the conventional method toshow that the proposed method can reduce searchtime to about 1/40 with retrieval rates in excess of
70%.
The following section describes the conventional
retrieval method. The s-CDP and the retrieval method
using s-CDP is proposed in Section 3. The method is
evaluated in Section 4 and newly developed retrieval
system is introduced in Section 5.

2. OUR CONVENTIONAL RETRIEVALMETHOD
Continuous DP [7] is improved from temporally
monotonous Dynamic Programming (DP) for speechor gesture recognition. Continuous DP achievesinconsistent recognition because it can segment the
input pattern automatically but it cannot consider
multiple possibilities of transpositions. Therefore, we
proposed mpCDP [5] for music retrieval method
adding one dimension (pitch) for input pattern andfinding similar pitch sequence to the query.

2.1 Continuous DP
As shown in Figure 2 (a), continuous DP calculates
accumulated similarities S (t ,τ ) between referenceRτ (1 ≤ τ ≤ T ) and input I t (0 ≤ t ≤ ∞) by adding
local similarities s (t ,τ ) . Denoting the temporal axisof reference and input as t and τ , respectively,
continuous DP calculates S (t ,τ ) using the following
recursive equations.

Boundary conditions (1 ≤ τ ≤ T ,0 ≤ t ) :S (t ,0) = S (t ,−1) = 0
S (−1,τ ) = S (0,τ ) = 0
Recursive equations ( 1 ≤ t ):S (t ,1) = 3 ⋅ s(t ,1)
S (t ,τ ) = S (t − 2,τ − 1) + 2s(t − 1,τ ) + s(t,τ )

(1)
max
S (t − 1,τ − 1) + 3s(t,τ )S (t − 1,τ − 2) + 3s(t,τ − 1) + 3s(t ,τ )


(2 ≤ τ ≤ T )In this equation, local path with maximum similarity
is chosen among the three paths as shown in Figure2(c). Numbers besides each point are weights for local
similarities. Notice that the summation of weights isalways three for one frame up along the reference axis.
Therefore, dividing accumulated similarities by three
can normalize them.
Next, we find a similar interval. Figure 2(b) shows
accumulated similarities S (t , T ) ; and the continuous
DP decide the maximum point with higher similarity
than a certain threshold α as the end point of thesimilar interval.
In brief, continuous DP finds the optimal path andmaximum accumulated similarities by choosing the
maximum local path successively from bottom left to
top right in the reference-input plane. The S (t , T ) is
the similarity between the whole reference and the
input considering temporal warps from 1/2 to 2 times.

Figure 2. Continuous Dynamic Programming.

2.2 Humming Retrieval by mpCDP
This section explains the conventional humming
retrieval method using Figure 3. The method has threesteps. First, database audio signals are analyzed every
frame, 64ms in this paper, and sequence of melodylikeness of each pitch (SMLP) is obtained. When aquery is input to the method, highest melody-likenesspitch is chosen from SMLP every frame and querymodel is created by the relative pitch change. Third,
model-driven path Continuous Dynamic Programming(mpCDP) compares the model and all partial intervals
in the database and output similar intervals byconsidering multiple possibilities of transpositions.
The local path of mpCDP is different from that ofcontinuous DP in that they are shifted along the pitch
axis according to the model, which is the relative
pitch change of the query. By executing suchprocesses successively, accumulated similarity
S (t , T , x) (Here x denotes pitch axis) takes amaximum similarity along the pitch axis at the end of
the model as shown in top-right figure of Figure 3.
Then, max S (t , T , x) changes similar to Figure 2(b).
x

Finally the mpCDP outputs the maximum point withhigher similarity than a certain threshold α as the end
point of the similar interval.

Figure 3. Conventional retrieval method.

3. PROPOSAL OF s-CDP
3.1 s-CDP
The definition of s-CDP is that local similaritiess (t ,τ ) are dependent on the feature of the start point( p (t ,τ ),1) of optimal paths. Therefore local
similarities
of
s-CDP
are
describedass (t ,τ ) = f ( Rτ , I t , R1 , I p ( t ,τ ) ) using a certain similarity
function.
f ()s (t ,τ ) = f ( Rτ , I t ) ).

(For

continuousDP:

Figure 4. Comparison of matching methods.

The difference between conventional continuous DP
and s-CDP is shown in Figure 4. All local similarities
can be calculated beforehand for continuous DP(Figure 4(a)), whereas local similarities are obtained
incrementally as the optimal paths are fixed for s-CDP
as shown in Figure 4(b). There are three local
similarities for each point (t ,τ ) because the startpoints are different among three local paths as shownin Figure 2 (c). Equation (1) is rewritten for s-CDP as:

Recursive equations ( 1 ≤ t ):In case of error in start points, features of start points
R1 , I p ( t ,τ ) are incorrect - leading to miscalculation of

S (t ,1) = 3 ⋅ s 2 (t ,1)
S (t ,τ ) = S (t − 2,τ − 1) + 2s 2 (t − 1,τ ) + s1 (t ,τ )max
S (t − 1,τ − 1) + 3s 2 (t ,τ )(2)
S (t − 1,τ − 2) + 3s (t ,τ − 1) + 3s (t ,τ )23
(2 ≤ τ ≤ T )Here we call the local paths in Figure 2 (c) path1,
path2,
path3
from
top-leftanddefine,,aslocal
similaritiesfor
path1,s1 (t ,τ ) s 2 (t ,τ ) s3 (t ,τ )path2, and path3, respectively. Those are defined as:s 2 (t ,τ ) = f ( Rτ , I t , R1 , I p ( t ,τ ) ) (τ = 1)
s1 (t ,τ ) = f ( Rτ , I t , R1 , I p ( t − 2,τ −1) ) (2 ≤ τ )s 2 (t ,τ ) = f ( Rτ , I t , R1 , I p (t −1,τ −1) ) (2 ≤ τ )s 3 (t ,τ ) = f ( Rτ , I t , R1 , I p (t −1,τ − 2 ) ) (2 ≤ τ )The s 2 (t ,τ ) alone takes τ = 1 and requires exception
because the start point is the same as the point (t ,1) .
Second terms of path1 and path3 in equation (2) ares2 (⋅,⋅) because both points come from points (−1,−1)relatively in the plane.

accumulated similarities. Therefore, one must choosea high melody-likeness point as the start point in order
to segment the reference. As for input, segmenting asimilar interval is the method’s purpose, so such ameasure is impossible. Still, those errors arerecovered if one feature near the start point is correct
because s-CDP matches, warping the reference
temporarily.

3.2 Apply for Humming Retrieval
In this section, s-CDP is modified for the humming
retrieval method. Because melody is expressed as thepitch sequence, the feature is pitch and each pitch is
subtracted from the start pitch to cope withtranspositions, assuming that start pitch is correct.
Query is transposed to make the start pitch 0 as shownin Figure 5. On the other hand, database transpositionis possible just after the start pitch is fixed by tracing
back the optimal path derived from s-CDP. Then thesegmented database is similarly transposed to makethe start pitch 0 as shown in Figure 5. Finally, s-CDP
compares the transposed query and database without
any influence of transpositions.

Outputs of s-CDP are obtained as points withmaximum accumulated similarities in the same way as
continuous DP, but they have positions of start points
and features of start points.
To calculate the start position p (t ,τ ) on the input
axis, first initialize with time t when τ = 0,1 .
p (t ,0) = p (t ,1) = t
Next, copy the start point memorized at the local startpoint to p(t ,τ ) as follows: p (t − 2, τ − 1) (if path1)
p (t , τ ) =  p (t − 1, τ − 1) (if path 2)
 p (t − 1, τ − 2) (if path3)
Start positions ( p (t ,τ ),1) are obtained incrementallyby the recursive equations above.

Figure 5. Overview of melody matchingconsidering transpositions.

Figure 6 helps to explain the detail method. First,
make relative pitch sequence of query as the reference'Rτ = Rτ − R1 . Second, obtain N high melody-likenesscandidates from database musical signal as input
I t ( k )(k = 1, L , N ) . In this study, local similaritiess (t ,τ ) are defined:candidates is equal to relative pitch of the query. We
set N = 5 in experiments in this paper.

1( Dt ,τ = 0)s (t , τ ) = 
0( Dt ,τ ≠ 0)
Here Dt ,τ = min abs[ Rτ' − {I t (k ) − I p (t ,τ ) (1)}] and localksimilarities are 1 if one of the relative pitches of N

Figure 6. Proposed retrieval method using s-CDP.

4. EXPERIMENTS
4.1 Experimental Method
We prepared 20 WAV files (about 80 minutes intotal) in 16 kHz sampling and monaural recording
format as a music database to compare s-CDP with
mpCDP. This database includes 10 Japanese pop
songs, 8 children's songs, an animation song, and aJapanese enka. There are 4 male and 16 female vocal
artists in the database. Also, 3 males and 2 females
sang a portion of each song in the database for about
20 seconds. Hence, the total number of queries was100.
Let fb[Hz] (in this experiment: 55[Hz]) denote thelowest frequency of melody. We compute the melody

likeness for the frequency 2 x / 12 f b ( x = 1,L, X ) [Hz] by
FFT analysis in consideration of the harmonic
structure of acoustic signals. This method is a simple
version of [5]. The step of the pitch axis of mpCDP is
set at 60 (5 octaves: X = 60 ) considering the male andfemale voice pitch range.
Two thresholds segmented a reference from a query.
To decide the start point, the threshold is set at 0.5 P ,where P is average power (summation of square ofsignal). For the end point, the threshold is set at 0.1P .
The start point threshold is set larger because the startpoint pitch should be correct.
The search rate, which depends on a threshold α(0 ≤ α≤ 1), is defined as the average of precision rate
NC/ND and recall rate NC/NT, where NC, ND, and NT
represent the number of similar terms to the humming
query in detected terms, the number of detected terms
by mp-CDP, and the number of similar terms to thehumming, respectively. The detected term by mpCDP is correct if the following overlapping rate
similar term ∩ detected term
overlapping rate =similar term ∪ detected term

is greater than 0.5. This means the overlapping terms
between similar and detected ones has 70%
intersection when lengths of both terms are mutually
identical. Since the search rate depends on threshold α,"the search rate for a humming query" is defined as
the maximum value running over all α. The computer
for this experiment is OS: Windows2000, CPU:
Pentium IV 1.5GHz.

4.2 Results
Table 1 shows average search rates and search times
for 5 persons × 20 songs = 100 queries for query
duration of 20 seconds. Those results show that s-

CDP reduced search time to about 1/40. The mpCDP
has 60 times the local path calculation because it has
60 steps in pitch axis. The reduction effect is only
about 1/40 because s-CDP calculates the start pointand has three times the number of local similarities.
The s-CDP search rate was lower by 16%, though it ismore than 70%, showing practical usefulness.

Table 1: Comparison of the two search methods.
Search method

mpCDP

s-CDP

Average search
rate

89.0%

73.3%

Search time532(s)

14.2(s)5. RETRIEVAL SYSTEM
We made a humming retrieval system as shown in
Figure 7. From the top window, the query wave, thequery pitch sequence, similarities in the database, andhit results are shown. On clicking the peak on thesimilarities or the hit results, similar intervals of video
or music are played in the right-bottom window.
Using a notebook PC with a Pentium III 750MHz
CPU, retrieving a 10[s] query from 60[min] database
took about 10 seconds. There are several similarity
peaks in Figure 7 because the same song was recorded
from a TV program and a radio program and also thesong had several repeated melodies. Retrieving froman audio video database that captured a scene fromkaraoke has been successful with this system, which
will be demonstrated in presentation.

Figure 7. Monitor of the developed retrieval system.

6. SUMMARY[3] Sonoda T., Goto M., and Muraoka Y.: A WWW-

based Melody Retrieval System, ICMC’98 Proc.,
1998, 349-352.

We proposed a start frame feature dependent
continuous DP assuming that the start point pitch of
the extracted optimal interval is correct. Test results
showed that the proposed method reducescomputational costs to about 1/40.

[4] Kosugi N., Nishihara Y., Sakata T., Yamamuro

One method for further reducing retrieval time is tocompress similar intervals in the database because asong usually has a repeated melody.

[5] Hashiguchi H., Nishimura T., Takita J., Zhang J.

7. REFERENCES[6] Goto M.: A Predominat-F0 Estimation Method[1] Kageyama T., Mochizuki K., and Takashima Y.:

Melody Retrieval with Humming, ICMC Proc.,
1993, 349-351.
[2] Asif Ghias and Logan J.: Query By Humming –Musical Information Retrieval in an Audio
Database, ACM Multimedia '95, Electronic Proc.,
1995.

M., and Kushima K.: A practical Query-byHumming system for a large music database,
ACM Multimedia 2000, 333--342.
X., and Oka R.: Music Signal Spotting Retrieval
by Humming Query Using Model Driven PathContinuous Dynamic Programming, SCI2001,
for CD Recordings: MAP Estimation using EM
Algorithm for Adaptive Tone Models, Proc. of
ICASSP 2001.
[7] Oka R.: Continuous word recognition with

Continuous DP (in Japanese), Report of the
Acoustic Society of Japan, S78-20, 1978, 145-152.