Algorithms for melody search and transcription

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-951-51-1702-1
Title: Algorithms for melody search and transcription
Author: Laaksonen, Antti
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Publisher: Helsingin yliopisto
Date: 2015-11-20
URI: http://urn.fi/URN:ISBN:978-951-51-1702-1
http://hdl.handle.net/10138/157624
Thesis level: Doctoral dissertation (article-based)
Abstract: This thesis studies two problems in music information retrieval: search for a given melody in an audio database, and automatic melody transcription. In both of the problems, the representation of the melody is symbolic, i.e., the melody consists of onset times and pitches of musical notes. In the first part of the thesis we present new algorithms for symbolic melody search. First, we present algorithms that work with a matrix representation of the audio data, that corresponds to the discrete Fourier transform. We formulate the melody search problem as a generalization of the classical maximum subarray problem. After this, we discuss algorithms that operate on a geometric representation of the audio data. In this case, the Fourier transform is converted into a set of points in the two-dimensional plane. The main contributions of the first part of the thesis lie in algorithm design. We present new efficient algorithms, most of which are based on dynamic programming optimization, i.e., calculating dynamic programming values more efficiently using appropriate data structures and algorithm design techniques. Finally, we experiment with the algorithms using real-world audio databases and melody queries, which shows that the algorithms can be successfully used in practice. Compared to previous melody search systems, the novelty in our approach is that the search can be performed directly in the Fourier transform of the audio data. The second part of the thesis focuses on automatic melody transcription. As this problem is very difficult in its pure form, we ask whether using certain additional information would facilitate the transcription. We present two melody transcription systems that extract the main melodic line from an audio signal using additional information. The first transcription system utilizes as additional information an initial transcription created by the human user of the system. It turns out that users without a musical background are able to provide the system with useful information about the melody, so that the transcription quality increases considerably. The second system takes a chord transcription as additional information, and produces a melody transcription that matches both the audio signal and the harmony given in the chord transcription. Our system is a proof of concept that the connection between melody and harmony can be used in automatic melody transcription.Väitöskirjan aiheena on kaksi musiikkitiedonhaun ongelmaa: melodian etsiminen audiotietokannasta sekä automaattinen melodian nuotinnus. Molemmissa ongelmissa melodia on esitetty symbolisesti eli melodia muodostuu nuottien alkukohdista ja korkeuksista. Väitöskirjan alkuosa esittelee uusia algoritmeja symbolisen melodian etsimiseen. Ensin tarkastelussa on tilanne, jossa audiodata on diskreettiä Fourier-muunnosta vastaavassa matriisimuodossa. Tällöin melodian etsiminen voidaan nähdä yleistyksenä klassisesta taulukon suurimman summan tuottavan välin etsimisestä. Tämän jälkeen käsittely siirtyy algoritmeihin, joissa audiodata on esitetty geometrisesti kaksiulotteisen tason pistejoukkona. Tärkeimmät kontribuutiot väitöskirjan alkuosassa liittyvät algoritmien suunnitteluun. Väitöskirja esittelee uusia tehokkaita algoritmeja, joista useimmat perustuvat dynaamisen ohjelmoinnin optimointiin. Tämä tarkoittaa, että dynaamisen ohjelmoinnin arvoja lasketaan tavallista tehokkaammin käyttämällä sopivia tietorakenteita ja algoritmien suunnittelun tekniikoita. Algoritmeja myös testataan todellisilla audiotietokannoilla ja melodiahauilla, mikä osoittaa niiden toimivuuden käytännössä. Verrattuna aiempiin tutkimuksiin väitöskirjan lähestymistavan etuna on, että melodian haku voidaan kohdistaa suoraan audiodatan Fourier-muunnokseen. Väitöskirjan jälkiosa keskittyy automaattiseen melodian nuotinnukseen. Koska ongelma on hyvin vaikea sellaisenaan, tutkimuskysymyksenä on, miten nuotinnusta voi helpottaa käyttämällä musiikillista lisätietoa. Väitöskirja esittelee kaksi melodian nuotinnukseen tarkoitettua järjestelmää, jotka pyrkivät erottamaan tärkeimmän melodialinjan audiosignaalista musiikillisen lisätiedon avulla. Ensimmäinen järjestelmä käyttää lisätietona ihmiskäyttäjän arvioita nuottien alkukohdista ja korkeuksista. Osoittautuu, että käyttäjät, joilla ei ole musiikkitaustaa, pystyvät tarjoamaan järjestelmälle hyödyllistä lisätietoa, jonka avulla nuotinnuksen laatu parantuu merkittävästi. Toisen järjestelmän lisätietona on sointukulku, joka kuvaa musiikin harmoniaa. Järjestelmä tuottaa nuotinnuksen, joka perustuu sekä audiosignaaliin että sointukulkuun. Järjestelmä on osoitus siitä, että melodian ja harmonian yhteyttä voidaan hyödyntää automaattisessa melodian nuotinnuksessa.
Subject: tietojenkäsittelytiede
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


Files in this item

Total number of downloads: Loading...

Files Size Format View
algortih.pdf 504.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record