基于改進(jìn)KNN算法的動(dòng)態(tài)手勢(shì)識(shí)別研究

陳嘉偉，韓 晶，郝瑞玲，胡 迪

(1. 中北大學(xué) 機(jī)電工程學(xué)院，山西 太原 030051； 2. 中國(guó)人民解放軍32382部隊(duì)，北京 100072)

0 引 言

手勢(shì)是最常用到的交流和操控方式，在日常生活中作用很大. 隨著傳感器技術(shù)的發(fā)展，手勢(shì)識(shí)別成為了可能. 近年來(lái)，越來(lái)越多的研究者將微型傳感器應(yīng)用于人體動(dòng)作的識(shí)別[1]，人們通過(guò)手勢(shì)傳感器獲取手部動(dòng)作數(shù)據(jù)，達(dá)到了人機(jī)交互的目的.

一直以來(lái)，手勢(shì)識(shí)別的算法都是人們研究的重點(diǎn). Mantyjarvi[2]提出了一種利用小波變換的計(jì)算機(jī)視覺(jué)人體動(dòng)作識(shí)別的方法. 徐賢[3]等應(yīng)用傳統(tǒng)K最近鄰(KNN: K-Nearest Neighbor)算法和電容式傳感器實(shí)現(xiàn)了手勢(shì)識(shí)別，相比普通的閾值識(shí)別方式，有效提高了識(shí)別成功率； 呂蕾[4]等利用數(shù)據(jù)手套實(shí)現(xiàn)了靜態(tài)手勢(shì)識(shí)別方法，通過(guò)靜態(tài)手勢(shì)特征以及相應(yīng)的手勢(shì)特征點(diǎn)集的提取來(lái)實(shí)現(xiàn)手勢(shì)識(shí)別； 孫榮宗[5]等提出了一種基于粗糙集的KNN算法，將粗糙集與傳統(tǒng)KNN算法結(jié)合，有效提高了KNN算法的識(shí)別效率. Xu Ruize[6]等通過(guò)定義多個(gè)手勢(shì)信號(hào)的特征值并對(duì)其符號(hào)進(jìn)行編碼，結(jié)合Hopfield算法實(shí)現(xiàn)了手勢(shì)識(shí)別. 本文結(jié)合上述研究，提出一種改進(jìn)的KNN算法來(lái)對(duì)ADXL335傳感器的手勢(shì)動(dòng)作識(shí)別，改進(jìn)KNN算法對(duì)手勢(shì)動(dòng)作信號(hào)中提取的特征量進(jìn)行編碼，并將KNN算法的訓(xùn)練組數(shù)據(jù)進(jìn)行了優(yōu)化處理，從而提高手勢(shì)識(shí)別結(jié)果的準(zhǔn)確率，為了驗(yàn)證試驗(yàn)效果，本文在LabVIEW平臺(tái)設(shè)計(jì)了一款體感俄羅斯方塊[7]游戲.

1 算法原理

1.1 傳統(tǒng)KNN算法

KNN算法[8]是目前常用的一種數(shù)據(jù)挖掘算法，廣泛用于數(shù)據(jù)分析、 圖像處理、 文本分類(lèi)等領(lǐng)域[9-10]. KNN算法的基本思想是： 給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，選定一個(gè)適當(dāng)?shù)木嚯x機(jī)制，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例， 這K個(gè)實(shí)例的多數(shù)屬于某個(gè)類(lèi)，就把該輸入實(shí)例分類(lèi)到此類(lèi)中.

KNN算法步驟：

1) 處理數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行降噪處理；

2) 輸入已分類(lèi)的訓(xùn)練組向量以及測(cè)試組向量數(shù)據(jù)；

3) 根據(jù)距離機(jī)制計(jì)算訓(xùn)練組與測(cè)試組間的距離，多數(shù)采用歐式距離；

(1)

式中：Di,Dj分別為測(cè)試組向量與訓(xùn)練組向量；di,dj分別為測(cè)試組向量與訓(xùn)練組向量中的元素.

4) 根據(jù)計(jì)算出的距離大小，在訓(xùn)練組中選出K個(gè)與測(cè)試組數(shù)據(jù)Di距離最小的訓(xùn)練組數(shù)據(jù)，計(jì)算出測(cè)試組數(shù)據(jù)Di屬于每個(gè)分類(lèi)的權(quán)重Y，Di屬于分類(lèi)Xl的權(quán)重公式為

(2)

其中

(3)

5) 輸出訓(xùn)練樣本中權(quán)重最大的樣本所屬的分類(lèi)標(biāo)簽.

傳統(tǒng)KNN算法的不足[11]之處是當(dāng)測(cè)試組分類(lèi)不均衡時(shí)，會(huì)導(dǎo)致分類(lèi)出的結(jié)果誤差較大； 當(dāng)傳統(tǒng)KNN算法面對(duì)大樣本數(shù)據(jù)集時(shí)，計(jì)算成本消耗較大.

1.2 改進(jìn)KNN算法

在手勢(shì)識(shí)別過(guò)程中，如果需要識(shí)別的手勢(shì)數(shù)量較多，將會(huì)導(dǎo)致傳統(tǒng)的KNN算法訓(xùn)練組數(shù)據(jù)過(guò)于龐大，從而影響識(shí)別效率. 改進(jìn)KNN算法對(duì)手勢(shì)識(shí)別中需要識(shí)別的手勢(shì)進(jìn)行特征提取，根據(jù)提取的特征值對(duì)手勢(shì)進(jìn)行編碼，使得每個(gè)手勢(shì)都有唯一的編碼，這樣有效減少了訓(xùn)練組的數(shù)據(jù)量，進(jìn)而提高了手勢(shì)識(shí)別的成功率. 目前，對(duì)于特征提取沒(méi)有固定的規(guī)則，應(yīng)用在動(dòng)作識(shí)別中的特征主要有靜態(tài)特征，動(dòng)態(tài)特征以及時(shí)空特征[12]. 為了保證手勢(shì)識(shí)別的準(zhǔn)確，優(yōu)化KNN算法中手勢(shì)特征的選擇應(yīng)保證同類(lèi)的特征量較為穩(wěn)定且不同類(lèi)的特征量的差異明顯大于同類(lèi)特征量[13]. 靜態(tài)特征可以更好地反映出動(dòng)作細(xì)節(jié)，因此本文對(duì)手勢(shì)信號(hào)進(jìn)行靜態(tài)特征提取，加速度傳感器采集到的信號(hào)為三維信號(hào)，可以將采集到的信號(hào)看作三維空間的向量從而方便特征提取，分別采集手勢(shì)動(dòng)作各軸向的幅值、 向量歸一化值以及距原點(diǎn)的距離.

加速度傳感器的信號(hào)經(jīng)濾波器處理后較為穩(wěn)定，記手背向上時(shí)的動(dòng)作為初始動(dòng)作，采集到的加速度信號(hào)為

GA=(xa,ya,za).

(4)

手掌右翻，左翻以及上抬時(shí)采集到的加速度信號(hào)為

Gi=(xi,yi,zi),i=1,2,3.

(5)

基于加速度傳感器手勢(shì)靜態(tài)特征量提取的公式為

1)手勢(shì)動(dòng)作的幅值

GAGi=(ki,li,mi)=(xa-xi,ya-yi,za-zi),

i=1,2,3,

(6)

式中：k,l,m為做出手勢(shì)動(dòng)作后傳感器產(chǎn)生的三軸信號(hào)的幅值.

2) 向量歸一化

(7)

式中：Y代表輸出的歸一化向量；X代表長(zhǎng)度為的向量.

(8)

(9)

式中：xi是X的第i個(gè)元素.

3) 距原點(diǎn)距離差

(10)

根據(jù)改進(jìn)KNN算法特征量提取方法，圖1 手勢(shì)信號(hào)所提出的特征量為

T1=(0.01,-0.18,0.16,1.32,-1.10,

-0.22,-1.25).

(11)

為了對(duì)提出的特征量進(jìn)一步簡(jiǎn)化，分別檢查提取特征量的符號(hào)，并將其儲(chǔ)存為手勢(shì)代碼，若特征量的數(shù)值小于0.1，則將該特征量簡(jiǎn)化為0. 因此，圖1 手勢(shì)信號(hào)所提出的符號(hào)序列代碼為

M1=(0,-1,1,1,-1,-1,-1).

(12)

改進(jìn)KNN算法手勢(shì)特征量的提取大大減少了數(shù)據(jù)量，從而降低了算法的復(fù)雜程度. 圖1 手勢(shì)信號(hào)的符號(hào)序列的提取如圖2 所示.

圖1 隨機(jī)手勢(shì)信號(hào)Fig.1 Random gesture signal

圖2 隨機(jī)手勢(shì)信號(hào)特征量Fig.2 Characteristic quantities of random gesture signals

2 手勢(shì)識(shí)別系統(tǒng)

2.1 手勢(shì)操作俄羅斯方塊

在LabVIEW平臺(tái)搭建的手勢(shì)操作俄羅斯方塊系統(tǒng)中，利用ADXL335三軸加速度傳感器實(shí)時(shí)采集動(dòng)態(tài)手勢(shì)信號(hào)，再通過(guò)美國(guó)國(guó)家儀器NI公司的USB-6002數(shù)據(jù)采集卡將信號(hào)輸入LabVIEW程序中. 信號(hào)將在程序中經(jīng)過(guò)二階貝塞爾濾波器處理后，利用改進(jìn)KNN算法對(duì)手勢(shì)進(jìn)行識(shí)別，從而對(duì)游戲進(jìn)行手勢(shì)操作. 系統(tǒng)框圖如圖3 所示.

圖3 系統(tǒng)框圖Fig.3 System block diagram

2.2 手勢(shì)識(shí)別流程

手勢(shì)識(shí)別實(shí)驗(yàn)流程如圖4 所示. 在手勢(shì)識(shí)別實(shí)驗(yàn)開(kāi)始后，測(cè)試組數(shù)據(jù)將會(huì)以與訓(xùn)練組相同的方式進(jìn)行手勢(shì)特征量的提取.

圖4 手勢(shì)識(shí)別實(shí)驗(yàn)流程Fig.4 Experimental flow of gesture recognition

2.3 手勢(shì)定義

本文設(shè)計(jì)的是一款體感俄羅斯方塊游戲，根據(jù)該游戲的基本原理[14]，需要對(duì)下落的模型進(jìn)行右移，左移以及旋轉(zhuǎn)三種控制操作，本文采用手掌右翻，左翻以及上抬三種手勢(shì)動(dòng)作與這三種操作對(duì)應(yīng)，圖5(a)中為手勢(shì)的初始狀態(tài)； (b)為右翻手勢(shì)； (c)為左翻手勢(shì)； (d)為上抬手勢(shì). 每次游戲控制都是從手勢(shì)初始狀態(tài)開(kāi)始，完成控制操作后返回手勢(shì)初始狀態(tài).

3 實(shí)驗(yàn)驗(yàn)證

本文對(duì)操作者在坐姿和站姿兩種情況下的手腕部右翻、 左翻、 上翻三種動(dòng)作進(jìn)行識(shí)別，實(shí)驗(yàn)中，實(shí)驗(yàn)人員對(duì)三種動(dòng)態(tài)手勢(shì)各做 100次，觀察閾值判別法與改進(jìn)KNN算法的識(shí)別成功率.

3.1 閾值判別法

閾值判別法作為一種簡(jiǎn)單直觀的判別方法，常被用于傳感器信號(hào)識(shí)別中. 在本文的手勢(shì)識(shí)別中，以手腕右翻為例，實(shí)驗(yàn)者做出100次右翻動(dòng)作以確定閾值，X軸信號(hào)如圖6 所示，采集到右翻手勢(shì)的三軸信號(hào)初始值、 峰峰值均值及閾值如表1 所示.

圖6 峰峰值的分布Fig.6 Distribution of peak-to-peak values

表1 右翻動(dòng)態(tài)手勢(shì)參數(shù)

經(jīng)過(guò)計(jì)算，右翻動(dòng)作X軸信號(hào)峰峰值均值為

EXi=μ=1.601.

(13)

方差為

DXi=σ2=0.039.

(14)

根據(jù)本文選取閾值的方法，右翻手勢(shì)X軸的峰峰值滿(mǎn)足中心極限定理

(15)

右翻手勢(shì)X軸的閾值為

Fi=μ-1.96σ=1.526(V).

(16)

3.2 改進(jìn)KNN算法

根據(jù)改進(jìn)KNN算法的特征量提取方法，實(shí)驗(yàn)開(kāi)始前，令實(shí)驗(yàn)者多次做出三種手勢(shì)動(dòng)作，將三種手勢(shì)信號(hào)進(jìn)行特征量提取并對(duì)符號(hào)序列編碼記錄，結(jié)果如表2 所示.

表2 訓(xùn)練組手勢(shì)編碼

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

實(shí)驗(yàn)中，實(shí)驗(yàn)者將傳感器穿戴好后隨機(jī)做出三個(gè)手勢(shì)動(dòng)作各50次，記錄兩種算法的識(shí)別成功率.

本文采用識(shí)別成功率M衡量手勢(shì)識(shí)別結(jié)果的準(zhǔn)確率.

(17)

式中：Na為手勢(shì)識(shí)別正確結(jié)果的個(gè)數(shù)；N為手勢(shì)動(dòng)作的總次數(shù).

兩種識(shí)別方法的識(shí)別結(jié)果如表3 所示.

表3 改進(jìn)KNN算法識(shí)別成功率對(duì)比

由識(shí)別結(jié)果可以看出，改進(jìn)KNN算法在手勢(shì)識(shí)別成功率上有一定的提升，約為10%. 閾值判別法在前30次的動(dòng)態(tài)手勢(shì)識(shí)別率較高，在后70次的動(dòng)態(tài)手勢(shì)識(shí)別中識(shí)別成功率明顯下降，主要原因是在實(shí)驗(yàn)過(guò)程中，人手的疲勞導(dǎo)致做出的動(dòng)態(tài)手勢(shì)動(dòng)作不標(biāo)準(zhǔn)，并且在動(dòng)作過(guò)程中細(xì)微的動(dòng)作也會(huì)對(duì)閾值判別法的識(shí)別造成干擾. 相比閾值判別法，改進(jìn)KNN算法在動(dòng)態(tài)手勢(shì)識(shí)別當(dāng)中不易受操作者自身的影響，并且能保證較高的識(shí)別成功率.

將改進(jìn)KNN算法與傳統(tǒng)KNN算法相比較，100次隨機(jī)手勢(shì)的識(shí)別成功率如表4 所示.

表4 傳統(tǒng)KNN算法與改進(jìn)KNN算法識(shí)別結(jié)果對(duì)比

與傳統(tǒng)KNN算法相比，改進(jìn)KNN算法的識(shí)別成功率提升在5%左右，主要原因在于傳統(tǒng)KNN算法的訓(xùn)練組數(shù)據(jù)量過(guò)于龐大，而且K值的選取會(huì)影響傳統(tǒng)KNN算法的識(shí)別結(jié)果. 而本文的改進(jìn)KNN算法，不但訓(xùn)練樣本較少而且選取K=1即可保證識(shí)別率.

4 結(jié) 論

本文利用傳統(tǒng)KNN算法易實(shí)現(xiàn)且無(wú)需估計(jì)參數(shù)的特點(diǎn)，提出了一種優(yōu)化KNN手勢(shì)識(shí)別算法，實(shí)現(xiàn)了對(duì)三種手勢(shì)動(dòng)作的識(shí)別，實(shí)驗(yàn)結(jié)果證明，在LabVIEW平臺(tái)搭建的ADXL335體感游戲中，相比閾值判別法，改進(jìn)KNN算法可以有效提高手勢(shì)識(shí)別成功率. 考慮到動(dòng)態(tài)手勢(shì)種類(lèi)眾多，未來(lái)的研究中將會(huì)在保證識(shí)別率的情況下進(jìn)行更多動(dòng)態(tài)手勢(shì)的識(shí)別.