動態時間規整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.