嵌入式語音識別系統中的DTW在線并行算法

摘 要:為提高語音識別系統的實時性，利用動態規劃和并行計算思想，提出一種適用于嵌入式語音識別系統的DTW(動態時間規整)在線并行算法。通過分析標準DTW及其主要衍生算法，對DTW算法的數據結構進行改進以滿足在線算法要求，在尋找最佳路徑過程中動態連續地分配和釋放內存或預先分配固定大小的內存，并將多個關鍵詞的DTW計算分布到多個運算單元;最后匯總各運算單元的結果得到識別結果。實驗表明，該算法比經典DTW降低了內存使用和識別時間，并使語音識別的實時系數達到1.17，具有較高的實時性。

關鍵詞:語音識別; 動態時間規整; 在線算法; 并行算法; 嵌入式系統

中圖分類號:TN912.34文獻標志碼:A

文章編號:1001-3695(2010)03-0977-04

doi:10.3969/j.issn.10013695.2010.03.046

Online parallel dynamic time warping algorithm for speech recognition in embedded system

JIANG Gan-xina， CHEN Weib

(a.College of Computer Science Technology， b.Zhejiang Key Laboratory of Service Robot， Zhejiang University， Hangzhou 310027， China)

Abstract:The classical DTW can be enhanced using dynamic programming and parallel computing. This paper introduced an online parallel DTW to improve the realtime performance for embedded speech recognition systems. After comprehensive analysis of DTW and its major derivatives， the algorithm used data structures that fit the requirements of online algorithm. During the stage of figuring out optimal warping path， manipulated memory as dynamically allocated (and released) or statically allocated prior， and distributed calculations for each keyword to multiple computing units， then obtained the final recognition result from them. Experimental results indicate that the algorithm can reduce memory and time usage compared with classical DTW. Besides， the coefficient of realtime performances is reduced to 1.17， which is of high performance.

Key words:speech recognition; dynamic time warping (DTW); online algorithm; parallel algorithm; embedded system

0 引言

隨著嵌入式系統軟硬件技術的不斷發展，語音識別已在該領域得到了廣泛應用。目前，嵌入式系統中的語音識別應用主要為孤立詞語音識別，其主要方法有動態時間規整(DTW)、矩陣和分段量化(matrix and segment quantization)、矢量量化(vector quantization， VQ)、隱馬爾可夫模型(hidden Markov model， HMM)、人工神經網絡(artificial neural network， ANN)以及多種方法的組合[1]。這些方法由于各自的優點，得到了深入的研究和廣泛的應用。

嵌入式系統受軟硬件資源的限制，通常執行的是帶有特定要求的預定義任務。由于嵌入式系統一般只針對一項或幾項特殊的任務，設計人員能夠對軟硬件進行優化、減小尺寸、降低成本，單個產品的成本節約能夠隨著產量成百上千倍地放大。低成本的軟硬件勢必要求語音識別系統有較高的時間和空間效率，同時能夠保證語音識別的準確度。DTW算法由于沒有有效采用基于統計方法進行訓練的框架，在解決大詞匯量、連續語音和非特定人語音識別問題時較HMM等算法相形見絀;但DTW算法在實現小詞匯量孤立詞語音識別系統時，其識別準確率等性能指標與用HMM等復雜算法實現幾乎沒有差異，同時由于DTW算法本身的簡潔性和高效性以及孤立詞識別應用的廣泛性，在嵌入式系統中得到了很好的應用[2]。

相比HMM等復雜算法和模型，在小詞匯量語音識別中，經典DTW及其各種優化算法無論在時間效率還是空間需求上都有很大優勢，在帶有多核處理器、DSP或FPGA等具有并行計算能力的嵌入式軟件和硬件系統實現中，算法性能上仍有很大的提升空間。在語音識別的前端處理即端點檢測(voice activity detection， VAD)和MFCC特征向量提取中，文獻[3~5]使用具有高度并行計算能力的硬件FPGA分別實現了這兩步。為實現完整的語音識別系統，DTW等匹配算法也應能高效率實現。

本文先從并行計算和在線算法的角度，對標準DTW及其主要衍生優化算法進行深入分析，在此基礎上提出一種適合于嵌入式系統的DTW在線并行算法。該算法能充分利用具有并行計算能力的硬件，實現固定內存使用量，并有效降低計算過程中的數據依賴。最后通過實驗的方法，在不降低識別準確率的前提下，使語音識別的實時系數達到了1.17。

1 DTW算法分析

DTW是一種使用動態規劃(dynamic programming， DP)思想，衡量時間或速度本質上非線性、但以線性方式表示的兩個序列之間的相似度算法[6]?；贒TW的孤立詞語音識別將未知語音片段與所有已知的參考模板進行相似度計算，尋找一個在時域上最佳匹配的參考模板。在孤立詞語音識別中，通常表現為計算未知語音和每個參考模板之間的非線性距離，然后取距離最小的參考模板作為識別的結果。

DTW問題描述[6]:給定時域序列或模式X和Y(通常是語音片段的特征矢量序列)，其長度分別為|X|和|Y|，即X =x1， x2，…， xi，…， x|X|，Y = y1， y2，…， yj，…， y|Y| ，構造彎折路徑W:

W=w1，w2，…，wk，…，wK max(|X|，|Y|)≤K≤|X|+|Y|(1)

其中:K為彎折路徑的長度，彎折路徑的第k個元素記為wk=(i，j)，i和j分別為序列X和Y的下標。彎折路徑有幾個限制條件:a)路徑必須開始于兩個序列的起點w1=(1，1)，結束于兩個序列的終點wk=(|X|，|Y|);b)彎折路徑中的i和j都具有單調性，以保證路徑不發生重疊;c)兩個序列的每個元素必須都使用到，即

wk=(i，j)，wk+1=(i′，j′);i≤i′≤i+1，j≤j′≤j+1(2)

假定彎折路徑W中的每一段權重都相同，則W的歸一化距離D(W)表示為

D(W)=1KKk=1D(wki，wkj)(3)

其中:D(wki，wkj)是彎折路徑的第k個點中來自序列X的元素wi和來自序列Y中的元素wj構成的點對的距離(所有點對的距離構成距離矩陣，見下文)。最優彎折路徑是指所有彎折路徑中的總長度最小的那條路徑，因而模式X、Y的最優彎折路徑可表示為argminw{D(W)}。

采用動態規劃的方法能高效地求出最優路徑并計算出最優路徑的長度，其結果稱為非線性時間歸一化或動態時間彎折(DTW)。該過程實質是一個兩步處理過程:

a)計算特征矢量模式X和Y各幀之間的距離矩陣。如圖1(a)中水平模式X長5幀，垂直模式Y長4幀，特征矢量為3維(X為垂直方向的3個陰影格子，Y為水平方向的3個陰影格子，下同)，距離矩陣A={aij} (1≤i≤|X|， 1≤j≤|Y|)中，aij為模式X的第i幀的特征矢量與模式Y的第j幀特征矢量之間的距離。

b)用動態規劃的方法，在距離矩陣A中求出一條最佳路徑，該路徑始于A的左上方a11，終于A的右下方a|X||Y|，且長度在所有可能的路徑中最小。動態規劃算法思想要求利用局部最優化處理來達到全局最優，因此需要使用局部判決函數(圖1(a)左上)，這里局部判決函數為無斜率限制的對稱形式，其等效動態規劃式子可以表示為D(i，j)=aij+min(D(i-1，j)，D(i，j-1)，D(i-1，j-1))。局部判決函數加上距離矩陣即構成累加距離矩陣(圖1(b)上)。為找到最優路徑，須記住每次進行局部判決時選擇的是哪條路徑，最后從終點開時沿局部判決函數進行回溯(圖1(b)下)。

DTW算法的時間復雜度比較容易得出，在第一步的距離矩陣A中，每個元素都需要填滿且只需計算一次，在第二步累加矩陣中，每個元素也只需計算一次，因此計算量為2|X||Y|次，若|X|=|Y|=N則算法的時間復雜度為O(N2)。如果局部判決函數中有斜率限制，則運算量會少一些。在孤立詞語音識別中，通常只需要計算出最優路徑的歸一化長度而不需要最優路徑本身，因此在步驟b)的最后不再需要回溯。進一步分析可以發現:a)距離矩陣生成過程中對輸入模式X進行了一次順序掃描，輸入模式中的每個向量按序生成了距離矩陣的每一列(圖2(a));b)累加矩陣可以在距離矩陣列生成后在其基礎上原地計算并存儲而不需要另外分配內存，并且，根據所使用的局部判決函數，只需保留累加矩陣的最新幾列，這些列在新的列生成并計算出最優路徑后可將最舊的列丟棄(圖2(b))。整個計算過程猶如一個固定大小的窗口在前面的累加矩陣上移動，窗口的長度為局部判決函數的水平跨度H與參考模式長度|Y|的乘積(本例中局部判決函數的水平跨度為2，矢量維數為3)。為了計算歸一化距離，需使用一個計數器記錄路徑的長度K。因此，算法所需的空間為H|Y|+1，即算法的空間復雜度為常數。當給定局部判決函數和模板的長度后，即可精確確定所需的內存大小。顯然，局部判決函數的水平跨度(這里為2)和模板長度與所需的內存都成正比。當模板的個數較多時，可將模板分批載入內存。

圖2(a)距離矩陣和累加矩陣按從上到下、從左到右的順序同時生成圖2;(b)累加矩陣生成過程中，先創建一個窗口并在最后一列填入第一個距離列向量，其余列全部為無窮大(Ⅰ)，然后根據局部判決函數生成累加列向量(Ⅱ);然后(Ⅱ)中有斜線陰影的那一列被刪除，后面的列前移，并在窗口最后一列填入新的距離列向量(Ⅲ)，依次下去，直到處理完X的所有列向量。

時間復雜度為二次方的DTW算法在實際應用中效率不高，當語音模式比較長時，運算量將急劇增加。如果語音的幀長(frame length)為30 ms，幀移(frame shift)為15 ms，則每秒語音有65幀，直接實現時實時性比較差，通?？蓮男甭氏拗坪途嚯x計算方法上對DTW進行優化[7]。斜率限制(slope constraint)是指對局部判決函數的斜率范圍進行約束，將動態規劃的搜索區域限制在對角線附近，以減少計算量。文獻[8]提出了許多斜率限制函數并進行了分析，形式化地對幾種典型的斜率限制方法進行了對比分析，認為在不同的場合下應選擇合理的斜率限制方法。當采用斜率限制的方法時，前面對計算順序的分析及結論仍適用，其影響是改變了局部判決函數的水平跨度及相應的窗口寬度。文獻[9]提出了一種DTW優化算法FastDTW，該算法采用多層映射、逐步求精的方法，將DTW的時間復雜度和空間復雜度都降低到了接近線性復雜度，極大提高了算法的時間效率。不過，該算法要求首先知道完整的兩個待計算模式，即必須在一次語音輸入完成后方可啟動算法，這有悖在線算法的思想。Keogh等人[10]提出了一種DTW衍生算法DDTW，該算法額外地考慮到了語音流中加速度對識別結果的影響，在計算n×m距離矩陣中(ith， jth)位置的點對(qi， cj)的距離d(qi， cj)時，不采用歐氏距離，而是qi和cj斜率估計值平方的簡化計算形式:

Dx[q]=12[(qi-qi-1)+(qi+1-qi-1)/2]，1

DDTW算法不修改DTW的數據結構及算法的時間復雜度就增強了DTW的魯棒性，其計算速度通常比計算歐氏距離更快，可直接應用于前面對計算順序的分析過程中。

2 DTW在線并行算法

從前面對DTW算法的分析過程中可得出如下結論:

a)算法所需的內存大小與參考模式的總長度成正比，且與未知模式的長度無關。在嵌入式系統中，對于完成特定任務的識別詞集合，通常參考模式的總長度在每次語音識別過程中不變，即所需的內存可預先精確預知。

b)算法所需的時間與未知模式的長度、參考模式的長度均成正比，時間復雜度為O(N2)。如果將未知模式與多個參考模式的最佳路徑求取過程分配到多個運算單元，則可以借助硬件冗余將算法的時間復雜降低到O(N)。當運算單元數量少于參考模式時，通過細化計算過程，采用流水線可進一步減少整體識別時間。在使用硬件實現時，距離計算使用DDTW的方法更高效;在使用軟件實現時，可用多線程的方法分配多個DTW計算過程。顯然，由于不存在對原始數據的數據依賴，并行度能獲得很大的提升。

2.1 算法簡述

結合DTW自身固有的特性，本文提出的DTW在線并行算法(online parallel DTW， OPDTW)主要適用于具有并行處理能力的嵌入式小詞匯量孤立詞語音識別系統。OPDTW算法首先對問題進行分解，將未知模式與多個已知參考模式的距離計算相對獨立地在多個運算單元中進行，同時分解每個運算單元的計算量，以流水線的方式提高實時性。在DTW計算過程中預先計算并分配固定大小的內存(軟件實現時，為增加cache命中率，應限制局部判決函數的水平跨度)。最后，匯合所有運算單元的計算結果，傳送到決策模塊，并由該模塊給出最終識別結果。

2.2 OPDTW算法

算法整體框圖如圖3所示，先計算出每幀未知語音的特征矢量，再按照時間順序將這些矢量構成的序列一起傳遞到多條同構DTW流水線上，每條流水線按照本文第1章的方法獨立計算未知語音矢量序列與參考模式的距離。所有流水線完成DTW計算后，由決策模塊根據各個流水線的計算結果以及未知語音的其他信息得出識別結果。由于參考模式長度不一，各流水線的計算時間存在差異，每條流水線都設置了完成標志位Pi (1≤i≤N)，決策模塊依據這些標志位，陸續處理已流水線的計算結果。實際應用中，可根據歷史語音識別結果提前終止尚未完成的計算過程的方法。該方法可方便地在本算法框架中實現，如圖3中虛線所示。由于流水線數目的增加會消耗更多的硬件資源，從系統的角度，應控制流水線的數量。流水線的數量小于參考模式的個數時，通過決策過程將未知模式與參考模式的DTW運算分批次進行。

算法的在線性表現為，未知語音的特征矢量序列在以幀為單位生成后立即注入各條空閑流水線，且在處理完成后，這些特征矢量立即被丟棄而不保存。算法的并行性主要表現在兩方面:a)多個參考模式可同時進入多個流水線計算，當參考模式數量多于流水線時，參考模式根據其長度被均勻地劃分為多個批次;b)單個DTW處理過程流水化，流水線分為距離矩陣計算、累加矩陣計算和最短路徑計算三個節拍。其中，距離矩陣計算根據計算方法的不同，可進一步細化流水。本文第1章提到的斜率估計方法由于計算小，可不細化流水;而采用歐式距離，由于涉及到大量乘法，若沒有對此類運算作特殊處理(如查表)，應細化流水。

圖3中的決策過程主要包括:

a)檢測所有流水線的完成情況，當發現有計算完成的流水線時，進行相應處理。一般包括計算當前已完成流水線中最短距離最小的單詞。

b)根據歷史記錄，應用啟發式算法預測當前已計算完成的流水線中的最佳單詞是否達到一定精度，若達到則對所有尚在計算中的流水線發出終止信號。當參考模式的數量較多或特征矢量生成速度較快時，該方法能避免流水線擁塞。

c)當所有流水線計算完成或被終止時，存儲本次語音識別的結果數據(如最佳匹配單詞的距離)并給出識別結果。

d)流水線數量較少時，將參考模式分批次送入流水線計算。

流水線擁塞控制策略:當決策過程發現流水線產生擁塞現象時，根據搜集到的其他未知語音序列信息，決定丟棄新到來的矢量序列或放棄正在流水線中處理的數據而處理新來的矢量序列。由于大多數情況下新來的數據比舊數據更重要，通常在流水線擁塞時選擇丟棄舊數據較為合理。

2.3 算法分析

令特征矢量的維度為k，未知模式的長度為u，參考模式的個數為m(詞匯表大小)，參考模式的總長度為n，局部判決函數的水平跨度為h，流水線條數為p。流水線的距離矩陣A的窗口平均大小為hm/n，若令t為特征向量的數據類型所占的字節數，則OPDTW算法所需的內存為hmt/n Byte，所有流水線所需的內存為hmtp/n Byte，經典DTW所需的內存至少為nuk Byte。當p≥m時，算法所需時間為經典DTW的1/m;當p

3 實驗流程及結果分析

嵌入式系統中目前最為靈活的硬件設備當屬FPGA(現場可編程邏輯門陣列)，它非常適合實現本算法。本實驗在Xilinx ISE 10.1(NT)上進行，采用Verilog硬件描述語言設計，使用ISE Simulator工具進行仿真，FPGA采用Spartan3系列的XC3S200 FT256芯片，輸入時鐘頻率50 MHz，詞匯表采用浙江省11個地級市和杭州地區13個縣級市名稱，共24個詞;測試例子采用50個詞匯表中的語音波形。系統框圖如圖4所示。

系統中，24個參考模式以及50個測試模式的語音數據特征向量用MATLAB在PC上預先計算好并生成coe文件，在使用IP核生成只讀內存時加載該文件。圖4中“讀入數據并初始化內存IP核”之前的步驟全部在MATLAB上實現[11]，之后的步驟使用Verilog HDL實現。語音采樣率為8 000 Hz，量化位數16位，通道數1個，幀長30 ms，幀移10 ms，端點檢測方法采用文獻[12]的方法，語音的參數特征采用12維MFCC及其一階差分系數，共24維。在生成的coe文件中去掉了靜音、噪聲幀，只含參考模式有效語音幀的特征向量。特征向量的數據類型為32位有符號整數，特征向量的個數(有效語音的幀數)直接硬編碼在Verilog設計中。由于本算法使用Verilog實現，算法所需的內存(寄存器)固定不變。實現OPDTW時，每個時鐘周期從內存中讀取各個參考模式的一組特征向量并更新累加矩陣和距離矩陣。實驗中，OPDTW的同構流水線條數為6條，24個參考模式每次識別需重復4次流水線操作，每條流水線有4個節拍，每個節拍的時間長度相同。流水線的第一節拍是未知模式數據緩存，這是為了在多次流水線操作中避免數據依賴(如果參考模式個數不大于流水線條數則本節拍可省略)。第二和第三節拍分別是距離矩陣和最短路徑計算。最后一個節拍設置流水線完成標志位。

在流水線數據提供與控制單元(以下簡稱控制單元)中，特征矢量從內存中讀取，內存配置為一個時鐘周期可讀取兩次數據(上升沿和下降沿)，內存的數據輸出端口連接到各條流水線的第一個節拍中，由控制單元統一負責內存地址控制。為協調各條流水線的執行進度，每條流水線的完成標志由控制單元主動探測，當所有流水線都完成后，控制單元發出識別結果。識別結果在仿真時，使用Verilog系統任務在仿真控制臺顯示識別結果及耗費的時鐘周期數;在FPGA實驗板上運行時，識別結果為識別結果在詞匯表中的序號，并顯示在與FPGA相連接的數碼管上。

實驗結果及實時性分析:根據ISE的綜合結果統計信息，本設計消耗了3 607個邏輯門，占總邏輯門的83.5%[13]。根據仿真結果，關鍵詞的平均識別時間大約為827個時鐘周期。實驗中參考模式平均有效語音長度為58幀，大約為0.6 s。不過，這只是語音識別過程的一個階段所需的時間，整個語音識別的時間還包括特征提取等。根據中文語音識別系統通用技術規范[14]提出的實時系數計算方法，即假設發音從Ts開始，到Te結束，識別結束時間為Tr，實時性系數為R=(Tr-Ts)/(Te-Ts)。根據文獻[3~5]的實驗方法，端點檢測的時間為語音持續時間的3%~6%，24維MFCC參數提取時間比例為5%~10%，從而得到整個語音識別過程的實時性系數大約為R=1+4%+7.5%+827/50 MHz≈1.17，比較接近于1，具有較高的實時性，能滿足大部分應用場合的需要。

4 結束語

本文提出了一種DTW在線并行算法，減少了因數據依賴帶來的等待時間;提高了DTW的并行度，充分挖掘出硬件的計算能力，減少了算法所需時間。由于DTW自身的普適性，OPDTW算法適用于數據可表示為一維非線性形式的匹配問題。隨著并行編程語言以及多核技術的發展，可采用軟件的方法實現本算法，以獲得更靈活更廣泛的應用。

參考文獻:

[1]

林常志.基于統計的語音識別方法分析報告 [R/OL].(2003-12-26)[2009-06-13].http://icrc.hitsz.edu.cn/data/林常志語音識別技術報告.doc.

[2]萬春.基于DTW的語音識別應用系統研究與實現[J].集美大學學報:自然科學版，2002，7(2):104-108.

[3]李昱，林志謀，黃云鷹，等.基于短時能量和短時過零率的VAD算法及其FPGA實現[J].電子技術應用，2006，32(9):110-113.

[4]謝秋云，肖鐵軍.語音MFCC特征提取的FPGA實現[J].計算機工程與設計，2008，29(21):5474-5475，5493.

[5]高謙，張國杰，張樹才.基于FPGA的高性能MFCC特征參數提取[J].通信技術，2008，41(6):153-154，157.

[6]HIROAKI S， SEIBI C. Dynamic programming algorithm optimization for spoken word recognition[M]// Readings in speech recognition. San Francisco: Morgan Kaufmann Publishers， 1990: 159-165.

[7]姚天任.數字語音處理[M].武漢:華東科技大學出版社，2007: 382.

[8] RABINER L R. Considerations in dynamic time warping algorithms for discrete word recognition[J]. The Journal of the Acoustical Society of America， 1978， 63(S1): S79.

[9]STAN S， PHILIP C. FastDTW: toward accurate dynamic time warping in linear time and space[J]. Intelligent Data Analysis， 2007， 11(5): 561-580.

[10]KEOGH E J， PAZZANI M J. Derivative dynamic time warping[C]// Proc of the 2001 SIAM International Conference on Data Mining. Chicago: SIAM， 2001:1-11.

[11]龍銀東， 劉宇紅， 敬嵐，等.在MATLAB環境下實現的語音識別[J]. 微計算機信息， 2007(34):255-256，276.

[12]劉華平，李昕，徐柏齡，等.語音信號端點檢測方法綜述及展望[J].計算機應用研究，2008，25(8):2278-2282.

[13]Spartan3 FPGA family: complete data sheet，v1.4[R]. San Jose， CA: Xilinx Inc， 2006.

[14]中華人民共和國國家質量監督檢驗檢疫總局，中國國家標準化管理委員會. GB/T 21023—2007， 中文語音識別系統通用技術規范[S].北京:中國標準出版社，2007.