Music Signal Spotting Retrieval by a Humming Query
Hiroki Hashiguchi†, Takuichi Nishimura†∗ , Junko Takita‡,
J. Xin Zhang††, and Ryuichi Oka†
† Real World Computing Partnership
1-6-1 Takezono Tsukuba-shi, Ibaraki 305-0032, JAPAN‡ Mathematical Systems Inc.
2-4-3 Shinjuku, Shinjuku-ku, Tokyo, 160-0022, JAPAN†† Mediadrive Corp.
3-195 Tsukuba, Kumagaya-shi, Saitama, 360-0037, JAPANABSTRACTThis paper presents a method to retrieve similar intervals of feature sequence of music acoustic data by using a query sequence composed of intervals extractedfrom a humming or singing wave data. The method iscalled “Model driven path Continuous Dynamic Programming (mp-CDP)” which is a modiﬁcation of Continuous Dynamic Programming (CDP) commonly used
for spotting retrieval. The key feature of mp-CDP isto determine variations of the local path of CDP in advance by a reference sequence pattern which is a model
to be matched. The paper conﬁrms the usefulness ofthe proposed method based on retrieval experimentsfor 20 popular music tracks in WAV format.
1.

INTRODUCTION

Interesting researches on the use of multimedia databases
and their retrieval methods have spread throughout
the world, thanks to the ready availability of highperformance, low-cost personal computers. Such databases
include image, audio and video data in addition to traditional text and numerical data. The retrieval system
requires the convention of a human interface, highspeed processing and accurate searching. Oka [5],a co-author of this paper, proposed Continuous Dynamic Programming (CDP) in order to create a spotting retrieval system in the ﬁeld of voice recognition.
In this paper we describe a melodic matching method
for musical acoustic data by a humming query. Thismethod is an extension of CDP and is called “Modeldriven path Continuous Dynamic Programming (mpCDP)”. Another aim is to develop a retrieval system∗ Presently he is working for National Institute for Advanced
Industrial Science and Technology (AIST), Cyber Assist Research Center

for music tracks by humming.
Several previous works conﬁrmed that a music retrieval system actually realized. Ghias et al. [1],Kageyama and Takashima [3] and Sonoda et al. [6]used an alphabet of three possible relationships between pitches (‘U’, ‘D’, and ‘S’), representing the situations where a note is above, below or the same as
the previous note. Kosugi et al. [4] developed a music retrieval system by humming based on beats instead of notes and reported that the retrieval time isat most one second for over 10,000 songs. Their goal
was that they used MIDI data or human humming as adatabase, so it is much easier to extract from melodies
such data than from musical audio signals.
The key feature of this paper is to determine melody
likeness from musical audio signals and to compare themelody likeness in a music database with the pitch sequence of a humming query.
This paper is divided into ﬁve sections. In the next
section we outline the retrieval system for a humming
query. Section 3 deals with mp-CDP which is central
to this paper. In Section 4 we experimentally validate
mp-CDP based on retrieval experiments for 20 popular music data in WAV format. Finally, Section 5summarises conclusions and directions of future work.
2.

MUSIC SIGNAL RETRIEVAL SYSTEMBY HUMMING

As shown in Figure 1, we organize the retrieval system into the following principal procedures: extracting from humming/music as the feature vector, matching the mutual features, and playing the detected parts
from a music database. In Figure 1 the notation x represents a music note and t represents time or a frameof FFT.

Figure 1: Outline of a music signal retrieval system using a humming query

In order to acquire the pitch sequence extracted
from humming, we carry out FFT with a harmonic
process. Each pitch transposes the corresponding note.
In a similar manner to the above process, we acquire
some melody likeness in music based on the powers
analyzed by FFT.
The mp-CDP matching method ﬁnds successivenotes in music that have similar intervals and tempos
to the ones of the humming query
3.
3.1

MODEL DRIVEN PATH CDP(MP-CDP)Overview

A new method called “mp-CDP ” ﬁnds paths having
the approximately maximum similarity accumulatedwith local paths in a 3-dimensional lattice, while theordinal CDP walks in 2-dimensional lattice. The mpCDP diﬀer from the ordinal CDP as follows:• The database as an input is represented by music note and time sequences in a 2-dimensionallattice, and• A humming query is represented by a scalar vector whose element is an interval of music notes.
Figure 2 shows the conceptual diagram of mp-CDP. The horizontal axis represents notes and the verticalaxis represents the frames for query in Figure 2–(a).
Being able to move parallel in the (x, τ )-plane permits
any transposition of a humming query.
Figure 2–(b) shows the projection of the note axis
x onto (t, τ )-plane and permits time elasticity fromhalf to the twice of humming duration in the samemanner as ordinary CDP. A small diﬀerence in tempo
between humming and music is shown to be acceptablein Figure 2–(b). Figure 2–(c) shows the integrationof the permission for transposition (a) and the timeelasticity (b) in 3-dimensional space. When τ = T ,Figure 2–(d) shows the variety of cumulative similarity
S(x, T, t). The mp-CDP method detects the path forwhich S(x, T, t) is maximum.
3.2

FormulaLet fb [Hz] denote the lowest frequency of melody. We
compute the melody likeness for the frequency 2x/12 fb[Hz] through the FFT analysis and we write the sequence of the likeness of size W as It (x) (t = 1, . . . , W ,x = 1, . . . , N, 0 ≤ It (x) ≤ 1). Here 2N/12 fb [Hz] represents the highest frequency which compose melody.
Here the melody likeness It (x) is based on the power
spectrum in consideration of harmonic structure of
acoustic signals [2].
In a similar manner, we obtain the sequence ofthe degree of belief for pitch Rτ (x) (τ = 1, . . . , T ,x = 1, . . . , N, 0 ≤ Rτ (x)) from a humming query.
This belief Rτ (x) is based on the power spectrum inconsideration of harmonic structure; see Hashiguchi etal. [2] for details. Therefore, if Rτ (x) is very small, sayRτ (x) <  for a suitable threshold , the corresponding
frame (τ ) must be a silent period. We derive the notenumber on each frame asxτ = arg max Rτ (x)1≤x≤N

and brieﬂy write its power asR (τ ) = Rτ (xτ ).

S(x q(τ ), τ 1, t 2)
+ 2d(x, τ, t − 1) + d(x, τ, t);S(x − q(τ ), τ − 1, t − 1)
(3)
max+ 3d(x, τ, t);S(x − q(τ ) − q(τ − 1), τ − 2, t − 1)
+ 3d(x − q(τ ), τ − 1, t) + 3d(x, τ, t);where the boundary conditions for d(x, τ, t) and S(x, τ, t)satisfyd(x, τ, t) = S(x, τ, t) = 0. (x ≤ 0 or τ ≤ 0 or t ≤ 0).
The value S(x, τ, T ) when the frame τ arrives at T is
divided by the constant 3Tv so that it can be normalized from 0 to 1 where Tv is the number of non-silences
in a humming query. The ﬁnal result of mp-CDP isa collection of (x, t)’s which attain the approximately
maximum value of S(x, T, t), i.e., for a given threshold
α (0 ≤ α ≤ 1) the following result is obtained;1
S(x, T, t) > α(4)(x, t) |3Tv
and S(x, T, t) is a local maximum value .

4.
4.1

Figure 2: Conceptual diagram of mp-CDP

Without loss of generality, the powers R (τ ) for theﬁrst and the last frames（τ = 1 and T ) are assumed
to be greater than .
A sequence of intervals is given by the diﬀerenceof successive notes. Now consider the frame τ and its
nearest frame τ  < τ whose power is greater than ,τ  = max{τ ∗ | R (τ ∗ ) > }∗τ <τ

we deﬁne the interval q(τ ) at τ (τ = 1, . . . , T ) as

if τ = 1;
x1 ,q(τ ) = xτ − xτ  , if τ ≥ 2 and R (τ ) > ;0,otherwise
If R (τ ) > , the interval q(τ ) means the diﬀerence
between the current note and the previous one at thenearest frame τ  with R (τ  ) > . Then we deﬁne thelocal similarity d(x, τ, t)，and the cumulative similarity S(x, τ, t) as the following equations (1) ∼ (3):It (x), if R (τ ) > d(x, τ, t) =(1)0,otherwise
S(x, 1, t) = 3d(x, 1, t);S(x, τ, t) =(2)RETRIEVAL EXPERIMENTMusic database and humming queriesWe prepared 20 WAV ﬁles in 16 kHz sampling andmonaural recording as the music database to test themp-CDP matching method. This database includes
10 Japanese pops, 8 children’s songs, an animation
song and a Japanese enka. There are 4 male and 16
female vocal artists in the database. On the otherhand, 3 males and 2 females sang a part of each songin the database for about 20 seconds. Hence, the total
number of queries of 20 second duration was 300. To
investigate the eﬀect of the length of queries, we prepared shortened queries of 5 and 10 seconds from the20-second originals. We adopted FFT analysis (2048samples for each frame, 64 msec frame interval) for extracting features from both the music signal database
and the humming signal data.
4.2

Search rate for music database and queries

The search rate, which depends on a threshold α(0 ≤α ≤ 1), is deﬁned as the average of precision rate
NC /ND and recall rate NC /NT , where NC , ND andNT 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 the humming, respectively. The detected term by
mp-CDP is correct if the following overlapping rate:
overlapping rate =similar term ∩ detected term
(5)
similar term ∪ detected termSearch rate
Table 1: Average of search rates (%)
Query duration
5s
10s
20s
Average search rate 55.3% 73.9% 89.0%

100PersonAB
CD
E

90
80
70Rate (%)

60

10050
51015

2090
8020s

7010s

60

5s

Music numberFigure 4: Search rate of each son for ﬁve persons(Query duration 10 s).

50A

BC

DE

PersonFigure 3: Average of search rate of each person forthree diﬀerent query durations

Search rate
10080
60
40

is greater than 0.5. This means the overlapping terms
between similar and detected ones has 70-% intersection when the lengths of both terms are mutually thesame. Since the search rate depends on the threshold
α, “the search rate for a humming query” is deﬁned
as the maximum value running over all α.
4.320s 10s 5s

205101520Music number
Figure 5: Average of search rate of each song for three
diﬀerent query durations

Experimental results

Table 1 shows the average of the search rate for 5 persons×
20 songs = 100 queries for the query duration of 20
seconds. Furthermore, Table 1 also shows the averagefor the query duration of 5 seconds and 10 seconds.
Figure 3 shows the average of the search rate for 20
songs for each person and Figure 5 shows the averageof the search rate for 5 persons for each song. Persons
A, B and C are male, and the others are female.
The experimental results are summarized below.
• From the results of Table 1 the longer the duration of a query, the higher the average. If theduration of a query is short, there will be manysimilar terms to the query in the music database.
• From Figures. 4 and 5, the average for songs 8
and 14 is lower than the others on every persons. Comparing disirable terms with undisirable detected terms in originals by playing, weconﬁrmed that these terms are similar to eachother.
• For song 3 (female vocal), the search rate for thequery 20s of Male A is 58 %, while that of FemaleD is 100 %. The sequences of notes for staﬀ,
Male A and Female D are shown in Figure 6–(a), (b) and (c). This humming of Female D
is probably better than that of Male A. This
result shows that the similarity in (3) as well as
the search rate reﬂect the goodness of humming.

5.

CONCLUSIONS

We have proposed a methodology for matching piecesof music accoding to the similarity of melody likenessand the pitch of humming. The mp-CDP matching
method is eﬀective for queries of about 5 to 20 seconds
and a music database containing clear, melodic songs.
The computing time for retrieval is directly proportional to the duration of the humming query. The
computing time requried, for each 5 second query was,about 1/40 of the database length on the current fastest
machine (OS: Windows 2000, CPU: Pentium IV 1.5

GHz). For 10 or 20 queries, the retrival time took
about 1/20 or 1/10 of the music database length. Reduction of retrieval time is a feature task. One possible solution for the reduction is to project the 3dimmensional searching space to 2-dimensional spaceand to compress the similarity terms in the database.

Pitch (x)40

ACKNOWLEDGMENT
The authors are very grateful to Dr. Junichi Shimada, a managing director of RWCP, who has not
only given them constant advice on this research, but
has also provided a superb research environment. We
wish to thank Mr. Hironubu Takahashi, Mr. Yasuhiro Mori of RWCP, Mrs. Shinobu Ogi, Mr. Michinao Mizuno of Mathematical System Inc. and Mrs.
Megumi Nishimura for their assistance in collecting
humming query data.
REFERENCES

353025201510τ501001502002503005010015020025030050100150200250300(a) Pitch sequence extracted from the melody ofmusic 3Pitch (x)4035[1] A. Ghias, J. Logan, D. Chamberlin and B. C.
Smith, Query by humming – Musical Information
retrieval in an audio database. In ACM Multimedia 95–Electronic Proceedings, 1995.
[2] H. Hashiguchi, T. Nishimura, J. X. Zhang, H.
Takahashi and R. Oka. Model driven path CDP
for music retrieval with humming query (inJapanese). Technical Report of IEICE, PRMU2000-66 (2000-09), pp. 35–40, 2000.
[3] T. Kageyama and Y. Takashima. A melodyretrieval method with hummed melody (inJapanese). Transactions of the Institute of Electronics, Information and Communication Engineers (D-II), Vol. J77-D-II, No. 8, pp. 1543–1551,1994.
[4] N. Kosugi, Y. Nishihara, T. Sakata, M. Yamamuro and K. Kushima, “A practical Query-byHumming system for a large music database”,
ACM Multimedia 2000, pp 333–342, 2000.
[5] R. Oka. Continuous word recognition with Continuous DP (in Japanese), Report of the Acoustic
Society of Japan, S78-20, pp. 145–152, 1978.
[6] T. Sonoda, M. Goto and Y. Muraoka. A WWWbased melody retrieval system (in Japanese).
Transactions of the Institute of Electronics, Information and Communication Engineers (D-II),Vol. J82-D-II, No. 4, pp. 721–731, 1999.

3025201510

τ(b) Pitch sequence extracted from a humming queryindicating a high search rate.
Pitch (x)40353025201510

τ(c) Pitch sequence extracted by a humming queryindicating a low search rate.
Figure 6: Comparison of a music note sequences andextracted pitch sequences indicating high/low searchrate.