DTW演算法是什麼

dtw演算法是指動態時間規則演算法，是基於動態規劃DP的思想，是一種計算2個時間序列尤其是不同長度序列相似度的一種動態規劃演算法；它解決了發音長短不一的模板比對問題，是語音辨識中出現較早、較經典的一種演算法。 dtw演算法主要應用在時序資料上，例如孤立字詞語音辨識、手勢辨識、資料探勘、資訊檢索等。

本教學操作環境：windows7系統、Dell G3電腦。

時間序列資料存在多種相似或距離函數，其中最突出的是DTW。在孤立詞語音辨識中，最簡單有效的方法是採用DTW（Dynamic Time Warping，動態時間歸整）演算法，該演算法基於動態規劃（DP）的思想，解決了發音長短不一的模板匹配問題，是語音辨識中出現較早、較為經典的一種演算法，用於孤立詞辨識。

DTW（Dynamic Time Warping ）動態時間規則演算法，是一種計算2個時間序列尤其是不同長度序列相似度的動態規劃演算法。主要應用在時序資料上，例如孤立詞語音辨識、手勢辨識、資料探勘、資訊檢索等。

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 +1，m）
（n ，m ）=（n +1，m +1）
（n ，m ）=（n ，m+1 ）

用r表示上述三個限制條件。求最佳路徑的問題可以歸結為滿足約束條件r時，求最佳路徑函數m =Ø（n ），使得沿路徑的累積距離達到最小值，即：

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

D[(n, m)]=d[T(n),R(m)]+min{D(n-1,m),D(n-1,m-1),D(n,m-1)}

这样可以从（n ，m ）=（1，1）出发搜索（n ，m ），对每一个（n ，m ）都存储相应的距离，这个距离是当前格点的匹配距离与前一个累计距离最小的格点（按照设定的斜率在三个格点中进行比较）。搜索到（n ，m ）时，只保留一条最佳路径。如果有必要的话，通过逐点向前寻找就可以求得整条路径。这套DP算法便是DTW算法。

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

更多相关知识，请访问常见问题栏目！

以上是DTW演算法是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！