Dynamic Time Warping

Dynamic time warping program. Calculates the similarity between 2 vectors.

Description

If you pass in 2 vectors it returns the unnormalized distance between the vectors, the accumulated distance between them, the length of the warping path (the normalizing factor), and the warping path points.

To compare 2 vectors A and B call:
[Dist,D,k,w]=dtw(A,B)
Dist is the unnormalized distance
D is the accumulated distance
k is the length of the warping path
(the normalizing factor)
w is a matrix containing the points along the warping path

• Acknowledgements: This submission has inspired the following:; Constrained Dynamic Time Warping Distance Measure, Continuous Dynamic Time Warping
• MATLAB release: MATLAB 6.1 (R12.1)

[zhlong l]

 

[mahajan bhushan]

 

[Carlos Franco]

 

[Georg Schmitz]

The routine can be made 10 times faster by doing the d(n,m) calculation by

d=(repmat(t(:),1,M)-repmat(r(:)',N,1)).^2;

instead of the loop.

[Ivo Ihrke]

The loop

for m=2:m
    D(1,m)=d(1,m)+D(1,m-1);
end

contains an error ( for statement ), should be:

for m=2:M
    D(1,m)=d(1,m)+D(1,m-1);
end

If you want to compare vectors, where the vectors themselves are unknown, but their distance matrix is known, you can use your distance matrix instead of "d"

[jamal habibi]

 

[Natan K]

Can you tell me about speaker verification using mfcc and dtw. Please let me know.

[Rogelio Ramos]

 

[reza rezaww]

 

[Yuzeng Lv]

 

[Boat MiMi]

...

[Sven Mensing]

Good function
Another 10-fold Speed-up can be achived if you use a double-MIN construction for the Distance matrix

D(n,m)=d(n,m)+min(D(n-1,m),min(D(n-1,m-1),D(n,m-1)));

[weera kompreyaray]

 

[Pau Micó]

I think it should be better to replace the sentence: w=cat(1,w,[n,m]); by: w=[n m; w];
In this way we get the w indexes in ascending order and it is easier to get t_warped and r_warped as: t_warped=t(w(:,1)); and r_warped=t(w(:,2));. In this way we can directly compare the warped sequences with the original ones without any index inversion.

[twinss ahmed]

 

[Sai Man]

Great code thanks for writing. But, I noticed a small discrepancy with my C code. In the .m file line 45:
min([D(n-1,m),D(n,m-1),D(n-1,m-1)]);

it would be much better to have the D(n-1,m-1) element in the first argument like this:
min([D(n-1,m-1),D(n,m-1),D(n-1,m)]);
and also swap the cases on the following lines.

This is because we are trying to find the minimum path length, and in the case where D(n-1,m-1)=D(n,m-1) or D(n-1,m-1)=D(n-1,m) then it would make sense to preference the diagonal element over the offdiagonal.

[Ahmed Bderhman]

I think this is a good working and had help me more.

I have this question: i like to change euclidean distance{d=(repmat(Test',1,N)-repmat(Ref,M,1)).^2;} with mahalanobis distance is it possipole? if yes how can i do that?

because i like to test the efficiency of my system when i use euclidean distance and when i used mahalnobis distance.

 

[Zhuo Feibao]

 

[Tony Mei]

Can anyone explain how to use the normalizing factor? Thanks a lot.

[Wen]

should not be, d(n,m)=sqrt(sum((t(:,n)-r(:,m)).^2)); instead of d(n,m)=(t(n)-r(m))^2;
t, r are sequences of rows-dim vectors

[Mano Samuel]

Hi Timothy,
   could you let me know which article or book you used as a reference to code this ? . Thank you.
Mano

[Nandha]

Can I know how can I implement lower bounding (LB_keogh) and global constraint to this algorithm ?

Also, how to use obtain normalized distance using the normalizing factor ?

[abdur]

im trying to compare two vectors of audio samples but the matrix dimensions dont match n d code gives error. plz assist

[Lars]

Maybe add code to ensure proper vectors, e.g. t=t(:)'; and r=r(:)'; in this case ;)

[Mohammed Khalilia]

At least answer the previous questions!

[He]

 

[Vicky]

 

[Akhil Sudhakar]

please send complete code for melodic contour matching....