The MUSART Testbed for Query-By-Humming Evaluation

Music Information Retrieval has become an active area of research motivated by the increasing importance of Internet-based music distribution. In December 2003, Apple Computer announced it was selling almost 1.5 million music downloads per week (www.apple.com/pr/library/2003/dec/15itunes.html), and some analysts predict that downloads will account for 33 percent of the music industry's sales by 2008 (Zeidler 2003). Online catalogs are already approaching one million songs, so it is important to study new techniques for searching these vast stores of audio.

One approach to finding music that has received much attention is Query-by-Humming (QBH). This approach enables users to retrieve songs and information about them by singing, humming, or whistling a melodic fragment. In QBH systems, the query is a digital audio recording of the user, and the ultimate target is a complete digital audio recording. The audio waveforms of the query will have little or no direct similarity to those of the target audio recording, so QBH systems always search using some other representation. Most commonly, this representation is a sequence of notes described by pitch and duration. It is possible to transcribe monophonic queries into note sequences (although accurate transcription of the monophonic voice is still an active research area). Polyphonic target music, however, cannot be automatically transcribed into melodies. Therefore, most QBH systems assume that a MIDI or symbolic representation is available from which a note sequence can be derived.

Our system uses a database consisting of standard MIDI files, so one can state the QBH problem as follows: "Given a user's audio query, find matching melodies in a database of standard MIDI files." Once the melody is identified, the QBH system might offer links to audio files, ring tones, album titles, card catalog information, sheet music, or other useful data.

While many researchers have investigated related problems and have built prototype systems, there have been few systematic investigations of different solutions. It is difficult to compare different studies, because there are no standard databases adopted by the community of researchers, and intellectual property issues inhibit the sharing of music to form a standard database. Our work aims to evaluate different techniques for QBH using a common framework, the MUSART testbed, so that we can obtain quantitative information about the relative performance of different search techniques.

We hope to work with other researchers to compare other systems in the future. One conclusion of our work is that merely reporting data such as "90 percent of the time, the correct song is included in the 10 closest matches" is not very meaningful. Performance is highly sensitive to the quality of the queries and the material in the database. Therefore, it is important to compare search algorithms using a common set of queries and data. We have compared three classes of algorithms in this manner.

Another result of our work is a method for studying how retrieval precision is affected by the size of the database. Because it is difficult to construct a large music database for research, we would like to have some idea of how performance will scale as databases grow large. We present some evidence that retrieval rates fall very slowly as the database size increases. This trend is simple to compute and could be useful to predict performance for any retrieval system.

In the next section, we describe our project, the motivation, and the origins of this research in more detail, followed by the software architecture of our testbed. Then, we describe three different search systems that we have studied. Next, we describe the performance of these search systems in our testbed, followed by the general sources of error we observed that limit QBH performance and a discussion of searching performance as databases grow. Finally, we present a general discussion and conclusions.

The MUSART Project

The MUSART project is a collaboration between the University of Michigan and Carnegie Mellon University. Together, we have been exploring the design of QBH systems (Birmingham et al. 2001; Hu and Dannenberg...