https://github.com/cran/dtw
Tip revision: d51529a8ee2827cd8c1bd7c4a9e0265dd0cc72cf authored by Toni Giorgino on 19 September 2022, 16:36:11 UTC
version 1.23-1
version 1.23-1
Tip revision: d51529a
stepPattern.Rd
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/stepPattern.R
\name{stepPattern}
\alias{stepPattern}
\alias{is.stepPattern}
\alias{print.stepPattern}
\alias{t.stepPattern}
\alias{plot.stepPattern}
\alias{symmetric1}
\alias{symmetric2}
\alias{asymmetric}
\alias{rabinerJuangStepPattern}
\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}
\alias{mori2006}
\alias{rigid}
\title{Step patterns for DTW}
\usage{
\method{t}{stepPattern}(x)
\method{plot}{stepPattern}(x, ...)
\method{print}{stepPattern}(x, ...)
rabinerJuangStepPattern(type, slope.weighting = "d", smoothed = FALSE)
}
\arguments{
\item{x}{a step pattern object}
\item{...}{additional arguments to \code{\link[=print]{print()}}.}
\item{type}{path specification, integer 1..7 (see (Rabiner1993), table 4.5)}
\item{slope.weighting}{slope weighting rule: character \code{"a"} to \code{"d"} (see (Rabiner1993), sec. 4.7.2.5)}
\item{smoothed}{logical, whether to use smoothing (see (Rabiner1993), fig. 4.44)}
}
\description{
A \code{stepPattern} object lists the transitions allowed while searching
for the minimum-distance path. DTW variants are implemented by passing one
of the objects described in this page to the \code{stepPattern} argument of
the \code{\link[=dtw]{dtw()}} call.
}
\details{
A step pattern characterizes the matching model and slope constraint
specific of a DTW variant. They also known as local- or slope-constraints,
transition types, production or recursion rules (GiorginoJSS).
\strong{Pre-defined step patterns}
\if{html}{\out{<div class="sourceCode">}}\preformatted{ ## Well-known step patterns
symmetric1
symmetric2
asymmetric
## Step patterns classified according to Rabiner-Juang (Rabiner1993)
rabinerJuangStepPattern(type,slope.weighting="d",smoothed=FALSE)
## Slope-constrained step patterns from Sakoe-Chiba (Sakoe1978)
symmetricP0; asymmetricP0
symmetricP05; asymmetricP05
symmetricP1; asymmetricP1
symmetricP2; asymmetricP2
## Step patterns classified according to Rabiner-Myers (Myers1980)
typeIa; typeIb; typeIc; typeId;
typeIas; typeIbs; typeIcs; typeIds; # smoothed
typeIIa; typeIIb; typeIIc; typeIId;
typeIIIc; typeIVc;
## Miscellaneous
mori2006;
rigid;
}\if{html}{\out{</div>}}
A variety of classification schemes have been proposed for step patterns, including
Sakoe-Chiba (Sakoe1978); Rabiner-Juang (Rabiner1993); and Rabiner-Myers
(Myers1980). The \code{dtw} package implements all of the transition types
found in those papers, with the exception of Itakura's and
Velichko-Zagoruyko's steps, which require subtly different algorithms (this
may be rectified in the future). Itakura recursion is almost, but not quite,
equivalent to \code{typeIIIc}.
For convenience, we shall review pre-defined step patterns grouped by
classification. Note that the same pattern may be listed under different
names. Refer to paper (GiorginoJSS) for full details.
\strong{1. Well-known step patterns}
Common DTW implementations are based on one of the following transition
types.
\code{symmetric2} is the normalizable, symmetric, with no local slope
constraints. Since one diagonal step costs as much as the two equivalent
steps along the sides, it can be normalized dividing by \code{N+M}
(query+reference lengths). It is widely used and the default.
\code{asymmetric} is 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. Normalized by
\code{N} (length of query).
\code{symmetric1} (or White-Neely) is quasi-symmetric, no local constraint,
non-normalizable. It is biased in favor of oblique steps.
\strong{2. The Rabiner-Juang set}
A comprehensive table of step patterns is proposed in Rabiner-Juang's book
(Rabiner1993), tab. 4.5. All of them can be constructed through the
\code{rabinerJuangStepPattern(type,slope.weighting,smoothed)} function.
The classification foresees seven families, labelled with Roman numerals
I-VII; here, they are selected through the integer argument \code{type}.
Each family has four slope weighting sub-types, named in sec. 4.7.2.5 as
"Type (a)" to "Type (d)"; they are selected passing a character argument
\code{slope.weighting}, as in the table below. Furthermore, each subtype can
be either plain or smoothed (figure 4.44); smoothing is enabled setting the
logical argument \code{smoothed}. (Not all combinations of arguments make
sense.)
\if{html}{\out{<div class="sourceCode">}}\preformatted{ Subtype | Rule | Norm | Unbiased
--------|------------|------|---------
a | min step | -- | NO
b | max step | -- | NO
c | Di step | N | YES
d | Di+Dj step | N+M | YES
}\if{html}{\out{</div>}}
\strong{3. The Sakoe-Chiba set}
Sakoe-Chiba (Sakoe1978) discuss a family of slope-constrained patterns; they
are implemented as shown in page 47, table I. Here, they are called
\verb{symmetricP<x>} and \verb{asymmetricP<x>}, where \verb{<x>} corresponds
to Sakoe's integer slope parameter \emph{P}. Values available are
accordingly: \code{0} (no constraint), \code{1}, \code{05} (one half) and
\code{2}. See (Sakoe1978) for details.
\strong{4. The Rabiner-Myers set}
The \verb{type<XX><y>} step patterns follow the older Rabiner-Myers'
classification proposed in (Myers1980) and (MRR1980). Note that this is a
subset of the Rabiner-Juang set (Rabiner1993), and the latter should be
preferred in order to avoid confusion. \verb{<XX>} is a Roman numeral
specifying the shape of the transitions; \verb{<y>} is a letter in the range
\code{a-d} specifying the weighting used per step, as above; \code{typeIIx}
patterns also have a version ending in \code{s}, meaning the smoothing is
used (which does not permit skipping points). The \verb{typeId, typeIId} and
\code{typeIIds} are unbiased and symmetric.
\strong{5. Others}
The \code{rigid} pattern enforces a fixed unitary slope. It only makes sense
in combination with \code{open.begin=TRUE}, \code{open.end=TRUE} to find gapless
subsequences. It may be seen as the \code{P->inf} limiting case in Sakoe's classification.
\code{mori2006} is Mori's asymmetric step-constrained pattern (Mori2006). It
is normalized by the matched reference length.
\code{\link[=mvmStepPattern]{mvmStepPattern()}} implements Latecki's Minimum Variance
Matching algorithm, and it is described in its own page.
\strong{Methods}
\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 shown along the step leading to
the corresponding element.
\code{t.stepPattern} transposes the productions and normalization hint so
that roles of query and reference become reversed.
}
\note{
Constructing \code{stepPattern} objects is tricky and thus undocumented. For a commented example please see source code for \code{symmetricP1}.
}
\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(symmetric2) # or just "symmetric2"
#########
##
## The well-known plotting style for step patterns
plot(symmetricP2,main="Sakoe's Symmetric P=2 recursion")
#########
##
## Same example seen in ?dtw , now with asymmetric step pattern
idx<-seq(0,6.28,len=100);
query<-sin(idx)+runif(100)/10;
reference<-cos(idx);
## Do the computation
asy<-dtw(query,reference,keep=TRUE,step=asymmetric);
dtwPlot(asy,type="density",main="Sine and cosine, asymmetric step")
#########
##
## Hand-checkable example given in [Myers1980] 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))
}
\references{
\itemize{
\item (GiorginoJSS) 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 (Itakura1975) Itakura, F., \emph{Minimum prediction residual
principle applied to speech recognition,} Acoustics, Speech, and Signal
Processing, IEEE Transactions on , vol.23, no.1, pp. 67-72, Feb 1975.
\doi{10.1109/TASSP.1975.1162641}
\item (MRR1980) Myers,
C.; Rabiner, L. & Rosenberg, A. \emph{Performance tradeoffs in dynamic time
warping algorithms for isolated word recognition}, IEEE Trans. Acoust.,
Speech, Signal Process., 1980, 28, 623-635.
\doi{10.1109/TASSP.1980.1163491}
\item (Mori2006) 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}
\item (Myers1980) Myers,
Cory S. \emph{A Comparative Study Of Several Dynamic Time Warping
Algorithms For Speech Recognition}, MS and BS thesis, Dept. of Electrical
Engineering and Computer Science, Massachusetts Institute of Technology,
archived Jun 20 1980, \url{https://hdl.handle.net/1721.1/27909}
\item (Rabiner1993) Rabiner, L. R., & Juang, B.-H. (1993). \emph{Fundamentals of
speech recognition.} Englewood Cliffs, NJ: Prentice Hall.
\item (Sakoe1978) 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}
}
}
\seealso{
\code{\link[=mvmStepPattern]{mvmStepPattern()}}, implementing Latecki's Minimal
Variance Matching algorithm.
}
\author{
Toni Giorgino
}
\keyword{ts}