文档介绍：DTW算法
引言
随着时代的发展，人们越来越注重生活的品质。便捷时尚成为当代人们的追求目标。现在,语音信号处理的技术趋于完善,语音识别技术的应用有两个发展方向:一个是大词汇量连续语音识别系统,主，m ）一定选择这3个距离之路径延伸而通过（n ，m ），这时此路径的积累距离为：
D[（n ，m ）]=d[T(n ),R(m )]+D[(n , m )]
其中的n = n -1 ,m -1由下式决定：
D[（n ，m ）]=min{D[(n , m )],D[(n , m -1)],D[(n , m -2)]}
这样可以从（n ，m ）=（1，1）出发搜索（n ，m ），再搜索（n ，m ），……，对每一个（n ，m ）都存储相应的前一格点（n ，m ）及相应的帧匹配距离d[n ，m ]。搜索到（n ，m ）时，只保留一条最佳路径。如果有必要的话，通过逐点向前寻找就可以求得整条路径。这套DP算法便是DTW算法。
DTW算法可以直接按上面的描述来实现，即分配两个N×M的矩阵，分别为积累距离矩阵D和帧匹配距离矩阵d，其中帧匹配距离矩阵d（i，j）的值为测试模板的第i帧与参考模板的第j帧间的距离。D（N，M）即为最佳匹配路径所对应的匹配距离。
3 Matlab程序的实现
DTW的一般算法

function dist = dtw(t,r)
n = size(t,1);
m = size(r,1);
% 帧匹配距离矩阵
d = zeros(n,m);
for i = 1:n
for j = 1:m
 d(i,j) = sum((t(i,:)-r(j,:)).^2);
end
end
% 累积距离矩阵
D = ones(n,m) * realmax;
D(1,1) = d(1,1);
% 动态规划
for i = 2:n
for j = 1:m
 D1 = D(i-1,j);
 if j>1
  D2 = D(i-1,j-1);
else
D2 = realmax;
 end
 if j>2
  D3 = D(i-1,j-2);
else
D3 = realmax;
 end
 D(i,j) = d(i,j) + min([D1,D2,D3]);
end
end
dist = D(n,m);
程序中，首先申请两个n×m的距阵D和d，分别为累积距离和帧匹配距离。这里n和m为测试模板与参考模板的帧数。然后通过一个循环计算两个模板的帧匹配距离距阵d。接下来进行动态规划，为每个格点（i，j）都计算其三个可能的前续格点的累积距离D1、D2和D3。考虑到边界问题，有些前续格点可能不存在，因此要加入一些判断条件。
最后利用最小值函数min，找到三个前续格点的累积距离的最小值作为累积距离，与当前帧的匹配距离d（i，j）相加
，作为当前格点的累积距离。该计算过程一直达到格点（n，m），并将D（n，m）输出，作为模板匹配的结果。
DTW的高效算法
由于匹配过程中限定了弯折的斜率，因此许多格点实际上是到达不了的，如图3-1所示。因此菱形之外的格点对应的帧匹配距离是不需要计算的。另外也没有必要、保存所有的帧匹配距离距阵和累积距阵，因为每一列各格点上的匹配计算只用到了前一列的三个网格。充分利用这两个特点可以减少计算量和储存空间的需要。
如图3-1所示，把实际的动态弯折分为三段，（1，Xa），（Xa+1，Xb）和（Xb+1，N），其中：
图3-1 匹配路径约束示意图
Xa和Xb都取相近的整数。由此也得出对M和N长度的限制条件：
当不满足以上条件时，认为两者差别实在太大，无法进行动态弯折匹配。
在X轴上的每一帧不再需要与Y轴上的每一帧进行比较，而只是与Y轴上[y ，y ]间的帧进行比较，y 和y 的计算如下式：
也可能会出现Xa>Xb的情况，此时弯折匹配的三段为（1，Xb），（Xb+1，Xa）和（Xa+1，N）。
对于X轴上每前进一帧，虽然所要比较Y轴上的帧数不同，但弯折特性是一样的，累积距离的更新都是用下式实现的：
由于X轴上每前进一帧，只需要用到前一列的累积距离距阵。每前进一帧都进行更新，即按上式利用前一列的累积距离D和当前列的所有帧匹配的距离d（x，y），求出当前帧的累积距离，保存于矢量d中，再把更新的距离d赋值给D，作为新的累积距离，供下一列使用。如图3-2所示。这样一直前进到X轴上最后一列，矢量D的第M个元素即为两个模板动态弯折的匹配距离。
图3