Dynamic programming in transposition and time-warp invariant polyphonic content-based music retrieval

Mika Laitinen, Kjell Lemström

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

We consider the problem of transposition and time-warp invariant (TTWI) polyphonic content-based music retrieval (CBMR) in symbolically encoded music. For this setting, we introduce two new algorithms based on dynamic programming. Given a query point set, of size m, to be searched for in a database point set, of size n, and applying a search window of width w, our algorithms run in time O(mnw) for finding exact TTW Ioccurrences, and O(mnw2) for partial occurrences. Our new algorithms are computationally more efficient as their counterparts in the worst case scenario. More importantly, the elegance of our algorithms lies in their simplicity: they are much easier to implement and to understand than the rivalling sweepline-based algorithms. Our solution bears also theoretical interest. Dynamic programming has been used in very basic content-based retrieval problems, but generalizing them to more complex cases has proven to be challenging. In this special, seemingly more complex case, however, dynamic programming seems to be a viable option.
Alkuperäiskielienglanti
OtsikkoProceedings of the 12th International Society for Music Information Retrieval Conference
Julkaisupäivä2011
Sivut369-374
TilaJulkaistu - 2011
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa

Siteeraa tätä