StepPattern¶
- class dtw.StepPattern(mx, hint='NA')¶
Bases:
object
Step patterns for DTW
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 thestepPattern
argument of the [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).
Pre-defined step patterns
## 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;
A variety of classification schemes 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 totypeIIIc
.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
Common DTW implementations are based on one of the following transition types.
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 byN+M
(query+reference lengths). It is widely used and the default.asymmetric
is asymmetric, slope constrained between 0 and 2. Matches each element of the query time series exactly once, so the warping pathindex2~index1
is guaranteed to be single-valued. Normalized byN
(length of query).symmetric1
(or White-Neely) is quasi-symmetric, no local constraint, non-normalizable. It is biased in favor of oblique steps.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 argumentslope_weighting
, as in the table below. Furthermore, each subtype can be either plain or smoothed (figure 4.44); smoothing is enabled setting the logical argumentsmoothed
. (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>
andasymmetricP<x>
, where<x>
corresponds to Sakoe’s integer slope parameter P. Values available are accordingly:0
(no constraint),1
,05
(one half) and2
. 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), and the latter 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 rangea-d
specifying the weighting used per step, as above;typeIIx
patterns also have a version ending ins
, meaning the smoothing is used (which does not permit skipping points). ThetypeId, typeIId
andtypeIIds
are unbiased and symmetric.5. Others
The
rigid
pattern enforces a fixed unitary slope. It only makes sense in combination withopen_begin=True
,open_end=True
to find gapless subsequences. It may be seen as theP->inf
limiting case in Sakoe’s classification.mori2006
is Mori’s asymmetric step-constrained pattern (Mori2006). It is normalized by the matched reference length.[mvmStepPattern()] implements Latecki’s Minimum Variance Matching algorithm, and it is described in its own page.
Methods
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.- Parameters:
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)
... – additional arguments to [print()].
Notes
Constructing
stepPattern
objects is tricky and thus undocumented. For a commented example please see source code forsymmetricP1
.References
(GiorginoJSS) Toni Giorgino. 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
(Itakura1975) Itakura, F., 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
(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. doi:10.1109/TASSP.1980.1163491
(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
(Myers1980) Myers, Cory S. 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, https://hdl_handle_net/1721.1/27909
(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, IEEE Transactions on , vol.26, no.1, pp. 43-49, Feb 1978 doi:10.1109/TASSP.1978.1163055
Examples
>>> from dtw import * >>> import numpy as np
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) Step pattern recursion: g[i,j] = min( g[i-1,j-1] + 2 * d[i ,j ] , g[i ,j-1] + d[i ,j ] , g[i-1,j ] + d[i ,j ] , ) Normalization hint: N+M
The well-known plotting style for step patterns
>>> import matplotlib.pyplot as plt; ... symmetricP2.plot().set_title("Sakoe's Symmetric P=2 recursion")
Same example seen in ?dtw , now with asymmetric step pattern
>>> (query, reference) = dtw_test_data.sin_cos()
Do the computation
>>> asy = dtw(query, reference, keep_internals=True, ... step_pattern=asymmetric);
>>> dtwPlot(asy,type="density" ... ).set_title("Sine and cosine, asymmetric step")
Hand-checkable example given in [Myers1980] p 61 - see JSS paper
>>> tm = numpy.reshape( [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], (5,5), "F" )
Methods Summary
T
()Transpose a step pattern.
Number of rules in the recursion.
Total number of steps in the recursion.
plot
()Provide a visual description of a StepPattern object
Methods Documentation
- T()¶
Transpose a step pattern.
- get_n_patterns()¶
Number of rules in the recursion.
- get_n_rows()¶
Total number of steps in the recursion.
- plot()¶
Provide a visual description of a StepPattern object