Step patterns for DTW
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
stepPattern argument of the
## 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;"print"(x,...) "plot"(x,...) "t"(x)stepPattern(v,norm=NA) is.stepPattern(x)
- a step pattern object
- path specification, integer 1..7 (see [Rabiner1993], table 4.5)
- slope weighting rule: character
"d"(see [Rabiner1993], sec. 188.8.131.52)
- logical, whether to use smoothing (see [Rabiner1993], fig. 4.44)
- a vector defining the stepPattern structure
- normalization hint (character)
- additional arguments to
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].
print.stepPattern prints an user-readable
description of the recurrence equation defined by the given pattern.
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.
t.stepPattern transposes the productions and normalization hint
so that roles of query and reference become reversed.
A variety of classifications have been proposed for step patterns, including Sakoe-Chiba [Sakoe1978]; Rabiner-Juang [Rabiner1993]; and Rabiner-Myers [Myers1980]. The
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
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.
1. Well-known step patterns
These common transition types are used in quite a lot of implementations.
symmetric1 (or White-Neely) is the commonly used
quasi-symmetric, no local constraint, non-normalizable. It is biased
in favor of oblique steps.
symmetric2 is 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
N+M (query+reference lengths).
asymmetric is asymmetric, slope constrained between 0 and
2. Matches each element of the query time series exactly once, so
the warping path
index2~index1 is guaranteed to
be single-valued. Normalized by
N (length of query).
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
The classification foresees seven families, labelled with Roman numerals I-VII; here, they are selected through the integer argument
type. Each family has four slope weighting sub-types, named in
sec. 184.108.40.206 as "Type (a)" to "Type (d)"; they are selected passing a
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
smoothed. (Not all combinations of arguments make sense.)
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
corresponds to Sakoe's integer slope parameter P. Values available are accordingly:
05(one half) and
2. See [Sakoe1978] for details.
4. The Rabiner-Myers set The
typestep patterns follow the older Rabiner-Myers' classification proposed in [Myers1980] and [MRR1980]. Note that this is a subset of the Rabiner-Juang set [Rabiner1993], which should be preferred in order to avoid confusion.
is a roman numeral specifying the shape of the transitions;
is a letter in the range
a-dspecifying the weighting used per step, as above;
typeIIxpatterns also have a version ending in
s, meaning the smoothing is used (which does not permit skipping points). The
typeIIdsare unbiased and symmetric.
rigidpattern enforces a fixed unitary slope. It only makes sense in combination with
open.end=Tto find gapless subsequences. It may be seen as the $P->inf$ limiting case in Sakoe's classification.
mori2006is Mori's asymmetric step-constrained pattern [Mori2006]. It is normalized by the matched reference length.
stepPattern objects is tricky and thus
undocumented. For a commented example please see source code for
[GiorginoJSS] Toni Giorgino. Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package. Journal of Statistical Software, 31(7), 1-24. http://www.jstatsoft.org/v31/i07/ [Itakura1975] Itakura, F., 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: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1162641 [MRR1980] Myers, C.; Rabiner, L. & Rosenberg, A. Performance tradeoffs in dynamic time warping algorithms for isolated word recognition, IEEE Trans. Acoust., Speech, Signal Process., 1980, 28, 623-635. URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1163491&tag=1 [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. URL: http://dx.doi.org/10.1109/ICPR.2006.467 [Myers1980] Myers, C. S. A Comparative Study Of Several Dynamic Time Warping Algorithms For Speech Recognition, MS and BS thesis, MIT Jun 20 1980, dspace.mit.edu/bitstream/1721.1/27909/1/07888629.pdf [Rabiner1993] Rabiner, L. R., & Juang, B.-H. (1993). Fundamentals of speech recognition. Englewood Cliffs, NJ: Prentice Hall. [Sakoe1978] 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
Latecki's Minimal Variance Matching algorithm.
######### ## ## 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))