dtw (version 0.4-2)

stepPattern: Local constraints and step patterns for DTW

Description

A step pattern object lists the allowed step patterns for a given DTW variant. It can be used to constrain the warping paths considered by the dtw function.

Usage

# predefined step patterns:
symmetric1
symmetric2
asymmetric
symmetricP1
asymmetricItakura
## S3 method for class 'stepPattern':
print(x,...)
is.stepPattern(x)
stepPattern(v)

Arguments

x

a step pattern object

v

a vector defining the stepPattern structure (see below)

...

additional arguments to print.

code

print.stepPattern

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 branch: 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
• 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 pattern.

Several step patterns are pre-defined:

• symmetric1

{quasi-symmetric, no slope constraint. Favours oblique steps.}

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

asymmetric{asymmetric, no slope constraint. Matches each element of the query time series exactly once.}

symmetricP1{symmetric, slope contraint $P=1$ (see reference [1], page 47, table I)}

asymmetricItakura{asymmetric, slope contrained. This is the recursive function described in reference [2] that generates the Itakura parallelogram. }

{...more to come}

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

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)



## Same example seen in dtw help, but with asymmetric  step pattern

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

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

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