DTW算法是什么

這篇文章給大家分享的是有關DTW算法是什么的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。

dtw算法是基于動態規劃DP的思想，解決了發音長短不一的模板匹配問題，是語音識別中出現較早、較為經典的一種算法，用于孤立詞識別，DTW算法仍然得到廣泛的應用。

時間序列數據存在多種相似或距離函數，其中最突出的是DTW。 在孤立詞語音識別中，最為簡單有效的方法是采用DTW（Dynamic Time Warping，動態時間歸整）算法，該算法基于動態規劃（DP）的思想，解決了發音長短不一的模板匹配問題，是語音識別中出現較早、較為經典的一種算法，用于孤立詞識別。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<M可以將T線性映射為一個M幀的序列，再計算它與{R（1），R（2），……，R（M）}之間的距離。但是這樣的計算沒有考慮到語音中各個段在不同情況下的持續時間會產生或長或短的變化，因此識別效果不可能最佳。因此更多的是采用動態規劃（DP）的方法。

若把測試模板的各個幀號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，&Oslash;（1）=1，&Oslash;（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 =&Oslash;（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算法是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！