# Step patterns for DTW

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

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

### 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`

.

### Author(s)

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

### See Also

`mvmStepPattern`

, implementing
Latecki's Minimal Variance Matching algorithm.

### Examples

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