TRANSPOSITION AND TIME-WARP INVARIANT GEOMETRIC MUSIC RETRIEVAL ALGORITHMS
Kjell Lemström, Mika LaitinenAbstract
In this paper, we study the problem of transposition and time-warp invariant (TTWI) polyphonic content-based music retrieval (CBMR) in symbolically encoded music for which, to our best knowledge, no solutions exist. Representing music by sets of points in plane, we introduce two new algorithms for this setting. 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(mwn log n) for finding exact TTWI occurrences, and O(mnw² log n) for partial occurrences. The algorithms are related to our prior transposition and time-scale invariant (TTSI) algorithms. As local tempo changes and jittering are always present in real-world CBMR queries, any TTSI algorithm cannot provide a sufficient solution to the problem; the extra robustness of the new algorithms bridges this gap perfectly.
Read Submission [144]