dtw (version 1.2-1)

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 

## 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{symmetric, slope contraint $P=x$;}

asymmetricPx{asymmetric, slope contraint $P=x$.}

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.

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