Dynamic time warping

Not to be confused with the Time Warp mechanism for discrete event simulation, or the Time Warp Operating System that used this mechanism.
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.
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" nonlinearly in the time dimension to determine a measure of their similarity independent of certain nonlinear variations in the time dimension. This sequence alignment method is often used in the context of hidden Markov models.
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 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 twodimensional "series" like images (planar warping) is NPcomplete, while the problem for onedimensional signals like time series can be solved in polynomial time.
Contents
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[i1, j ], // insertion DTW[i , j1], // deletion DTW[i1, j1]) // match return DTW[n, m] }
We sometimes want to add a locality constraint. That is, we require that if
s[i]
is matched witht[j]
, then i  j
 is no larger thanw
, 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 thanw
, i.e. the end point is within the window length from diagonal. In order to make the algorithm work, the window parameterw
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(nm)) // 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, iw) to min(m, i+w) cost := d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i1, j ], // insertion DTW[i , j1], // deletion DTW[i1, j1]) // match return DTW[n, m] }
Open Source software
 The lbimproved C++ library implements Fast NearestNeighbor 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.
References
 Sakoe, H. and Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1) pp. 43 49, 1978, ISSN: 00963518
 C. S. Myers and L. R. Rabiner.
A comparative study of several dynamic timewarping algorithms for connected word recognition.
The Bell System Technical Journal, 60(7):13891409, September 1981.  L. R. Rabiner and B. Juang.
Fundamentals of speech recognition.
PrenticeHall, Inc., 1993 (Chapter 4)
See also
Categories: Dynamic programming
 Machine learning algorithms
 Time series analysis
Wikimedia Foundation. 2010.
Look at other dictionaries:
Dynamic Time Warping — Dynamic time warp(ing) ist ein Algorithmus, um Wertefolgen unterschiedlicher Länge aufeinander abzubilden.[1] Inhaltsverzeichnis 1 Anwendung 2 Algorithmus 3 Siehe auch 4 Einzelnachweise 5 … Deutsch Wikipedia
DynamicTimeWarping — Dynamic time warp(ing) ist ein Algorithmus, um Wertefolgen unterschiedlicher Länge aufeinander abzubilden.[1] Inhaltsverzeichnis 1 Anwendung 2 Algorithmus 3 Siehe auch 4 … Deutsch Wikipedia
Time series — Time series: random data plus trend, with best fit line and different smoothings In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at … Wikipedia
Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… … Wikipedia
Speech recognition — For the human linguistic concept, see Speech perception. The display of the Speech Recognition screensaver on a PC, in which the character responds to questions, e.g. Where are you? or statements, e.g. Hello. Speech recognition (also known as… … Wikipedia
Needleman–Wunsch algorithm — The Needleman–Wunsch algorithm performs a global alignment on two sequences (called A and B here). It is commonly used in bioinformatics to align protein or nucleotide sequences. The algorithm was published in 1970 by Saul B. Needleman and… … Wikipedia
Levenshtein distance — In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences. The term edit distance is often used to refer specifically to Levenshtein distance. The… … Wikipedia
List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… … Wikipedia
EditDistanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… … Deutsch Wikipedia
Editierdistanz — Die Levenshtein Distanz (auch Edit Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und… … Deutsch Wikipedia