Dynamic Time Warp
Description
Compute Dynamic Time Warp and find optimal alignment between two time series.
Usage
1 2 3 4 5 6 7 8 9 10 11 12 13 
Arguments
x 
query vector or local cost matrix 
y 
reference vector, unused if 
dist.method 
pointwise (local) distance function to use. See

step.pattern 
a stepPattern object describing the
local warping steps allowed with their cost (see 
window.type 
windowing function. Character: "none", "itakura", "sakoechiba", "slantedband", or a function (see details). 
open.begin, open.end 
perform openended alignments 
keep.internals 
preserve the cumulative cost matrix, inputs, and other internal structures 
distance.only 
only compute distance (no backtrack, faster) 
d 
an arbitrary R object 
... 
additional arguments, passed to 
Details
The function performs Dynamic Time Warp (DTW) and computes the optimal
alignment between two time series x
and y
, given as
numeric vectors. The “optimal” alignment minimizes the sum of
distances between aligned elements. Lengths of x
and y
may differ.
The local distance between elements of x
(query) and y
(reference) can be computed in one of the following ways:
if
dist.method
is a string,x
andy
are passed to thedist
function in package proxy with the method given;if
dist.method
is a function of two arguments, it invoked repeatedly on all pairsx[i],y[j]
to build the local cost matrix;multivariate time series and arbitrary distance metrics can be handled by supplying a localdistance matrix. Element
[i,j]
of the localdistance matrix is understood as the distance between elementx[i]
andy[j]
. The distance matrix has thereforen=length(x)
rows andm=length(y)
columns (see note below).
Several common variants of the DTW recursion are supported via the
step.pattern
argument, which defaults to
symmetric2
. Step patterns are commonly used to locally
constrain the slope of the alignment function. See
stepPattern
for details.
Windowing enforces a global constraint on the envelope of the
warping path. It is selected by passing a string or function to the
window.type
argument. Commonly used windows are (abbreviations
allowed):
"none"
No windowing (default)"sakoechiba"
A band around main diagonal"slantedband"
A band around slanted diagonal"itakura"
Socalled Itakura parallelogram
window.type
can also be an userdefined windowing function.
See dtwWindowingFunctions
for all available windowing
functions, details on userdefined windowing, and a discussion of the
(mis)naming of the "Itakura" parallelogram as a global constraint.
Some windowing functions may require parameters, such as the
window.size
argument.
Openended alignment, i.e. semiunconstrained alignment, can be
selected via the open.end
switch. Openend DTW computes the
alignment which best matches all of the query with a leading
part of the reference. This is proposed e.g. by Mori (2006), Sakoe
(1979) and others. Similarly, openbegin is enabled via
open.begin
; it makes sense when open.end
is also enabled
(subsequence finding). Subsequence alignments are similar e.g. to
UE21 algorithm by Rabiner (1978) and others. Please find a review in
Tormene et al. (2009).
If the warping function is not required, computation can be sped
up enabling the distance.only=TRUE
switch, which skips
the backtracking step. The output object will then lack the
index{1,2,1s,2s}
and stepsTaken
fields.
is.dtw
tests whether the argument is of class dtw
.
Value
An object of class dtw
with the following items:
distance 
the minimum global distance computed, not normalized. 
normalizedDistance 
distance computed, normalized for path length, if normalization is known for chosen step pattern. 
N,M 
query and reference length 
call 
the function call that created the object 
index1 
matched elements: indices in 
index2 
corresponding mapped indices in 
stepPattern 
the 
jmin 
last element of reference matched, if 
directionMatrix 
if 
stepsTaken 
the list of steps taken from the beginning to the end of the alignment (integers indexing chosen step pattern) 
index1s, index2s 
same as 
costMatrix 
if 
query, reference 
if 
Note
Cost matrices (both input and output) have query elements arranged rowwise (first index), and reference elements columnwise (second index). They print according to the usual convention, with indexes increasing down and rightwards. Many DTW papers and tutorials show matrices according to plotlike conventions, i.e. reference index growing upwards. This may be confusing.
A fast compiled version of the function is normally used. Should it be unavailable, the interpreted equivalent will be used as a fallback with a warning.
Author(s)
Toni Giorgino
References
Toni Giorgino. Computing and Visualizing Dynamic Time Warping
Alignments in R: The dtw Package. Journal of Statistical
Software, 31(7), 124. http://www.jstatsoft.org/v31/i07/
Tormene, P.; Giorgino, T.; Quaglini, S. & Stefanelli,
M. Matching incomplete time series with dynamic time warping: an
algorithm and an application to poststroke rehabilitation. Artif
Intell Med, 2009, 45, 1134. http://dx.doi.org/10.1016/j.artmed.2008.11.007
Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization
for spoken word recognition, Acoustics, Speech, and Signal Processing
[see also IEEE Transactions on Signal Processing], IEEE Transactions
on , vol.26, no.1, pp. 4349, Feb 1978.
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1163055
Mori, A.; Uchida, S.; Kurazume, R.; Taniguchi, R.; Hasegawa, T. &
Sakoe, H. Early Recognition and Prediction of Gestures
Proc. 18th International Conference on Pattern Recognition ICPR 2006,
2006, 3, 560563
Sakoe, H. Twolevel DPmatching–A dynamic programmingbased pattern
matching algorithm for connected word recognition Acoustics, Speech,
and Signal Processing [see also IEEE Transactions on Signal
Processing], IEEE Transactions on, 1979, 27, 588595
Rabiner L, Rosenberg A, Levinson S (1978). Considerations in
dynamic time warping algorithms for discrete word recognition.
IEEE Trans. Acoust., Speech, Signal Process.,
26(6), 575582. ISSN 00963518.
Muller M. Dynamic Time Warping in Information Retrieval for Music
and Motion. Springer Berlin Heidelberg; 2007. p. 6984.
http://link.springer.com/chapter/10.1007/9783540740483_4
See Also
dtwDist
, for iterating dtw over a set of timeseries;
dtwWindowingFunctions
, for windowing and global constraints;
stepPattern
, step patterns and local constraints;
plot.dtw
, plot methods for DTW objects.
To generate a local distance matrix, the functions
dist
in package proxy,
distance
in package analogue,
outer
may come handy.
Examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90  ## A noisy sine wave as query
idx<seq(0,6.28,len=100);
query<sin(idx)+runif(100)/10;
## A cosine is for reference; sin and cos are offset by 25 samples
reference<cos(idx)
plot(reference); lines(query,col="blue");
## Find the best match
alignment<dtw(query,reference);
## Display the mapping, AKA warping function  may be multiplevalued
## Equivalent to: plot(alignment,type="alignment")
plot(alignment$index1,alignment$index2,main="Warping function");
## Confirm: 25 samples offdiagonal alignment
lines(1:10025,col="red")
#########
##
## Partial alignments are allowed.
##
alignmentOBE <
dtw(query[44:88],reference,
keep=TRUE,step=asymmetric,
open.end=TRUE,open.begin=TRUE);
plot(alignmentOBE,type="two",off=1);
#########
##
## Subsetting allows warping and unwarping of
## timeseries according to the warping curve.
## See first example below.
##
## Most useful: plot the warped query along with reference
plot(reference)
lines(query[alignment$index1]~alignment$index2,col="blue")
## Plot the (unwarped) query and the inversewarped reference
plot(query,type="l",col="blue")
points(reference[alignment$index2]~alignment$index1)
#########
##
## Contour plots of the cumulative cost matrix
## similar to: plot(alignment,type="density") or
## dtwPlotDensity(alignment)
## See more plots in ?plot.dtw
##
## keep = TRUE so we can look into the cost matrix
alignment<dtw(query,reference,keep=TRUE);
contour(alignment$costMatrix,col=terrain.colors(100),x=1:100,y=1:100,
xlab="Query (noisy sine)",ylab="Reference (cosine)");
lines(alignment$index1,alignment$index2,col="red",lwd=2);
#########
##
## An handcheckable example
##
ldist<matrix(1,nrow=6,ncol=6); # Matrix of ones
ldist[2,]<0; ldist[,5]<0; # Mark a clear path of zeroes
ldist[2,5]<.01; # Forcely cut the corner
ds<dtw(ldist); # DTW with usersupplied local
# cost matrix
da<dtw(ldist,step=asymmetric); # Also compute the asymmetric
plot(ds$index1,ds$index2,pch=3); # Symmetric: alignment follows
# the lowdistance marked path
points(da$index1,da$index2,col="red"); # Asymmetric: visiting
# 1 is required twice
ds$distance;
da$distance;
