基于關鍵幀和局部極值的手勢特征提取算法

劉楊俊武，程春玲

(南京郵電大學 計算機學院，江蘇 南京 210003)

0 引 言

動態手勢包含運動軌跡變化和結構變化等，準確的識別動態手勢需要研究動態手勢特征提取算法，用于表達手勢的運動軌跡特征和結構特征。根據提取的特征類型不同，目前的動態手勢特征提取算法主要分為基于圖像屬性的動態手勢特征提取算法和基于幾何結構的動態手勢特征提取算法。其中，基于圖像屬性的手勢特征提取算法是利用目標檢測算法提取出圖像的像素點分布情況來表達手勢，常用方法包括Hu矩[1]、梯度方向直方圖(histogram of oriented gradient，HOG)[2]、光流直方圖(histogram of optical flow，HOF)[3]等。這些算法計算較為簡便，且易于實現，但是提取出的特征維度較大，會增加手勢識別的計算量和計算時間。基于幾何結構的手勢特征提取算法是對圖像原始數據進行處理，提取出能夠反映手勢本質的結構信息，有利于區分手勢，提高手勢識別的準確性，主要方法包括結構特征點[4]、凸包[5]、k-曲率[6]等。但是該類算法的計算復雜度較高，計算時間較長。

為了縮短手勢特征提取的時間，Hasan等通過兩種半徑大小不同的動態圓模板區分出手勢的手掌區域和手指區域，然后根據各個區域中的動態圓模板分布確定手勢中的指尖、指根以及手掌中心的位置[7]。但是該算法易受到噪聲數據的干擾，識別準確性不穩定。Huang等提出一種基于套索的手勢特征提取算法，通過設置一個固定寬度的套索，并對手勢輪廓上的每個峰值點進行遍歷，若輪廓的寬度與套索的寬度相同，則認為該段為手勢的一個手指[8]。這種方法的不足是套索寬度的設置依賴人的先驗知識，可能造成誤差或者漏查手指的情況，導致手勢識別的準確性降低。文獻[9]提出一種基于凸包缺陷的動態手勢特征提取算法。該算法對于凸包中的每一個凸包缺陷，根據它的起始點、中心點、距離最遠點以及最遠點到凸包的距離四個特征之間的相互關系，判斷是否存在指尖點。但是該算法只能計算出指尖的個數，并不能獲取指尖點的位置信息，且易受到噪聲數據的干擾，對于相似的手勢類型識別正確率較差。文獻[10]認為傳統基于k-曲率的指尖特征提取算法會受到曲率較大的非指尖特征點的干擾，降低識別的準確性，因此提出一種改進算法，在篩選出曲率較大的候選指尖點集后，采用聚類算法將候選指尖點劃分成多個子集，并選擇每個子集中的中位點表示指尖位置。但是該算法需要依賴人為設置的曲率閾值，并且對候選指尖特征點集進行聚類過濾需要消耗較長的計算時間。

此外，還可以通過減少手勢特征提取的次數來縮短動態手勢特征提取的時間。文獻[11]提出一種基于關鍵幀的手勢特征提取算法，通過計算和比較相鄰幀手勢圖像的質心距離，選擇出距離大于閾值的手勢圖像進行特征提取。Tan等認為具有較小變化的手勢圖像能夠反映手勢序列的關鍵信息，因此提出通過計算相鄰幀手勢圖像之間像素點的變化個數，將像素點近似不變的手勢圖像作為關鍵幀[12]。雖然該類方法可以縮短特征提取的計算時間，但是關鍵幀選取閾值的設置會影響手勢識別的準確性和實時性，由于不同動態手勢的運動速率存在差異，很難確定合適的閾值。

因此，針對動態手勢特征提取算法計算時間較長的問題，文中提出一種基于關鍵幀和局部極值的動態手勢特征提取算法，并通過實驗對其進行驗證。

1 基于關鍵幀和局部極值的動態手勢特征提取算法

動態手勢特征提取算法可以看成是對一組手勢圖像采用靜態手勢特征提取算法進行手勢特征提取的過程，算法的計算時間取決于特征提取的次數和特征提取的計算量。為了縮短手勢特征提取過程的計算時間，文中算法的基本思想是從手勢視頻中選出具有較強區分能力的手勢圖像，并提取這些圖像中的質心特征和指尖特征，用于表達手勢的運動軌跡和外形結構。

在進行手勢特征提取之前，首先需要對獲取的手勢圖像進行手勢分割，獲取手勢的輪廓。由于膚色在HSV顏色空間中具有良好的聚類特性，采用文獻[13]提出的基于膚色的手勢分割算法，從手勢視頻的每一幀手勢圖像中分割出手勢區域，然后采用基于Canny算子的輪廓檢測算法得到手勢輪廓[14]。

1.1 基于運動方向和自適應閾值的關鍵幀手勢圖像選取算法

由于動態手勢運動軌跡中運動方向發生改變的手勢數據能夠充分描述該手勢的運動軌跡特征，對這些特征點進行提取可以提供區分手勢的重要信息。另一方面，均值能夠反映數據集中的一般變化程度，可以通過計算當前幀手勢圖像之前所有質心距離的均值，確定關鍵幀手勢圖像選取閾值的大小。因此，提出一種基于運動方向和自適應閾值的關鍵幀手勢圖像選取算法。

首先計算出相鄰幀手勢圖像之間的相對運動方向，相對運動方向通過質心之間的偏移角度θt確定，根據θt將手勢運動劃分成八個不同方向，其計算公式如下：

dirt=

(1)

其中，dirt為第t幀手勢圖像的方向碼值。

若dirt≠dirt-1，說明動態手勢的運動方向發生改變，則將當前幀手勢圖像作為一個關鍵幀手勢圖像進行特征提取。否則表示動態手勢的運動方向沒有發生改變，通過計算相鄰幀手勢圖像的質心距離，將距離大于閾值的手勢圖像作為關鍵幀。

由于動態手勢具有不同的運動速率，為了降低人為設置閾值參數對手勢特征提取準確性的影響，關鍵幀手勢圖像選取閾值的大小應根據手勢運動軌跡的變化程度動態調整。其基本思路是在每次比較相鄰幀手勢圖像之間的質心距離后，根據式(2)和式(3)計算出當前幀手勢圖像之前所有質心距離的平均值，作為新的關鍵幀手勢圖像選取閾值。

(2)

dist(t1,t2)=|gt1-gt2|

(3)

其中，δt表示第t幀的關鍵幀手勢圖像選取閾值；dist(t1,t2)表示第t1幀和第t2幀手勢圖像之間的質心距離。

基于運動方向和自適應閾值的關鍵幀手勢圖像選取算法偽代碼描述如下：

算法1：KeyFrameSelect(It)

輸入：手勢圖像It

輸出：關鍵幀手勢圖像標記iskeyframet

1.iskeyframet←1;//初始化關鍵幀手勢圖像標記

2.calculategt;//計算質心

3.calculate dirtusing Eq.(1);//計算運動方向

4.if(dirt==dirt-1) //判斷運動方向是否相同

5.calculate dist(t,t-1)using Eq.(3);//計算質心距離

6.if(dist(t,t-1)<δt-1)//判斷質心距離是否小于閾值

7.iskeyframet←0;//若質心距離小于閾值則將標記置0

8.end if;

9.end if;

10.calculateδtusing Eq.(2);//更新閾值

11.return iskeyframet;

1.2 基于局部極值的指尖特征提取算法

手勢指尖特征能夠反映手勢的結構特性，通過指尖特征的比較，可以區分具有相同運動軌跡但結構不同的動態手勢。由于指尖處在手指的尖部，若將手指輪廓看作是一個光滑曲線，則指尖點就是該曲線上的局部極值點。因此，可以通過尋找手勢輪廓上的局部極值點，確定手勢中存在的指尖特征。

由于手勢輪廓是一個連續的、多凹凸的曲線，很難構造出準確的函數表達式f來描述手勢輪廓，因此無法通過求導的方式來確定曲線上的局部極值點。考慮到一根手指的指尖點與手勢質心的距離應大于該手指上其他輪廓點與質心的距離，可以通過構造距離函數，確定手勢中存在的指尖特征點。

定義1(手勢指尖點)：設第t幀手勢圖像輪廓點集為cst={ct,1,ct,2,…,ct,Nt}，Nt為cst中輪廓點的個數。若存在一個ε>0，使得所有滿足|ct,λ-ct,*|<ε的ct,λ，都有dist(ct,λ,gt)≤dist(ct,*,gt)，則ct,*為一個手勢指尖點。其中dist(ct,λ,gt)為距離函數，其表達式為：

(4)

其中，ct,λ=(xt,λ,yt,λ)為輪廓點ct,λ的坐標；gt=(xt,yt)為第t幀手勢圖像的質心坐標。

手勢輪廓并非是一條理想的平滑曲線，輪廓上存在許多凹凸不平的點，僅通過距離計算與比較容易產生許多噪聲特征點，降低指尖特征提取的準確性。此外，參數ε是影響指尖特征提取準確性的關鍵因素，若ε設置過大，則可能造成指尖特征點的丟失，相反則會產生許多噪聲特征點。由于手勢輪廓的凸包曲線是由手勢最外層的輪廓點連接起來形成的凸多邊形，手勢的指尖特征必定處在手勢的凸包曲線上，因此，可以利用手勢的凸包曲線對得到的指尖特征點集進行過濾，只有滿足手勢指尖點的定義同時也處在凸包曲線上的特征點才認為是指尖特征點。

基于局部極值的指尖特征提取算法首先在手勢輪廓上按順序進行遍歷，當某個輪廓點與質心的距離大于下一個輪廓點與質心的距離時，判斷該點是否滿足手勢指尖點的定義，若滿足，則認為該點為一個類指尖特征點；然后去除類指尖特征點集上所有在手勢朝向上位置低于質心的特征點；最后計算手勢的凸包，若類指尖點也處在手勢的凸包曲線上，則認為該點為指尖特征點。

基于局部極值的指尖特征提取算法偽代碼描述如下：

算法2：FingertipExtract(It)

輸入：手勢圖像It

輸出：手勢指尖特征vt

1.max_dist←0;count←0;//初始化

2.cst←findcontours(It);//獲取手勢輪廓點集

3.hull←ConvexHull(It);//計算凸包

4.gt←CentroidCaculate(cst);//計算質心

5.forλ←0 to cst.length

6.calculate dist(cst,λ,gt) using Eq.(4);//計算與質心之間的距離

7.if(max_dist

8.max_dist=dist(cst,λ,gt);

9.fingertip←cst,λ;

10.count←0;

11.continue;

12.end if;

13.count←count+1;

14.if(count>ε&&fingertip.y>gt.y&&Exist(hull,fingertip))//過濾類指尖特征點

15.add fingertip tovt;//將fingertip添加到vt中

16.end if;

17.end for;

1.3 算法描述和時間復雜度分析

KFLE算法包括兩個步驟：

(1)關鍵幀手勢圖像選取。首先計算當前幀手勢圖像的運動方向，若運動方向與前一幀手勢圖像的運動方向不同，則將該幀手勢圖像作為關鍵幀。否則計算相鄰幀手勢圖像之間的質心距離，將距離大于閾值的手勢圖像作為關鍵幀。同時計算當前幀之前所有質心距離的平均值，更新閾值；

(2)指尖檢測和提取。將滿足手勢指尖點定義同時處在手勢凸包曲線上的輪廓點作為指尖特征點。

KFLE算法的偽代碼描述如下：

算法3：KFLE

輸入:手勢圖像序列IInput={I1,I2,…,IN}

輸出:手勢特征向量VOutput={v1,v2,…,vM}

1.for eachItinIInput

2.isKeyFramet←KeyFrameSelect(It);//關鍵幀手勢圖像選取

3.if(isKeyFramet==0)//判斷是否為關鍵幀手勢圖像

4.continue;

5.end if;

6.vt←FingertipExtract(It);//獲取手勢指尖特征

7.addvttoVOutput;//將vt添加到VOutput中

8.end for;

KFLE算法的時間復雜度為O(tn)，其中t為進行手勢特征提取的次數，最壞情況下，t為動態手勢序列的長度；由于在手勢特征提取的過程中，需要對每個輪廓點進行計算，因此，基于局部極值的指尖特征提取算法的時間復雜度為O(n)，n為手勢輪廓點集的長度。表1比較了三種動態手勢特征提取算法的時間復雜度。可以看出，KFLE算法具有較低的時間復雜度，可以縮短手勢特征提取的時間。

表1 三種動態手勢特征提取算法的時間復雜度

2 實驗結果與分析

2.1 實驗環境及參數設置

參照文獻[15]的實驗，文中共定義了十種動態手勢類型，分別為單指向右、單指向下、二指向左、二指向上、三指向上、三指向右、四指向下、四指畫圓、五指畫圓、五指向左。每種手勢類型由五名實驗者各做2次，共得到100組動態手勢視頻。

與文獻[9]提出的基于凸包缺陷的手勢特征提取算法(簡稱為“CHD算法”)和文獻[10]提出的基于改進k-曲率的手勢特征提取算法(簡稱為“IKC”算法)進行對比。首先分析KFLE算法中關鍵參數數值的不同大小對手勢特征提取準確性的影響，從而設置合適的關鍵參數數值。然后分別從手勢特征提取處理時間和手勢識別正確率兩個方面評估各手勢特征提取算法的性能。

實驗的軟硬件環境為：CPU：Intel(R) Core(TM) i5-4 210 M CPU@2.60 GHz；內存：8.00 GB；OS：Windows 8 Enterprise Professional 64 bit；攝像頭：Integrated Camera；編程語言：C++；開發環境：OpenCV和Visual Studio 2013。

2.2 KFLE算法中關鍵參數的設置

KFLE算法中的參數為范圍閾值ε，ε的設置對指尖特征提取準確性具有較大的影響，參數設置過大或過小，都可能降低手勢識別的準確性。為了分析和確定合適的ε，文中在相同的系統配置和實驗環境下，首先為每個測試樣本構造標準手勢模板集，即運動軌跡相同，指尖個數分別為1～5，共五種動態手勢類型；然后提取出在不同ε下的手勢特征向量，特征向量包括每個關鍵幀手勢圖像的質心坐標和手勢的指尖個數；最后采用動態時間彎曲(dynamic time warping，DTW)算法進行手勢識別，并計算不同ε下的手勢識別正確率，如圖1所示。

圖1 不同參數數值下的識別正確率

從圖1可以看出，當范圍閾值參數ε為10～30時，識別準確率較高，這是因為此時ε值能夠在不丟失特征點的前提下，減少噪聲特征點的出現。當ε設置過小時，可能會將凸包曲線上的其他數據點也作為指尖特征點進行提取，生成噪聲特征點，降低手勢識別的準確性。而當ε值設置過大時，可能造成即使是指尖點也很難滿足手勢指尖點的定義，導致指尖特征點的丟失。因此，ε的大小應選擇在[10,30]范圍內，文中實驗設置ε=30。

2.3 手勢特征提取時間的比較

在相同的系統配置和實驗環境下，針對同一組動態手勢視頻，分別采用不同的動態手勢特征提取算法進行特征提取，通過計算特征提取前后的時間差得到算法對該手勢視頻的特征提取時間，最后計算出每種算法對每種動態手勢類型的平均特征提取時間，如圖2所示。

圖2 三種動態手勢特征提取算法的平均特征提取時間

從圖2中可以明顯看出，與CHD算法和IKC算法相比，KFLE算法的平均特征提取時間分別降低了44.3%和71.9%。這是因為CHD算法和IKC算法需要對每一幀手勢特性進行特征提取，而KFLE算法通過比較手勢圖像之間的運動方向和質心距離，僅對運動方向或距離發生明顯改變的手勢圖像進行特征提取，減少了特征提取的次數。此外，在手勢特征提取過程中，KFLE算法通過距離計算和凸包過濾，尋找手勢輪廓曲線上的局部極值點，得到手勢的指尖特征，降低了特征提取的時間復雜度，從而縮短了整個動態手勢特征提取的時間。

2.4 手勢識別正確率的比較

將不同的手勢特征提取算法提取出的特征向量采用DTW算法進行手勢識別。實驗采用留一交叉驗證法，分別從每種手勢類型的樣本集中隨機選擇一組作為手勢模板，將剩下的手勢樣本作為測試樣本，對每種動態手勢類型共進行100次測試，計算每種手勢類型的識別正確率，如表2所示。

表2 各算法對不同手勢類型的識別正確率

從表2可以看出，CHD算法的識別正確率明顯低于IKC算法和KFLE算法，這是因為CHD算法通過比較手勢中每個凸包缺陷的特征量之間的相互關系來判斷是否存在指尖點，易受到噪聲數據的干擾，因此識別正確率較低。而KFLE算法和IKC算法是通過對手勢輪廓點的遍歷和計算獲得指尖點的位置信息，能夠區分相似的手勢類型，因此具有較高的識別正確率。

3 結束語

為了縮短動態手勢特征提取的時間，提出一種基于關鍵幀和局部極值的動態手勢特征提取算法。首先提出一種基于運動方向和自適應閾值的關鍵幀手勢圖像選取算法，通過比較相鄰幀手勢圖像之間的運動方向和質心距離，選擇運動方向或距離發生明顯改變的手勢圖像進行特征提取。在對手勢圖像進行指尖特征提取的過程中，提出一種基于局部極值的指尖特征提取算法，通過構造距離函數并結合凸包過濾，尋找手勢輪廓曲線上的局部極值點，確定手勢中存在的指尖特征。

該手勢特征提取算法對手勢交互的環境具有較高的要求，在復雜背景和光照效果較差的環境下，會降低手勢特征提取的準確性。因此，下一步將對在復雜環境下的手勢特征提取算法進行研究，增加算法的實用性和健壯性。

[1] LIU Y,YIN Y,ZHANG S.Hand gesture recognition based on HU moments in interaction of virtual reality[C]//Proceedings of 2012 4th international conference on intelligent human-machine systems and cybernetics.Washington,DC,USA:IEEE Computer Society,2012:145-148.

[2] LIN J,DING Y.A temporal hand gesture recognition system based on hog and motion trajectory[J].International Journal for Light and Electron Optics,2013,124(24):6795-6798.

[4] 張墨逸,張秋余,蘆俊池,等.基于結構特征點的手勢建模與高層特征提取[J].華中科技大學學報:自然科學版,2015,43(10):87-91.

[5] NAGARAJAN S,SUBASHINI T S,RAMALINGAM V.Vision based real time finger counter for hand gesture recognition[J].International Journal of Technology,2012,2(2):1-5.

[6] 馮志全,楊 波,鄭艷偉,等.基于特征點分布分析的手勢

特征檢測方法[J].計算機集成制造系統,2011,17(11):2333-2342.

[7] HASAN M M,MISHRA P K,MISHRA P K.Real time fingers and palm locating using dynamic circle templates[J].International Journal of Computer Applications,2012,41(6):33-34.

[8] HUANG H,JU Z,LIU H.Real-time hand gesture feature extraction using depth data[C]//2014 international conference on machine learning and cybernetics.[s.l.]:IEEE,2014:206-213.

[9] GANAPATHYRAJU S. Hand gesture recognition using convexity hull defects to control an industrial robot[C]//2013 3rd international conference on instrumentation control and automation.[s.l.]:IEEE,2013:63-67.

[10] 李博男,林 凡.基于曲率的指尖檢測方法[J].南京航空航天大學學報,2012,44(4):587-591.

[11] PATHAK B,JALAL A S,AGRAWAL S C,et al.A framework for dynamic hand gesture recognition using key frames extraction[C]//2015 fifth national conference on computer vision,pattern recognition,image processing and graphics.[s.l.]:IEEE,2015:1-4.

[12] TAN W,WU C,ZHAO S,et al.Dynamic hand gesture recognition using motion trajectories and key frames[C]//2010 2nd international conference on advanced computer control.[s.l.]:IEEE,2010:163-167.

[13] 曹昕燕,趙繼印,李 敏.基于膚色和運動檢測技術的單目視覺手勢分割[J].湖南大學學報:自然科學版,2011,38(1):78-83.

[14] 王小俊,劉旭敏,關 永.基于改進Canny算子的圖像邊緣檢測算法[J].計算機工程,2012,38(14):196-198.

[15] 王西穎,戴國忠,張習文,等.基于HMM-FNN模型的復雜動態手勢識別[J].軟件學報,2008,19(9):2302-2312.