Dynamic time warping

The dynamic time warping algorithm compares two sequences of points. A cost function is defined between each pairs of points. In our case, the cost function $f$ is the square of the euclidian distance between the points. The total cost of comparing two sequences is the sum of the cost for each corresponding point defined by the warping of time. We want to find the best warping that gives the lowest cost for comparing two sequences of points, that is two pathlets.

Since dynamic time warping assumes continuity and monotonicity of the time, the minimum cost can be computed recursively by computing the minimum cost between two sub-sequences starting at the origin, then stepping forward in time, either on one sequence or the other or both and computing the minimum cost between the new sequences by adding the cost of the newly matched points. Figure A.1 summarises the dynamic time warping algorithm.

Figure A.1: The dynamic time warping matching algorithm.

It is possible to retrieve the warp of time used to compute the minimum cost of matching two point sequences. Figure A.2 shows an example of the usual representation of that warp. The grid nodes store the similarity values between two subsequences built using the first elements of the point sequences. For instance the grid node circled in figure A.2 represents the similarity between subsequences built using the 5 first elements of one sequence and the 3 first elements of the other one. The arrows represent the optimal warp found between the two sequences. It is the path of lowest cost between the bottom-left corner of the grid to the top-right corner. However, we are only interested in the final cost, which is the value of the similarity between the two point sequences. This value is stored at the top-right node of the grid.

Figure A.2: Grid representation of the optimal warp. The nodes of the grid corresponds to pair of points of the two sequences we want to match. They store the cost of the optimal warp up to that point. The arrows and black dots represent the optimal warp found for matching the two sequences.