溫俊芹 王修暉

(1.浙江經(jīng)濟職業(yè)技術(shù)學(xué)院數(shù)字信息技術(shù)學(xué)院，杭州，310018; 2.中國計量大學(xué)信息工程學(xué)院，杭州，310018)

基于線性判別分析和自適應(yīng)K近鄰法的手勢識別

溫俊芹1王修暉2

(1.浙江經(jīng)濟職業(yè)技術(shù)學(xué)院數(shù)字信息技術(shù)學(xué)院，杭州，310018; 2.中國計量大學(xué)信息工程學(xué)院，杭州，310018)

基于小容量數(shù)據(jù)集的手勢識別是人機交互技術(shù)研究中的一個重要課題。本文提出了一種基于線性判別分析和自適應(yīng)K近鄰法的手勢識別方法。首先,應(yīng)用高斯背景建模方法從包含目標交互者的訓(xùn)練視頻集中提取各類手型圖像,并調(diào)整到相同尺度來構(gòu)建手勢訓(xùn)練集。然后,通過改進的線性判別分析對訓(xùn)練數(shù)據(jù)進行特征提取。最后提出一種自適應(yīng)K近鄰法對實時交互過程中得到的手型信息進行分類和識別。應(yīng)用上述方法自建小型手勢庫進行實驗和比較分析,結(jié)果顯示與現(xiàn)有的手勢識別算法相比，本文方法具有更高的識別率。

線性判別分析;手勢識別;自適應(yīng)K近鄰法;人機交互

引 言

手勢交互是一種更加自然的非接觸式人機交互方式，它通過將人手的各種姿態(tài)作為控制語義輸入到計算機中實現(xiàn)對特定目標或者場景的控制。手勢是通過人手的連續(xù)動作產(chǎn)生的各種狀態(tài)或者狀態(tài)的組合，通常包括靜態(tài)的手勢和動態(tài)的手勢(泛指一組靜態(tài)手勢的組合)[1]。隨著高級人機交互技術(shù)的廣泛應(yīng)用，如何實現(xiàn)更加自然的人機交互成為相關(guān)領(lǐng)域的關(guān)注焦點，包括人體姿態(tài)識別、手勢識別、步態(tài)識別以及自然語言識別等[2]。其中手勢識別作為一種非接觸式的關(guān)鍵輸入技術(shù)，在機器人、虛擬現(xiàn)實游戲和工業(yè)控制等領(lǐng)域應(yīng)用廣泛。根據(jù)傳感器類型不同，現(xiàn)有關(guān)于手勢識別的研究成果大致可以分為基于物理傳感器和基于視頻兩類方法?；谖锢韨鞲衅鞯氖謩葑R別方法包括使用數(shù)據(jù)手套檢測手指變化情況的方法[3]和通過在手指關(guān)節(jié)佩戴感應(yīng)裝置來判斷手指狀態(tài)的方法[4]。這類方法的一個共同點是依賴于交互者手上佩戴的某種機械或者電子感知設(shè)備，在很大程度上影響了用戶的方便性。此外，由于感知裝置本身靈敏度對人手尺度的固有敏感性和裝置的易磨損性，進一步限制了該類手勢識別方法的使用空間?；谝曨l的手勢識別主要通過計算機視覺和模式識別技術(shù)對交互者手部輪廓進行建模和特征提取，從而抽象出不同的交互語義。文獻[5]提出了一種簡單的骨骼模型來描述人的手部特征。在此基礎(chǔ)上，融合遺傳算法中迭代優(yōu)選的思想,實現(xiàn)當(dāng)前交互者的手型輪廓與模式庫中手形輪廓的匹配。文獻[6]提出了一種靜態(tài)的手勢辨識方法,該方法利用手勢空間分布特征來提升手勢辨識的正確率，但是該方法難以解決遮擋帶來的問題。文獻[7]提出了一種使用SVM作為分類器的手勢識別方法。文獻[8]提出了一種基于無線信號的手勢識別系統(tǒng)，該系統(tǒng)提供基于家庭的手勢識別解決方案?？傊? 基于視頻的手勢識別和交互技術(shù)能夠?qū)崿F(xiàn)更加自然的非接觸式交互。同時手勢正確識別率也有所提高。但是由于人手非剛體的本質(zhì), 手勢識別在誤判率和識別效率等方面都存在很大的困難。為了解決當(dāng)前基于視頻的手勢識別方法難以滿足實時交互要求的難題, 本文在文獻[5]基礎(chǔ)上，設(shè)計了一種無模型的手勢識別解決方案。該方案分為離線手勢分類器訓(xùn)練和實時手勢識別兩個步驟。在離線處理階段，應(yīng)用高斯背景建模方法從包含目標交互者的訓(xùn)練視頻集中提取各類手型圖像來建立訓(xùn)練集，并通過改進的線性判別分析對訓(xùn)練數(shù)據(jù)進行特征提取和壓縮。在實時手勢識別階段, 采用一種自適應(yīng)K近鄰法(Adaptive K-nearest neighbor,A-KNN)對實時交互過程中得到的手型信息進行分類和識別。

1 手勢分類器訓(xùn)練

1.1 手型圖像提取和歸一化

手型圖像提取主要研究如何從連續(xù)的手勢交互圖像中分離出完整的手型部分。本文根據(jù)實際交互中的運動連續(xù)性、人體膚色特征以及腕部環(huán)狀標識信息, 使用漸進性方法完成手型部分的分割[5]。然后，對得到的各種手型模板進行旋轉(zhuǎn)和尺寸歸一化(全部展開的手指中分線朝上；尺寸200像素×220像素)。本文選取了18種差異較大的靜態(tài)手勢建立訓(xùn)練集，圖1顯示了18種手勢之一的“兩手指分開伸展手勢”歸一化處理后得到的10個模板。

圖1 兩手指分開伸展手勢的歸一化模板Fig.1 Normalized templates for hand gesture with two-finger separate extension

1.2 基于改進LDA算法的手勢分類器訓(xùn)練

J(φ)=φTSbφ/φTSwφ

(1)

(2)

(3)

SbW=λSw

(4)

式中：λ為拉格朗日因子；Sw可能奇異，此時式(4)無法直接求解。針對小樣本手勢樣本庫的特點，使用類似文獻[9-11]的思路對LDA算法進行改進，并使用改進后算法來訓(xùn)練手勢分類器。改進算法的基本思想是在Sw內(nèi)求解1個線性變換矩陣，使得在Sw上Sb最大，從而將LDA求解問題轉(zhuǎn)換為一個最優(yōu)化問題，則

M=argmax(MTSbM)

(5)

使得MTSwM=0，M∈RD。式(5)已經(jīng)在文獻[9]中進行了收斂性證明，并給出了具體解決方法，這里不在贅述。

2 基于自適應(yīng)KNN算法的手勢識別

(6)

判決條件為

(7)

訓(xùn)練樣本數(shù)量較少時，KNN算法的誤判率對距離度量方法比較敏感。A-KNN算法使用的歐氏距離為

(8)

式中：x=[x1,x2,…,xn]T；y=[y1,y2,…,yn]T；n為輸入特征的維數(shù)。對應(yīng)的置信度函數(shù)為

(9)

本文提出的A-KNN算法流程如下：

(1) 數(shù)據(jù)預(yù)處理，使用與離線處理階段類似的方法將待分類手勢樣本x從輸入視頻流中分割出來，并調(diào)整尺寸大小實現(xiàn)歸一化。

(2) 獲得自適應(yīng)k值，設(shè)定k初始值為0.5×N,N為訓(xùn)練集容量。

(3) 創(chuàng)建一個長度為k的隊列保存最相似的訓(xùn)練樣本集，并按照式(8)定義的距離從大到小排序。首先從訓(xùn)練樣本集中隨機地選擇k個樣本構(gòu)成最相似的訓(xùn)練樣本集，然后計算這些樣本與待分類樣本之間的距離，并將對應(yīng)序號存入隊列。

(4) 依次計算訓(xùn)練集中所有個體與未知手勢樣本的距離d，并將其與隊列中的最大距離D比較：如果d≥D，則舍棄該樣本集；如果d

(5) 完成遍歷之后，統(tǒng)計隊列中多數(shù)樣本所屬的分類，并將其作為標準測試集的類別。

(6) 計算測試結(jié)果的置信度，然后選取k值繼續(xù)訓(xùn)練。最終取置信度最大的k值作為輸出。

3 算法性能實驗

3.1 手勢識別測試系統(tǒng)實現(xiàn)

在多臺投影儀拼接實現(xiàn)的大屏幕環(huán)境下，搭建了一個沉浸式手勢識別系統(tǒng)來測試本文提出算法的性能。該系統(tǒng)的運行包括手勢分類器訓(xùn)練和手勢識別兩個階段，如圖2所示。其中手勢輪廓提取和手部運動目標跟蹤雖然是該系統(tǒng)的重要模塊之一，相關(guān)內(nèi)容已經(jīng)在相關(guān)工作[5]中進行了詳細描述，不屬于本文研究內(nèi)容，這里不再詳述。從圖2可以看出，該系統(tǒng)的輸入包括訓(xùn)練圖像序列和手部實時運動視頻兩類，其中訓(xùn)練圖像序列用于訓(xùn)練離線階段的手勢分類器，而實時視頻則用于測試手勢識別算法。在離線的預(yù)處理階段，輸入的訓(xùn)練圖像序列包含當(dāng)前交互者的不同手勢。因此，在對手勢分類器進行訓(xùn)練前，需要先提取手勢輪廓。本文實驗采用了高斯混合背景建模方法建立手勢模型，根據(jù)人體膚色、手指和手掌的基本關(guān)系等進行手勢輪廓檢測，并進行圖像分割和尺度調(diào)整，建立規(guī)格化的手勢訓(xùn)練集。在手勢分類器訓(xùn)練過程中，采用本文提出的改進線性判別分析方法提取手勢特征并進行降維操作，以提高分類器訓(xùn)練的效率。實時手勢識別階段包括以下幾個處理過程：(1)手部運動目標跟蹤。與離線階段的手勢輪廓提取不同，實時視頻流中的背景比較復(fù)雜。為了方便下一步進行輪廓提取，需要從來自于監(jiān)控攝像頭的實時視頻數(shù)據(jù)中檢測出交互者的手部，并實現(xiàn)可靠的跟蹤。(2)手勢輪廓提取。這一步與離線處理階段的手勢輪廓提取類似，需要采用混合高斯模型建模和膚色檢測方法檢測出手部的位置并調(diào)整到統(tǒng)一的規(guī)格。但是該階段的手部移動更加顯著，為了提高手勢識別的效率，需要利用運動的連貫性。(3)手勢識別。該步驟使用本文提出的A-KNN算法，利用訓(xùn)練好的手勢分類器，對步驟2提取的手勢輪廓數(shù)據(jù)進行實時分類，從而實現(xiàn)手勢識別。在該手勢識別系統(tǒng)中，離線階段完成計算相對復(fù)雜的手勢分類器訓(xùn)練，能夠較好地提高手勢識別的實時性；同時，手勢識別中采用A-KNN算法，相比采用固定k值的KNN算法，較大幅度地提高了識別率。

圖2 手勢識別測試系統(tǒng)Fig.2 Hand gesture recognition system

3.2 實驗結(jié)果與分析

圖3 本文識別方案與數(shù)據(jù)手套識別方案的比較Fig.3 Comparison between proposed method and data glove scheme

本文設(shè)計了兩個實驗，分別將本文算法與通過手機、手套硬件實現(xiàn)的手勢識別方法，基于序貫相似檢測算法(Sequential similarity detection algorithm,SSDA)的識別算法和基于自適應(yīng)遺傳算法的識別算法[5]進行了比較，并對結(jié)果進行了分析。測試中的用例為對虛擬常見中的物體進行“選中”、“移動”和“旋轉(zhuǎn)”等3種基本操作。實驗中所用的數(shù)據(jù)手套采用了5DT Data虛擬現(xiàn)實體感手套，每個節(jié)點14個傳感器。用于視頻采集的攝像頭采用了巨峰科技的高清網(wǎng)絡(luò)攝像頭，焦距為6 mm，清晰度1 080 P。測試系統(tǒng)的運行環(huán)境為HP Pro 3380 MT(4GB RAM，I5-3470 CPU)。實驗1比較了本文提出的手勢識別方法和基于硬件傳感器實現(xiàn)的手勢識別方法，實驗結(jié)果如圖3所示。實驗中“選中”、“移動”和“旋轉(zhuǎn)”3種測試用例各執(zhí)行了200次?？梢钥闯鼋柚布鞲衅鲗崿F(xiàn)的手勢識別方法的誤判率比本文方法高, 尤其是對“平移”和“旋轉(zhuǎn)”測試用例中一些相互差異較小的手勢。這主要由硬件手勢識別裝置中的傳感器對不同人手部尺度的依賴性和機電裝置內(nèi)在感應(yīng)度局限性造成。另一方面，從交互的自然和諧方面來說，本文的手勢識別方案無需交互者穿戴特殊裝置，更符合人類日常習(xí)慣。然而盡管本文手勢識別算法的平均識別速度已經(jīng)能夠滿足一般的實時交互需求，但是在整體識別速度方面，仍然無法和硬件實現(xiàn)方法相比擬，因此這里只比較誤判率。實驗2比較了本文手勢識別算法與其他兩種手勢識別算法，結(jié)果如圖4，5所示。實驗過程中，3種測試用例(“選中”、“移動”和“旋轉(zhuǎn)”)各執(zhí)行了200次。其中的KNN算法，其前期處理仍然采用改進的LDA算法，在手勢識別中采用了KNN算法。圖4的結(jié)果顯示，在誤判率方面本文算法顯著優(yōu)于基于SSDA的方法和基于自適應(yīng)遺傳算法的手勢識別方法[5]，在一些存在區(qū)分度較小手勢的組合操作中差別更加明顯；與傳統(tǒng)的KNN算法比較也有明顯的提高。這是由于本文提出的基于自適應(yīng)KNN的手勢識別算法自適應(yīng)選擇置信度最高的K值，降低了傳統(tǒng)KNN算法由于K值偏大或者偏小造成的識別精度損失。此外在平均辨識速度[5]方面，本文提出的方法與SSDA算法和同樣采用改進LDA進行前期處理的KNN算法類似，但是和文獻[5]相比有了較大改善。

圖4 本文手勢識別算法與其他手勢識別算法誤判率比較Fig.4 Comparison of proposed method and other recognition algorithms in misjudgment rate

圖5 本文手勢識別算法與其他手勢識別算法平均識別時間比較Fig.5 Comparison of proposed method and other recognition algorithms in average recognition time

4 結(jié)束語

手勢識別的正確率和識別速度是評價一個手勢識別算法的主要標準，但是通常情況下手勢識別率和識別速度是難以兼顧的。如何在提高手勢識別率的同時，改善識別速度是提升手勢識別算法實用性的關(guān)鍵。本文提出一種基于小容量手勢集的視頻手勢分類和識別方法。該方法通過在離線階段實現(xiàn)復(fù)雜度較高的手勢分類器訓(xùn)練，并在實時手勢識別中采用A-KNN算法提高手勢識別率。實驗結(jié)果顯示, 本文提出的算法在很大程度上提高了實時手勢識別的正確率，并改善了交互階段的識別效率。

[1] Kirishima T, Sato K, Chihara K. Real-time gesture recognition by learning and selective control of visual interest points[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):351-364.

[2] Gonzalez-Sanchez T, Puig D. Real-time body gesture recognition using depth camera[J]. Electronics Letters,2011,47(12):697-698.

[3] 李琪,白英彩,曾芬芳.一個虛擬手原型的實現(xiàn)[J].上海交通大學(xué)學(xué)報,2009,33(11):1377-1380.

Li Qi, Bai Yingcai, Zeng Fenfang. Implementation of a virtual hand prototype[J]. Journal of Shanghai Jiaotong University,2009,33(11):1377-1380.

[4] Haritaoglu I, Harwood D, Davis L S. W4: Real-time surveillance of people and their activities[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):809-830.

[5] 王修暉，鮑虎軍. 基于自適應(yīng)遺傳算法的手勢識別[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報,2007,19(8):1056-1063.

Wang Xiuhui, Bao Hujun. Gesture recognition based on adaptive genetic algorithm[J]. Journal of Computer-Aided Design & Computer Graphics,2007,19(8):1056-1062.

[6] 楊波,宋曉娜,馮志全,等.復(fù)雜背景下基于空間分布特征的手勢識別算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2010,22(10):1841-1848.

Yang Bo, Song Xiaona, Feng Zhiquan, et al. Gesture recognition in complex background based on distribution features of hand[J].Journal of Computer-Aided Design & Computer Graphics,2010,22(10):1841-1848.

[7] Wu Chihhung, Chen Weilun, Lin Changhong. Depth-based hand gesture recognition[J]. Multimedia Tools and Applications,2016,75(12):7065-7086.

[8] Pu Qifan, Gupta S, Gollakota S. Shwetak patel: Gesture recognition using wireless signals[J]. ACM GetMobile,2015,18(4):15-18.

[9] Zhang Ya, Chen Weiyuan, Zha Hongyuan, et al. A time-topic coupled LDA model for IPTV user behaviors[J]. IEEE Transactions on Broadcasting,2015,61(1):56-65.

[10]Yang Feng, Mao K Z, Lee G K K, et al. Emphasizing minority class in LDA for feature subset selection on high-dimensional small-sized problems[J]. IEEE Transactions on Knowledge and Data Engineering,2015,27(1):88-101.

[11]劉紹毓,周杰,李弼程，等.基于多分類SVM-KNN的實體關(guān)系抽取方法[J].數(shù)據(jù)采集與處理,2015,30(1):202-210.

Liu Shaoyu, Zhou Jie, Li Bicheng, et al. Entity relation extraction method based on multi-SVM-KNN classifier[J].Journal of Data Acquisition and Processing,2015,30(1):202-210.

Gesture recognition based on small samples is one of the main trends in the advanced human-computer interaction research. A novel gesture recognition method based on adaptive K-nearest neighbor (A-KNN) and linear discriminant analysis (LDA) is presented. First, hand-shape images are segmented from the given interaction videos, and scaled to the same size to construct the training set. Then an optimized LDA algorithm is designed to extract gesture features. Finally, an improved KNN algorithm is introduced with adaptiveKvalue to classify the real-time gesture information. Test results show that the correct recognition rate of the proposed approach is higher than most existing methods.

linear discriminant analysis (LDA); hand gesture recognition; adaptive K-nearest neighbor; human computer interaction

國家自然科學(xué)基金(61303146)資助項目。

2015-06-05；

2015-06-30

TP301

A

溫俊芹(1977-),女,副教授,研究方向:數(shù)字圖像處理、模式識別, E-mail:wenjunqin@zjtie.edu.cn。

王修暉(1978-),男,博士，副教授,研究方向:計算機圖形學(xué)、計算機視覺和模式識別。

Hand Gesture Recognition with Linear Discriminant Analysis and Adaptive K-Nearest Neighbor Algorithms

Wen Junqin1, Wang Xiuhui2

(1.Digital Information Technology Institute, Zhejiang Technical Institute of Economics, Hangzhou, 310018, China; 2.School of Information Engineering, China Jiliang University, Hangzhou, 310018, China)