Implement Dynamic Time Warping Algorithm

Various implementations of Dynamic Time Warping ([login to view URL]) algorithms exist, written in almost any programming language. Common algorithms, however, do only compute the warping path which minimizes the DTW distance, i.e. find the best warping path. For my application, I need an implementation that finds the k-best paths. Algorithm details can be found in [1], where the authors introduce three algorithms to find the k-best warping paths (cf. Section 4.7.5). An implementation of a k-best paths algorithm is available as part of Sun’s mediaLib [2]. The k-best paths algorithm should be implemented in Python, on the basis of the DTW implementation in mlpy [3]. In mlpy, the DTW algorithm is implemented in C (dtwcore.c) for the sake of performance and a wrapper is available in Python (class Dtw in [login to view URL]). Project objectives: - Extend mlpy’s DTW algorithm - The constructor of the Dtw class should accept an additional optional argument k (number of best paths to compute) which defaults to 1. - The compute method returns an array of length k with the distances of the k best warping paths. Likewise, [login to view URL] and [login to view URL] are both arrays of length k that contain the px and py of the k-best paths. - The following assumptions / simplifications can be made for k>1: . derivative=False . startbc=True . wincond=”nowindow” . onlydist=False Please feel free to contact me should you require additional information. References: [1] Rabiner, Lawrence R.; Juang, Biing-Hwang (1993): Fundamentals of speech recognition. Upper Saddle River, NJ: Prentice Hall PTR (Prentice Hall signal processing series). [2] [login to view URL] [3] [login to view URL]~dfsg1-2/[login to view URL]