dtw (version 0.4-2)

dtw: Dynamic Time Warp

Description

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

Usage

dtw(x, y=NULL, distance.function=euclideanSquared, step.pattern="s",
  window.type="none", keep.internals=FALSE, ...)
is.dtw(d)

Arguments

x

query vector OR local cost matrix

y

template vector, or unused if cost matrix given

distance.function

pointwise distance function. See e.g. dtwDistanceFunctions

step.pattern

step pattern. Char: "s" (symmetric), "a" (asymmetric), or step matrix containing the allowed steps with their cost (see stepPattern)

window.type

windowing function, character or function. Char: "none", "itakura", "sakoechiba", "slantedband". Function: boolean of two arguments.

keep.internals

don't discard the cumulative cost matrix and other internal structures

d

an arbitrary R object

...

additional arguments, passed to window.function

Value

• An object of class dtw with the following items:
• distance
  the computed distance not normalized. Normalization depends on the chosen step pattern.
• index1
  matched elements: indices in x
• index2
  corresponding mapped indices in y
• stepPatterns
  the stepPattern object used for the computation
• costMatrix
  if keep.internals=TRUE, the cumulative cost matrix
• directionMatrix
  if keep.internals=TRUE, the directions of steps that would be taken at each alignment pair (integers indexing step patterns)

code

dtw

concept

• Dynamic Time Warp
• Dynamic programming
• Align timeseries
• Minimum cumulative cost

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 be different. The (local) distance between elements of x (query) and y (template) is computed through the supplied distance.function (see dtwDistanceFunctions).

Multivariate time series and complex distance functions can be handled by supplying a local-distance matrix. Element [i,j] of the local-distance 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). To generate a local distance matrix, the functions outer and distance in package analogue may come handy.

Several common variants of DTW are supported via the step.pattern argument, which defaults to symmetric. Most common step patterns are supported and pre-defined matrices; the user can write their own. See stepPattern for details.

Windowing is supported by supplying a name into the window.type argument (abbreviations allowed) between the built-in types:

• "none"

{No windowing (default)} "sakoechiba"{A band around main diagonal} "slantedband"{A band around slanted diagonal} "itakura"{So-called Itakura parallelogram}

References

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. 43-49, Feb 1978 URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1163055

See Also

outer,distance; dtwWindowingFunctions, windowing and global constraints; stepPattern, step patterns and local constraints including slope; plot.dtw, the plot method for DTW objects.

Examples

## A noisy sine wave as query
idx<-seq(0,6.28,len=100);
query<-sin(idx)+runif(100)/10;

## A cosine is for template; sin and cos are offset by 25 samples
template<-cos(idx)
plot(template); lines(query);

## Find the best match (approx 1sec on Pentium 4)
## keep = TRUE so we can make a density plot later on
alignment<-dtw(query,template,keep=TRUE);


## Display the mapping
plot(alignment$index1,alignment$index2);

## That's all: 25 samples off-diagonal alignment
lines(1:100-25,col="red")


## Contour plots of the global cost


## A profile of the cumulative distance matrix
## similar to: plot(alignment,type="density") or dtwPlotDensity(alignment)

contour(alignment$costMatrix,col=terrain.colors(100),x=1:100,y=1:100,
	xlab="Query (noisy sine)",ylab="Template (cosine)");

lines(alignment$index1,alignment$index2,col="red",lwd=2);


## More plots on dtw.plot!


#########
## 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="a");	 # Also compute the asymmetric 
plot(ds$index1,ds$index2,pch=3);    	 # Symmetric: alignment follows the marked path
points(da$index1,da$index2,col="red");    	 # Asymmetric: visiting 1 is required twice

ds$distance;
da$distance;