DTW was originally used to measure similarity between speech signals. The DTW algorithm is now commonly used to compute the similarity of two time series, especially series of different lengths and different rhythms.
Algorithm
Suppose there are two sequences
$$\mathbf{X}=\{\mathbf{x}_1,\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\} $$$$\mathbf{Y}=\{\mathbf{y}_1,\mathbf{y}_{2},\ldots,\mathbf{y}_{m}\} $$
First, build an $m\times n$ two-dimensional array $W$. Each point $W(i,j)$ in the array is the cumulative distance between $\mathbf{X}_{i}$ and $\mathbf{Y}_{j}$, $\sqrt{ (\mathbf{X}_{i}-\mathbf{Y}_{j})^2 }$. The core idea of DTW is to find, in this distance matrix, the minimum-distance warping path from the start of both sequences to their ends. While searching for that path, several constraints must be satisfied:
- Boundary condition: the start must be $w(1,1)$ and the end must be $w(1,1)$; the path has to begin and it has to end.
- Continuity: the next valid gray square must be one of the squares in the ring immediately surrounding the current gray square.
- Monotonicity: the next valid gray square must lie above and to the right of the current gray square; the path cannot turn back. Suppose the two sequences are $\mathbf{X}=\{1,3,2,4,2\}$ and $\mathbf{Y}=\{0,3,4,2,2\}$. Using the Euclidean distance, the distance between them can be computed directly as: $$ dis = \sqrt{ (1-0)^2+(3-3)^2+(2-4)^2+(4-2)^2+(2-2)^2 }=\sqrt{ 5 } $$
Build the cumulative distance matrix $w$:
- First fill the leftmost column, $W(i,0)=dis(\mathbf{X}_{i}-\mathbf{Y}_{0})+W(i-1,0)$
- Then fill the bottom row: $W(0,j)=dis(\mathbf{X}_{0},\mathbf{Y}_{j})+W(0,j-1)$
- Finally fill the cells in the middle of the table: $W(i,j)=dis(\mathbf{X}_{i},\mathbf{Y}_{j})+\min(W(i-1,j),W(i,j-1),W(i-1),W(j-1))$
- Then, using the cumulative distance matrix just built, search for the warping path from the upper-right corner to the lower-left corner, and take the smaller of the three cells toward the lower left as the next node.
- The resulting alignment is $\{(\mathbf{x}_{1},\mathbf{y}_{1}), (\mathbf{x}_{2},\mathbf{y}_{2}),(\mathbf{x}_{3},\mathbf{y}_{2}),(\mathbf{x}_{4},\mathbf{y}_{3}),(\mathbf{x}_{5},\mathbf{y}_{4}),(\mathbf{x}_{5},\mathbf{y}_{5})\}$

Implementation
| |
