dtw (version 1.4-3)

stepPattern: Local constraints and step patterns for DTW

Description

DTW variants are implemented through step pattern objects. A stepPattern instance lists the transitions allowed by the dtw function in the search for the minimum-distance path.

Usage

## Well-known step patterns
  symmetric1
  symmetric2
  asymmetric
  asymmetricItakura
## Slope-constrained step patterns from Sakoe-Chiba
  symmetricP0;  asymmetricP0
  symmetricP05; asymmetricP05
  symmetricP1;  asymmetricP1
  symmetricP2;  asymmetricP2 
## Step patterns classified as per Rabiner-Myers
  typeIa;   typeIb;   typeIc;   typeId;
  typeIas;  typeIbs;  typeIcs;  typeIds;  # smoothed
  typeIIa;  typeIIb;  typeIIc;  typeIId;
  typeIIIc; typeIVc;
## S3 method for class 'stepPattern':
print(x,...)
stepPattern(v)
is.stepPattern(x)

Arguments

x

a step pattern object

v

a vector defining the stepPattern structure (see below)

...

additional arguments to print.

code

print.stepPattern

emph

• P
• P=1, Symmetric

preformatted

symmetricP1 <- stepPattern(c( 1,1,2,-1, # First branch: g(i-1,j-2) + 1,0,1,2, # + 2d( i ,j-1) + 1,0,0,1, # + d( i , j ) 2,1,1,-1, # Second br.: g(i-1,j-1) + 2,0,0,2, # + 2d( i , j ) 3,2,1,-1, # Third branch: g(i-2,j-1) + 3,1,0,2, # + 2d(i-1, j ) + 3,0,0,1 # + d( i , j ) ));

concept

• Dynamic Time Warp
• Dynamic Programming
• Step pattern
• Transition
• Local constraint
• Asymmetric DTW
• Symmetric DTW

Details

A step pattern characterizes the matching model and/or slope constraint specific of a DTW variant.

print.stepPattern prints an user-readable description of the recurrence equation defined by the given pattern. Several step patterns are pre-defined with the package:

• symmetric1

{quasi-symmetric, no slope constraint (favours oblique steps);}

symmetric2{properly symmetric, no slope constraint: one diagonal step costs as much as the sum of the equivalent steps along the sides; }

asymmetric{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; }

asymmetricItakura{asymmetric, slope contrained 0.5 -- 2 from reference [2]. This is the recursive definition that generates the Itakura parallelogram; } symmetricPx{Sakoe's symmetric, slope contraint x;}

asymmetricPx{Sakoe's asymmetric, slope contraint x.}

typeNNw{Rabiner-Myers classification (see details).}

References

[1] 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 [2] 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 [3] Rabiner, L. R., & Juang, B.-H. (1993). Fundamentals of speech recognition. Englewood Cliffs, NJ: Prentice Hall. [4] 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

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.stepPattern(symmetric2)   # or just "symmetric2"



#########
##
## Same example seen in ?dtw , now with asymmetric step pattern

idx<-seq(0,6.28,len=100);
query<-sin(idx)+runif(100)/10;
template<-cos(idx);

## Do the computation 
asy<-dtw(query,template,keep=TRUE,step=asymmetric);

dtwPlot(asy,type="density",main="Sine and cosine, asymmetric step")


#########
##
##  Hand-checkable example given in [4] 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))