Dynamic time warping is an algorithm that aims to measure similarity between two sequences which may vary in time or speed. DWT can be applied on both audio and video.
The sequence are warped non-linearly in the time-dimension, which determines a measure of their similarity independently of the non-linear variations in the time dimension. The algorithm uses dynamic programming, and does the following operations:
- the two sequences A and B to match are arranged on the sides of a grid.
- inside each cell a distance measure can be placed, which compares the corresponding elements of the two sequences.
- the best match (or alignment) between those two sequences is given by a path on the grid.
- to find the best path, we need to find all the possible routes through the grid and for each of them compute the overall distance between A and B (computed as the sum of distances between the individual elements on the grid). We can use dynamic programming to keep track of the cost of the best path at each point in the grid.
todo can be revisited
