动态时间规整DTW算法的研究杨洁

康宁

摘 要：传统的动态时间规整（Dynamic Time Warping）算法虽然可以有效解决语音信号特征参数序列比较时时长不等的问题，但计算量很大，严重影响了语音识别系统的响应速度。对传统的动态时间规整算法进行改进，主要目的是提高语音识别速率。首先对传统DTW算法的原理进行了详细的分析，然后提出了改进后新的DTW算法。对传统的算法进行改进时，主要从以下两方面入手：①对算法的搜索路径进行约束，使x轴上的每一帧不必再与y轴上的每一帧进行比较，而只需要与y轴上限定范围内的帧进行比较即可；②对齐松弛算法的起始点和终止点（不用完全对齐），并可以适当放松起始点和终止点两三帧。实验表明，系统在失真度基本保持不变的基础上，运行速率提高了近2倍。

关键词：动态时间规整；DTW算法；特征参数；语音信号

中图分类号：TP274+.2 文献标识码：A DOI：10.15913/j.cnki.kjycx.2016.04.011

语音识别是接收人类的语音信号，并对其进行模数转换、降噪、滤波、预加重、加窗分帧、端点检测，提取出相应的特征，然后按照识别算法识别，从而让机器“理解”人类的语言，完成相应的任务，实现人对机器的控制。

目前，语音识别算法有许多，比较常用的3种模式匹配算法为人工神经网络（Artificial Neural Networks，ANN）、隐马尔可夫模型（Hidden Markov Models，HMM）和动态时间规整（Dynamic Time Warping，DTW）算法。其中，ANN算法的缺点为存在时间规整问题、训练过程复杂和识别时间长等，因此，很难做到与语音信号的最佳匹配，一般不单独使用。HMM算法建立在统计模型的基础上，其优点为识别性能高、稳健性好等，缺点为占用资源较多、鲁棒性不好和分类能力差等，适用于大词汇量连续词语音识别系统。DTW算法是20世纪60年代由日本学者板仓提出的，基于动态规划的思想，解决了因发音长短不统一和说话速度不一致而产生的模式匹配问题，在小词汇量孤立词语音识别系统中取得了良好的应用效果。由于DTW算法本身较容易实现，对系统硬件要求很低，而且是一种比较成熟的算法，因此，这一算法被广泛应用于语音识别领域。

虽然DTW算法在小词汇量孤立词语音识别系统中表现出色，但它仍然存在很多问题。首先，DTW算法的训练方法不能有效利用统计方法，很难将顶层和底层的知识应用到识别算法中；其次，DTW算法运算量很大，其参考模板、测试模板分别为M帧和N帧，动态规划要运用MN次运算才能实现；最后，DTW算法在语音识别的过程中是将一个单词作为一个整体，没有考虑到单词的分段，当需要识别的两个词语差别很小时，其搜索路径会受到一定的影响，在距离上很难表现出来。针对上述问题，相关人员对DTW算法进行了改进，以提高语音识别系统的响应速度，满足实时性要求。

1 传统DTW算法的原理

DTW算法是通过动态规划使参考模板和测试模板在时间上实现最优匹配。假设参考模板的特征参数序列为{R（1），R（2），…，R（m），…，R（M）}，其中，M为该模板的总帧数，m为帧的时序标号，R（m）为对应的特征矢量；测试模板的特征参数序列为{T（1），T（2），…，T（n），…，T（N）}，其中，N为该模板的总帧数，n为帧的时序标号，T（n）为对应的特征矢量。参考模板和测试模板采用相同的特征矢量、帧长、帧移和窗口函数。这样，两个模板才具有可比性。

为了比较参考模板R和测试模板T的相似程度，需计算这两个模板各对应帧的失真度，失真度越小，则相似度越高。为了直观地显示R和T之间各帧的对应关系，将测试模板的帧号n=1，2，3，…，n标在直角坐标系的横坐标轴上，将参考模板的帧号m=1，2，3，…，m标在直角坐标系的纵坐标轴上。这样，连接横、纵各个坐标轴就可以形成一个矩形网络，网络中的每一个交叉点（n，m）表示R中一帧和T中一帧的交会点。R和T的对应关系形成了一条起始于（0，0）而终止于（N，M）的路径，如图1所示。

图1中路径所经过的交叉点就是参考模块和测试模板中失真计算的帧号，沿着路径对各个交叉点的失真度累加求和，就可以得到总体失真度。于是，本文所研究的问题就转换成了如何通过动态规划寻找最优路径。两对应帧之间的失真度公式如下：

式（1）中：p为特征矢量的维数。

总体失真度为：

在计算总体失真度时，如果 N=M，可以依次计算n=m=1，…，n=m=N=M各个帧之间的失真度并且求和；如果N≠M，用线性扩张映射将多的映射成少的，然后再计算。

2 改进后的DTW算法

传统的DTW算法严重影响了系统的识别速率，因此需要改进，以提高系统的识别速率。

2.1 DTW算法中的整体路径约束

采用传统的DTW算法进行语音识别时，需要逐个对比参考模板与测试模板的每一帧，如图2所示，这样就会耗费大量的时间和资源，因此，需要对DTW算法的路径进行约束。

改进后的DTW算法的路径如图4所示，其中，原有的DTW算法的路径为虚线所围区域，改进后的DTW算法的路径为竖线所围区域。

2.2 放松起始点和终止点的对齐

DTW算法对端点检测比较敏感，端点信息以独立参数的形式呈现，要求两个模板起点对应起点、终点对应终点，对端点检测的精度要求非常高。当周围环境噪声大或者有其他干扰时，端点检测的精度会受到极大的影响。实际中，测试模板帧数和参考模板帧数不能完全对应，人发声会晚于计算机开始计算搜索路径数据的时间，因此，可以适当放松起始点和终止点。实验表明，放宽5帧以上会影响到识别率，因此，本文选定放宽两三帧，使搜索路径的起点选择具有一定的特性。这样就克服了由于端点检测的精度影响而造成的测试模板和参考模板起始点和终止点不能完全对齐的问题。实现路径如图5中网格区域所示。

3 实验研究和分析

将传统的DTW算法和改进后的DTW算法进行比较。以Linux系统为系统平台，ARM为硬件平台，在安静的环境下，以频率44.1 kHz、时长3 s对特定人发出的“开灯”和“关灯”这两个词进行录音。进行10次测试，测试结果分别如表1、表2和表3所示。

从实验数据可以看出，按照上述方法，在约束DTW算法的路径，限定ymin和ymax的值和对起始点和终止点的对齐放宽两三帧的优化改进后，与传统的DTW算法相比，在保持系统识别率基本不变的提前下，识别速率得到了大幅度的提高，约为传统DTW算法的2倍，证明本文对传统DTW算法的改进具有可行性。

4 结论

本文首先介绍了三种常用的模式匹配算法，然后对DTW算法进行了详细的阐述，分析了传统的DTW算法的基本原理及其优、缺点，并针对传统DTW算法所存在的问题制定了两种改进方案，即对路径进行约束和放松起始点和终止点的对齐。通过实验分析发现，改进后的DTW算法在保持系统识别率几乎不变的前提下，识别速率得到了大幅度的提升，约为传统DTW算法的2倍。

参考文献

[1]陈尚勤，罗承劣.近代语音识别[M].成都：电子科技大学出版社，1991.

[2]万春.基于DTW的语音识别应用系统研究与实现[J].集美大学学报（自然科学版），2002，7（2）.

[3]刘敬伟.基于DTW相似度的统计学习方法及其在模式识别中的应用[D].北京：北京大学，2002.

[4]刘化兰.DSP算法、应用与设计[J].实验技术与管理，2003，20（2）.

[5]Bian Z Q，Zhang X G.Pattern Recognition[M].The 2nd Edition.Beijing：Tsinghua University Press，2000.