I have calculated 26 MFCCs for two sample speech data. My mfcc matrices thus contain 26 columns and 120 rows each, where 120 is the number of frames. Now I want to apply DTW on them and I am doing this (on MATLAB):


which I have taken from this post

But I don't quite understand why the similarity matrix and why it has to be 1-M ?

Also if I exclude the first co-efficient, the result becomes totally invalid i.e it seems the first co-efficient is mandatory for DTW.

Is there something wrong with my approach? If it is, then how can I make it right?


function [p,q,D] = dp(M)
% [p,q] = dp(M) 
%    Use dynamic programming to find a min-cost path through matrix M.
%    Return state sequence in p,q
% 2003-03-15 dpwe@ee.columbia.edu

% Copyright (c) 2003 Dan Ellis <dpwe@ee.columbia.edu>
% released under GPL - see file COPYRIGHT

[r,c] = size(M);

% costs
D = zeros(r+1, c+1);
D(1,:) = NaN;
D(:,1) = NaN;
D(1,1) = 0;
D(2:(r+1), 2:(c+1)) = M;

% traceback
phi = zeros(r,c);

for i = 1:r; 
  for j = 1:c;
    [dmax, tb] = min([D(i, j), D(i, j+1), D(i+1, j)]);
    D(i+1,j+1) = D(i+1,j+1)+dmax;
    phi(i,j) = tb;

% Traceback from top left
i = r; 
j = c;
p = i;
q = j;
while i > 1 & j > 1
  tb = phi(i,j);
  if (tb == 1)
    i = i-1;
    j = j-1;
  elseif (tb == 2)
    i = i-1;
  elseif (tb == 3)
    j = j-1;
  p = [i,p];
  q = [j,q];

% Strip off the edges of the D matrix before returning
D = D(2:(r+1),2:(c+1));


function M = simmx(A,B)
% M = simmx(A,B)
%    calculate a sim matrix between specgram-like feature matrices A and B.
%    size(M) = [size(A,2) size(B,2)]; A and B have same #rows.
% 2003-03-15 dpwe@ee.columbia.edu

% Copyright (c) 2003 Dan Ellis <dpwe@ee.columbia.edu>
% released under GPL - see file COPYRIGHT

EA = sqrt(sum(A.^2));
EB = sqrt(sum(B.^2));

%ncA = size(A,2);
%ncB = size(B,2);
%M = zeros(ncA, ncB);
%for i = 1:ncA
%  for j = 1:ncB
%    % normalized inner product i.e. cos(angle between vectors)
%    M(i,j) = (A(:,i)'*B(:,j))/(EA(i)*EB(j));
%  end

% this is 10x faster
M = (A'*B)./(EA'*EB);
  • $\begingroup$ What is [p,q,c]=dp(1-M); Can you provide the matlab reference for the dp() function, I googled but could not find it quickly. This will help me understand what is going on with 1-M $\endgroup$ – ruoho ruotsi Apr 4 '17 at 16:24
  • $\begingroup$ @ruohoruotsi : Added the code.. $\endgroup$ – Jahid Apr 5 '17 at 5:23

Let's unpack this code:

1    mfcc1=mfcc1';
2    mfcc2=mfcc2';
3    M=simmx(mfcc1,mfcc2);
4    [p,q,c]=dp(1-M);
5    v=c(size(c,1),size(c,2))

in line 3, M=simmx(mfcc1,mfcc2); is computing the Cosine Similarity, i.e. normalized inner product or the cosine of the angle between them. Here are my comments about why the authors used 1-M instead of M.

When computing dtw, you want to find the lowest-cost path through the "cost" matrix. Dan Ellis's implementation uses dynamic programming to find the lowest-cost path between the opposite corners of the cost matrix.

However Cosine Similarity (whose values are on the range [-1,1]) is not a proper distance metric (i.e. not strictly positive), but its complement, the Cosine Distance is more appropriate as a cost measure (i.e. strictly positive). The complement is computed by simply taking 1-M.

The Wikipage https://en.wikipedia.org/wiki/Cosine_similarity, elaborates a bit better: enter image description here

enter image description here

Finally, have a look at the author's (Dan Ellis) original code: https://labrosa.ee.columbia.edu/matlab/dtw/ You can see the comments about 1-M as well as the matrix he uses to illustrate the the lowest cost path. Good luck!

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.