Publication
Musical Alignment Using Globally Optimal Short-Time Dynamic Time Warping
Hagen Kaprykowsky; Xavier Rodet
In: Proceedings of the Deutsche Jahrestagung für Akustik. Deutsche Jahrestagung für Akustik (DAGA-07), Fortschritte der Akustik, March 19-22, Stuttgart, Germany, DAGA, 2007.
Abstract
Dynamic Time Warping (DTW) aligns two sequences by time warping them optimally. Global optimization is done using whole sequences. This can be very demanding in terms of calculation costs and memory requirements which means the sequence length that is possible to align is limited. In this paper a novel algorithm Short-Time Dynamic Time Warping (STDTW) is presented, which requires much less memory because optimization is done iteratively on smaller portions of the sequences. The particularly remarkable characteristic of the algorithm is that it finds the same globally optimal solution, under some weak hypothesis as the classical DTW algorithm. As an example, STDTW is applied to Musical Alignment which links events in a musical score and points on a audio performance time axis. It also provides an interesting insight into the structure of the sequences to be aligned.