基于改進(jìn)凸包算法的手勢定位

摘 "要： 文中主要介紹了手勢分割、手勢輪廓、手勢凸包、凸包缺陷、指尖定位與手勢跟蹤，并基于此架構(gòu)實現(xiàn)對鍵盤鼠標(biāo)的模擬。將圖像由RGB模型轉(zhuǎn)化為HSV模型后，再通過HSV利用膚色閾值對人手進(jìn)行分割，從而獲得手勢輪廓凸包。通過三角形原理計算出指尖與凸包缺陷，解決了手勢水平狀態(tài)下凸包缺陷無法定位的問題。采用單目視覺下的手勢跟蹤算法進(jìn)行指尖定位初始化跟蹤目標(biāo)，實現(xiàn)無監(jiān)督的Camshift實時手勢跟蹤。實驗結(jié)果表明，在光照良好的條件下，對鍵盤模擬的準(zhǔn)確率高達(dá)90%以上。

關(guān)鍵詞： 指尖定位； 手勢跟蹤； 鍵鼠模擬； 凸包缺陷； 單目視覺； 幀差法； 色彩模型； 圖像增強(qiáng)

中圖分類號： TN911.7?34； TP391.4 " " " " " " " " " " 文獻(xiàn)標(biāo)識碼： A " " " " " " " 文章編號： 1004?373X（2024）15?0081?05

Gesture positioning based on improved convex hull algorithm

GUO Jinpeng1， HAN Changlin2， LU Zhou2， SHAO Yang3

（1. Zhejiang Uniview Technologies Co.， Ltd.， Hangzhou 310051， China; 2. Anhui Open University， Hefei 230022， China;

3. Guangdong University of Technology， Guangzhou 510006， China）

Abstract： In this paper， the gesture segmentation， gesture contour， gesture convex hull， convex hull defect， fingertip positioning and gesture tracking are introduced mainly， and the simulation of keyboard and mouse is realized based on this architecture. The image is transformed from RGB model to HSV （hue， saturation， value） model， and then the skin color threshold is used to segment the hand according to HSV， so as to obtain the convex hull of gesture contour. In this paper， the number of the fingertips and the convex hull defects is calculated by principle of triangle， which solves the problem that convex hull defects fail to be positioned in the horizontal state of gesture. The gesture tracking algorithm with monocular vision is used to perform fingertip positioning initialization object tracking in order to realize unsupervised Camshift real?time gesture tracking. The experimental results show that the accuracy rate of keyboard simulation is over 90% under the conditions of good lighting.

Keywords： fingertip positioning; gesture tracking; simulation of keyboard and mouse; convex hull defect; monocular vision; frame difference method; color model; image enhancement

0 "引 "言

基于視覺的手勢識別的人機(jī)交互關(guān)鍵技術(shù)[1]，從過程上看，包括數(shù)據(jù)采集、手勢檢測、手勢分割、匹配和識別等；從方法上，通常是對手勢進(jìn)行RGB預(yù)處理，再使用模型匹配實現(xiàn)手勢識別。這類方法存在很多問題，如在預(yù)處理階段，手勢分割效果不好，由于手勢的角度等問題，識別率不高。在進(jìn)行手勢識別的過程中，有兩個重要環(huán)節(jié)：一是要明確采集的數(shù)據(jù)中是否包含手；二是運(yùn)用圖像處理的方法提取出手部區(qū)域。

基于膚色的手部檢測方法是手勢識別中常用的一類方法[2]。膚色的基本特點(diǎn)有：第一，與背景存在色彩差異性；第二，膚色具備較好的魯棒性，即旋轉(zhuǎn)不變性，可以克服一定的移動角度等影響[3]。但是同樣會受到人種、相近膚色背景等影響，從而影響手勢識別的準(zhǔn)確性。

針對上述問題，在RGB的基礎(chǔ)上，本文采用HSV色彩分量對圖像進(jìn)行處理，以增強(qiáng)不同光照條件下膚色檢測的魯棒性。在進(jìn)行手勢分割時，本文提出改進(jìn)的凸包算法對手勢輪廓進(jìn)行提取，提高指尖定位的準(zhǔn)確度。對動態(tài)手勢的跟蹤，本文采用Camshift進(jìn)行實時跟蹤[4]，將獲取到的指尖定位作為手勢跟蹤算法的搜索窗口初始值，實現(xiàn)無監(jiān)督初始化跟蹤，同時提高了跟蹤的準(zhǔn)確率。結(jié)合改進(jìn)的算法，本文設(shè)計并實現(xiàn)了計算機(jī)的鍵盤和鼠標(biāo)功能模擬系統(tǒng)。

1 "手部分割

1.1 "建立色彩模型

本文利用HSV（Hue， Saturation， Value）色彩模型的H（色調(diào)）分量來進(jìn)行膚色區(qū)域檢測[5]，其中S（飽和度）與V（明度）分量取經(jīng)驗值。HSV色彩空間采用近似人眼視覺的認(rèn)知表示，用色調(diào)、飽和度和明度三個相關(guān)性較弱的分量來表示顏色。因此，在膚色分割階段可以由RGB色彩空間轉(zhuǎn)化為HSV色彩空間，如圖1所示。

HSV色彩空間

這里[H]、[S]、[V]的值可由式（1）得到：

[H=6+G-BMAX-MIN×60°， " "R=MAXS=2+B-RMAX-MIN×60°， " "G=MAX V=4+R-GMAX-MIN×60°， " "B=MAX] （1）

色調(diào)（H）的值為0.0°～360.0°，飽和度（S）和明度（V）的值為0.0～1.0，再轉(zhuǎn)換成0～100%。

如果MAX = MIN，則[H]=0°，沒有色彩，灰色。超過360°取360°除余值。

如果MAX=0，[S]=0，沒有色彩。

如果[V]=0，即沒有亮度，純黑色。

當(dāng)獲取到HSV色彩空間后，分離成三個灰度空間，如圖2所示，然后進(jìn)行閾值分割，則可獲取到所需的二值圖像。

1.2 "圖像增強(qiáng)

采用圖像增強(qiáng)技術(shù)減少圖像內(nèi)的干擾元素。在本文中使用的圖像增強(qiáng)是開運(yùn)算，目的是消除二值化后不連通的散點(diǎn)，同時填充手部中的缺失點(diǎn)，從而達(dá)到較好的圖像效果[6]，如圖3所示。

1.3 "輪廓與凸包查找

在完成圖像增強(qiáng)的過程后，可以開始進(jìn)行輪廓與凸包的查找[7]，之所以把凸包與輪廓查找放一起操作主要是為了從輪廓組成的矩陣中尋找凸包。一個輪廓一般對應(yīng)一系列的點(diǎn)，也就是圖像中的一條曲線，是通過順序找出邊緣點(diǎn)來跟蹤邊界的。若圖像是二值圖像或圖像中不同區(qū)域具有不同的像素值，但每個區(qū)域內(nèi)的像素值是相同的，則可通過基于4連通或8連通區(qū)域進(jìn)行輪廓查找。對獲取到的二值圖像查找閉合邊界的輪廓跟蹤算法為：首先按從上到下、從左到右的順序搜索，找到的第一個黑點(diǎn)或白點(diǎn)一定是最左上方的邊界點(diǎn)，記為[A]；它的右、右下、下、左下（或者左、左下、下、右下）4個鄰點(diǎn)中至少有一個是邊界點(diǎn)，記為[B]；從[B]開始找起，按順時針（逆時針）的順序找相鄰點(diǎn)中的邊界點(diǎn)[C]。如果[C]就是[A]點(diǎn)，則表明已經(jīng)轉(zhuǎn)了一圈，結(jié)束；否則從[C]點(diǎn)繼續(xù)找，直到找到[A]為止。

在獲取唯一的輪廓后便可以開始著手凸包查找的工作。通常來說，計算凸包與凸包缺陷是作為另一種理解物體形狀或輪廓的方法。很多復(fù)雜特性的物體都能用這種方法表現(xiàn)出來。

從點(diǎn)集的角度來說，凸包是指一個最小凸多邊形，滿足一個點(diǎn)集中的所有點(diǎn)在多邊形邊上或者內(nèi)部，如圖4所示，線段圍成的多邊形就是點(diǎn)集[{p0，p1，p2，…，p12}]的凸包。同理擴(kuò)展到平面上。

本文凸包的求解方法是GrahamScan方法[8?9]。首先，找到所有點(diǎn)中最左邊的（[y]坐標(biāo)最小的），如果[y]坐標(biāo)相同，找[x]坐標(biāo)最小的；以這個點(diǎn)為基準(zhǔn)求所有點(diǎn)的極角（arctan2（[y-y0]，[x-x0]）），并按照極角對這些點(diǎn)排序，前述基準(zhǔn)點(diǎn)在最前面，設(shè)這些點(diǎn)為[P[0]～P[n-1]]；建立一個棧，初始時[P[0]]、[P[1]]、[P[2]]進(jìn)棧，對于[P[3]]，[P[4]]，[…]，[P[n-1]]的每個點(diǎn)，若棧頂?shù)膬蓚€點(diǎn)與它不構(gòu)成“向左轉(zhuǎn)”的關(guān)系，則將棧頂?shù)狞c(diǎn)出棧，直至沒有點(diǎn)需要出棧以后將當(dāng)前點(diǎn)進(jìn)棧；所有點(diǎn)處理完之后棧中保存的點(diǎn)就是凸包了，如圖5所示。

1.4 "凸包缺陷與指尖定位

如圖6凸包缺陷所示即可說明，手掌周圍的線描繪出的是凸包，[A]至[E]則為凸包間各個“缺陷”，稱為“凸包缺陷”。

考慮到手勢動作的幅度不大，本文對凸包缺陷計算的函數(shù)是基于極小值點(diǎn)，即通過式（2）找出凸包點(diǎn)間的各點(diǎn)坐標(biāo)與其所對應(yīng)前后坐標(biāo)點(diǎn)間的相對位置來做出的判斷，找到基于相鄰兩個凸包點(diǎn)間的極小值點(diǎn)。

[f（x0）≥f（x1） "and "f（x0）≥f（x2） ] （2）

式中：[f（x0）]為當(dāng)前垂直方向像素點(diǎn)坐標(biāo)值；[f（x1）]與[f（x2）]分別為其前驅(qū)坐標(biāo)值與后繼坐標(biāo)值，代碼中選擇的前驅(qū)后繼跨度為3個像素點(diǎn)，目的是防止像素點(diǎn)間構(gòu)成線條的布局影響。

該算法有個缺陷，當(dāng)手呈水平狀態(tài)時，則無法準(zhǔn)確定位到其中某個凸包缺陷點(diǎn)。因此，本文提出另一種解決方案。由于在三角形內(nèi)部過任意角做一條穿過對邊的線所圍成的三角形的三邊和沒有原三角形三邊大的原理。由圖7可知，[AB+ACgt;BD+DC]，所以解決方案可基于此原理通過公式（3）獲取相鄰?fù)拱c(diǎn)間輪廓點(diǎn)至兩點(diǎn)間歐幾里德距離和最大值點(diǎn)，相對于前一種，該算法效果更精確。

[ACB=（Cx-Ax）2+（Cy-Ay）2+（Cx-Bx）2+（Cy-By）2MAX=MAX， "ABC≤MAXABC， "ABCgt;MAX]

（3）

式中：[ACB]為相鄰?fù)拱聊繕?biāo)歐氏距離之和；[C]為目標(biāo)像素點(diǎn)坐標(biāo)；[A]、[B]為相鄰?fù)拱c(diǎn)[A]與點(diǎn)[B]。目標(biāo)點(diǎn)[C]從[A]點(diǎn)出發(fā)，當(dāng)[ABC]gt;MAX時則賦值為[ABC]，如此直至[C]點(diǎn)到達(dá)[B]點(diǎn)，最終獲取的MAX點(diǎn)則為所需的凸包缺陷點(diǎn)。

此方法求出的并非全是指尖間的凸包缺陷，有時會包含手掌或手腕的兩側(cè)（如圖8所示），可以通過向量夾角公式（4）去除該兩點(diǎn)。

[px=Ax-Cx， " py=Ay-Cy，qx=Bx-Cx， " qy=By-Cycosθ=px×qx+py×qyp2x+p2y×q2x+q2y] （4）

式中：[px]與[qx]分別表示從[C]點(diǎn)出發(fā)指向[A]點(diǎn)與[B]點(diǎn)的向量，如此便可由向量夾角公式得出[cosθ]，定義當(dāng)[cosθlt;0]時則該點(diǎn)去除。

在獲取凸包后，由于指尖部位并不是只有一個凸包點(diǎn)，因此需要除去多余的指尖點(diǎn)。此時需要用到凸包缺陷點(diǎn)，通過凸包缺陷點(diǎn)在兩指尖之間這一特性，查找同時符合相鄰點(diǎn)之間有凸包缺陷點(diǎn)和距凸包缺陷點(diǎn)的距離超過自定的閾值這兩個條件，如圖9所示。

繪制指尖點(diǎn)與凸包缺陷點(diǎn)，如圖10所示。

2 "手部跟蹤

在Camshift跟蹤算法中，需要事先選定感興趣區(qū)域，一般來說，觸發(fā)一條鼠標(biāo)事件來選取跟蹤范圍，但這屬于有監(jiān)督性的[10]。這里需要對算法做進(jìn)一步改進(jìn)，使之可以無監(jiān)督選取感興趣的區(qū)域。本文主要通過指尖定位來獲取該區(qū)域，即在達(dá)到指尖定位的功能后，分別選取指尖坐標(biāo)[x]、[y]值組成一個坐標(biāo)作為左上角點(diǎn)，寬度和高度取水平垂直最長距離的最小值。[A]點(diǎn)與[B]點(diǎn)則分別為指尖的左上角點(diǎn)[A（x，y）]與右下角點(diǎn)[B（x，y）]，再對兩點(diǎn)進(jìn)行差值運(yùn)算，通過公式[MINAx-Bx，Ay-By]計算得出跨度大小。即[rg?]gt;[dist=MIN（（Maxx?rg?gt;x）]，[（Maxy?rg?gt;y））]；其中Max[x]、Max[y]分別取坐標(biāo)[x]、[y]最大值，rg?gt;[x]、rg?gt;[y]分別取坐標(biāo)[x]、[y]最小值。于是便可以得到一個左上角為（rg?gt;[x]，rg?gt;[y]）、長度為rg?gt;dist的矩形作為初始跟蹤區(qū)域。

3 "模擬鍵鼠算法設(shè)計

在手勢跟蹤與指尖定位問題解決之后，模擬簡單鍵鼠工作就相對容易很多[11?13]?？梢圆捎脦罘▉碛嬎阒讣庾鴺?biāo)與跟蹤重心的移動向量，跟蹤面積的變化與指尖和凸包缺陷的數(shù)量，做一個簡單的判斷。

1） 鍵盤模擬

鍵盤模擬用到的參數(shù)為跟蹤重心與跟蹤面積，首先通過幀差法計算出重心移動向量與面積變化向量。在模擬方向鍵的計算中，本文用事先定義的時間來計算出移動的速度，當(dāng)超過該速度則判斷方向按鍵。由于垂直方向比水平方向做功多，所以默認(rèn)垂直方向鍵的優(yōu)先級較高?？崭竦膬?yōu)先級是最低的，判斷其按鍵時，本文將變化后的面積與上一幀的面積進(jìn)行對比，如果變化后的面積小于上一面積的[35]，則判定激活空格鍵。

2） 鼠標(biāo)模擬

同鍵盤模擬一樣，先用幀差法計算出指尖的移動向量與指尖、凸包缺陷點(diǎn)的個數(shù)。然后通過事先定義的時間計算出移動的速度，當(dāng)超過該速度則判斷移動的向量，再賦值給當(dāng)前鼠標(biāo)的坐標(biāo)。凸包缺陷的個數(shù)是為了判定是否進(jìn)行鼠標(biāo)的移動與是否進(jìn)行鼠標(biāo)單擊。

4 "實現(xiàn)結(jié)果分析

4.1 "鍵盤和鼠標(biāo)模擬實驗效果

實現(xiàn)電腦上模擬鍵盤的上下左右與空格鍵操作一些程序（如圖片瀏覽器、視頻播放器、俄羅斯方塊等），圖片瀏覽器實驗效果如圖11a）所示。實現(xiàn)電腦上模擬鼠標(biāo)的移動、單擊與拖動的功能，如圖11b）所示。

4.2 "精確度測試

測試包括指尖與凸包缺陷定位，鍵盤模擬與鼠標(biāo)模擬的精確性。測試前，對環(huán)境進(jìn)行了調(diào)整，使其背景環(huán)境與光照環(huán)境可與以上手勢與背景有明顯的區(qū)別，如圖12所示。表1是各種操作的準(zhǔn)確率。

同時，對鼠標(biāo)移動模擬進(jìn)行測試，即給定一個坐標(biāo)點(diǎn)，通過手勢運(yùn)動模擬鼠標(biāo)移動，根據(jù)鼠標(biāo)停止的位置與固定坐標(biāo)點(diǎn)的像素差，判斷移動的差異。如圖13所示，本文進(jìn)行了50次測試，測試的像素差如[y]軸所示。50次測試的像素平均差是5像素，可以滿足鼠標(biāo)移動需求。

5 "結(jié) "語

本文提出改進(jìn)的凸包算法，即通過三角形原理計算出指尖與凸包缺陷，解決了手勢水平狀態(tài)下凸包缺陷無法定位的問題，并應(yīng)用在基于手勢的鍵盤鼠標(biāo)模擬交互中。運(yùn)用Camshift算法來對手部進(jìn)行跟蹤，Camshift算法有很好的實時性。為達(dá)到自動定位跟蹤，對Camshift算法使用指尖定位進(jìn)行了無監(jiān)督的改進(jìn)。實驗結(jié)果表明，本文算法能夠?qū)崿F(xiàn)對手勢的準(zhǔn)確跟蹤，在鍵盤鼠標(biāo)模擬的交互中，應(yīng)用效果較好?；谀w色的跟蹤對光照和背景的要求比較高，同時該項目關(guān)于鼠標(biāo)模擬部分的算法還有待改進(jìn)。

參考文獻(xiàn)

[1] 齊靜，徐坤，丁希侖.機(jī)器人視覺手勢交互技術(shù)研究進(jìn)展[J].機(jī)器人，2017，39（4）：565?584.

[2] SUN J H， JI T T， ZHANG S B， et al. Research on the hand gesture recognition based on deep learning [C]// 2018 12th International Symposium on Antennas， Propagation and EM Theory （ISAPE）. New York： IEEE， 2018： 1?4.

[3] SOKHIB T， WHANGBO T K. A combined method of skin?and depth?based hand gesture recognition [J]. International Arab journal of information technology， 2020， 17（1）： 137?145.

[4] ROY P P， KUMAR P， KIM B G. An efficient sign language recognition （SLR） system using Camshift tracker and hidden Markov model （HMM） [J]. SN computer science， 2021， 2（2）： 79.

[5] 朱慶杰，潘航，陳顯軍，等.面向人機(jī)交互的常見桌面手勢識別[J].計算機(jī)工程與設(shè)計，2018，39（10）：3246?3251.

[6] 張晗，錢育蓉，王躍飛，等.基于圖像邊緣增強(qiáng)與弱化的邊緣檢測[J].計算機(jī)工程與設(shè)計，2019，40（11）：3106?3110.

[7] 姚澤烽，程顯毅，謝璐.基于ORB和最小凸包的感興趣區(qū)域檢測方法研究[J].計算機(jī)應(yīng)用研究，2018，35（10）：3186?3188.

[8] AN V， QU Z H， ROBERTS R. A rainbow coverage path planning for a patrolling mobile robot with circular sensing range [J]. IEEE transactions on systems， man， and cybernetics： Systems， 2018， 48（8）： 1238?1254.

[9] NEVE P， BARNEY J N， BUCKLEY Y， et al. Reviewing research priorities in weed ecology， evolution and management： A horizon scan [J]. Weed research， 2018， 58（4）： 250?258.

[10] 吳瑋，鄭娟毅，杜樂.多特征融合的Camshift運(yùn)動目標(biāo)跟蹤算法[J].計算機(jī)科學(xué)，2018，45（7）：252?258.

[11] LIANG H， WANG S， GAO S， et al. Deephullnet： A deep learning approach for solving the convex hull and concave hull problems with transformer [J]. International journal of digital earth， 2024， 17（1）： 2358843.

[12] KIRKPATRICK D G， SEIDEL R. The ultimate planar convex hull algorithm？ [J]. SIAM journal on computing， 1986， 15（1）： 287?299.

[13] KENWRIGHT B. Convex hulls： Surface mapping onto a sphere [EB/OL]. [2023?04?18]. https：//doi.org/10.48550/arXiv.2304.04079.

作者簡介：郭金朋（1992—），男，安徽泗縣人，碩士，工程師，主要研究方向為人工智能、模式識別。

韓昌林（1994—），男，安徽泗縣人，碩士，助教，研究方向為圖像處理、計算機(jī)視覺。

陸 "洲（1995—），女，安徽樅陽人，碩士，助教，研究方向為數(shù)字金融。

邵 "陽（1986—），男，安徽六安人，碩士，研究方向為機(jī)器視覺。