dtw: Dynamic Time Warp

dtwR Documentation

Dynamic Time Warp


Compute Dynamic Time Warp and find optimal alignment between two time series.


  y = NULL,
  dist.method = "Euclidean",
  step.pattern = symmetric2,
  window.type = "none",
  keep.internals = FALSE,
  distance.only = FALSE,
  open.end = FALSE,
  open.begin = FALSE,


## S3 method for class 'dtw'
print(x, ...)



query vector or local cost matrix


reference vector, or NULL if x given as a local cost matrix


pointwise (local) distance function to use. See proxy::dist() in package proxy


a stepPattern object describing the local warping steps allowed with their cost (see stepPattern())


windowing function. Character: "none", "itakura", "sakoechiba", "slantedband", or a function (see details).


preserve the cumulative cost matrix, inputs, and other internal structures


only compute distance (no backtrack, faster)

open.begin, open.end

perform open-ended alignments


additional arguments, passed to window.type


an arbitrary R object


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:

  1. if dist.method is a string, x and y are passed to the proxy::dist() function in package proxy with the method given;

  2. if dist.method is a function of two arguments, it invoked repeatedly on all pairs x[i],y[j] to build the local cost matrix;

  3. multivariate time series and arbitrary distance metrics can be handled by supplying a precomputed local cost matrix. Element [i,j] of the local cost matrix is understood as the distance between element x[i] and y[j]. The distance matrix has therefore n=length(x) rows and m=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" So-called Itakura parallelogram

window.type can also be an user-defined windowing function. See dtwWindowingFunctions() for all available windowing functions, details on user-defined 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.

Open-ended alignment, i.e. semi-unconstrained alignment, can be selected via the open.end switch. Open-end 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, open-begin is enabled via open.begin; it makes sense when open.end is also enabled (subsequence finding). Subsequence alignments are similar e.g. to UE2-1 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.


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 x

  • index2 corresponding mapped indices in y

  • stepPattern the stepPattern object used for the computation

  • jmin last element of reference matched, if open.end=TRUE

  • directionMatrix if keep.internals=TRUE, the directions of steps that would be taken at each alignment pair (integers indexing production rules in the chosen step pattern)

  • stepsTaken the list of steps taken from the beginning to the end of the alignment (integers indexing chosen step pattern)

  • index1s, index2s same as index1/2, excluding intermediate steps for multi-step patterns like asymmetricP05()

  • costMatrix if keep.internals=TRUE, the cumulative cost matrix

  • query, reference if keep.internals=TRUE and passed as the x and y arguments, the query and reference timeseries.


Cost matrices (both input and output) have query elements arranged row-wise (first index), and reference elements column-wise (second index). They print according to the usual convention, with indexes increasing down- and rightwards. Many DTW papers and tutorials show matrices according to plot-like conventions, i.e. reference index growing upwards. This may be confusing.


Toni Giorgino


  1. Toni Giorgino. Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package. Journal of Statistical Software, 31(7), 1-24. doi: 10.18637/jss.v031.i07

  2. Tormene, P.; Giorgino, T.; Quaglini, S. & Stefanelli, M. Matching incomplete time series with dynamic time warping: an algorithm and an application to post-stroke rehabilitation. Artif Intell Med, 2009, 45, 11-34. doi: 10.1016/j.artmed.2008.11.007

  3. Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, Acoustics, Speech, and Signal Processing, IEEE Transactions on , vol.26, no.1, pp. 43-49, Feb 1978. doi: 10.1109/TASSP.1978.1163055

  4. 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, 560-563 doi: 10.1109/ICPR.2006.467

  5. Sakoe, H. Two-level DP-matching–A dynamic programming-based pattern matching algorithm for connected word recognition Acoustics, Speech, and Signal Processing, IEEE Transactions on, 1979, 27, 588-595 doi: 10.1109/TASSP.1979.1163310

  6. 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), 575-582. doi: 10.1109/TASSP.1978.1163164

  7. Muller M. Dynamic Time Warping in Information Retrieval for Music and Motion. Springer Berlin Heidelberg; 2007. p. 69-84. doi: 10.1007/978-3-540-74048-3_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 cost matrix, the functions proxy::dist(), analogue::distance(), vegan::vegdist(), or outer() may come handy.


## A noisy sine wave as query

## A cosine is for reference; sin and cos are offset by 25 samples
plot(reference); lines(query,col="blue");

## Find the best match

## Display the mapping, AKA warping function - may be multiple-valued
## Equivalent to: plot(alignment,type="alignment")
plot(alignment$index1,alignment$index2,main="Warping function");

## Confirm: 25 samples off-diagonal alignment

## Partial alignments are allowed.

alignmentOBE <-

## 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 the (unwarped) query and the inverse-warped reference

## 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


	xlab="Query (noisy sine)",ylab="Reference (cosine)");


## An hand-checkable 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 user-supplied local
                                 #   cost matrix
da<-dtw(ldist,step=asymmetric);	 # Also compute the asymmetric 
plot(ds$index1,ds$index2,pch=3); # Symmetric: alignment follows
                                 #   the low-distance marked path
points(da$index1,da$index2,col="red");  # Asymmetric: visiting
                                        #   1 is required twice


dtw documentation built on Sept. 20, 2022, 1:06 a.m.