改進(jìn)K-means 聚類(lèi)剪枝的DTW 動(dòng)態(tài)手勢(shì)識(shí)別方法

倪慶千，喬冀瑜，連宗凱

（中山大學(xué)智能工程學(xué)院，廣州 510006）

0 引言

手勢(shì)是一種簡(jiǎn)單而自然的交流方式，也是人機(jī)交互的重要手段。手勢(shì)識(shí)別可理解為通過(guò)計(jì)算機(jī)理解人的手部語(yǔ)言。由于人體的靈活性使得動(dòng)態(tài)手勢(shì)豐富多變，建立計(jì)算機(jī)識(shí)別模型困難[1]。現(xiàn)有模型非特定人適應(yīng)性弱、手勢(shì)庫(kù)容量小[2]，因此需要探究更加適宜處理大量動(dòng)態(tài)手勢(shì)動(dòng)作的方法。

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

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

根據(jù)上述分析，研究從設(shè)備成本、數(shù)據(jù)量和可擴(kuò)展性的角度考量，著力研究緩解動(dòng)態(tài)手勢(shì)識(shí)別寬容度、識(shí)別容量、識(shí)別速度和識(shí)別精度之間的矛盾。我們基于可穿戴數(shù)據(jù)手套，提出一種改進(jìn)K-means 聚類(lèi)剪枝的DTW 動(dòng)態(tài)手勢(shì)識(shí)別方法。該方法首先以DTW 為度量，對(duì)手勢(shì)模板庫(kù)的片段序列進(jìn)行K-means 聚類(lèi)預(yù)處理。在此基礎(chǔ)上，先對(duì)當(dāng)前傳入手勢(shì)序列的片段使用DTW 確定所在類(lèi)，然后在類(lèi)內(nèi)采用整個(gè)序列進(jìn)行DTW模板匹配，獲得最終識(shí)別結(jié)果。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，我們提出的手勢(shì)識(shí)別方法具有成本低、計(jì)算速度快、可擴(kuò)展性?xún)?yōu)良等優(yōu)點(diǎn)，具有成為手勢(shì)交互底層技術(shù)的潛力。

1 數(shù)據(jù)手套手勢(shì)采集系統(tǒng)

1.1 硬件系統(tǒng)簡(jiǎn)介

數(shù)據(jù)手套手勢(shì)采集系統(tǒng)的硬件部分為左右手兩只手套（GloveR，GloveL），每只手套由姿態(tài)傳感器模塊Mpu9255、彎曲度傳感器 Flex2.2、2.4G 通信模塊NRF24l01、藍(lán) 牙 通 信 模 塊 JDY- 08、主 控 模 塊STM32F103RCT6 及周邊電路構(gòu)成，電路結(jié)構(gòu)示意圖與實(shí)物圖如圖1、圖2 所示。

圖1 電路結(jié)構(gòu)示意圖

圖2 數(shù)據(jù)手套實(shí)物圖

其中Mpu9255 為九軸傳感器，手部姿態(tài)的變化會(huì)引起內(nèi)部傳感器的參數(shù)變化，用于獲取手部姿態(tài)信息；Flex2.2 為長(zhǎng)條狀電阻應(yīng)變片，通過(guò)與標(biāo)準(zhǔn)電阻進(jìn)較的電壓差，獲得手指彎曲程度；NRF24l01 負(fù)責(zé)左右手套內(nèi)部數(shù)據(jù)通訊，JDY-08 則負(fù)責(zé)數(shù)據(jù)手套最終數(shù)據(jù)對(duì)外通信；STM32F103RCT6 為控制核心，負(fù)責(zé)傳感器數(shù)據(jù)采集、數(shù)據(jù)規(guī)整與無(wú)線(xiàn)通訊調(diào)度。

1.2 數(shù)據(jù)格式

數(shù)據(jù)手套通過(guò)藍(lán)牙對(duì)外發(fā)送原始數(shù)據(jù)，其每次發(fā)送十個(gè)手指的彎曲數(shù)據(jù)與手部的運(yùn)動(dòng)姿態(tài)數(shù)據(jù)，令為O=[Rcurvature,RAcc,RGyro,Lcurvature,LAcc,LGyro]，動(dòng)態(tài)手勢(shì)數(shù)據(jù)按時(shí)間順序取得序列S={O1,O2,…,On}。

2 改進(jìn)K-means聚類(lèi)預(yù)處理

動(dòng)態(tài)時(shí)間規(guī)整DTW 本質(zhì)上是一種模板匹配方法。當(dāng)手勢(shì)模板過(guò)多時(shí)，如果直接使用DTW 和模板手勢(shì)庫(kù)逐個(gè)遍歷比較，則計(jì)算量與手勢(shì)模板量成線(xiàn)性增長(zhǎng)，最終獲取結(jié)果只有一個(gè)，存在大量無(wú)效計(jì)算。因此，文章采用K-means 聚類(lèi)算法對(duì)原始序列進(jìn)行聚類(lèi)預(yù)處理，形成剪枝減去無(wú)效計(jì)算。

K-means 是一種常見(jiàn)的動(dòng)態(tài)迭代求解的無(wú)監(jiān)督學(xué)習(xí)算法[13]。K-means 聚類(lèi)算法計(jì)算速度快，算法思路清晰，并且聚類(lèi)效果較好。在原始K-means 算法的基礎(chǔ)上，我們提出以DTW 相似度為度量指標(biāo)，替代傳統(tǒng)的歐氏距離用于評(píng)價(jià)序列之間的距離，以解決使用歐氏距離難以準(zhǔn)確計(jì)算時(shí)序序列之間距離的缺陷。

以DTW 相似度為距離度量的K-means 聚類(lèi)主要分為兩步：一是動(dòng)態(tài)時(shí)間規(guī)整算法計(jì)算不同手勢(shì)片段序列之間的相似度；二是基于DTW 相似度，給定K 值與隨機(jī)初始中心進(jìn)行K-means 聚類(lèi)迭代，獲得K 個(gè)類(lèi)簇及相應(yīng)聚類(lèi)中心。

2.1 動(dòng)態(tài)時(shí)間規(guī)整算法計(jì)算相似度

由于人體的靈活多變性與個(gè)體差異，同一個(gè)手勢(shì)不同的人做出來(lái)時(shí)，動(dòng)作速度、運(yùn)動(dòng)軌跡和運(yùn)動(dòng)節(jié)奏存在差別，甚至同一個(gè)動(dòng)作由同一個(gè)人在不同時(shí)間做出相同含義的手勢(shì)也存在差別。這使得數(shù)據(jù)手套傳入的時(shí)序序列數(shù)據(jù)在時(shí)間軸上存在不完全對(duì)齊現(xiàn)象，同時(shí)又無(wú)法通過(guò)線(xiàn)性縮放的方法對(duì)齊。DTW 通過(guò)對(duì)時(shí)間序列進(jìn)行局部非線(xiàn)性縮放，使兩個(gè)序列形態(tài)盡可能對(duì)齊，如圖3 DTW 示意圖所示。

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

圖3 DTW示意圖

此時(shí)，最佳路徑的累積距離值即為兩個(gè)序列的DTW 相似度，即兩個(gè)時(shí)間序列經(jīng)過(guò)非線(xiàn)性縮放后的最小距離。

2.2 基于DDTTWW相似度進(jìn)行K-mmeeaannss聚類(lèi)

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

圖4 K-means算法流程圖

由上分析可知，K-means 算法需要根據(jù)序列之間的距離來(lái)判斷序列之間的遠(yuǎn)近。但是傳統(tǒng)的歐氏距離難以合理計(jì)算時(shí)間序列之間的距離，因此使用序列之間的DTW 相似度來(lái)代替歐氏距離是有必要的。

3 DTW動(dòng)態(tài)手勢(shì)識(shí)別算法

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

開(kāi)始識(shí)別手勢(shì)動(dòng)作時(shí)，對(duì)于數(shù)據(jù)手套新采集的完整序列，取相應(yīng)片段依次與R 中片段序列通過(guò)DTW 進(jìn)行比較，DTW 計(jì)算結(jié)果最小值所對(duì)應(yīng)的類(lèi)C，確定為新序列所歸屬類(lèi)別Ci。再將完整序列依次與類(lèi)Ci內(nèi)完整序列進(jìn)行比較，直到得到DTW 計(jì)算結(jié)果最小，即相似度最高的序列，即為最終動(dòng)態(tài)手勢(shì)識(shí)別結(jié)果。具體流程如圖5 所示。

圖5 手勢(shì)識(shí)別流程圖

4 測(cè)試結(jié)果與分析

針對(duì)動(dòng)態(tài)手勢(shì)識(shí)別，實(shí)驗(yàn)從識(shí)別容量、平均分類(lèi)正確率、平均識(shí)別正確率、平均識(shí)別運(yùn)算時(shí)間標(biāo)準(zhǔn)差、聚類(lèi)后∕前識(shí)別所需時(shí)間比和擴(kuò)展比率幾個(gè)性能指標(biāo)，用以評(píng)估所提出方法的有效性。

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

當(dāng)式1 中x為Class時(shí)為平均分類(lèi)正確率，x為Gesture時(shí)為平均識(shí)別正確率。

平均識(shí)別運(yùn)算時(shí)間公式為：

上述三項(xiàng)目平均值的有效性，我們利用標(biāo)準(zhǔn)差Si來(lái)計(jì)算其原始數(shù)據(jù)的離散程度，標(biāo)準(zhǔn)差Si可由下式表示：

為了說(shuō)明該算法的可擴(kuò)展性，我們提出聚類(lèi)后∕前識(shí)別所需時(shí)間比例Time scale和擴(kuò)展比率Expansion ratio來(lái)量化衡量，其中Time scale為聚類(lèi)后平均識(shí)別時(shí)間除以聚類(lèi)前平均識(shí)別時(shí)間，從識(shí)別時(shí)間的角度評(píng)估識(shí)別效率的改進(jìn)程度：

同時(shí)，從時(shí)間角度也可從平均識(shí)別時(shí)間提升倍數(shù)Time multiplier的角度說(shuō)明效率的改進(jìn)程度，其值為T(mén)ime scale的倒數(shù)，即：

擴(kuò)展比率Expansion ratio用于刻畫(huà)所提出該方法的在可用范圍內(nèi)的容量擴(kuò)展能力，表示為識(shí)別手勢(shì)量的提升比例、提升后平均識(shí)別正確率與平均識(shí)別時(shí)間提升倍數(shù)三項(xiàng)乘積，即：

式（2）、（6）中NumGes為手勢(shì)數(shù)量，式（6）中T為第幾次實(shí)驗(yàn)為平均識(shí)別正確率。

4.1 模板手勢(shì)庫(kù)

模板手勢(shì)庫(kù)數(shù)據(jù)是由根據(jù)《中國(guó)手語(yǔ)（上下修訂版）》中示意手勢(shì)，由實(shí)驗(yàn)員采集和維護(hù)。手勢(shì)庫(kù)數(shù)據(jù)包括了數(shù)字“1-9”、字符“A-Z”、肯定否定、動(dòng)作詞和問(wèn)候等常用詞匯。

表1 模板手勢(shì)庫(kù)

4.2 實(shí)驗(yàn)流程

首先，對(duì)已有模板手勢(shì)數(shù)據(jù)庫(kù)進(jìn)行改進(jìn)K-means聚類(lèi)預(yù)處理，輸入不同的k 值和隨機(jī)選取的初始序列中心，迭代獲取不同k 值下的聚類(lèi)結(jié)果C。其次，實(shí)驗(yàn)員戴上數(shù)據(jù)手套，手套，將感知到的雙手?jǐn)?shù)據(jù)通過(guò)藍(lán)牙傳輸至上位機(jī)。上位機(jī)通過(guò)串口讀取數(shù)據(jù)，獲得實(shí)時(shí)輸入的當(dāng)前手勢(shì)序列。

最后，將實(shí)時(shí)輸入的當(dāng)前手勢(shì)序列，取出對(duì)應(yīng)片段與K-means 聚類(lèi)預(yù)處理后的類(lèi)代表序列片段R進(jìn)行DTW 運(yùn)算，確定當(dāng)前手勢(shì)所在類(lèi)C。再將完整當(dāng)前手勢(shì)序列依次和類(lèi)內(nèi)完整序列進(jìn)行比較，直到得到相似度最高的序列，獲得其對(duì)應(yīng)手勢(shì)含義，即為最終動(dòng)態(tài)手勢(shì)識(shí)別結(jié)果。

上述過(guò)程可由圖6 簡(jiǎn)要概述。

4.3 實(shí)驗(yàn)結(jié)果及分析

按照上述實(shí)驗(yàn)說(shuō)明，實(shí)驗(yàn)結(jié)果如表2 所示。

圖6 手勢(shì)識(shí)別流示意圖

圖7 實(shí)驗(yàn)結(jié)果

表2 實(shí)驗(yàn)結(jié)果

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

5 結(jié)語(yǔ)

我們提出改進(jìn)K-means 聚類(lèi)剪枝的DTW 動(dòng)態(tài)手勢(shì)識(shí)別方法，旨在實(shí)現(xiàn)非特定人大量動(dòng)態(tài)手勢(shì)的高效識(shí)別。本文從構(gòu)建獲取與處理數(shù)據(jù)的數(shù)據(jù)手套入手，基于動(dòng)態(tài)手勢(shì)時(shí)間序列的特性，提出采用DTW 作為距離度量的無(wú)監(jiān)督的改進(jìn)K-means 聚類(lèi)方法，有效消解了時(shí)序數(shù)據(jù)不完全對(duì)齊的問(wèn)題，具備良好的伸縮性和高效性。明顯且可控地提高了動(dòng)態(tài)手勢(shì)的識(shí)別速度和精確度，達(dá)到良好效果，有較高的實(shí)際應(yīng)用價(jià)值。

無(wú)論是手勢(shì)識(shí)別或手語(yǔ)翻譯技術(shù)均是大有裨益的研究，該研究提供肢體動(dòng)作這一個(gè)在計(jì)算機(jī)視覺(jué)、聽(tīng)覺(jué)與腦機(jī)接口外更符合直覺(jué)的維度，這些多模態(tài)信息有助于讓機(jī)器理解人類(lèi)更近一步，充分的實(shí)驗(yàn)和實(shí)驗(yàn)結(jié)果驗(yàn)證了我們的想法。

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