语音信号处理之（一）动态时间规整（DTW）
語音信號處理之（一）動態(tài)時間規(guī)整（DTW）
zouxy09@qq.com
http://blog.csdn.net/zouxy09
?
????????這學(xué)期有《語音信號處理》這門課，快考試了，所以也要了解了解相關(guān)的知識點。呵呵，平時沒怎么聽課，現(xiàn)在只能抱佛腳了。順便也總結(jié)總結(jié)，好讓自己的知識架構(gòu)清晰點，也和大家分享下。下面總結(jié)的是第一個知識點：DTW。因為花的時間不多，所以可能會有不少說的不妥的地方，還望大家指正。謝謝。
?
????????Dynamic Time Warping（DTW）誕生有一定的歷史了（日本學(xué)者Itakura提出），它出現(xiàn)的目的也比較單純，是一種衡量兩個長度不同的時間序列的相似度的方法。應(yīng)用也比較廣，主要是在模板匹配中，比如說用在孤立詞語音識別（識別兩段語音是否表示同一個單詞），手勢識別，數(shù)據(jù)挖掘和信息檢索等中。
?
一、概述
???????在大部分的學(xué)科中，時間序列是數(shù)據(jù)的一種常見表示形式。對于時間序列處理來說，一個普遍的任務(wù)就是比較兩個序列的相似性。
???????在時間序列中，需要比較相似性的兩段時間序列的長度可能并不相等，在語音識別領(lǐng)域表現(xiàn)為不同人的語速不同。因為語音信號具有相當(dāng)大的隨機性，即使同一個人在不同時刻發(fā)同一個音，也不可能具有完全的時間長度。而且同一個單詞內(nèi)的不同音素的發(fā)音速度也不同，比如有的人會把“A”這個音拖得很長，或者把“i”發(fā)的很短。在這些復(fù)雜情況下，使用傳統(tǒng)的歐幾里得距離無法有效地求的兩個時間序列之間的距離（或者相似性）。
???????例如圖A所示，實線和虛線分別是同一個詞“pen”的兩個語音波形（在y軸上拉開了，以便觀察）。可以看到他們整體上的波形形狀很相似，但在時間軸上卻是不對齊的。例如在第20個時間點的時候，實線波形的a點會對應(yīng)于虛線波形的b’點，這樣傳統(tǒng)的通過比較距離來計算相似性很明顯不靠譜。因為很明顯，實線的a點對應(yīng)虛線的b點才是正確的。而在圖B中，DTW就可以通過找到這兩個波形對齊的點，這樣計算它們的距離才是正確的。
???????也就是說，大部分情況下，兩個序列整體上具有非常相似的形狀，但是這些形狀在x軸上并不是對齊的。所以我們在比較他們的相似度之前，需要將其中一個（或者兩個）序列在時間軸下warping扭曲，以達到更好的對齊。而DTW就是實現(xiàn)這種warping扭曲的一種有效方法。DTW通過把時間序列進行延伸和縮短，來計算兩個時間序列性之間的相似性。
???????那如果才知道兩個波形是對齊了呢？也就是說怎么樣的warping才是正確的？直觀上理解，當(dāng)然是warping一個序列后可以與另一個序列重合recover。這個時候兩個序列中所有對應(yīng)點的距離之和是最小的。所以從直觀上理解，warping的正確性一般指“feature to feature”的對齊。
?
二、動態(tài)時間規(guī)整DTW
?????????動態(tài)時間規(guī)整DTW是一個典型的優(yōu)化問題，它用滿足一定條件的的時間規(guī)整函數(shù)W(n)描述測試模板和參考模板的時間對應(yīng)關(guān)系，求解兩模板匹配時累計距離最小所對應(yīng)的規(guī)整函數(shù)。
??????假設(shè)我們有兩個時間序列Q和C，他們的長度分別是n和m：（實際語音匹配運用中，一個序列為參考模板，一個序列為測試模板，序列中的每個點的值為語音序列中每一幀的特征值。例如語音序列Q共有n幀，第i幀的特征值（一個數(shù)或者一個向量）是qi。至于取什么特征，在這里不影響DTW的討論。我們需要的是匹配這兩個語音序列的相似性，以達到識別我們的測試語音是哪個詞）
Q = q1, q2,…,qi,…, qn ;
C = c1, c2,…, cj,…, cm ;
???????如果n=m，那么就用不著折騰了，直接計算兩個序列的距離就好了。但如果n不等于m我們就需要對齊。最簡單的對齊方式就是線性縮放了。把短的序列線性放大到和長序列一樣的長度再比較，或者把長的線性縮短到和短序列一樣的長度再比較。但是這樣的計算沒有考慮到語音中各個段在不同情況下的持續(xù)時間會產(chǎn)生或長或短的變化，因此識別效果不可能最佳。因此更多的是采用動態(tài)規(guī)劃（dynamic programming）的方法。
??????為了對齊這兩個序列，我們需要構(gòu)造一個n x m的矩陣網(wǎng)格，矩陣元素(i, j)表示qi和cj兩個點的距離d(qi, cj)（也就是序列Q的每一個點和C的每一個點之間的相似度，距離越小則相似度越高。這里先不管順序），一般采用歐式距離，d(qi, cj)= (qi-cj)2（也可以理解為失真度）。每一個矩陣元素(i, j)表示點qi和cj的對齊。DP算法可以歸結(jié)為尋找一條通過此網(wǎng)格中若干格點的路徑，路徑通過的格點即為兩個序列進行計算的對齊的點。
???????那么這條路徑我們怎么找到呢？那條路徑才是最好的呢？也就是剛才那個問題，怎么樣的warping才是最好的。
我們把這條路徑定義為warping path規(guī)整路徑，并用W來表示， W的第k個元素定義為wk=(i,j)k，定義了序列Q和C的映射。這樣我們有：
?????首先，這條路徑不是隨意選擇的，需要滿足以下幾個約束：
1）邊界條件：w1=(1, 1)和wK=(m, n)。任何一種語音的發(fā)音快慢都有可能變化，但是其各部分的先后次序不可能改變，因此所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束。
2）連續(xù)性：如果wk-1= (a’, b’)，那么對于路徑的下一個點wk=(a, b)需要滿足 (a-a’) <=1和 (b-b’) <=1。也就是不可能跨過某個點去匹配，只能和自己相鄰的點對齊。這樣可以保證Q和C中的每個坐標(biāo)都在W中出現(xiàn)。
3）單調(diào)性：如果wk-1= (a’, b’)，那么對于路徑的下一個點wk=(a, b)需要滿足0<=(a-a’)和0<= (b-b’)。這限制W上面的點必須是隨著時間單調(diào)進行的。以保證圖B中的虛線不會相交。
?????????結(jié)合連續(xù)性和單調(diào)性約束，每一個格點的路徑就只有三個方向了。例如如果路徑已經(jīng)通過了格點(i, j)，那么下一個通過的格點只可能是下列三種情況之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。
??????滿足上面這些約束條件的路徑可以有指數(shù)個，然后我們感興趣的是使得下面的規(guī)整代價最小的路徑：
??????分母中的K主要是用來對不同的長度的規(guī)整路徑做補償。我們的目的是什么？或者說DTW的思想是什么？是把兩個時間序列進行延伸和縮短，來得到兩個時間序列性距離最短也就是最相似的那一個warping，這個最短的距離也就是這兩個時間序列的最后的距離度量。在這里，我們要做的就是選擇一個路徑，使得最后得到的總的距離最小。
??????這里我們定義一個累加距離cumulative distances。從(0, 0)點開始匹配這兩個序列Q和C，每到一個點，之前所有的點計算的距離都會累加。到達終點(n, m)后，這個累積距離就是我們上面說的最后的總的距離，也就是序列Q和C的相似度。
??????累積距離γ(i,j)可以按下面的方式表示，累積距離γ(i,j)為當(dāng)前格點距離d(i,j)，也就是點qi和cj的歐式距離（相似性）與可以到達該點的最小的鄰近元素的累積距離之和：
??????最佳路徑是使得沿路徑的積累距離達到最小值這條路徑。這條路徑可以通過動態(tài)規(guī)劃（dynamic programming）算法得到。
???????具體搜索或者求解過程的直觀例子解釋可以參考：
http://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html
?
三、DTW在語音中的運用
???????假定一個孤立字（詞）語音識別系統(tǒng)，利用模板匹配法進行識別。這時一般是把整個單詞作為識別單元。在訓(xùn)練階段，用戶將詞匯表中的每一個單詞說一遍，提取特征后作為一個模板，存入模板庫。在識別階段，對一個新來的需要識別的詞，也同樣提取特征，然后采用DTW算法和模板庫中的每一個模板進行匹配，計算距離。求出最短距離也就是最相似的那個就是識別出來的字了。
?
四、參考資料
[1] http://baike.baidu.com/view/1647336.htm
[2] http://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html
[3] http://www.cnblogs.com/luxiaoxun/archive/2013/05/09/3069036.html (有matlab/C++ code)
[4] Eamonn J. Keogh, Derivative Dynamic Time Warping
[5]趙立《語音信號處理》
---------------------?
作者：zouxy09?
來源：CSDN?
原文：https://blog.csdn.net/zouxy09/article/details/9140207?
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請附上博文鏈接！
總結(jié)
以上是生活随笔為你收集整理的语音信号处理之（一）动态时间规整（DTW）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： linux内核计算list的长度,Lin
- 下一篇： 黔东南天气预报软件测试,黔东南天气预报1