% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/dtw.R
\name{dtw}
\alias{dtw}
\alias{is.dtw}
\alias{print.dtw}
\title{Dynamic Time Warp}
\usage{
dtw(
  x,
  y = NULL,
  dist.method = "Euclidean",
  step.pattern = symmetric2,
  window.type = "none",
  keep.internals = FALSE,
  distance.only = FALSE,
  open.end = FALSE,
  open.begin = FALSE,
  ...
)

is.dtw(d)

\method{print}{dtw}(x, ...)
}
\arguments{
\item{x}{query vector \emph{or} local cost matrix}

\item{y}{reference vector, or NULL if \code{x} given as a local cost matrix}

\item{dist.method}{pointwise (local) distance function to use. See
\code{\link[proxy:dist]{proxy::dist()}} in package \CRANpkg{proxy}}

\item{step.pattern}{a stepPattern object describing the local warping steps
allowed with their cost (see \code{\link[=stepPattern]{stepPattern()}})}

\item{window.type}{windowing function. Character: "none", "itakura",
"sakoechiba", "slantedband", or a function (see details).}

\item{keep.internals}{preserve the cumulative cost matrix, inputs, and other
internal structures}

\item{distance.only}{only compute distance (no backtrack, faster)}

\item{open.begin, open.end}{perform open-ended alignments}

\item{...}{additional arguments, passed to \code{window.type}}

\item{d}{an arbitrary R object}
}
\value{
An object of class \code{dtw} with
the following items:
\itemize{
\item \code{distance} the minimum global distance computed, \emph{not} normalized.
\item \code{normalizedDistance} distance computed, \emph{normalized} for path length, if normalization is known for chosen step pattern.
\item \verb{N,M} query and reference length
\item \code{call} the function call that created the object
\item \code{index1} matched elements: indices in \code{x}
\item \code{index2} corresponding mapped indices in \code{y}
\item \code{stepPattern} the \code{stepPattern} object used for the computation
\item \code{jmin} last element of reference matched, if \code{open.end=TRUE}
\item \code{directionMatrix} if \code{keep.internals=TRUE}, the directions of steps that would be taken at each alignment pair (integers indexing  production rules in the chosen step pattern)
\item \code{stepsTaken} the list of steps taken from the beginning to the end of the alignment (integers indexing chosen step pattern)
\item \verb{index1s, index2s} same as \code{index1/2}, excluding intermediate steps for multi-step patterns like \code{\link[=asymmetricP05]{asymmetricP05()}}
\item \code{costMatrix} if \code{keep.internals=TRUE}, the cumulative cost matrix
\item \verb{query, reference} if \code{keep.internals=TRUE} and passed as the \code{x} and \code{y} arguments, the query and reference timeseries.
}
}
\description{
Compute Dynamic Time Warp and find optimal alignment between two time
series.
}
\details{
The function performs Dynamic Time Warp (DTW) and computes the optimal
alignment between two time series \code{x} and \code{y}, given as numeric
vectors.  The "optimal" alignment minimizes the sum of distances between
aligned elements. Lengths of \code{x} and \code{y} may differ.

The local distance between elements of \code{x} (query) and \code{y}
(reference) can be computed in one of the following ways:
\enumerate{
\item if \code{dist.method} is a string, \code{x} and \code{y} are passed to the \code{\link[proxy:dist]{proxy::dist()}} function in package \CRANpkg{proxy} with the method given;
\item if \code{dist.method} is a function of two arguments, it invoked repeatedly on all pairs \verb{x[i],y[j]} to build the local cost matrix;
\item multivariate time series and arbitrary distance metrics can be handled by supplying a precomputed local cost matrix. Element \verb{[i,j]} of the local cost matrix is understood as the distance between element \code{x[i]} and \code{y[j]}. The distance matrix has therefore \code{n=length(x)} rows and \code{m=length(y)} columns (see note below).
}

Several common variants of the DTW recursion are supported via the
\code{step.pattern} argument, which defaults to \code{symmetric2}. Step
patterns are commonly used to \emph{locally} constrain the slope of the
alignment function. See \code{\link[=stepPattern]{stepPattern()}} for details.

Windowing enforces a \emph{global} constraint on the envelope of the warping
path. It is selected by passing a string or function to the
\code{window.type} argument. Commonly used windows are (abbreviations
allowed):
\itemize{
\item \code{"none"} No windowing (default)
\item \code{"sakoechiba"} A band around main diagonal
\item \code{"slantedband"} A band around slanted diagonal
\item \code{"itakura"} So-called Itakura parallelogram
}

\code{window.type} can also be an user-defined windowing function.  See
\code{\link[=dtwWindowingFunctions]{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 \code{window.size} argument.

Open-ended alignment, i.e. semi-unconstrained alignment, can be selected via
the \code{open.end} switch.  Open-end DTW computes the alignment which best
matches all of the query with a \emph{leading part} of the reference. This
is proposed e.g. by Mori (2006), Sakoe (1979) and others. Similarly,
open-begin is enabled via \code{open.begin}; it makes sense when
\code{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 \code{distance.only=TRUE} switch, which skips the backtracking step. The
output object will then lack the \verb{index\{1,2,1s,2s\}} and
\code{stepsTaken} fields.

\code{is.dtw} tests whether the argument is of class \code{dtw}.
}
\note{
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.
}
\examples{


## 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 multiple-valued
## Equivalent to: plot(alignment,type="alignment")
plot(alignment$index1,alignment$index2,main="Warping function");

## Confirm: 25 samples off-diagonal alignment
lines(1:100-25,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 inverse-warped 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 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

ds$distance;
da$distance;




}
\references{
\enumerate{
\item Toni Giorgino. \emph{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}
\item Tormene, P.;
Giorgino, T.; Quaglini, S. & Stefanelli, M. \emph{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}
\item Sakoe, H.;
Chiba, S., \emph{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}
\item Mori, A.; Uchida, S.; Kurazume, R.; Taniguchi, R.; Hasegawa, T. & Sakoe, H.
\emph{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}
\item Sakoe,
H. \emph{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}
\item Rabiner L, Rosenberg A, Levinson
S (1978). \emph{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}
\item Muller M. \emph{Dynamic Time
Warping} in \emph{Information Retrieval for Music and Motion}. Springer
Berlin Heidelberg; 2007. p. 69-84. \doi{10.1007/978-3-540-74048-3_4}
}
}
\seealso{
\code{\link[=dtwDist]{dtwDist()}}, for iterating dtw over a set of timeseries;
\code{\link[=dtwWindowingFunctions]{dtwWindowingFunctions()}}, for windowing and global constraints;
\code{\link[=stepPattern]{stepPattern()}}, step patterns and local constraints;
\code{\link[=plot.dtw]{plot.dtw()}}, plot methods for DTW objects.  To generate a local
cost matrix, the functions \code{\link[proxy:dist]{proxy::dist()}},
\code{analogue::distance()}, \code{vegan::vegdist()}, or \code{\link[=outer]{outer()}} may come handy.
}
\author{
Toni Giorgino
}
\concept{Align timeseries}
\concept{Distance}
\concept{Dynamic Time Warp}
\concept{Dynamic programming}
\concept{Minimum cumulative cost}
\keyword{ts}