A WWW-based Melody Retrieval System
Tomonari Sonoda Masataka Goto Yoichi Muraoka
School of Science and Engineering, Waseda University
3-4-1 Ohkubo Shinjuku-ku, Tokyo 169-8555 JAPAN
sonoda@muraoka.info.waseda.ac.jp, goto@etl.go.jp, muraoka@muraoka.info.waseda.ac.jp
ABSTRACT: This paper describes a WWW-based melody retrieval system which takes a sung melody as a queryand retrieves the song’s title from a music database. In previous works, the pitch information was mainly used as asearch clue while the span information was not used effectively, and it was difficult to improve the matching accuracy
by using only the pitch information. We therefore propose the following two methods for effective matching: a method
for obtaining search clues with the maximum quantity of information from pitch and span and a method for effectively
reducing the number of answer candidates.

1Introduction

WWW-based melody retrieval services that utilize a sung melody as a query require a reliable retrieval method that isrobust enough to deal with anonymous users’ inputs.
The main issue in building a melody retrieval system is that an input melody can consist of various errors which arecaused by the uncertainty of the user’s memory or by the user’s singing ability. Those errors are usually tolerated byusing several thresholds and converting the input melody into approximate relative-value sequences of pitch change(the pitch difference between adjacent notes) and of span change (the inter-onset interval ratio of adjacent notes). For
instance, an approximate relative-pitch value is expressed by using three characters (U (p), D (own), and E(qual)), andthe sequence “do-re-mi-mi-re-do” is converted into “X-U-U-E-D-D” (“X” indicates the first note which does not have arelative value). These approximate sequences are then utilized in the matching process which compares the input withall songs in a database.
Previous melody retrieval systems [Kageyama et al., 1993; Ghias et al., 1995] utilized static heuristic thresholds toobtain these approximate sequences. Since it was difficult to determine the optimum thresholds for all songs, thosesystems did not take advantage of the span information which can potentially be useful. Moreover, the public use ofmusic databases over the network was not considered.
We therefore propose the following two methods for effective DP matching. The first method, dynamic thresholddetermination, can obtain the approximate relative-value sequence of pitch/span with the maximum quantity of information by determining thresholds dynamically. The second method, coarse-to-fine matching, effectively reduces thenumber of answer candidates by considering the trade-off between coarse matching and fine matching. Coarse matching
can tolerate input errors but it can not reduce the number of answer candidates while fine matching does the opposite.
In our experiment, the matching accuracy of our system was 98 % when we used 112 inputs from 12 subjects, which
is high enough for melody retrieval services over the network.

2

WWW-based Melody Retrieval System

Figure 1 is an illustration of our retrieval system. The system consists of a database server and JAVA Applet clients.
This section describes each process of them and proposes two methods for effective matching.

2.1

User-side Client

ClientUserA/DExtracts
conversion
The main function of each client is to extract the pitch and span
pitch/span
Shows
information from a user’s input. After A/D conversion, the client
the result
detects the frames that have voiced sounds and determines the pitch
relativeranked
sequences ofsong
and span values of each note during those frames. The client conpitch/span
Servertitles
databaseverts the pitch and span values into the relative-values of pitch andDP
matching
span and transmits the relative-value sequences of pitch and spanto the server. The client then shows a list of song titles received
from the server.
Figure 1: WWW-based melody retrieval system.
The process which the client uses is as follows.
 Input a sung melody - The client allows a user to sing from an arbitrary part of a song and to choose an arbitrary
key and tempo. The client assumes that each input note begins with a voiceless consonant and ends with a vowel(e.g. ta-ta-ta, cha-cha-cha).
 Detect voiced sound frames - The length of each frame is defined as 16 msec. On the assumption that environmental sounds are not included in the input, the client regards the frames with enough amplitude as voiced soundframes.
 Estimate pitch and span values - The span of each note is defined as the inter-onset interval, which is the numberof frames between the adjacent onset times. The onset time is the first frame of the successive voiced sound frames.

1The pitch of each note is defined as the highest pitch value of all the frames during its span. We use FFT to estimate
the pitch value of each frame.
 Determine relative-pitch/span values - The relative-pitch value is the normalized pitch difference between theadjacent notes in which a semitone difference is normalized to the value of 100. On the other hand, the relative-spanvalue is the ratio of the span value to its previous value and is represented by percentage.

2.2

Song Retrieval Server

The main function of the database server is matching. The server receives an input melody from a client and ranks song
titles in an order based on the distance calculated by DP matching between the input melody and each song of its music
database. The server then transmits the list of the ranked song titles to the client as a matching result.
The process which the server uses is as follows.
 Music Database - The database consists of a number of songs, which can be inputted by singing. For each song,the database stores its title and the relative-value sequences of the pitch and span.
 DP matching - The distance between the input melody and each database song is the sum of the pitch and spandistances. The pitch and span distances are respectively calculated by DP matching that utilizes the approximate
relative-pitch/span values categorized by several thresholds.

2.3

Methods for Effective Matching

The most important point in the whole process is determining the thresholds to categorize the relative-pitch/span values
since it directly has a great influence on the accuracy of the matching. Because previous methods utilized static heuristic
thresholds, they had the following problems.
1. The span information was not utilized effectively since it was difficult to determine the appropriate thresholds forcategorization.
2. It was difficult to reduce the number of answer candidates because several songs in a large database tended to havethe same patterns of the approximate relative-value pitch/span sequences.
In order to solve these problems, we propose the following two methods.
1. Dynamic Threshold Determination- This method is used to determine the optimum thresholds by utilizing thehistogram of relative-pitch/span values of all the songs in the database.
2. Coarse-to-Fine Matching- This method is used to effectively reduce the number of answer candidates by gradually increasing the number of categories of relative-values used in the DP matching.
These methods are respectively described in the following two sections.

3Dynamic Threshold Determination

This section describes the problem found in threshold determination and proposes the algorithm of the dynamic threshold determination method.

3.1

Figure 2 and 3 respectively illustrates the histogram ofrelative-pitch/span values that appear in all of the databasesongs we have utilized in this study. The x-axis shows therelative values; the relative-pitch value is normalized so thata semitone difference has the value of 100, and the relativespan value is represented in percentage. The y-axis shows thefrequency of the relative-values.
Previous systems [Kageyama et al., 1993; Ghias et al.,
1995] mainly utilized three categories for obtaining approximate relative-pitch/span values such as U(p), E(qual), andD(own) for pitch, and L(onger), E(qual), and S(horter) forspan. [Kageyama et al., 1993] utilized pitch thresholds of+100 and -100 and span thresholds of 50 percent and 200percent. While the pitch thresholds, shown at the top of Figure 2, divided the relative-values equally, the span thresholds,
shown at the top of Figure 3, did not divide the span values
successfully. Since most relative-span values were categorized in the middle part (E), several database songs had similar
sequences, and the span information was not effectively used
for the search clue. It was, however, difficult to heuristicallydetermine the optimum thresholds especially for span.
2100-100

frequencyof values

Thresholds for Categorization

D

previous thresholds
EU

E0

U
200

400
300
200
1000D-400 -200-112

400

relativepitch value

105 dynamic thresholds

Figure 2: Histogram of the relative-pitch values.
frequencyof values 50
S
1200

E200
previous thresholds
L

1000
800
600
400
2000（％）
400
200300relativeELspan value
87 115 dynamic thresholds

1000S

Figure 3: Histogram of the relative-span values.

We therefore propose a dynamic threshold determination method which can obtain optimum thresholds dynamically.
Those dynamic thresholds for pitch/span are shown at the bottom of Figure 2 and 3. This method considers suchhistograms of all the songs in the database in order to determine the thresholds so that each category has an equalamount of relative-value frequencies. Since each pitch/span value has the maximum quantity of information, bothsequences are able to be utilized effectively for search clues. Moreover, this method facilitates creating any number ofcategories in order to generate approximate relative-value sequences. If three categories are not enough to reduce thenumber of answer candidates, more categories can be utilized. This enables to use coarse-to-fine matching which isdescribed in the section 4.

3.2

Algorithm for Dynamic Threshold Determination

The algorithm for dynamic threshold determination is as follows.
1. Make the relative-pitch/span histogram like Figure 2 or 3.
2. Count all of the relative-pitch/span values in all of the database songs, and let it be S um.
3. Assume that the number of category is C ategoryN um, and that the average number of values that each category
has is defined as Ave = S um=C ategoryN um.
4. Determine threshold(j ); (j = 0; 1; :::; C ategoryN um 0 1) so that the number of frequencies in each category isas equal to Ave as possible.
With these thresholds, the relative-pitch/span values of the input and each database song are converted into approximate values.

4Coarse-to-Fine MatchingThis section describes the problem in reducing the number of answer candidates and proposes the algorithm of thecoarse-to-fine matching method.

4.1

Answer Candidates Reduction

If relative-pitch/span values are coarsely categorized into threeCategories
parts, the more songs a database has, the more difficult to reduce
1st step
UED(3)
the number of answer candidates since the same melody patterns
DP Matchingare likely to appear in several songs. On the other hand, if too
If the number of answer
candidates is not reduced
many categories are used for finer matching, the retrieval result
enough.
is easily affected by the input errors and fluctuations.
2nd stepU1 U2 U3 E1 E2 E3 D1 D2 D3(9)
We propose a method which takes advantage of both coarse
DP Matching
matching and fine matching. We call this method coarse-to-fine
If the number of answer
candidates is not reduced
matching since the basic idea came from the pattern matchingenough.
technique for images that takes coarse matching first and then
3rd step(27)
takes finer matching after that. Figure 4 shows an example ofFigure
4: Example of coarse-to-fine matching.
the method used for pitch. In converting a relative-pitch sequence
into an approximate one, our system first uses the three categories(U, E, and D) for the coarse matching. It then repeats the finer matching, and increases the number of categories until
the number of answer candidates is reduced to one.

4.2

Coarse-to-Fine Matching Algorithm

We assume that input relative-pitch/span sequences Qp =Qs are converted into approximate relative-value sequences
QRp =QRs , and that relative-pitch/span sequences of a database song Sp =Ss are similarly converted into S Rp =SRs .
Our system calculates the distance between QRn (n = p; s) and each SRn from the database songs by DPmatching. If the number of answer candidates are not reduced enough, the system prunes several songs thatare ranked lower in the matching, and converts the pitch/span sequences of the higher-ranked songs into finer
sequences by increasing the number of categories. If the number of categories is increased M times such as
C ategoryN um(0); C ategoryN um(1); :::C ategoryN um(M 0 1)(C ategoryN um(i) < C ategoryN um(i + 1); i =0; 1; 2; :::; M 0 1), the coarse-to-fine matching algorithm is as follows.
1. Set i = 0.
2. To generate the QRn (i) and SRn (i), each relative value in Qn and Sn is categorized into C ategoryN um(i) partsby the set of dynamic thresholds DT H (i).
3. For all database songs, the distance Dn between each QRn and SRn is calculated and ranked in order of distance.
4. Take N (i)(N (i) > N (i + 1)) songs from the top of the ranked songs.
5. If several songs from N (i) songs have the same values of Dn , the system assumes that the number of answer
candidates have not been successfully reduced. In that case, it increases i and repeats the process from 2. to 4.
while i < M or the number of answer candidates are not reduced enough. Otherwise, if all Dn from N (i) differfrom one another, the answer candidate is successfully found and it stops the coarse-to-fine matching method.
35Experiments and Results

In this section, we evaluate the two proposed methods and verify their effectiveness. We then evaluate the overall
performance of our system.

5.1

Experimental Conditions

Our system consisted of a database retrieval server on WWW, which was written in Java, and user-side JAVA Applet
clients with a specially designed Netscape Plug-in for recording an input sung melody. In our experiment, the server
had a 200 song database which contained various genres of songs such as rock, pop, and folk music.
We tested our system using 112 inputs from 12 subjects (8 men and 4 women). The matching accuracy was evaluatedin 3 ways; (1) used only span for retrieval, (2) used only pitch, (3) used both pitch and span. The recording time waslimited within 8 seconds and the sampling rate was 8 kHz. FFT with 512 points a frame (16 msec) was utilized toconvert the acoustic data into melody data.

5.2

Evaluation for Dynamic Threshold Determination

We compared the performance of our dynamicTable 1: Performance of dynamic thresholds.
thresholds with previous thresholds [Kageyama et al.,pitchspan
pitch and span
1993] that used pitch thresholds of +100 and -100 andprevious thresholds 47.3% 13.4%
90.2%
span thresholds of 50 percent and 200 percent. Table
dynamic thresholds 49.1% 35.1%
97.3%
1 shows the result when we utilized three categories to112 inputs for 200 songs.
determine the dynamic thresholds. The matching accuracy for the dynamic thresholds obviously improved when we used the span information, and the accuracy of both
pitch and span information also improved.

5.3

Evaluation for Coarse-to-Fine Matching

We tested the robustness against the input errors
by comparing normal DP matching with coarse-to-finematching. The normal DP matching utilized 27 categories for the approximate relative-pitch/span values,
and the coarse-to-fine matching utilized 3 steps to increase the categories (3, 9, 27). We intentionally added
errors to the input melodies so that each song had 2 pitch
errors (added +200 or -200 to 2 relative-pitch values thatwere randomly selected) and 2 span errors (changed theratio of the relative-span to 4 times of its value or to aquarter of its value). Table 2 shows the result with noinput errors, and Table 3 shows the result with input errors. The tables show that the coarse-to-fine matching
was robust enough to tolerate the input errors.

5.4

Table 2: Matching accuracy with no intentional errors.

normalcoarse-to-fine

pitch
87.5%
83.0%

span
82.1%
79.5%

pitch and span
97.3%
98.2%

112 inputs for 200 songs.
Table 3: Matching accuracy with intentional errors.

normalcoarse-to-fine

pitch
75.9%
80.3%

span
34.8%
50.0%

pitch and span
90.1%
94.6%

112 inputs for 200 songs.
Table 4: Matching accuracy of the system.

ranked in the top
ranked in top 3

pitch
83.0%
88.4%

span
79.5%
88.4%

pitch and span
98.2%
100.0%

112 inputs for 200 songs.

Matching Accuracy of the System

The matching accuracy of our system with the two proposed methods is shown in Table 4. The result shows that oursystem achieved an accuracy high enough for WWW-based melody retrieval services.

6Conclusion

We described a system that enables a user to retrieve a song’s title from a music database by singing via WWW. For aneffective DP matching, we proposed two methods, dynamic threshold determination and coarse-to-fine matching, andwe achieved higher matching accuracy than the previous methods.
The current system utilized a fixed music database which was prepared in advance. There are, however, a lot of songdata that are open to public on the Internet. We therefore plan to build a WWW Search Robot for such song data andwe plan to extend the system so that it can retrieve various songs from WWW databases all over the world.

References[Ghias et al., 1995] Asif Ghias and Jonathan Logan : Query By Humming – Musical Information Retrieval in an Audio
Database, ACM Multimedia 95, Electronic Proc., 1995.
[Kageyama et al., 1993] T.Kageyama, K.Mochizuki, and Y.Takashima : Melody Retrieval with Humming, ICMC Proc., pp.349351, 1993.

4