Finding the better function to calculate the Dynamic time warping distance (DTW)

I want to calculate the DTW dynamic Time Wrapping distance between two pair of time series records (two vectors r and t, each vector is a time series record), I am using this function:

1- http://www.mathworks.com/matlabcentral/fileexchange/6516-dynamic-time-warping/content/dtw.m

I also found this function:

2- http://au.mathworks.com/matlabcentral/fileexchange/43156-dynamic-time-warping--dtw-/content/dynamic_time_warping_v2.1/dtw.m

I am wondering which one of these functions is more accurate and doing the right job?? can you please help me with this

Answer 1

[Greg Dionne]

If you have the R2016a Signal Processing Toolbox, have a look at:

http://www.mathworks.com/help/signal/ref/dtw.html

You'll want this syntax:

[dist,ix,iy] = dtw(x,y) returns the common set of instants, or warping path, such that x(ix) and y(iy) have the smallest possible dist between them.

The vectors ix and iy have the same length. Each contains a monotonically increasing sequence in which the indices to the elements of the corresponding signal, x or y, are repeated the necessary number of times.

Answer 2

[m qasim]

Hi iam using Matlab 2018a

the DTW function for 2D matrix of DTW returns the absolute value for both metrics 'euclidean as well as absolute

[___] = dtw(___,metric)

[Erik Jakobsson]

I also noticed this bug. It has been reported to Mathworks, but without response now in a month.

[m qasim]

OK I found out the solution.. you can cntct me on email

[Greg Dionne]

Hi Erik, hopefully you have gotten a response by now, but just in case...

The usual confusion around the interpretation behind the 'euclidean' and 'absolute' metric flags is that they are used when comparing each column of data when comparing two matrices. When you are comparing two (row) vectors, there is only one element in each column, and the metric is used pairwise between candidate elements.

There is an attempt to explain this in the help text:

%   When data and signal are matrices, the distances are taken between
%   corresponding column vectors; when data and signal are vectors,
%   distances are taken between the corresponding elements. Note that when
%   data and signal are vectors, 'absolute' and 'euclidean' are equivalent.

So when comparing the error between column m of X and column n of Y you should get something like this:

    abs_d_mn = sum(abs(x(:,m) - y(:,n));          % 'abs' metric
    euc_d_mn = sqrt(sum( (x(:,m) - y(:,n)).^2 )); % 'euclidean' metric.

For two real row vectors, there is no difference between the 'abs' and the 'euclidean' flags since there is only one row to "sum" across, so:

   abs_d_mn = abs(x(1,m) - y(1,n))
   euc_d_mn = sqrt((x(1,m) - y(1,n)).^2)

When comparing two matrices then the 'abs' and 'euclidean' distance flags are meaningfully distinct:

 abs_d_mn = abs(  x(1,m) - y(1,n)) + abs(x(2,m) - y(2,n)) + abs(x(3,m) - y(3,n)) + ...
 euc_d_mn = sqrt((x(1,m) - y(1,n)).^2 + (x(2,m) - y(2,n)).^2 + (x(3,m) - y(3,n)).^2 + ... ))

The motive behind slicing the metric in this fashion is to allow for comparison of data along columns (e.g. looking for similarities behind two spectrograms). For an example of signal search in speech which uses the DTW variant of FINDSIGNAL, see: https://www.mathworks.com/help/signal/ug/finding-a-signal-in-data.html. There we use the (symmetric) Kullback-Leibler distance metric to match columns.

The takeaway is that when you are comparing two vectors, the distance you get is the arithmetic sum of each of the distances across elements - not one distance metric taken across surviving elements.

But what if you actually want the resulting final distance metric to be the Euclidean distance of the matched vectors? Well, a way to get that is to just use the 'squared' metric variant, then take the square root of the sum of the individual squared distances:

s1 = [1, 3, 4, 0.4, 4, 3, 6, 1, 3, 4, 5, 4, 2, 3, 0.4];
s2 = [1, 1, 3, 4, 44, 4, 3, 6, 3, 4, 5, 5, 2, 5, 0.2];

% dtw_dist is the sum of the individual squared distances between matching
% elements of the warping path
[dtw_dist, ix, iy] = dtw(s1, s2, 'squared');

% report the square root of the sum of individual squared distances along
% the warping path
sqrt(dtw_dist)

ans =

  38.3380

% report the euclidean distance of the matched vectors:  
sqrt(sum((s1(ix)-s2(iy)).^2))

ans =

   38.3380  

That will get them to agree (and hopefully give some insight as to how the total distance metric is computed).

Hope this helps!