FlatDTW – Dynamic Time Warping optimization for piecewise constant templates

Abstract The aim of this work is to construct and analyze a method of optimization of the Dynamic Time Warping (DTW) algorithm – a well-known and popular pattern recognition tool. DTW is typically used to evaluate the degree of similarity between time series subjected to non-linear time warping, which is a common problem i.a. in speech recognition, music information retrieval, motion analysis and gesture recognition. Based on the dynamic programming principle, DTW is computed efficiently in O ( N 2 ) time, which contributes to its popularity and makes it applicable in many real-time scenarios. In this paper we propose a method of DTW algorithm optimization in the case when one of the time series may be modeled as a piecewise constant sequence. Such sequences, composed of several “flat” sections, typically occur when real-world data are compared to some predefined templates, as in the task of matching a melody sung by a user to a MIDI-based template melody (a.k.a. Query-by-Singing/Humming, QbH). The modified DTW processes such templates in a more efficient way reducing the computational complexity. The obtained speed-up of the algorithm is not associated with any quality loss of the matching process results.