dtw (version 1.2-1)

dtwWindowingFunctions: Global constraints and windowing functions for DTW

Description

Various global constraints (windows) which can be applied to the window.type argument of dtw, including the Sakoe-Chiba band, the Itakura parallelogram, and custom functions.

Usage

noWindow(iw, jw, ...);
sakoeChibaWindow(iw,jw,  window.size,...);
slantedBandWindow(iw,jw,query.size,template.size,  window.size,...);
itakuraWindow(iw,jw,query.size,template.size,  ...); 
dtwWindow.plot(fun,query.size=200,template.size=220,...);

Arguments

iw

index in the query (row) -- automatically set

jw

index in the template (column) -- automatically set

query.size

size of the query time series -- automatically set

template.size

size of the template time series -- automatically set

window.size

window size, used by some windowing functions -- must be set

fun

a windowing function

...

additional arguments passed to windowing functions

Value

• Windowing functions return TRUE if the coordinates passed as arguments fall within the chosen warping window, FALSE otherwise. User-defined functions should do the same.

concept

• Dynamic Time Warp
• Global contraint
• Windowing
• Sakoe-Chiba Band
• Itakura Parallelogram

Details

Windowing functions can be passed to the window.type argument in dtw to put a global constraint to the warping paths allowed. They take two integer arguments (plus optional parameters) and must return a boolean value TRUE if the coordinates fall within the allowed region for warping paths, FALSE otherwise.

dtwWindow.plot can be used to visualize a chosen windowing function. Some functions take parameters which must be set (e.g. window.size). dtwWindow.plot plots a 200 x 220 rectangular region by default, which can be changed passing template.size and query.size arguments. User-defined functions can read variables template.size, query.size and window.size; these are pre-set upon invocation. User-defined functions are free to implement any window shape, as long as at least one path is allowed between the initial and final alignment points, i.e., they are compatible with the DTW constraints.

The Sakoe-Chiba band is a band of window.size elements around the main diagonal. If the window size is too small, i.e. $template.size-query.size > window.size$, warping becomes impossible.

A widely held misconception is that the "Itakura parallelogram" (as described in reference [2]) is a global constraint, i.e. a window. To the author's knowledge, it instead arises from the local slope restrictions imposed to the warping path, such as the one implemented by the asymmetricItakura step pattern.

An itakuraWindow global constraint is still provided with this package. See example below for a demonstration of the difference between a local the two.

The slantedBandWindow (package-specific) is a band centered around the (jagged) line segment which joins element [1,1] to element [query.size,template.size], and will be window.size columns wide. In other words, the "diagonal" goes from one corner to the other of the possibly rectangular cost matrix, therefore having a slope of M/N, not 1.

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

## Display some windowing functions
dtwWindow.plot(itakuraWindow, main="So-called Itakura parallelogram window")
dtwWindow.plot(slantedBandWindow, window.size=2,
  template=13, query=17, main="The slantedBandWindow at window.size=2")


## Asymmetric step with Sakoe-Chiba band

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

asyband<-dtw(query,template,keep=TRUE,
             step=asymmetric,
             window.type=sakoeChibaWindow,
             window.size=30                  );

dtwPlot(asyband,type="density",main="Sine/cosine: asymmetric step, S-C window")