Class for temporal alignment based on Dynamic Time Warping (DTW).

Description

The class Dtw can be used for aligning two temporal sequences using the Dynamic Time Warping (DTW). DTW calculates the optimal path which minimizes the distance between the two signals to be aligned. Given two signals $s$ and $t$ , with $n_s$ and $n_t$ samples respectively, DTW constructs the $n_s x n_t$ distance matrix $D$ , where $D_{(i,j)} = d(s_i,t_j) + \min{(d(i-1,j-1),d(i-1,j),d(i,j-1))}$ , and $d(i,j) = \sqrt{(s_i-t_i)^2}$ . A warping path has to satisfy the following conditions:

monotonic condition: the path monotonically increases;
continuity condition: the path advances one step at a time;
boundary condition: the path starts at bottom left and ends at top right. The optimal warping path with length is the one that minimizes the total distance among all possible warping paths:
$d_{DTW} = \min_{i=1}^k D(w_i)$
The DTW distance is the total distance of the optimal warping path.

DTW can be also applied to multidimensional temporal sequences, by applying the same procedure independently to the corresponding components of the two signals. The DTW distance is the sum of the DTW distances of each component.

Additional constraints can be used to restrict the space of search of the warping path. The library includes the adjustment window condition, which enforces the search of the warping path inside a window around the distance matrix diagonal.

Example

Given two vectors v1,v2, the following piece of code can be used to align them and get the DTW distance:

Dtw dtw(-1);
vector<double> w_v1,w_v2; //aligned signals
dtw.align(v1,v2,w_v1,w_v2);
double d = dtw.getDistance();

For the multidimensional case, given two signals with $n$ samples over time and $m$ components, v1 and v2 have to be defined as $n$ vector of $m$ vectors. The following piece of code can be used to align them and get the DTW distance:

Dtw dtw(-1);
vector<vector<double>> w_v1,w_v2; //aligned signals are now defined as vector of vectors
dtw.align(v1,v2,w_v1,w_v2);
double d = dtw.getDistance();

Author: Valentina Vasco valen.nosp@m.tina.nosp@m..vasc.nosp@m.o@ii.nosp@m.t.it