前段时间在做语音识别技术的研讨，通过对网上资料的学习，加上自己的一些理解，整理出一篇DTW算法简介，欢迎大家指出不足之处。
在进行语音帧对应关系的建立和总失真度的计算时，我们采用的是动态时间规整算法(DTW)，该算法本质上是一种动态规划算法，利用局部最佳化的处理来寻找这样一条路径：沿着这条路径，两个特征矢量序列间的累积失真量最小，即是要寻找一条从起始点到终止点的最佳路径，使得该路径上所有帧失真度总和(总失真)达到最小。
设测试模板T共有N帧，参考模板R共有M帧，将测试模板和参考模板的帧号分别在坐标系的横轴和纵轴上标出，则各个帧号之间的关系形成一个网络，网格中的任何一个交叉点(n，m)表示测试模板的T(n)和参考模板R(m)相交，并且该交叉点拥有帧失真度为D[T(n), R(m)]。DTW算法利用动态规划思想求出一条由起点(1, 1)到终点(n, m)的路径，该路径实现了输入模板和测试模板时间帧的对应，并且满足路径上所经过的交叉点所对应的失真度总和最小(全局最优解)。
事实上，在上述搜索过程中路径的选择并不是任意的。首先，考虑到实际语音的发音情况，虽然语音的发音快慢会有所变化，但是各个部分的先后次序不可能颠倒，因此上述路径必然从左下角出发，终止于右上角；其次，为了防止盲目的搜索，一般不容许横轴或纵轴过分倾斜的路径，一般对路径中点处路径的斜率的最大、最小值作出规定，通常最大斜率为2，最小斜率为1/2。图示的外边框平行四边形说明了DTW算法的搜索范围，其中两个边框的斜率分别为1和1/2。
将路径上的当前点记为(n. m)，根据上图，DTW算法的约束条件是：
（1）路径经过起始点和终止点，即： （2）路径所通过的网格点必须在上左图所示的平行四边形区域内；
（3）根据上右图，当前的的上一个路径点必须满足以下条件： 根据上述约束条件，定义路径代价函数d[n, m]，其意义为从起始点(n0, m0)（即(1, 1)）到点(n, m)的路径上失真度和的最小值，则有以下递推公式： 其中D[T(n), R(m)]为当前点对应帧T(n)和R(m)的失真度。该算法从点(1, 1)开始，到(N, M)结束，当n = N，m = M时算法停止，返回最小失真度总和，并且沿算法所得路径向前回溯，即得到(1, 1)到(N, M)的最优路径，即为测试模板和参考模板语音帧之间的最佳匹配。
附主要参考资料链接
