https://github.com/cran/dtw
Tip revision: 9fbfbef539cfc60884f6828c62f0aa328335a0b1 authored by Toni Giorgino on 08 January 2008, 00:00:00 UTC
version 1.5-3
version 1.5-3
Tip revision: 9fbfbef
stepPattern.Rd
\name{stepPattern}
\alias{stepPattern}
\alias{is.stepPattern}
\alias{print.stepPattern}
\alias{plot.stepPattern}
\alias{symmetric1}
\alias{symmetric2}
\alias{asymmetric}
\alias{asymmetricItakura}
%\alias{symmetricVelichkoZagoruyko}
\alias{symmetricP0}
\alias{asymmetricP0}
\alias{symmetricP05}
\alias{asymmetricP05}
\alias{symmetricP1}
\alias{asymmetricP1}
\alias{symmetricP2}
\alias{asymmetricP2}
\alias{typeIa}
\alias{typeIas}
\alias{typeIb}
\alias{typeIbs}
\alias{typeIc}
\alias{typeIcs}
\alias{typeId}
\alias{typeIds}
\alias{typeIIa}
\alias{typeIIb}
\alias{typeIIc}
\alias{typeIId}
\alias{typeIIIc}
\alias{typeIVc}
\title{Local constraints and step patterns for DTW}
\description{ DTW variants are implemented through step pattern objects.
A \code{stepPattern} instance lists the transitions allowed by the
\code{\link{dtw}} function in the search for the minimum-distance
path. }
\usage{
## Well-known step patterns
symmetric1
symmetric2
asymmetric
asymmetricItakura
% symmetricVelichkoZagoruyko
## Slope-constrained step patterns from Sakoe-Chiba
symmetricP0; asymmetricP0
symmetricP05; asymmetricP05
symmetricP1; asymmetricP1
symmetricP2; asymmetricP2
## Step patterns classified as per Rabiner-Myers
typeIa; typeIb; typeIc; typeId;
typeIas; typeIbs; typeIcs; typeIds; # smoothed
typeIIa; typeIIb; typeIIc; typeIId;
typeIIIc; typeIVc;
\method{print}{stepPattern}(x,...)
\method{plot}{stepPattern}(x,...)
stepPattern(v)
is.stepPattern(x)
}
\arguments{
\item{x}{a step pattern object}
\item{v}{a vector defining the stepPattern structure (see below)}
\item{...}{additional arguments to \code{\link{print}}.}
}
\details{
A step pattern characterizes the matching model and/or slope constraint
specific of a DTW variant.
\code{print.stepPattern} prints an user-readable
description of the recurrence equation defined by the given pattern.
\code{plot.stepPattern} graphically displays the step patterns
productions which can lead to element (0,0). (Weights are not
currently shown.)
% TODO REPLACE as TABLE
Several step patterns are pre-defined with the package:
\itemize{
\item{\code{symmetric1}}{quasi-symmetric, no slope constraint
(favours oblique steps);}
\item{\code{symmetric2}}{properly symmetric, no slope constraint:
one diagonal step costs as much as the sum of the equivalent steps
along the sides; }
\item{\code{asymmetric}}{asymmetric, slope constrained between 0 and
2. Matches each element of the query time series exactly once, so
the warping path \code{index2~index1} is guaranteed to
be single-valued; }
\item{\code{asymmetricItakura}}{asymmetric, slope contrained 0.5
-- 2 from reference [2]. This is the recursive definition
that generates the Itakura parallelogram; }
% \item{\code{symmetricVelichkoZagoruyko}}{symmetric, reproduced from [1]. Use distance matrix \code{1-d}}
\item{\code{symmetricPx}}{Sakoe's symmetric, slope contraint \code{x};}
\item{\code{asymmetricPx}}{Sakoe's asymmetric, slope contraint \code{x}.}
\item{\code{typeNNw}}{Rabiner-Myers classification (see details).}
}
The \code{symmetricPx} and \code{asymmetricPx} slope-constrained
patterns are discussed in Sakoe-Chiba [1], and reproduced as shown in
page 47, table I. Values available for \emph{P} (\code{x}) are
accordingly: \code{0} (no constraint), \code{1}, \code{05} (one half)
and \code{2}. See [1] for details. % They are also known as type V (Rabiner and Huang) [3].
The \code{typeNNw} steps follow Rabiner and Myers' classification
given in [3-4]. \code{NN} is a roman numeral specifying the shape of
the transitions; \code{w} is a letter in the range \code{a-d}
according the type of weighting used per step (see table below for
meaning); \code{type2} patterns also have a version ending in \code{s}
meaning the path smoothing is used (which does not permit skipping
points). The \code{type1d, type2d} and \code{type2ds} are unbiased and
symmetric.
\preformatted{
rule norm unbiased
--------------------------------
a min step ~N NO
b max step ~N NO
c x step N YES
d x+y step N+M YES
}
The \code{stepPattern} constructor is currently not well
documented. Please see the example below, implementing Sakoe's
\emph{P=1, Symmetric} algorithm.
\preformatted{
symmetricP1 <- stepPattern(c(
1,1,2,-1, # First branch: g(i-1,j-2) +
1,0,1,2, # + 2d( i ,j-1) +
1,0,0,1, # + d( i , j )
2,1,1,-1, # Second br.: g(i-1,j-1) +
2,0,0,2, # + 2d( i , j )
3,2,1,-1, # Third branch: g(i-2,j-1) +
3,1,0,2, # + 2d(i-1, j ) +
3,0,0,1 # + d( i , j )
));
}
Decoding is left to the reader as an exercise, and
\code{print.stepPattern} may come handy.
}
\references{
[1] Sakoe, H.; Chiba, S., \emph{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: \url{http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1163055}
\cr \cr
[2] Itakura, F., \emph{Minimum prediction residual principle applied to speech
recognition,} Acoustics, Speech, and Signal Processing [see also IEEE
Transactions on Signal Processing], IEEE Transactions on , vol.23, no.1, pp.
67-72, Feb 1975. URL:
\url{http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1162641}
\cr \cr
[3] Rabiner, L. R., & Juang, B.-H. (1993). \emph{Fundamentals of speech
recognition.} Englewood Cliffs, NJ: Prentice Hall.
\cr \cr
[4] Myers, C. S. \emph{A Comparative Study Of Several Dynamic Time Warping
Algorithms For Speech Recognition}, MS and BS thesis, MIT Jun 20
1980, \url{dspace.mit.edu/bitstream/1721.1/27909/1/07888629.pdf}
}
\author{Toni Giorgino}
\examples{
#########
##
## The usual (normalizable) symmetric step pattern
## Step pattern recursion, defined as:
## g[i,j] = min(
## g[i,j-1] + d[i,j] ,
## g[i-1,j-1] + 2 * d[i,j] ,
## g[i-1,j] + d[i,j] ,
## )
print.stepPattern(symmetric2) # or just "symmetric2"
#########
##
## The well-known plotting style for step patterns
plot.stepPattern(symmetricP2,main="Sakoe's Symmetric P=2 recursion")
# or just "plot(symmetricP2)"
#########
##
## Same example seen in ?dtw , now with asymmetric step pattern
idx<-seq(0,6.28,len=100);
query<-sin(idx)+runif(100)/10;
template<-cos(idx);
## Do the computation
asy<-dtw(query,template,keep=TRUE,step=asymmetric);
dtwPlot(asy,type="density",main="Sine and cosine, asymmetric step")
#########
##
## Hand-checkable example given in [4] p 61
##
`tm` <-
structure(c(1, 3, 4, 4, 5, 2, 2, 3, 3, 4, 3, 1, 1, 1, 3, 4, 2,
3, 3, 2, 5, 3, 4, 4, 1), .Dim = c(5L, 5L))
}
\concept{Dynamic Time Warp}
\concept{Dynamic Programming}
\concept{Step pattern}
\concept{Transition}
\concept{Local constraint}
\concept{Asymmetric DTW}
\concept{Symmetric DTW}
\keyword{ ts }