DTW算法是什么常见问题

本教程操作环境：windows7系统、DellG3电脑。

HMM算法在训练阶段需要提供大量的语音数据，通过反复计算才能得到模型参数，而DTW算法的训练中几乎不需要额外的计算。所以在孤立词语音识别中，DTW算法仍然得到广泛的应用。

无论在训练和建立模板阶段还是在识别阶段，都先采用端点算法确定语音的起点和终点。以存入模板库的各个词条称为参考模板，一个参考模板可表示为R={R（1），R（2），……，R（m），……，R（M）}，m为训练语音帧的时序标号，m=1为起点语音帧，m=M为终点语音帧，因此M为该模板所包含的语音帧总数，R（m）为第m帧的语音特征矢量。所要识别的一个输入词条语音称为测试模板，可表示为T={T（1），T（2），……，T（n），……，T（N）}，n为测试语音帧的时序标号，n=1为起点语音帧，n=N为终点语音帧，因此N为该模板所包含的语音帧总数，T（n）为第n帧的语音特征矢量。参考模板与测试模板一般采用相同类型的特征矢量（如MFCC，LPC系数）、相同的帧长、相同的窗函数和相同的帧移。

假设测试和参考模板分别用T和R表示，为了比较它们之间的相似度，可以计算它们之间的距离D[T，R]，距离越小则相似度越高。为了计算这一失真距离，应从T和R中各个对应帧之间的距离算起。设n和m分别是T和R中任意选择的帧号，d[T（n），R（m）]表示这两帧特征矢量之间的距离。距离函数取决于实际采用的距离度量，在DTW算法中通常采用欧氏距离。

若N=M则可以直接计算，否则要考虑将T（n）和R（m）对齐。对齐可以采用线性扩张的方法，如果N若把测试模板的各个帧号n=1~N在一个二维直角坐标系中的横轴上标出，把参考模板的各帧号m=1~M在纵轴上标出，通过这些表示帧号的整数坐标画出一些纵横线即可形成一个网络，网络中的每一个交叉点（n，m）表示测试模式中某一帧的交汇点。DP算法可以归结为寻找一条通过此网络中若干格点的路径，路径通过的格点即为测试和参考模板中进行计算的帧号。路径不是随意选择的，首先任何一种语音的发音快慢都有可能变化，但是其各部分的先后次序不可能改变，因此所选的路径必定是从左下角出发，在右上角结束

为了描述这条路径，假设路径通过的所有格点依次为（n1，m1），……，（ni，mj），……，（nN，mM），其中（n1，m1）=（1，1），（nN，mM）=（N，M）。路径可以用函数m=Oslash;（n）描述，其中n=i，i=1，2，……，N，（1）=1，（N）=M。为了使路径不至于过倾斜，可以约束斜率在0.5~2的范围内，如果路径已经通过了格点（n，m），那么下一个通过的格点（n，m）只可能是下列三种情况之一：

搜索该路径的方法如下：搜索从（n,m）点出发，可以展开若干条满足的路径，假设可计算每条路径达到（n,m）点时的总的积累距离，具有最小累积距离者即为最佳路径。易于证明，限定范围的任一格点（n,m）只可能有一条搜索路径通过。对于（n,m），其可达到该格点的前一个格点只可能是（n-1,m）、（n-1,m-1）和（n,m-1），那么（n,m）一定选择这3个距离之路径延伸而通过（n,m），这时此路径的积累距离为：

DTW算法可以直接按上面描述来实现，即分配两个N×M的矩阵，分别为积累距离矩阵D和帧匹配距离矩阵d，其中帧匹配距离矩阵d（i，j）的值为测试模板的第i帧与参考模板的第j帧间的距离。D（N，M）即为最佳匹配路径所对应的匹配距离