DTW算法是什么

這篇文章給大家分享的是有關(guān)DTW算法是什么的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧。

dtw算法是基于動(dòng)態(tài)規(guī)劃DP的思想，解決了發(fā)音長(zhǎng)短不一的模板匹配問(wèn)題，是語(yǔ)音識(shí)別中出現(xiàn)較早、較為經(jīng)典的一種算法，用于孤立詞識(shí)別，DTW算法仍然得到廣泛的應(yīng)用。

時(shí)間序列數(shù)據(jù)存在多種相似或距離函數(shù)，其中最突出的是DTW。 在孤立詞語(yǔ)音識(shí)別中，最為簡(jiǎn)單有效的方法是采用DTW（Dynamic Time Warping，動(dòng)態(tài)時(shí)間歸整）算法，該算法基于動(dòng)態(tài)規(guī)劃（DP）的思想，解決了發(fā)音長(zhǎng)短不一的模板匹配問(wèn)題，是語(yǔ)音識(shí)別中出現(xiàn)較早、較為經(jīng)典的一種算法，用于孤立詞識(shí)別。HMM算法在訓(xùn)練階段需要提供大量的語(yǔ)音數(shù)據(jù)，通過(guò)反復(fù)計(jì)算才能得到模型參數(shù)，而DTW算法的訓(xùn)練中幾乎不需要額外的計(jì)算。所以在孤立詞語(yǔ)音識(shí)別中，DTW算法仍然得到廣泛的應(yīng)用。

無(wú)論在訓(xùn)練和建立模板階段還是在識(shí)別階段，都先采用端點(diǎn)算法確定語(yǔ)音的起點(diǎn)和終點(diǎn)。以存入模板庫(kù)的各個(gè)詞條稱(chēng)為參考模板，一個(gè)參考模板可表示為R={R（1），R（2），……，R（m），……，R（M）}，m為訓(xùn)練語(yǔ)音幀的時(shí)序標(biāo)號(hào)，m=1為起點(diǎn)語(yǔ)音幀，m=M為終點(diǎn)語(yǔ)音幀，因此M為該模板所包含的語(yǔ)音幀總數(shù)，R（m）為第m幀的語(yǔ)音特征矢量。所要識(shí)別的一個(gè)輸入詞條語(yǔ)音稱(chēng)為測(cè)試模板，可表示為T(mén)={T（1），T（2），……，T（n），……，T（N）}，n為測(cè)試語(yǔ)音幀的時(shí)序標(biāo)號(hào)，n=1為起點(diǎn)語(yǔ)音幀，n=N為終點(diǎn)語(yǔ)音幀，因此N為該模板所包含的語(yǔ)音幀總數(shù)，T（n）為第n幀的語(yǔ)音特征矢量。參考模板與測(cè)試模板一般采用相同類(lèi)型的特征矢量（如MFCC，LPC系數(shù)）、相同的幀長(zhǎng)、相同的窗函數(shù)和相同的幀移。

假設(shè)測(cè)試和參考模板分別用T和R表示，為了比較它們之間的相似度，可以計(jì)算它們之間的距離 D[T，R]，距離越小則相似度越高。為了計(jì)算這一失真距離，應(yīng)從T和R中各個(gè)對(duì)應(yīng)幀之間的距離算起。設(shè)n和m分別是T和R中任意選擇的幀號(hào)，d[T（n），R（m）]表示這兩幀特征矢量之間的距離。距離函數(shù)取決于實(shí)際采用的距離度量，在DTW算法中通常采用歐氏距離。

若N=M則可以直接計(jì)算，否則要考慮將T（n）和R（m）對(duì)齊。對(duì)齊可以采用線性擴(kuò)張的方法，如果N<M可以將T線性映射為一個(gè)M幀的序列，再計(jì)算它與{R（1），R（2），……，R（M）}之間的距離。但是這樣的計(jì)算沒(méi)有考慮到語(yǔ)音中各個(gè)段在不同情況下的持續(xù)時(shí)間會(huì)產(chǎn)生或長(zhǎng)或短的變化，因此識(shí)別效果不可能最佳。因此更多的是采用動(dòng)態(tài)規(guī)劃（DP）的方法。

若把測(cè)試模板的各個(gè)幀號(hào)n=1~N在一個(gè)二維直角坐標(biāo)系中的橫軸上標(biāo)出，把參考模板的各幀號(hào)m=1~M在縱軸上標(biāo)出，通過(guò)這些表示幀號(hào)的整數(shù)坐標(biāo)畫(huà)出一些縱橫線即可形成一個(gè)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每一個(gè)交叉點(diǎn)（n，m）表示測(cè)試模式中某一幀的交匯點(diǎn)。DP算法可以歸結(jié)為尋找一條通過(guò)此網(wǎng)絡(luò)中若干格點(diǎn)的路徑，路徑通過(guò)的格點(diǎn)即為測(cè)試和參考模板中進(jìn)行計(jì)算的幀號(hào)。路徑不是隨意選擇的，首先任何一種語(yǔ)音的發(fā)音快慢都有可能變化，但是其各部分的先后次序不可能改變，因此所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束

為了描述這條路徑，假設(shè)路徑通過(guò)的所有格點(diǎn)依次為（n1 ，m1 ），……，（ni ，mj ），……，（nN ，mM ），其中（n1 ，m1 ）=（1，1），（nN ，mM ）=（N，M）。路徑可以用函數(shù)m = Oslash;（n ）描述，其中n =i，i=1，2，……，N，&Oslash;（1）=1，&Oslash;（N）=M。為了使路徑不至于過(guò)傾斜，可以約束斜率在0.5~2的范圍內(nèi)，如果路徑已經(jīng)通過(guò)了格點(diǎn)（n ，m ），那么下一個(gè)通過(guò)的格點(diǎn)（n ，m ）只可能是下列三種情況之一：

（n ，m ）=（n +1，m）

（n ，m ）=（n +1，m +1）

（n ，m ）=（n ，m+1 ）

用r表示上述三個(gè)約束條件。求最佳路徑的問(wèn)題可以歸結(jié)為滿(mǎn)足約束條件r時(shí)，求最佳路徑函數(shù)m =&Oslash;（n ），使得沿路徑的積累距離達(dá)到最小值，即：

搜索該路徑的方法如下：搜索從（n, m）點(diǎn)出發(fā)，可以展開(kāi)若干條滿(mǎn)足?的路徑，假設(shè)可計(jì)算每條路徑達(dá)到（n, m）點(diǎn)時(shí)的總的積累距離，具有最小累積距離者即為最佳路徑。易于證明，限定范圍的任一格點(diǎn)（n, m）只可能有一條搜索路徑通過(guò)。對(duì)于（n, m），其可達(dá)到該格點(diǎn)的前一個(gè)格點(diǎn)只可能是（n-1, m）、（n-1, m -1）和（n, m-1），那么（n, m）一定選擇這3個(gè)距離之路徑延伸而通過(guò)（n, m），這時(shí)此路徑的積累距離為：

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）出發(fā)搜索（n ，m ），對(duì)每一個(gè)（n ，m ）都存儲(chǔ)相應(yīng)的距離，這個(gè)距離是當(dāng)前格點(diǎn)的匹配距離與前一個(gè)累計(jì)距離最小的格點(diǎn)（按照設(shè)定的斜率在三個(gè)格點(diǎn)中進(jìn)行比較）。搜索到（n ，m ）時(shí)，只保留一條最佳路徑。如果有必要的話，通過(guò)逐點(diǎn)向前尋找就可以求得整條路徑。這套DP算法便是DTW算法。

DTW算法可以直接按上面描述來(lái)實(shí)現(xiàn)，即分配兩個(gè)N×M的矩陣，分別為積累距離矩陣D和幀匹配距離矩陣d，其中幀匹配距離矩陣d（i，j）的值為測(cè)試模板的第i幀與參考模板的第j幀間的距離。D（N，M）即為最佳匹配路徑所對(duì)應(yīng)的匹配距離

感謝各位的閱讀！關(guān)于DTW算法是什么就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！