基于改進凸包算法的手勢定位

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

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

中圖分類號： TN911.7?34； TP391.4 " " " " " " " " " " 文獻標識碼： 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 "引 "言

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

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

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

1 "手部分割

1.1 "建立色彩模型

本文利用HSV（Hue， Saturation， Value）色彩模型的H（色調）分量來進行膚色區域檢測[5]，其中S（飽和度）與V（明度）分量取經驗值。HSV色彩空間采用近似人眼視覺的認知表示，用色調、飽和度和明度三個相關性較弱的分量來表示顏色。因此，在膚色分割階段可以由RGB色彩空間轉化為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）

色調（H）的值為0.0°～360.0°，飽和度（S）和明度（V）的值為0.0～1.0，再轉換成0～100%。

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

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

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

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

1.2 "圖像增強

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

1.3 "輪廓與凸包查找

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

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

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

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

1.4 "凸包缺陷與指尖定位

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

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

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

式中：[f（x0）]為當前垂直方向像素點坐標值；[f（x1）]與[f（x2）]分別為其前驅坐標值與后繼坐標值，代碼中選擇的前驅后繼跨度為3個像素點，目的是防止像素點間構成線條的布局影響。

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

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

（3）

式中：[ACB]為相鄰凸包至目標歐氏距離之和；[C]為目標像素點坐標；[A]、[B]為相鄰凸包點[A]與點[B]。目標點[C]從[A]點出發，當[ABC]gt;MAX時則賦值為[ABC]，如此直至[C]點到達[B]點，最終獲取的MAX點則為所需的凸包缺陷點。

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

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

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

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

繪制指尖點與凸包缺陷點，如圖10所示。

2 "手部跟蹤

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

3 "模擬鍵鼠算法設計

在手勢跟蹤與指尖定位問題解決之后，模擬簡單鍵鼠工作就相對容易很多[11?13]。可以采用幀差法來計算指尖坐標與跟蹤重心的移動向量，跟蹤面積的變化與指尖和凸包缺陷的數量，做一個簡單的判斷。

1） 鍵盤模擬

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

2） 鼠標模擬

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

4 "實現結果分析

4.1 "鍵盤和鼠標模擬實驗效果

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

4.2 "精確度測試

測試包括指尖與凸包缺陷定位，鍵盤模擬與鼠標模擬的精確性。測試前，對環境進行了調整，使其背景環境與光照環境可與以上手勢與背景有明顯的區別，如圖12所示。表1是各種操作的準確率。

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

5 "結 "語

本文提出改進的凸包算法，即通過三角形原理計算出指尖與凸包缺陷，解決了手勢水平狀態下凸包缺陷無法定位的問題，并應用在基于手勢的鍵盤鼠標模擬交互中。運用Camshift算法來對手部進行跟蹤，Camshift算法有很好的實時性。為達到自動定位跟蹤，對Camshift算法使用指尖定位進行了無監督的改進。實驗結果表明，本文算法能夠實現對手勢的準確跟蹤，在鍵盤鼠標模擬的交互中，應用效果較好。基于膚色的跟蹤對光照和背景的要求比較高，同時該項目關于鼠標模擬部分的算法還有待改進。

參考文獻

[1] 齊靜，徐坤，丁希侖.機器人視覺手勢交互技術研究進展[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].計算機工程與設計，2018，39（10）：3246?3251.

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

[7] 姚澤烽，程顯毅，謝璐.基于ORB和最小凸包的感興趣區域檢測方法研究[J].計算機應用研究，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運動目標跟蹤算法[J].計算機科學，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—），男，安徽泗縣人，碩士，助教，研究方向為圖像處理、計算機視覺。

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

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