# stepPattern: Step patterns for DTW In dtw: Dynamic Time Warping Algorithms

## Description

A `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 `stepPattern` argument of the `dtw` call.

## Usage

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33``` ```## 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; ## S3 method for class 'stepPattern' print(x,...) ## S3 method for class 'stepPattern' plot(x,...) ## S3 method for class 'stepPattern' t(x) stepPattern(v,norm=NA) is.stepPattern(x) ```

## Arguments

 `x` a step pattern object `type` path specification, integer 1..7 (see [Rabiner1993], table 4.5) `slope.weighting` slope weighting rule: character `"a"` to `"d"` (see [Rabiner1993], sec. 4.7.2.5) `smoothed` logical, whether to use smoothing (see [Rabiner1993], fig. 4.44) `v` a vector defining the stepPattern structure `norm` normalization hint (character) `...` additional arguments to `print`.

## 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].

`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 to `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.

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 `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 `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 `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.)

 Subtype Rule Norm Unbiased a min step -- NO b max step -- NO c Di step N YES d Di+Dj step N+M YES

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 `symmetricP<x>` and `asymmetricP<x>`, where `<x>` corresponds to Sakoe's integer slope parameter P. Values available are accordingly: `0` (no constraint), `1`, `05` (one half) and `2`. See [Sakoe1978] for details.

4. The Rabiner-Myers set

The `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], which should be preferred in order to avoid confusion. `<XX>` is a roman numeral specifying the shape of the transitions; `<y>` is a letter in the range `a-d` specifying the weighting used per step, as above; `typeIIx` patterns also have a version ending in `s`, meaning the smoothing is used (which does not permit skipping points). The `typeId, typeIId` and `typeIIds` are unbiased and symmetric.

5. Other

The `rigid` pattern enforces a fixed unitary slope. It only makes sense in combination with `open.begin=T`, `open.end=T` to find gapless subsequences. It may be seen as the P->inf limiting case in Sakoe's classification.

`mori2006` is Mori's asymmetric step-constrained pattern [Mori2006]. It is normalized by the matched reference length.

## Note

Constructing `stepPattern` objects is tricky and thus undocumented. For a commented example please see source code for `symmetricP1`.

Toni Giorgino

## References

[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

`mvmStepPattern`, implementing Latecki's Minimal Variance Matching algorithm.
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44``` ```######### ## ## 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)) ```