function [Dist,D,k,w]=dtw(r,t)
%
% [Dist,D,k,w]=dtw(r,t)
%
% Dynamic Time Warping Algorithm
% Dist is unnormalized distance between t and r
% D is the accumulated distance matrix
% k is the normalizing factor
% w is the optimal path
% t is the vector you are testing against
% r is the vector you are testing
% r和t是测试向量和模板向量，此为待输入量
%
[row,M]=size(r); if (row > M) M=row; r=r'; end;
[row,N]=size(t); if (row > N) N=row; t=t'; end;
d=sqrt((repmat(r',1,N)-repmat(t,M,1)).^2); %repmat函数是为了把矩阵进行重复放置，
%d就是对应点的距离矩阵
%把矢量转化为矩阵，便于求矩阵的差值d
D=zeros(size(d));
D(1,1)=d(1,1);
for m=2:M
D(m,1)=d(m,1)+D(m-1,1); %计算垂直方向对应点的距离，相邻值加上步长
end
for n=2:N
D(1,n)=d(1,n)+D(1,n-1); %计算水平方向上对应点的距离，相邻值加上步长
end
for m=2:M %计算对角线上的对应点的距离，此时应该找相邻3点的最小距离相加
for n=2:N
D(m,n)=d(m,n)+min(D(m-1,n),min(D(m-1,n-1),D(m,n-1))); % this double MIn construction improves in 10-fold the Speed-up. Thanks Sven Mensing
end
end
% D矩阵就是累加距离D
Dist=D(M,N); %D矩阵的最左下方的D(M,N)即为所求的最小距离
n=N;
m=M;
k=1;
w=[M N];
while ((n+m)~=2) %找出最佳路径并输出
if (n-1)==0
m=m-1;
elseif (m-1)==0
n=n-1;
else
[values,number]=min([D(m-1,n),D(m,n-1),D(m-1,n-1)]);
switch number %values值为输出的最小值，number为最小值在所在的位置索引
case 1
m=m-1;
case 2
n=n-1;
case 3
m=m-1;
n=n-1;
end
end
k=k+1;
w=[m n; w]; % this replace the above sentence. Thanks Pau Mic
%w为最终的最优路径
end
end
