改進K-means 聚類剪枝的DTW 動態手勢識別方法

倪慶千，喬冀瑜，連宗凱

（中山大學智能工程學院，廣州 510006）

0 引言

手勢是一種簡單而自然的交流方式，也是人機交互的重要手段。手勢識別可理解為通過計算機理解人的手部語言。由于人體的靈活性使得動態手勢豐富多變，建立計算機識別模型困難[1]。現有模型非特定人適應性弱、手勢庫容量小[2]，因此需要探究更加適宜處理大量動態手勢動作的方法。

從識別設備的角度，目前手勢識別主要可分為基于計算機視覺的手勢識別和基于可穿戴設備的手勢識別[3]。基于視覺的手勢識別利用圖像視頻處理技術和深度學習[4]等技術，例如基于Kinect 的手語翻譯系統[5]、基于Leapmotion 的手勢識別系統[6]及王凱等人提出的基于AdaBoost 算法和光流匹配的實時手勢識別方案[7]。基于視覺的方案優點有識別精度高、容量大和動作自由等，但是易受光線、背景等環境因素影響，同時由于需先做大量預處理，計算消耗成本高[1]。基于可穿戴設備的手勢識別利用多種傳感器，例如早在1983 年AT&T的Grimes 原創性發明了數據手套[8]、2016 年Facebook的VR 交互設備Oculus Touch、鄭錦龍團隊的穿戴式手語識別翻譯系統[9]等，可穿戴設備雖然無法無感識別，但具有高精度高靈敏度、數據結構簡單以及計算成本低的優勢。

從識別方法的角度，主要有基于模板匹配的方法、基于統計模型的方法和基于人工神經網絡方法[2]。模板匹配是一種在模板庫中尋找特定目標的常用策略，這種方法遍歷比較所有可能的對象獲得相似度，并從中選出相似度足夠高的結果，認為其與模板匹配。常見方法有動態時間規整（Dynamic Time Warping，DTW）[10]。統計模型則以概率為基礎，采用數學統計的方法建立難以通過理論分析建立數學，但可以通過大量數據統計變量之間函數關系的模型，常見方法有隱馬爾可夫模型（Hidden Markov Model，HMM）。人工神經網絡的方法則通過調整網絡內部大量節點之間相互連接之間的關系從而處理信息，經典模型有BP 神經網絡（Back Propagation Neural Network）、卷積神經網絡（Convolutional Neural Networks，CNN）[11]、循環神經網絡（Recurrent Neural Network，RNN）[12]。統計模型、人工神經網絡模型方法適合解決高復雜度問題，但需要大量清洗過的數據，且計算量大，擴展彈性差。模板匹配方法所需數據量少，可動態擴展模板庫以識別新的手勢，但在待識別手勢模板較多時，遍歷比較會導致識別速度慢、識別正確率降低的問題。

根據上述分析，研究從設備成本、數據量和可擴展性的角度考量，著力研究緩解動態手勢識別寬容度、識別容量、識別速度和識別精度之間的矛盾。我們基于可穿戴數據手套，提出一種改進K-means 聚類剪枝的DTW 動態手勢識別方法。該方法首先以DTW 為度量，對手勢模板庫的片段序列進行K-means 聚類預處理。在此基礎上，先對當前傳入手勢序列的片段使用DTW 確定所在類，然后在類內采用整個序列進行DTW模板匹配，獲得最終識別結果。經過實驗驗證，我們提出的手勢識別方法具有成本低、計算速度快、可擴展性優良等優點，具有成為手勢交互底層技術的潛力。

1 數據手套手勢采集系統

1.1 硬件系統簡介

數據手套手勢采集系統的硬件部分為左右手兩只手套（GloveR，GloveL），每只手套由姿態傳感器模塊Mpu9255、彎曲度傳感器 Flex2.2、2.4G 通信模塊NRF24l01、藍 牙 通 信 模 塊 JDY- 08、主 控 模 塊STM32F103RCT6 及周邊電路構成，電路結構示意圖與實物圖如圖1、圖2 所示。

圖1 電路結構示意圖

圖2 數據手套實物圖

其中Mpu9255 為九軸傳感器，手部姿態的變化會引起內部傳感器的參數變化，用于獲取手部姿態信息；Flex2.2 為長條狀電阻應變片，通過與標準電阻進較的電壓差，獲得手指彎曲程度；NRF24l01 負責左右手套內部數據通訊，JDY-08 則負責數據手套最終數據對外通信；STM32F103RCT6 為控制核心，負責傳感器數據采集、數據規整與無線通訊調度。

1.2 數據格式

數據手套通過藍牙對外發送原始數據，其每次發送十個手指的彎曲數據與手部的運動姿態數據，令為O=[Rcurvature,RAcc,RGyro,Lcurvature,LAcc,LGyro]，動態手勢數據按時間順序取得序列S={O1,O2,…,On}。

2 改進K-means聚類預處理

動態時間規整DTW 本質上是一種模板匹配方法。當手勢模板過多時，如果直接使用DTW 和模板手勢庫逐個遍歷比較，則計算量與手勢模板量成線性增長，最終獲取結果只有一個，存在大量無效計算。因此，文章采用K-means 聚類算法對原始序列進行聚類預處理，形成剪枝減去無效計算。

K-means 是一種常見的動態迭代求解的無監督學習算法[13]。K-means 聚類算法計算速度快，算法思路清晰，并且聚類效果較好。在原始K-means 算法的基礎上，我們提出以DTW 相似度為度量指標，替代傳統的歐氏距離用于評價序列之間的距離，以解決使用歐氏距離難以準確計算時序序列之間距離的缺陷。

以DTW 相似度為距離度量的K-means 聚類主要分為兩步：一是動態時間規整算法計算不同手勢片段序列之間的相似度；二是基于DTW 相似度，給定K 值與隨機初始中心進行K-means 聚類迭代，獲得K 個類簇及相應聚類中心。

2.1 動態時間規整算法計算相似度

由于人體的靈活多變性與個體差異，同一個手勢不同的人做出來時，動作速度、運動軌跡和運動節奏存在差別，甚至同一個動作由同一個人在不同時間做出相同含義的手勢也存在差別。這使得數據手套傳入的時序序列數據在時間軸上存在不完全對齊現象，同時又無法通過線性縮放的方法對齊。DTW 通過對時間序列進行局部非線性縮放，使兩個序列形態盡可能對齊，如圖3 DTW 示意圖所示。

動態時間規整算法原理是給定兩個序列Q={Q1,Q2,…,Qi,…,Qn} 和C={C1,C2,…,Cj,…,Cm} ，其長度分別是n和m。構造一個n*m的矩陣網格，以歐氏距離D為標準，矩陣元素(i,j)為Qi和Cj兩個點的距離D(Qi,Cj)。從序列起始段所在的矩陣角為邊界條件，滿足連續性和單調性約束，通過動態規劃求得距離累積值最小的路徑即為最佳路徑。

圖3 DTW示意圖

此時，最佳路徑的累積距離值即為兩個序列的DTW 相似度，即兩個時間序列經過非線性縮放后的最小距離。

2.2 基于DDTTWW相似度進行K-mmeeaannss聚類

基于DTW 相似度的K-means 算法原理是給定聚類數k，隨機選擇k 個對象最為初始聚類中心。接著以DTW 相似度為距離度量，計算每個樣本序列和各個中心之間的距離，將序列劃分給距離它最近的中心，形成k 個聚類C={ }C1,C2,…,Ck。再重新計算每個聚類的均值作為新的中心。反復執行上述步驟直至各聚類中心移動幅度小于設定閾值ε。K-means 算法是動態迭代直至收斂的過程，流程如圖4。

圖4 K-means算法流程圖

由上分析可知，K-means 算法需要根據序列之間的距離來判斷序列之間的遠近。但是傳統的歐氏距離難以合理計算時間序列之間的距離，因此使用序列之間的DTW 相似度來代替歐氏距離是有必要的。

3 DTW動態手勢識別算法

在對模板手勢庫進行K-means 聚類預處理后，將所有手勢分有k個類，每個類別取出聚類中心作為類等代表序列ri，令所有類均取出的組成集合R={r1,r2,…,rk} 。

開始識別手勢動作時，對于數據手套新采集的完整序列，取相應片段依次與R 中片段序列通過DTW 進行比較，DTW 計算結果最小值所對應的類C，確定為新序列所歸屬類別Ci。再將完整序列依次與類Ci內完整序列進行比較，直到得到DTW 計算結果最小，即相似度最高的序列，即為最終動態手勢識別結果。具體流程如圖5 所示。

圖5 手勢識別流程圖

4 測試結果與分析

針對動態手勢識別，實驗從識別容量、平均分類正確率、平均識別正確率、平均識別運算時間標準差、聚類后∕前識別所需時間比和擴展比率幾個性能指標，用以評估所提出方法的有效性。

其中，識別容量分別設置為Vi={8,16,32,64,128}，平均正確率計算公式為：

當式1 中x為Class時為平均分類正確率，x為Gesture時為平均識別正確率。

平均識別運算時間公式為：

上述三項目平均值的有效性，我們利用標準差Si來計算其原始數據的離散程度，標準差Si可由下式表示：

為了說明該算法的可擴展性，我們提出聚類后∕前識別所需時間比例Time scale和擴展比率Expansion ratio來量化衡量，其中Time scale為聚類后平均識別時間除以聚類前平均識別時間，從識別時間的角度評估識別效率的改進程度：

同時，從時間角度也可從平均識別時間提升倍數Time multiplier的角度說明效率的改進程度，其值為Time scale的倒數，即：

擴展比率Expansion ratio用于刻畫所提出該方法的在可用范圍內的容量擴展能力，表示為識別手勢量的提升比例、提升后平均識別正確率與平均識別時間提升倍數三項乘積，即：

式（2）、（6）中NumGes為手勢數量，式（6）中T為第幾次實驗為平均識別正確率。

4.1 模板手勢庫

模板手勢庫數據是由根據《中國手語（上下修訂版）》中示意手勢，由實驗員采集和維護。手勢庫數據包括了數字“1-9”、字符“A-Z”、肯定否定、動作詞和問候等常用詞匯。

表1 模板手勢庫

4.2 實驗流程

首先，對已有模板手勢數據庫進行改進K-means聚類預處理，輸入不同的k 值和隨機選取的初始序列中心，迭代獲取不同k 值下的聚類結果C。其次，實驗員戴上數據手套，手套，將感知到的雙手數據通過藍牙傳輸至上位機。上位機通過串口讀取數據，獲得實時輸入的當前手勢序列。

最后，將實時輸入的當前手勢序列，取出對應片段與K-means 聚類預處理后的類代表序列片段R進行DTW 運算，確定當前手勢所在類C。再將完整當前手勢序列依次和類內完整序列進行比較，直到得到相似度最高的序列，獲得其對應手勢含義，即為最終動態手勢識別結果。

上述過程可由圖6 簡要概述。

4.3 實驗結果及分析

按照上述實驗說明，實驗結果如表2 所示。

圖6 手勢識別流示意圖

圖7 實驗結果

表2 實驗結果

在擴展性上，首先在圖7（a）中可以看出隨著識別容量的擴展，時間消耗大幅度縮小的趨勢更加明顯。其次從表2 擴展比率和圖7（b）可以看出，擴展能力隨著識別容量的成倍增大而先上升后下降的。在識別容量翻16 倍時，所需分類迭代次數和識別時間僅僅增長不到4 倍，并仍在可控范圍之內。如圖7（c）所示，高擴展低消耗來源于聚類剪枝，我們采用完整時序數據片段做聚類處理，針對時序序列的特點使用DTW 作為聚類內容相似度的度量指標。

5 結語

我們提出改進K-means 聚類剪枝的DTW 動態手勢識別方法，旨在實現非特定人大量動態手勢的高效識別。本文從構建獲取與處理數據的數據手套入手，基于動態手勢時間序列的特性，提出采用DTW 作為距離度量的無監督的改進K-means 聚類方法，有效消解了時序數據不完全對齊的問題，具備良好的伸縮性和高效性。明顯且可控地提高了動態手勢的識別速度和精確度，達到良好效果，有較高的實際應用價值。

無論是手勢識別或手語翻譯技術均是大有裨益的研究，該研究提供肢體動作這一個在計算機視覺、聽覺與腦機接口外更符合直覺的維度，這些多模態信息有助于讓機器理解人類更近一步，充分的實驗和實驗結果驗證了我們的想法。

我們也應當注意到這項工作的局限性：數據手套雖然使用方便，在日常使用中卻會稍顯笨重無法無感使用；模板手勢庫若用語手語翻譯，則數據庫大小仍然過小；采用的算法雖然經典，但其適用范圍存在局限性，同時存在無法確定實際數據分布情況與需要手動賦值k 值和閾值ε參數的問題；原始數據分布無法明確其在高維空間是否為簇狀分布，采用的K-means 算法對非簇狀；算法是串行計算的，并行程度相對最新的深度學習算法略遜一籌的同時卻無法計算長序列。這些未解決的問題有待進一步探討和研究，這說明了這個領域還有廣闊的進步空間，我們期待在未來的工作中能進一步解決這些問題。在下一步工作中，我們將改進數據采集設備，繼續擴展模板手勢庫，嘗試將深度學習算法和動態手勢識別相結合，以進一步調高識別的準確率與識別速度，并嘗試解決連詞成句的長序列的問題，使其能有效應用于手語翻譯或復雜的交互手勢識別。