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

Speech recognition

Speech recognition converts spoken words to text. The term "voice recognition" is sometimes used to refer to recognition systems that must be trained to a particular speaker—as is the case for most desktop recognition software...

, to cope with different speaking speeds.

In general, DTW is a method that allows a computer to find an optimal match between two given sequences (e.g. time series

Time series

In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at uniform time intervals. Examples of time series are the daily closing value of the Dow Jones index or the annual flow volume of the...

) 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

Sequence alignment

In bioinformatics, a sequence alignment is a way of arranging the 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. Aligned sequences of nucleotide or amino acid residues are...

 method is often used in the context of hidden Markov model

Hidden Markov model

A hidden Markov model is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved states. An HMM can be considered as the simplest dynamic Bayesian network. The mathematics behind the HMM was developed by L. E...

s.

One example of the restrictions imposed on the matching of the sequences is on the monotonicity of the mapping in the time dimension. Continuity is less important in DTW than in other pattern matching

Pattern matching

In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...

 algorithms; DTW is an algorithm particularly suited to matching sequences with missing information, provided there are long enough segments for matching to occur.

The extension of the problem for two-dimensional "series" like images (planar warping) is NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

, while the problem for one-dimensional signals like time series can be solved in polynomial time.

Example of one of the many forms of the algorithm

This example illustrates the implementation of dynamic time warping when the two sequences are strings of discrete symbols. d(x, y) is a distance between symbols, e.g. d(x, y) = | x - y |.

int DTWDistance(char s[1..n], char t[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] := cost + minimum(DTW[i-1, j  ],    // insertion

                                        DTW[i  , j-1],    // deletion

                                        DTW[i-1, j-1])    // match



    return DTW[n, m]

}

We sometimes want to add a locality constraint. That is, we require that if s[i] is matched with t[j], then | i - j | is no larger than w, a window parameter.

We can easily modify the above algorithm to add a locality constraint (differences marked in bold italic).
However, the above given modification works only if |n - m| is no larger than w, i.e. the end point is within the window length from diagonal. In order to make the algorithm work, the window parameter w must be adapted so that |n - m ≤ w| (see the line marked with (*) in the code).

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

w := max(w, abs(n-m)) // adapt window size (*)

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

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

return DTW[n, m]
}

Open Source software

• The lbimproved C++ library implements Fast Nearest-Neighbor Retrieval algorithms under the Dynamic Time Warping (GPL). It also provides a C++ implementation of Dynamic Time Warping as well as various lower bounds.
• The R package dtw implements most known variants of the DTW algorithm family, including a variety of recursion rules (also called step patterns), constraints, and substring matching.
• The mlpy Python library implements DTW.