基于Kinect動態手勢識別算法的研究與實現

張瑩瑩，郭 星

(1.安徽大學 計算智能與信號處理重點實驗室，安徽 合肥 230039；2.安徽大學 計算機科學與技術學院，安徽 合肥 230601)

基于Kinect動態手勢識別算法的研究與實現

張瑩瑩1，郭 星2

(1.安徽大學 計算智能與信號處理重點實驗室，安徽 合肥 230039；2.安徽大學 計算機科學與技術學院，安徽 合肥 230601)

隨著計算機技術和信息化的發展，人機交互在辦公以及生活中顯得越來越重要。由于手勢具有靈活、直觀、簡單等優點，成為人機交互研究的重要領域。針對手勢識別技術在自然人機交互中對時間和準確度要求較高的問題，提出一種新的手勢識別算法(IDTW-K)。該算法對經典動態時間規整(Dynamic Time Warping,DTW)算法進行了改進。利用節點在運動序列中的距離方差對各個節點進行權值動態分配，并對DTW的搜索路徑進行了詳細的分析，采用點和線相結合的范圍約束防止其搜索不合理以及優化DTW算法的計算速度，并結合KNN算法提高了手勢識別效率。通過實驗對IDTW-K算法、改進的DTW算法和傳統的DTW算法進行了對比，結果表明所提出的算法在精準度和識別速率上有一定的提高。

人機交互；特征提取；手勢識別；加權動態時間規整算法；K近鄰算法

0 引 言

近年來，由于計算機技術的發展，人機交互在實際生活中越來越重要[1]。人機交互也由傳統的輸入設備(如鼠標、鍵盤等)逐步向以語音、動作等智能的輸入設備發展。其中由于手勢具有簡單、靈活、易懂等優點，廣泛應用于動作識別的研究領域中。手勢識別作為一種智能的輸入設備具有廣泛的應用前景，例如智能家居、智能游戲以及先進的教育產品等。

國外學者對于手勢識別技術的研究起步較早。1983年，Grimes提出手勢識別并最早采用佩戴數據手套進行識別的方式。2011年，J.L.Raheja提出了利用Kinect跟蹤手指間和手掌中心的方法。G.F.He等在利用Kinect分割出手部區域后，使用Graham Scan算法進行各個手指的區分等等[2]。目前，研究較多的是隱馬爾可夫算法(HMM)[3]、神經網絡算法、支持向量機(SVM)和動態時間規則算法(DTW)[4]。DTW算法在分類長短不同的序列上有絕對優勢，這是前幾種算法不可代替的。Carmona等對DTW算法應用于手勢識別進行了研究，并強烈建議使用DTW算法代替HMM算法[4]。因此文中選用DTW算法進行手勢識別。

由于Kinect對于獲取人體相關的骨架節點信息有著簡單、方便的特性[5]，常被研究人體動作的研究者作為獲取特征信息的工具。文中則是用Kinect來獲取有關手勢的骨架節點信息。在DTW算法中，為了提高手勢識別的效率，考慮不同手勢中各關鍵節點運動的差異，根據不同的骨架節點在運動中的方差進行權值的動態分配。傳統DTW算法自身存在計算量和存儲空間比較大的缺點。針對這些缺點，對DTW算法的搜索路徑進行了線與點結合的約束，只計算可能遍歷到的節點數據，降低計算量，提高識別效率。若選取的測試樣本與訓練樣本的幀數相差很大或測試樣本與其他已知類別的訓練樣本最小歐氏距離相等時，誤差比較大，識別效率低。對此，文中結合DTW算法和KNN算法進行手勢識別，并對其進行實驗驗證。

1 手勢識別

手勢識別包括手勢分割、特征提取、手勢建模和手勢識別這幾個主要過程[6]。通過手勢識別的整個過程可以看出，對手勢進行識別的主要依據就是提取的特征參數，所有的手勢識別都是根據一定的特征參數來進行不同的分類。因此選擇一組好的特征參數對于手勢識別至關重要。

1.1 手勢特征提取

對相同樣本空間提取不同的特征參數進行識別，效果可能區別很大，因此特征參數的提取至關重要。由于每個人的高矮胖瘦不一或Kinect的擺放位置不同，對同一種手勢Kinect獲取的骨架節點的三維數據也不同[7]，針對該問題，提出利用球面坐標[8-9]的方法求各關節點到軀干關節點的距離和與此距離有關的兩個方位角度，作為節點的新信息。

圖1 球面坐標示例

如圖1所示，三維直角坐標系中的點p(x,y,z)對應球坐標中的序列為(γ,θ,φ)。其中，γ表示球面的點P到圓心O的距離；θ表示有向線段OP與Z軸正方向的夾角；φ表示P點映射在XOY面的點M與原點的有向線段OM與X軸正方向的夾角。文中選取軀干關節點作為球面的原點O，分別計算選取的關節點在球面坐標系中的表示。對Kinect獲得的骨架節點數據，通過上述歸一化處理后，避免了不同身高、胖瘦人體信息對實驗的影響。

在大部分的手勢識別中主要涉及到的關鍵節點有：左手，左手腕，左手肘，右手，右手腕，右手肘。文中通過Kinect獲取用戶骨骼框架的信息，從中提取實驗所需的這六個節點的數據并進行歸一化處理。手勢關鍵節點的數據集合為P={PLH,PLE,PLS,PRH,PRE,PRS}。

1.2 手勢識別算法

1.2.1 傳統動態時間規整算法

動態時間規整[10](Dynamic Time Warping，DTW)最初主要用于語音識別，解決同一句話不同人說出的時間長短不一的問題。在手勢識別中，針對同一種手勢，不同的人其完成時間不一樣[11]。然而隱馬爾可夫方法需要經過大量的訓練樣本進行訓練和數據統計，相對于簡單的手勢識別過于復雜；基于神經網絡[12]的方法，雖然具有很強的抗干擾性和較強的分類能力，但對手勢序列長度不一的情況處理能力明顯降低。因此，文中采用DTW算法進行手勢識別。

假設參考模板為R{R(1),R(2),…,R(M)}，測試模板為T{T(1),T(2),…,T(N)}。其中R(m)和T(n)分別表示參考模板和測試樣本的第m幀和第n幀的動作特征矢量，兩者間的維數是相同的，M不一定等于N。通過R,T之間的距離D[R,T]來衡量測試樣本和模板之間的相似度，d(R(m),T(n))表示任意兩幀之間的距離。DTW算法中訓練樣本和測試樣本在時間上是非線性映射的，這種映射關系表示為：(m1,n1),(m2,n2),…,(mf,nf)，則：

(1)

其中，D越小其相似度就越高，D越大則相似度就越低。

整個計算過程可以看成M*N的矩陣，T表示橫坐標，R表示縱坐標，計算量較大。根據Bellman最優原理：求D的最小值就是計算開始的節點(n0,m0)到終點(nf,mf)的最小路徑。其中(n,m)表示參考模板與測試樣本之間的交匯點。若起始點(n0,m0)表示為(0,0)，(n0,m0)的下一個節點(n1,m1)只有三種選擇，交匯點為(0,1),(1,0),(1,1)。求得這三個交匯點的代價d，代價最小的交匯點就是下一個節點。依次類推，直到找到最終的節點(nf,mf)為止。即

Dmin(nk,mk)=minDmin(nk-1,mk-1)+d(nk,mk)

(2)

其中，(nk-1,mk-1)是(nk,mk)的前一個節點。

最終通過比較測試樣本與各參考模板之間的D值來劃分屬于哪一類。

1.2.2 新動態時間規整算法

在手勢識別的過程中，不同的關節點在不同的手勢中所起到的作用不同。例如畫直線，手肘關節點基本是不動的，在使用右手做動作時左手基本保持靜止狀態。因此可以在計算時，針對不同的節點狀態分配不同的權值[13]，以提高手勢識別效率。

按照關節點的運動劇烈程度(關節點的運動方差[14]Si)進行權值分配。其中相鄰兩幀間第i個節點的歐氏距離為Disti(pn,pn-1)。考慮到提取的手勢分別為左、右手相關的三個節點，在用左手做動作時，右手相關的三個節點基本不動，故在分配權值時重點考慮前三個大小的方差。因此，規定后三個方差Si其閾值為Sa。權值分配公式如下所示：

(3)

其中，ωi表示節點i的權重；β的最佳值計算方法如下：

(4)

其中，SA(β)是所有訓練樣本的類間方差，SB(β)是所有訓練樣本的類內方差，則最優參數β的取值為：

β=argmax(R(β))

(5)

因此，訓練樣本和測試樣本的相鄰幀之間的距離d(R(m),T(n))為：

(6)

傳統DTW算法的計算量和存儲空間較大[15]，需要計算一個M*N矩陣。為了提高DTW算法的速度，可以減少所需要遍歷的點。通過上文對DTW算法的分析，測試樣本與參考模板在識別中尋找下一個節點時，其位置只有可能在三點上，如圖2所示。當前點若為(0,0)，則下一個點只可能是(0,1),(1,0),(1,1)中的一個。因此很多節點不需要參與計算，能減少很大的計算量。

然而，DTW算法對于測試樣本與兩個不同類別的訓練樣本的歐氏距離相同時，無法判斷測試樣本的類別[16]。例如，模板為R1{1,1,1,1,1,1,1,1,4,4}和R2{1,1,2,2,3,2,4,4}，測試樣本為T{1,2,3,4}，通過DTW算法計算得DTW(R1,T)=2，DTW(R2,T)=2。此時測試樣本與兩個模板的距離相同，不能識別手勢。根據R1與T的DTW匹配路徑，測試樣本T被“拉成”{1,1,1,1,1,1,2,3,4,4}來進行一一匹配。這樣的“拉伸”是不合理的，因此導致上述識別的失敗。

對此，文中提出用兩條斜線進行路徑搜索的約束，如圖2所示。在兩條斜線的約束范圍內搜索可能的節點，防止測試樣本被不合理的“拉伸”。在計算時結合這兩點特性進行DTW算法的路徑搜索，大大降低了計算量，在提高速率的同時也提高了效率。

圖2 DTW算法路徑約束示意圖

通過對DTW的改進，若出現同一類別的動作選擇的訓練樣本與測試樣本之間的時間相差較大，則計算出的歐氏距離較大，導致識別誤差增大。因此文中提出結合簡單的KNN算法進行綜合識別，提高了識別效率。

1.2.3 KNN分類器

KNN算法在分類算法中很常用，也比較簡單。它的核心思想是，若確定了近鄰樣本(靠近測試樣本的訓練樣本)數K的值，即在最小的范圍內找到K個訓練樣本，則訓練樣本數最多的這一類就是測試樣本的類別。

KNN算法基本步驟如下：

(1)算距離：給定測試樣本，計算測試樣本與每個參考樣本的距離；

(2)找近鄰：將步驟1中計算的距離從小到大進行有序排列，確定K的值；

(3)做分類：統計K個近鄰樣本的類別，找出樣本數最多的類別，即為測試樣本的類別。

圖3為KNN的工作原理示意圖。圓形標記為測試樣本，三角標記和方形標記分別表示兩種已知類別的樣本。當K=3時，測試樣本類別與三角標記樣本類別一致；當K=5時，測試樣本類別與方形標記樣本類別一致。

1.2.4 改進后的手勢識別算法

根據上文描述，文中提出一種新的算法即IDTW-K算法。該算法將改進的DTW算法與KNN算法相結合，通過計算測試樣本與各訓練樣本之間的可信度值確定測試樣本的類別。

圖3 KNN分類算法

設Ci代表類別，T代表測試樣本，Ri為近鄰中屬于Ci類的訓練樣本，K為近鄰的樣本總數，Ki為近鄰樣本屬于Ci類的樣本個數。L(Ci,T)為T對Ci的類別可信度，計算公式為：

(7)

手勢識別算法的步驟可歸納如下：

(1)分別計算測試樣本和參考模板中所有節點移動的方差；

(2)對求得的方差進行排序，后三個節點的方差設為固定值Sa，根據式(3)進行動態的權值分配；

(3)使用改進的DTW算法計算測試樣本與所有訓練樣本的歐氏距離；

(4)將步驟(1)中求得的歐氏距離從小到大進行有序排列，給定K值的大小，選擇前K個近鄰的訓練樣本，并標記這K個樣本的類別Ci，計算其所屬類別的個數Ki；

(6)比較Ci類的可信度大小。可信度最大的近鄰樣本的類別為測試樣本的類別，若所有類別的訓練樣本與測試樣本的可信度值都低于La,則判斷此動作為無效動作，從而達到識別不同手勢的效果。

2 實 驗

通過識別手勢的概率來衡量一個算法的好壞。文中通過識別左手和右手分別對向右畫箭頭、向左畫箭頭和畫圓這三個動作，對比傳統的DTW算法、改進后的DTW算法以及文中提出算法的識別效率和識別速度。

2.1 實驗過程

在VS2010環境下進行實驗，通過Kinect獲取人的骨架節點信息。實驗中選取20個同學，每個同學分別用左手和右手做了向左畫箭頭、向右畫箭頭和畫圓的六個動作進行5次重復操作，設置Kinect以1 s獲取20幀的速度對人的骨架節點進行捕獲。提取捕獲到的7個有用的骨架節點：左手、左手腕、左手肘、右手、右手腕、右手肘和人體的軀干節，然后根據提出的球面坐標原理進行標準化處理。計算測試樣本序列T{T(1),T(2),…,T(N)}中相鄰幀(以連續的3幀為相鄰幀)節點的方差Si，根據式(3)進行節點權值的分配。其中Sa的取值為方差有序序列的后三位的均值。

圖4所示為實驗過程中由彩色圖像獲得人的深度圖像，最后得到人體的骨架節點信息。

深度圖 骨骼圖 圖像

2.2 實驗結果

實驗中，給出對DTW算法在路徑約束的兩條直線斜率均為1，且到直線y=x的水平距離不大于4。對比三個有關DTW算法手勢識別的實驗結果，如表1所示。

表1 算法的正確率

普通的DTW算法的計算量較大，分類識別的效果不是特別理想，一般在分類識別時不會直接使用。文中對DTW算法的尋優路徑進行約束的同時考慮到分類識別中不同特征參數的重要性，對不同的特征參數進行權值分配來提高手勢識別的效率。表1證明了文中對DTW算法的改進是有效的。由于KNN算法比較簡單，易學易掌握，識別時間復雜度較小，但其自身識別效果不是很好。因此文中提出了結合KNN算法與改進DTW算法來提高手勢識別的效率，并證明了該想法是可行的。

在提高實驗效率的同時，對比三種算法的實驗速度。選擇右手向右畫箭頭、向左畫箭頭和畫圓這三個動作并進行識別時間的統計，計算其平均處理時間(單位：ms),如圖5所示。

圖5 耗時對比

從圖中可以看出，改進后的DTW算法比傳統的DTW算法在耗時上提高了30%～35%，而文中提出的算法比改進DTW算法的耗時有所增加，但幅度較小。

3 結束語

文中提出結合DTW算法和KNN算法進行綜合計算，從而識別測試樣本。同時，針對DTW算法自身計算量大這一缺點，提出對特征參數進行權值分配和搜索路徑進行約束的方法。實驗結果證明了該算法的有效性。

[1] 薛俊杰,陳健美.基于加權DTW手勢識別方法的研究與實現[J].信息技術,2015,39(11):125-129.

[2] 吳曉雨,楊 成,馮 琦.基于Kinect的手勢識別算法研究及應用[J].計算機應用與軟件,2015,32(7):173-176.

[3] 常亞南.基于HMM的動態手勢識別[D]．廣州：華南理工大學，2012．

[4] Carmona J M，Climent J．A performance evaluation of HMM and DTW for gesture recognition[M]//Progress in pattern recognition，image analysis，computer vision，and applications．Berlin:Springer，2012:236-243．

[5] 馮志全,蔣 彥.手勢識別研究綜述[J].濟南大學學報:自然科學版,2013,27(4):336-341.

[6] Zhang Zhengyou.Microsoft Kinect sensor and its effect[J].IEEE Multimedia,2012,19(2):4-10.

[7] 郭 雷.動態手勢識別技術綜述[J].軟件導刊,2015,14(7):8-10.

[8] 趙飛飛,劉喆頡,呂玉祥.基于Kinect骨骼信息的手勢識別[J].中國科技論文,2015,10(20):2412-2415.

[9] 吳彩芳,謝 鈞,俞 璐.基于骨骼和深度信息的手勢識別的研究與應用[J].計算機技術與發展,2016,26(8):200-204.

[10] 劉 陽,尚趙偉.基于Kinect骨架信息的交通警察手勢識別[J].計算機工程與應用,2015,51(3):157-161.

[11] 黃菲菲,曹江濤,姬曉飛.基于多通道信息融合的雙人交互動作識別算法[J].計算機技術與發展,2016,26(3):58-62.

[12] Chen Lingchen,Wang Feng,Deng Hui,et al.A survey on hand gesture recognition[C]//International conference on computer sciences & applications.Wuhan:IEEE,2013:313-316.

[13] Reyes M,Dominguez G,Escalera S.Feature weighting in dynamic time warping for gesture recognition in depth data[C]//IEEE international conference on computer vision workshops.[s.l.]:IEEE,2011:1182-1188.

[14] 汪成峰,陳 洪,張瑞萱,等.帶有關節權重的DTW動作識別算法研究[J].圖學學報,2016,37(4):537-544.

[15] Hussain S M A,Rashid H U.User independent hand gesture recognition by accelerated DTW[C]//International conference on informatics electronics&vision.[s.l.]:[s.n.],2012:1033-1037．

[16] 李 凱,王永雄,孫一品.一種改進的DTW動態手勢識別方法[J].小型微型計算機系統,2016,37(7):1600-1603.

ResearchandRealizationofDynamicalGestureRecognitionAlgorithmBasedonKinect

ZHANG Ying-ying1，GUO Xing2

(1.Key Laboratory of Intelligent Computing & Signal Processing of MoE,Anhui University,Hefei 230039,China;2.School of Computer Science and Technology,Anhui University,Hefei 230601,China)

With the development of computer technology and informatization,human-machine interaction is becoming more and more important in office and life.Due to the advantages of flexibility,intuition and simplicity for gesture, gesture recognition becomes a significant field in the study of human-machine interaction.According to the problem that gesture recognition has high requirements on time and accuracy in natural human-machine interaction,a new algorithm named IDTW-K is proposed with which the Dynamic Time Warping (DTW) is improved.It makes use of the variance of each node in the action sequence to distribute the weights and analyzes search path of DTW in detail,and then uses the range of constraints in combination of line and point to prevent its unreasonable search and optimize calculation speed of DTW,increasing efficiency of gesture recognition combining K-Nearest Neighbor (KNN).The experiments make a comparison of the IDTW-K,the improved DTW and the traditional DTW,which show that the proposed algorithm improves the accuracy and recognition efficiency.

human-machine interaction;feature extraction;gesture recognition;weighted dynamic time warping;K-nearest neighbors

TP301.6

A

1673-629X(2017)12-0011-05

10.3969/j.issn.1673-629X.2017.12.003

2016-11-11

2017-03-16 < class="emphasis_bold">網絡出版時間

時間：2017-08-01

國家科技支撐計劃(2015BAK24B01)

張瑩瑩(1991-)，女，碩士研究生，研究方向為模式識別；郭 星，博士研究生，講師，研究方向為模式識別、計算機視覺。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1551.036.html