Revision f3fa0a2ccb9bde3782d3555dfc9ebd3381d1757f authored by Toni Giorgino on 30 November 2007, 00:00:00 UTC, committed by Gabor Csardi on 30 November 2007, 00:00:00 UTC
1 parent 8635857
stepPattern.Rd
\name{stepPattern}
\alias{stepPattern}
\alias{is.stepPattern}
\alias{print.stepPattern}
\alias{symmetric1}
\alias{symmetric2}
\alias{asymmetric}
\alias{symmetricP1}
\alias{asymmetricItakura}
\title{Local constraints and step patterns for DTW}
\description{ A step pattern object lists the allowed step patterns for
a given DTW variant. It can be used to constrain the warping
paths considered by the \code{\link{dtw}} function.
}
\usage{
# predefined step patterns:
symmetric1
symmetric2
asymmetric
symmetricP1
asymmetricItakura
\method{print}{stepPattern}(x,...)
is.stepPattern(x)
stepPattern(v)
}
\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 pattern.
Several step patterns are pre-defined:
\itemize {
\item{\code{symmetric1}}{quasi-symmetric, no slope constraint. Favours oblique steps.}
\item{\code{symmetric2}}{properly symmetric, no slope constraint: oblique
step costs as much as the sum of the equivalent steps along the
sides.}
\item{\code{asymmetric}}{asymmetric, no slope constraint. Matches each
element of the query time series exactly once.}
\item{\code{symmetricP1}}{symmetric, slope contraint $P=1$ (see
reference [1], page 47, table I)}
\item{\code{asymmetricItakura}}{asymmetric, slope contrained. This is the
recursive function described in reference [2] that generates
the Itakura parallelogram.
}
\item{}{...more to come}
}
The vector description for \code{stepPattern} constructor is
currently not well documented. Please see the example below,
implementing Sakoe's P=1, Symmetric algorithm in Table I, p47 [1].
\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 branch: 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. \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}
}
\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)
## Same example seen in dtw help, but with asymmetric step pattern
idx<-seq(0,6.28,len=100);
query<-sin(idx)+runif(100)/10;
template<-cos(idx);
## Do the computation (takes ~5 s)
asy<-dtw(query,template,keep=TRUE,step=asymmetric);
dtwPlot(asy,type="density",main="Sine and cosine, asymmetric step")
}
\concept{Dynamic Time Warp}
\concept{Dynamic Programming}
\concept{Step pattern}
\concept{Local constraint}
\concept{Asymmetric DTW}
\concept{Symmetric DTW}
\keyword{ ts }
Computing file changes ...