Dynamic time warping is an algorithm for measuring similarity between two sequences which may vary in time or speed. For instance, similarities in walking patterns would be detected, even if in one video the person was walking slowly and if in another he or she were walking more quickly, or even if there were accelerations and decelerations during the course of one observation. DTW has been applied to video, audio, and graphics — indeed, any data which can be turned into a linear representation can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds. Speech recognition (in many contexts also known as automatic speech recognition, computer speech recognition or erroneously as Voice Recognition) is the process of converting a speech signal to a sequence of words, by means of an algorithm implemented as a computer program. ...

In general, DTW is a method that allows a computer to find an optimal match between two given sequences (e.g. time series) with certain restrictions. The sequences are "warped" non-linearly in the time dimension to determine a measure of their similarity independent of certain non-linear variations in the time dimension. This sequence alignment method is often used in the context of hidden Markov models. In bioinformatics, a sequence alignment is a way of arranging the primary sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. ... State transitions in a hidden Markov model (example) x — hidden states y — observable outputs a — transition probabilities b — output probabilities A hidden Markov model (HMM) is a statistical model where the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine...

One example of the restrictions imposed on the matching of the sequences is on the monotonic of the mapping in the time dimension. Continuity is less important in DTW than in other pattern matching algorithms; DTW is an algorithm particularly suited to matching sequences with missing information, provided there are long enough segments for matching to occur. In mathematics, monotonicity is a characteristic of certain functions between partially ordered sets. ...

The optimization process is performed using dynamic programming, hence the name. In computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ...

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. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Example of one of the many forms 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]} 

Reference

• C. S. Myers and L. R. Rabiner.
  A comparative study of several dynamic time-warping algorithms for connected word recognition.
  The Bell System Technical Journal, 60(7):1389-1409, September 1981.

See also

• Levenshtein distance