DTW

Dynamic Time Warping是Vintsiuk于1968年提出的算法。

Taras Klymovych Vintsiuk，1939～2012，烏克蘭科學(xué)家，畢業(yè)于Kyiv Polytechnic Institute。模式識別專家，語音識別領(lǐng)域的奠基人之一。

圖1

如上圖所示，因?yàn)檎Z音信號具有相當(dāng)大的隨機(jī)性，即使同一個人在不同時刻發(fā)同一個音，也不可能具有完全的時間長度。而且同一個單詞內(nèi)的不同音素的發(fā)音速度也不同，比如有的人會把“A”這個音拖得很長，或者把“i”發(fā)的很短。在這些復(fù)雜情況下，使用傳統(tǒng)的歐幾里得距離，無法有效地求得兩個時間序列之間的距離（或者相似性）。

回到上面的圖。如果我們將兩個序列中相關(guān)聯(lián)的點(diǎn)，用上圖中的虛線連接的話，就會發(fā)現(xiàn)這兩個序列實(shí)際上是很相似的。

那么如何用數(shù)學(xué)的方式描述上述DTW算法的思想呢？

假設(shè)現(xiàn)在有一個標(biāo)準(zhǔn)的參考模板R，是一個M維的向量，即R={R(1),R(2)，?，R(M)}R={R(1),R(2)，?，R(M)}，每個分量可以是一個數(shù)或者是一個更小的向量。現(xiàn)在有一個才測試的模板T，是一個N維向量，即T={T(1),T(2)，?，T(N)}T={T(1),T(2)，?，T(N)}同樣每個分量可以是一個數(shù)或者是一個更小的向量，注意M不一定等于N，但是每個分量的維數(shù)應(yīng)該相同。

然后，將兩個序列二維展開得到下圖：

這樣，兩個序列中點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，就可以用這個二維矩陣W來表述。比如，可以用W(i,j)表示第1個序列中的第i個點(diǎn)和第2個序列中的第j個點(diǎn)相對應(yīng)。所有這樣的W(i,j)最終構(gòu)成了上圖中的曲線。這條曲線也被稱作歸整路徑（Warp Path）。

顯然，這個歸整路徑不是隨意選擇的，它需要滿足以下幾個約束：

1）邊界條件：w1=(1,1)w1=(1,1)和wk=(m,n)wk=(m,n)。任何一種語音的發(fā)音快慢都有可能變化，但是其各部分的先后次序不可能改變，因此所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束。

2）連續(xù)性：如果wk?1=(a′,b′)wk?1=(a′,b′)，那么對于路徑的下一個點(diǎn)wk=(a,b)wk=(a,b)需要滿足(a?a′)≤1(a?a′)≤1和(b?b′)≤1(b?b′)≤1。也就是不可能跨過某個點(diǎn)去匹配，只能和自己相鄰的點(diǎn)對齊。這樣可以保證R和T中的每個坐標(biāo)都在W中出現(xiàn)。

3）單調(diào)性：如果wk?1=(a′,b′)wk?1=(a′,b′)，那么對于路徑的下一個點(diǎn)wk=(a,b)wk=(a,b)需要滿足0≤(a?a′)0≤(a?a′)和0≤(b?b′)0≤(b?b′)。這限制W上面的點(diǎn)必須是隨著時間單調(diào)進(jìn)行的。以保證圖1中的虛線不會相交。

結(jié)合連續(xù)性和單調(diào)性約束，每一個格點(diǎn)的路徑就只有三個方向了。例如如果路徑已經(jīng)通過了格點(diǎn)(i,j)(i,j)，那么下一個通過的格點(diǎn)只可能是下列三種情況之一：(i+1,j)(i+1,j)，(i,j+1)(i,j+1)或者(i+1,j+1)(i+1,j+1)。

歸整路徑實(shí)際上就是滿足上述約束的所有路徑中，cumulative distances最小的那條路徑，即：

D(i,j)=Dist(i,j)+min(D(i?1,j),D(i,j?1),D(i?1,j?1)),D(1,1)=0D(i,j)=Dist(i,j)+min(D(i?1,j),D(i,j?1),D(i?1,j?1)),D(1,1)=0

這里的距離可以使用歐氏距離，也可以使用馬氏距離。

DTW實(shí)例的具體計(jì)算過程可參見：

http://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html

從一個實(shí)例中學(xué)習(xí)DTW算法

從中可以看出，DTW實(shí)際上是一個動態(tài)規(guī)劃問題。

更一般的，DTW也可用于計(jì)算兩個離散的序列(不一定要與時間有關(guān))的相似度。和《機(jī)器學(xué)習(xí)（二十二）》的EMD距離相比，DTW距離能夠保持序列的形狀信息。

除此之外，我們還可以增加別的約束：

全局路徑窗口(Warping Window)：∣?x(s)??y(s)∣≤r∣?x(s)??y(s)∣≤r。比較好的匹配路徑往往在對角線附近，所以我們可以只考慮在對角線附近的一個區(qū)域?qū)ふ液线m路徑(r就是這個區(qū)域的寬度);

斜率約束(Slope Constrain)：?x(m)??x(n)?y(m)??y(n)≤p?x(m)??x(n)?y(m)??y(n)≤p和?y(m)??y(n)?x(m)??x(n)≤q?y(m)??y(n)?x(m)??x(n)≤q，這個可以看做是局部的Warping Window，用于避免路徑太過平緩或陡峭，導(dǎo)致短的序列匹配到太長的序列或者太長的序列匹配到太短的序列。

上圖是兩種常見的約束搜索空間的方法。

DTW的缺點(diǎn)：

1.運(yùn)算量大；

2.識別性能過分依賴于端點(diǎn)檢測；

3.太依賴于說話人的原來發(fā)音；

4.不能對樣本作動態(tài)訓(xùn)練；

5.沒有充分利用語音信號的時序動態(tài)特性；

DTW適合于特定人基元較小的場合，多用于孤立詞識別；

參考：

http://blog.csdn.net/zouxy09/article/details/9140207

動態(tài)時間規(guī)整（DTW）

https://blog.csdn.net/raym0ndkwan/article/details/45614813

DTW動態(tài)時間規(guī)整

http://www.cnblogs.com/luxiaoxun/archive/2013/05/09/3069036.html

Dynamic Time Warping動態(tài)時間規(guī)整算法

https://zhuanlan.zhihu.com/p/39450321

時間序列的搜索

Spectrogram

Window function

Fourier transform研究的是整個時間域和頻率域的關(guān)系。但實(shí)際的信號處理過程，不可能對無限長的信號進(jìn)行測量和運(yùn)算，而是取其有限的時間片段進(jìn)行分析。做法是從信號中截取一個時間片段，然后用截取的信號時間片段進(jìn)行周期延拓處理，得到虛擬的無限長的信號，然后就可以對信號進(jìn)行FT、相關(guān)分析等數(shù)學(xué)處理。

無限長的信號被截?cái)嘁院?#xff0c;其頻譜發(fā)生了畸變，原來集中在f(0)處的能量被分散到兩個較寬的頻帶中去了（這種現(xiàn)象稱之為頻譜能量泄漏）。

為了減少頻譜能量泄漏，可采用不同的截取函數(shù)對信號進(jìn)行截?cái)?#xff0c;這些截?cái)嗪瘮?shù)稱為Window function。

常用的Window function有：Hann window、Rectangular window、Triangular window、Hamming window、Gaussian window等。

不同的窗函數(shù)對信號頻譜的影響是不一樣的。例如，Rectangular window主瓣窄，旁瓣大，頻率識別精度最高，幅值識別精度最低；Blackman window主瓣寬，旁瓣小，頻率識別精度最低，但幅值識別精度最高。

對Window function更詳細(xì)的敘述參見：

https://en.wikipedia.org/wiki/Window_function

Hann window

Hann window雖然是以Julius Ferdinand von Hann的名字命名，但卻是Blackman和Tukey的作品。他們和同一實(shí)驗(yàn)室的Claude E. Shannon, Hendrik Wade Bode，合稱為Information Age的四大先鋒。

Julius Ferdinand von Hann，1839～1921，奧地利氣象學(xué)家。現(xiàn)代氣象學(xué)之父。

Ralph Beebe Blackman，1904～1990，美國數(shù)學(xué)家。長期供職于AT&T Bell Laboratories。二戰(zhàn)時，參與了防空火炮控制系統(tǒng)的平滑研究。

John Wilder Tukey，1915～2000，美國數(shù)學(xué)家。Princeton University博士，長期供職于AT&T Bell Laboratories。英國皇家學(xué)會會員。Cooley–Tukey FFT算法發(fā)明者。

w(n)=∑k=0K(?1)kakcos(2πknN?1),0≤n≤N?1w(n)=∑k=0K(?1)kakcos?(2πknN?1),0≤n≤N?1

上式是Cosine-sum windows的計(jì)算公式，令K=1，則：

w(n)=a0?(1?a0)a1?cos(2πnN?1),0≤n≤N?1w(n)=a0?(1?a0)?a1?cos?(2πnN?1),0≤n≤N?1

這類Window function有好幾個特例：

Hann window：

w(n)=0.5[1?cos(2πnN?1)]=sin2(πnN?1)w(n)=0.5[1?cos?(2πnN?1)]=sin2?(πnN?1)

Hamming window：

w(n)=0.54?0.46?cos(2πnN?1)w(n)=0.54?0.46?cos?(2πnN?1)

Richard Wesley Hamming，1915～1998，美國數(shù)學(xué)家。University of Chicago本科（1937）+University of Nebraska碩士（1939）+UIUC博士（1942）。參與曼哈頓計(jì)劃，后長期供職于Bell Lab。通信和計(jì)算機(jī)工程領(lǐng)域的宗師級人物，美國工程院院士，圖靈獎得主（1968）。Hamming code 、Hamming distance等都是他的貢獻(xiàn)。

STFT

STFT{x(t)}(τ,ω)≡X(τ,ω)=∫∞?∞x(t)w(t?τ)e?jωtdtSTFT{x(t)}(τ,ω)≡X(τ,ω)=∫?∞∞x(t)w(t?τ)e?jωtdt

上式是STFT（Short-time Fourier transform）的定義。和FT相比，STFT將FT中的被積函數(shù)x(t)x(t)，換成了x(t)w(t?τ)x(t)w(t?τ)。其中，w(t)是窗函數(shù)（Window function），因此STFT又叫做加窗傅立葉變換。

Spectrogram

DTW是一種時域方法，作為信號處理自然少不了頻域方法。這里我們先來了解一個叫聲譜圖的東西。

這段語音被分為很多幀，每幀語音都對應(yīng)于一個頻譜（通過短時FFT計(jì)算），頻譜表示頻率與能量的關(guān)系。在實(shí)際使用中，頻譜圖有三種，即線性振幅譜、對數(shù)振幅譜、自功率譜（對數(shù)振幅譜中各譜線的振幅都作了對數(shù)計(jì)算，所以其縱坐標(biāo)的單位是dB（分貝）。這個變換的目的是使那些振幅較低的成分相對高振幅成分得以拉高，以便觀察掩蓋在低幅噪聲中的周期信號）。

我們先將其中一幀語音的頻譜通過坐標(biāo)表示出來。

再將左邊的頻譜旋轉(zhuǎn)90度。

然后把這些幅度映射到一個灰度級表示的直方圖。0表示白色，255表示黑色。幅度值越大，相應(yīng)的區(qū)域越黑。

這樣我們會得到一個隨著時間變化的頻譜圖，這個就是描述語音信號的spectrogram聲譜圖。

Cepstrum Analysis

上圖是一個語音的頻譜圖。峰值就表示語音的主要頻率成分，我們把這些峰值稱為共振峰（formants），而共振峰就是攜帶了聲音的辨識屬性（就是個人身份證一樣）。所以它特別重要。用它就可以識別不同的聲音。

既然它那么重要，那我們就是需要把它提取出來！我們要提取的不僅僅是共振峰的位置，還得提取它們轉(zhuǎn)變的過程。所以我們提取的是頻譜的包絡(luò)（Spectral Envelope）。這包絡(luò)就是一條連接這些共振峰點(diǎn)的平滑曲線。

原始的頻譜由兩部分組成：包絡(luò)和頻譜的細(xì)節(jié)。這里用到的是對數(shù)頻譜，所以單位是dB。

怎么把他們分離開呢？也就是，怎么在給定logX[k]log?X[k]的基礎(chǔ)上，求得logH[k]log?H[k]和logE[k]log?E[k]以滿足logX[k]=logH[k]+logE[k]log?X[k]=log?H[k]+log?E[k]呢？

為了達(dá)到這個目標(biāo)，我們需要Play a Mathematical Trick。這個Trick是什么呢？就是對頻譜做FFT。

總結(jié)

以上是生活随笔為你收集整理的语音识别（四）——DTW, Spectrogram, Cepstrum Analysis的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。