Dynamic time warping is a technique applied in automatic speech recognition to cope with different speaking speeds. In general, it is a method that allows to find an optimal match between two given sequences (e.g. time series) with certain restrictions, i.e. the sequences are warped non-linearly to match each other. This sequence alignment method is often used in the context of hidden Markov models.

A typical example of the restrictions imposed on the matching of the sequences are the following:

The optimization process is carried out using dynamic programming, hence the name.

Interestingly, the extension of the problem for two-dimensional series like images (planar warping) is NP-complete, while the problem for one-dimensional signals like time series can be solved in polynomial time.

= Example of the algorithm =

int DTWDistance(char s[1..n], char t[1..m], int d[1..n,1..m]) { declare int DTW[0..n,0..m] declare int i, j, cost

for i := 1 to m DTW[0,i] := infinity for i := 1 to n DTW[i,0] := infinity DTW[0,0] := 0

for i := 1 to n for j := 1 to m cost:= d[s[i],t[j]] DTW[i,j] := minimum(DTW[i-1,j ] + cost, // insertion DTW[i ,j-1] + cost) // deletion DTW[i-1,j-1] + cost) // match

return DTW[n,m] }

= References =