Dynamic Time Warping

Dynamic time warping (DTW) 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. Other applications include speaker recognition and online signature recognition.

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 t 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, i.e. d(x, y) = | x - y |.

int DTWDistance(s: array, t: array ) { DTW := array for i := 1 to m DTW := infinity for i := 1 to n DTW := infinity DTW := 0 for i := 1 to n for j := 1 to m cost:= d(s, t) DTW := cost + minimum(DTW, // insertion DTW, // deletion DTW) // match return DTW }

We sometimes want to add a locality constraint. That is, we require that if s is matched with t, 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(s: array, t: array , w: int) { DTW := array w := max(w, abs(n-m)) // adapt window size (*) for i := 0 to n for j:= 0 to m DTW := infinity DTW := 0 for i := 1 to n for j := max(1, i-w) to min(m, i+w) cost := d(s, t) DTW := cost + minimum(DTW, // insertion DTW, // deletion DTW) // match return DTW }