DTWa

This is a supporting webpage to our paper: 
"Generalizing Dynamic Time Warping to the Multi-Dimensional Case Requires an Adaptive Approach"



 Source Code and Data Sets  


Here are the Codes and all the Data Sets we used in the paper.
  • The format for all data sets: Each row corresponds to a z-normalized time series exemplar, the first value is the class label and the remaining values are the time series.  
  •  All codes are written in Matlab, for classification results you need to run the classificationTest() funtion. The following inputs should be set up:
w :  the warping window constraint
train 1 and 2: the train sets for the first and second dimensions
test 1 and 2: the test sets for the first and second dimensions

This code is written for a two-dimensional time series. However, it is simply possible to generalize it to more than two dimensions. We have implemented the code for three and six dimensions. 
After the function runs over the whole test data, the results will be available at "Results.txt" including the following results (in order):

1- Classification accuracy using only the first dimension
2- Classification accuracy using only the second dimension
3- Classification accuracy using DTWI
4- Classification accuracy using DTWD
5- The optimal classification accuracy
6- Classification accuracy using DTW
7- Number of exemplars in iSuccess
8- Number of exemplars in dSuccess

 Bibliography of Related Work

We have done an extensive search in the literature to find papers which use DTWD , DTWI and papers which do not discuss their choice of DTW:
Papers which use DTWD :

1- Francois Petitjean, Jordi Inglada and Pierre Gancarski, Satellite Image Time Series Analysis under Time Warping:  
... "There are actually two main ways of comparing two multi-dimensional sequences with DTW: • computing DTW B times, one time per dimension (i.e., per band); • using a B-dimensional δ in the computation of DTW ... The second solution appears to better fit the analysis of radiometric series. Actually, to distinguish the several land cover states, the set of the B values sensed at the same time is required. The first solution would only be interesting if the behavior of the sequences in every band was independent; if the synchronicity of the B values was not required. In this way, the first solution would be adapted to sensed areas were the B are representing uncorrelated phenomenons, which is rarely the case in remote sensing" ...

2- Nicholas Gillian, R. Benjamin Knapp, Sile O’Modhrain, Recognition Of Multivariate Temporal Musical Gestures Using N-Dimensional Dynamic Time Warping:
... "This takes the summation of distance errors between each dimension of an N-dimensional template and the new N-dimensional time-series. The total distance across all N dimensions is then used to construct the warping ma- trix C. We will use the Euclidean distance as a distance measure across the N dimensions of the template and new time-series" ...

3- Ahmed Al-Jawad, Miguel Reyes Adame, Michailas Romanovas, Markus Hobert, Walter Maetzler, Martin Traechtler, Knut Moeller and Yiannos Manoli, Using multi-dimensional dynamic time warping for TUG Test instrumentation with inertial sensors:
... "The classical DTW can be extended to measure the similarity between two N-dimensional sequences A and B where the local distance is defined as" ...

4- Rodrigo Fernandes de Mello and Iker Gondra, Multi-Dimensional Dynamic Time Warping for Image Texture Similarity:
... "However, there are many applications in which calculating an optimal alignment requires the use of multi-dimensional series. Holt et al. [1] proposed the Multi-Dimensional Dynamic Time Warping (MD-DTW), an approach to calculate the DTW by synchronizing multi-dimensional series, which is basically an extension of the original DTW, where the matrix D is created by computing the distance be- tween k-dimensional points (where, differently from the original approach, k can be larger than 1)." ...

5-  R. Sherkat, D. Rafiei, "On efficiently searching trajectories and archival data for historical similarities", VLDB 2008


Papers which use DTW:  
(The following papers do not use exactly use the DTWI defined in our paper, they do something similar which is adding all the channels together)

1- G.A. ten Holta,b M.J.T. Reindersa E.A. Hendriks. Multi-DimensionalDynamicTimeWarpingforGesture Recognition:
This paper uses not exactly DTWI but something similar: ... "TheMD-DTWAlgorithm Let A,B be two series of dimension K and length M,N respectively. • Normalize each dimension of A and B separately to a zero mean and unit variance • If desired, smooth each dimension with a Gaussian filter • Fill the M by N distance matrix 
• Use this distance matrix (the total difference among dimensions) to find the best synchronization with the regular DTW algorithm" ...

2- Muzaffar Bashir and Jurgen Kempf. Reduced Dynamic Time Warping for Handwriting Recognition Based on Multi-Dimensional Time Series of a Novel Pen Device
... "the DTW algorithm is applied to the data of each channel and to the data obtained from the sum of all channels, respectively" ...

3- David McGlynn and Michael G. Madden. An Ensemble Dynamic Time Warping Classifier with Application to Activity Recognition:
... "When applying this to activity recognition, where we are dealing with 3D data (x, y and z-axis) read from on-body accelerometers, these three values must first be used to calculate the Signal Vector Magnitude" ...

Papers do not mention their DTW choice:
Most papers in the literature belong to this category, for example:
1- Jiayang Liu, Zhen Wang, Lin Zhong, Jehan Wickramasuriya, Venu Vasudevan, uWave: Accelerometer-based Personalized Gesture Recognition and Its Applications:
... "DTW employs dynamic programming to calculate the matching cost and find the corresponding optimal path. As illustrated in" ...

2- John Aach and George M. Church. Aligning gene expression time series with time warping algorithms

3- Ahmad Akl, Shahrokh Valaee. ACCELEROMETER-BASED GESTURE RECOGNITION VIA DYNAMIC–TIME WARPING, AFFINITY PROPAGATION, & COMPRESSIVE SENSING

4- Nimish Kale, Jaeseong Lee, Reza Lotfian and Roozbeh Jafari . Impact of Sensor Misplacement on Dynamic Time Warping Based Human Activity Recognition using Wearable Computers 
...


 Experiments on a Synthetic Data Set

We constructed the following two dimensional data set (two class problem A and B) in order to compare DTWI (I) and DTWD (D) on two types of data sets, dependently warped (d) and independently warped (i): 
The results suggest if the data dimensions are dependently warped, use DTWD to classify the data. If the data dimensions are independently warped, DTWI will give you more accurate results for classifying the data. 

 Experiments on Additional Data Sets

We have provided classification results on the acceleration data from the Handwriting data set. Here we provide additional results (error rates) on the data collected from its Gyroscope:

 Data Set DTWI DTWD DTWA
 Gyroscope X_Y 0.43 0.39 0.38
 Gyroscope X_Z0.38  0.29 0.29
 Gyroscope Y_Z 0.44 0.41 0.39


For the synthetic data set described in the previous section, we applied both DTWD and DTWI and found the following error rates for classification:

 Data Set DTWI DTWD DTWA
 Independent Warped 0.11 0.18 0.07
 Dependent Warped0.08  0.02 0.02
----

For the ElectroMagnetic Articulograph data set here we show the classification results for few more combinations of dimensions in addition to our paper:
 
 Data Set DTWI DTWD DTWA
 T1(Y)_T1(Z) 0.24 0.15 0.15
 T1(X)_T1(Y)_T1(Z)0.15 0.10 0.10
T1(X)_T1(Y)_UL(Y)0.160.180.14



 Images from Old Manuscripts

In the Introduction section of our paper, we show samples of images from old manuscripts, here you can find more examples with higher resolutions:




 The Cricket Data Set

Here is a complete list of cricket umpire signals: