基于改進自適應(yīng)正交匹配追蹤算法的手勢識別

李 貝 孫 瑛,2 李公法,2,3 蔣國璋,2,5 孔建益,2 江 都,4 陳迪斯,3

1.武漢科技大學(xué)冶金裝備及其控制教育部重點實驗室，武漢，430081 2.武漢科技大學(xué)生物機械手與智能測控研究中心，武漢，430081 3.武漢科技大學(xué)精密制造研究院，武漢，430081 4.武漢科技大學(xué)機械傳動與制造工程湖北省重點實驗室，武漢，430081 5.武漢科技大學(xué)3D打印與智能制造工程研究所，武漢，430081

0 引言

眾所周知，手勢識別作為一種自然的交互方式，被廣泛用于人工智能和模式識別領(lǐng)域?；谝曈X的手勢識別主要采用攝像頭捕捉手勢圖像，通過圖像處理和相關(guān)算法識別手勢動作，涉及到的技術(shù)包括手勢檢測分割、特征提取和分類識別等。這些技術(shù)近年來雖然有很大發(fā)展，但由于視覺傳感器采集手勢進行識別時，常常會遇到背景環(huán)境復(fù)雜、分類算法性能不高等問題，因此對于精確的手勢識別研究仍存在一定的挑戰(zhàn)［1?2］。近年來，稀疏表示理論的提出和發(fā)展為模式識別提供了新方法［3?4］，表現(xiàn)出較大的發(fā)展?jié)摿蛷V闊的應(yīng)用前景。WRIGHT等［5］提出稀疏的表示分類（sparse representation?based classification，SRC）框架將訓(xùn)練樣本用于構(gòu)建冗余字典［6］，通過稀疏求解算法［7?8］，測試樣本可以表示為訓(xùn)練樣本的稀疏線性組合，最后根據(jù)最小殘差分類［9］，成功解決了分類算法性能不高的問題。

SRC方法提出后，稀疏表示理論逐漸得到研究人員的重視［10］，研究者在稀疏求解算法方面提出了各種方法。常用的稀疏求解算法主要有近似求解最小化l0范數(shù)問題的貪婪算法。貪婪算法通過迭代選取合適原子，易于實現(xiàn)，常用的正交匹配追蹤（orthogonal matching pursuit，OMP）算法［11］每次迭代時只選擇一個原子，迭代次數(shù)多、效率低，而且需設(shè)定稀疏度。針對OMP算法存在的問題，出現(xiàn)了許多改進算法，如為了在每次迭代時選擇多個原子，提出基于正則化的ROMP（regularized OMP）算法［12］、基于原子選擇閾值的SWOMP（stagewise weak OMP）算法［13］、基于回溯思想的SP（subspace pursuit）算法，SP算法的優(yōu)勢在于降低了計算復(fù)雜度，但大部分算法都依賴于稀疏度［14］。SAMP（sparsity adaptive matching pursuit）算法沿用了SP算法的回溯思想，而且可以利用固定步長逐漸逼近稀疏度，其優(yōu)勢在于利用步長逼近的方法進行分階段迭代，每個階段增加固定步長直到滿足要求，其缺點是固定步長的選擇會對算法性能有較大的影響［15］。

本文從稀疏表示分類算法原理入手，針對現(xiàn)有貪婪算法在稀疏度估計上的優(yōu)勢和增加固定步長的不足，引入稀疏度估計方法和變步長的思想，提出改進的自適應(yīng)正交匹配追蹤（modified adap?tive orthogonal matching pursuit，MAOMP）算法，并在手勢庫上進行驗證，實驗結(jié)果表明所提出算法性能優(yōu)于其他算法性能，有效提高了算法的精度和效率。

1 稀疏表示分類算法

稀疏表示分類（SRC）的基本思想是將訓(xùn)練樣本構(gòu)成冗余字典，則測試樣本可以由該字典元素的稀疏線性組合表示，然后采用稀疏重構(gòu)算法求解稀疏系數(shù)。SRC算法主要涉及兩個方面，即冗余字典的構(gòu)造和稀疏系數(shù)的求解。

1.1 測試樣本作為訓(xùn)練樣本的線性表示

給定包含C類手勢的樣本集（總樣本數(shù)為n），假設(shè)第j（j=1，2，…，C）類包含nj個手勢樣本且樣本足夠多，該類的第i個手勢樣本可以用列向量aj,i∈Rm×1表示，將該類手勢樣本組成列向量矩陣Aj=[aj,1aj,2… aj,nj]∈Rm×nj，m是該矩陣的維數(shù)。理論上屬于第j類的某個測試樣本y∈Rm分布在該類樣本集所形成的一個線性子空間中，即y可由Aj線性表示：

式中，vj=(vj,1,vj,2…,vj,nj)∈Rnj×1為線性表示系數(shù)。

測試樣本的類別還未確定，所以將整個C類手勢樣本構(gòu)成一個冗余字典矩陣A=［A1A2…AC］∈Rm×n，則y可由A表示：

其中，x=[0 … 0 vj,1vj,2… vj,nj0 … 0]為測試樣本的稀疏系數(shù)，非零元素均對應(yīng)第j類，非零元素左側(cè)含有零元素nj(j-1)項，右側(cè)含零元素有nj(C-j)項，若稀疏度S=||x||0且S?n，則認為x是稀疏的。

1.2 最小化范數(shù)的稀疏計算方法

因為字典A的維數(shù)小于樣本數(shù)，即m＜n，所以式（2）屬于欠定方程，解不唯一。但x是稀疏矩陣，且A滿足2S階約束等距性質(zhì)（restricted isometry property，RIP），即A中任意2S列樣本數(shù)據(jù)線性無關(guān)，對于任意樣本y和常數(shù)δS∈（0，1），字典A滿足

則可以保證有唯一解［16?17］。

式（2）可以通過最小化l0范數(shù)求解：

但最小化l0范數(shù)的求解是個NP?hard問題，只能近似求解，為提高計算精度，可以將l0范數(shù)求解稀疏系數(shù)問題轉(zhuǎn)化為最小化l1范數(shù)問題進行分析。根據(jù)壓縮感知理論，當(dāng)x足夠稀疏時，式（4）可以等價于求解最小化l1范數(shù)問題［18］：

實際的樣本采集會受到噪聲、光照等影響，從而影響測試樣本和訓(xùn)練樣本的相關(guān)性，進而影響識別率。為提高魯棒性，可以添加噪聲約束：

1.3 最小殘差的分類

線性組合的稀疏系數(shù)已求得，那么可以利用稀疏系數(shù)和冗余字典重構(gòu)測試樣本，然后比較每個類的重構(gòu)樣本和測試樣本：

式中，γj(y)為第j類樣本對應(yīng)的殘差；δj(x^)為x^中第j類樣本對應(yīng)位置的系數(shù)值，其他位置的系數(shù)值為0；I(y)為測試樣本的類別。

根據(jù)最小殘差判斷測試樣本的類別。

SRC算法的步驟總結(jié)如下：

（1）輸入訓(xùn)練樣本 A∈Rm×n，測試樣本 y∈Rm，誤差閾值ε＞0；

（2）對A的每一列和y進行l(wèi)2范數(shù)歸一化；

（3）求解最小化l0范數(shù)問題：

或轉(zhuǎn)化為求解最小化l1范數(shù)問題：

（4）對j類樣本計算殘差：

（5）輸出類別I(y)=argminjγj(y)

2 改進的自適應(yīng)正交匹配追蹤算法

本文利用原子匹配測試來估計初始的稀疏度，該稀疏度S0小于真實的稀疏度S。將u=前S0個較大值對應(yīng)的索引構(gòu)成集合Λ0，其中，γ0為初始殘差，Al為訓(xùn)練樣本的第l列，對應(yīng)A的列構(gòu)成矩陣A0。文獻［17］提出一個真命題，即A以參數(shù)(S,δS)(δS∈(0,1))滿足受限等距性

稀疏表示理論中，稀疏系數(shù)的求解至關(guān)重要，即如何利用冗余字典中的少量原子表示原信號［19］，本文針對各種貪婪算法的缺點，為提高算法的精度和效率，提出改進的自適應(yīng)正交匹配追蹤(MACMP)算法。MAOMP算法無需輸入真實稀疏度，而是先通過匹配測試來估計稀疏度初始值，將滿足條件的估計值作為支撐集的長度；然后從投影集合中篩選原子，并更新索引集和支撐集，利用回溯思想和最小二乘法估計原始信號，更新殘差；最后分階段和變步長地調(diào)整篩選的原子數(shù)，逼近真實稀疏度，從而進行更好的稀疏表示。

2.1 稀疏度估計

2.2 變步長

由于稀疏度一般是未知的，而SAMP算法采用較小步長逼近且步長固定，這便降低了算法效率。由于每次迭代殘差是不斷下降的，剛開始下降較快，之后幅度逐漸減緩，最后趨于穩(wěn)定值，因此步長也應(yīng)該逐漸減小，即開始時，采用較大步長以減少迭代，然后逐漸減小步長、提高精度。本文實現(xiàn)變步長采用的方法是，在滿足變步長條件時給步長lstep乘以一個步長系數(shù)β∈（0,1），隨著階段nstage的增加，步長lstep逐漸減小，即

整個MAOMP算法的步驟如下：

（1）輸入訓(xùn)練樣本A∈Rm×n、測試樣本y∈Rm、常數(shù)δS、步長系數(shù)β。

（2）初始化。稀疏度S0=1，步長lstep=m/lbn，殘差γ0=y，索引（列序號）集合Λ0=?，索引集合對應(yīng)的支撐集合A0=?。

（3）計算投影集合u={uj|uj= ||γ0,Al,l=1,2,…,n}，選擇u中的前S0個較大值，并將其索引值和支撐集分別存入Λ0和A0。

（7）求解y=Agxg的最小二乘解x^g=

（8）從x^g中選出絕對值最大的L項記為x^gL，對應(yīng)的索引構(gòu)成集合ΛgL，對應(yīng)A的列構(gòu)成集合AgL；

（10）如果殘差 ||γg||2＜ε，則轉(zhuǎn)步驟（11）；L+lstep，g←g+1，轉(zhuǎn)步驟（5）；如果兩個條件都不滿足，則Λg= ΛgL，g←g+1,轉(zhuǎn)步驟（5）。

（11）輸出稀疏系數(shù)x^，其中索引集合Λg對應(yīng)位置的非零項為最終迭代后的x^g。

MAOMP算法和SAMP算法類似，輸入?yún)?shù)不需設(shè)定稀疏度，步驟（2）～步驟（4）為估計稀疏度過程，初始化支撐集的長度為所估計的稀疏度S0，提高了算法效率，另外，不同情況下的初始步長也不同，這里設(shè)定lstep=m/lbn。步驟（5）～步驟（10）為基于SAMP算法的分階段逼近過程，根據(jù)條件逐漸改變步長可以更好地逼近真實稀疏度，從步驟（10）可以看出，每次迭代后的殘差不斷減小，因此算法能夠收斂。MAOMP算法采用稀疏度估計和變步長在一定程度上減少了迭代次數(shù)并提高了精度。

3 實驗結(jié)果仿真分析

3.1 手勢樣本庫的建立

為驗證本文方法對手勢的識別效果，需采集手勢圖像，建立手勢樣本庫，分析各因素對手勢識別的影響情況。實驗時選取指定的手勢樣本，在YCbCr彩色空間建立橢圓模型進行手勢分割，并提取Hu不變矩和HOG特征。

3.1.1 抓取手勢樣本庫

本文采用攝像頭采集5個人的5類典型的抓取手勢樣本，即五指抓、三指抓、兩指捏、單指鉤和張開，如圖1所示，每人采集5類手勢各20張，即每類手勢采集100張，共500張圖像用于實驗，采集手勢的過程中，考慮手勢旋轉(zhuǎn)、尺度、光照和背景的變化。

圖1 五類抓取手勢樣本Fig.1 Five kinds of grasping gesture samples

3.1.2 ASL樣本庫

ASL樣本庫包含26個字母的手勢（字母j和z的手勢是動態(tài)的，所以本文不予考慮），這些手勢圖片采用Kinect在相同光照和場景下分別對5個人進行采集，每個操作者及每個字母都有顏色圖和深度圖，其中，每人采集24個字母的彩色圖像各20張，彩色圖像共2 400張可用于實驗。

3.2 參數(shù)選擇對MAOMP算法性能的影響

為驗證稀疏度的估計效果，比較參數(shù)δS取不同值時稀疏度S的估計值。實驗時，抓取手勢樣本庫中，每類手勢隨機選取50個訓(xùn)練樣本、10個測試樣本，并降維到100；ASL樣本庫中，每類手勢隨機選取50個訓(xùn)練樣本、2個測試樣本，并降維到100，實驗結(jié)果如圖2、圖3所示。

圖2 抓取手勢樣本庫上的稀疏度估計Fig.2 Sparsity estimation in grasping gesture sample database

圖3 ASL樣本庫上的稀疏度估計Fig.3 Sparsity estimation in ASL sample database

由圖2、圖3可以看出，每個δS對應(yīng)的稀疏度估計值S0都在某個值附近波動，比如δS=0.2時，在抓取手勢樣本庫上，估計值S0的平均值為27，在ASL樣本庫上，估計值S0的平均值為24；由于在兩個手勢庫上每類訓(xùn)練樣本均取50個，所以理論稀疏度S=50可作為稀疏度估計的參考。δS的值越小，稀疏度的估計值越大，波動越大，與理論稀疏度越接近，但估計值可能會大于理論稀疏度；δS的值越大，稀疏度的估計值越小，估計值越穩(wěn)定，但小到一定程度后，如當(dāng)δS=0.9時，稀疏度估計值保持致迭代終止條件的范圍增大，從而增加了迭代估計，稀疏度估計值便較大，反之亦然。所以為減少后續(xù)迭代，并防止過估計，本文選取δS=0.2。

下面通過實驗驗證不同β值對算法的影響。在抓取手勢樣本庫上，每類選取50個訓(xùn)練樣本，剩余樣本作為測試樣本，并將特征降維到100；在ASL樣本庫上，每類選取50個訓(xùn)練樣本，剩余樣本作為測試樣本，并將特征降維到100，δS取0.2。

圖4所示為不同的步長系數(shù)對識別率的影響，可以看出，隨著步長系數(shù)β的增大，兩個樣本庫上的識別率都逐漸降低。抓取手勢庫上，隨著β的增大，識別率從93.2%降到79.5%；ASL樣本庫上，隨著β的增大，識別率從94.9%降到80.2%，而且在β=0.4和β=0.5之間降的幅度最大，約為4%，其他區(qū)間降的幅度約為2%。

圖4 不同的步長系數(shù)對識別率的影響Fig.4 The influence of different step size coefficients on recognition rate

β=0.4和β=0.5之間識別率的降幅最大，為更好說明其情況，在兩個樣本庫上各迭代100次和150次，繪制了β取不同值時殘差隨迭代次數(shù)的變化曲線，如圖5、圖6所示。當(dāng)?shù)螖?shù)增加到一定值后，殘差收斂于某個較小值。圖5和圖6中，殘差保持不變時對應(yīng)的迭代次數(shù)即為階段數(shù)，并且隨著步長系數(shù)的增大，階段數(shù)減小，迭代次數(shù)也會減小，抓取手勢庫上的迭代次數(shù)最大值為88，最小值為9，在ASL樣本庫上的迭代次數(shù)最大值為103，最小值為14。由圖5和圖6可以看出，β=0.4和β=0.5之間迭代收斂次數(shù)下降的幅度比其他區(qū)間大，抓取手勢庫上的降幅為18，ASL樣本庫上的降幅為22，其他區(qū)間的降幅約為10。因為步長較大使得選取的元素較多，支撐集的長度較大，收斂快，但容易造成稀疏度的過估計從而使識別率降低，β=0.5時，已經(jīng)造成過估計，對測試樣本進行線性表示的原子中包含過多其他類原子，從而降低了識別率。綜合考慮識別率和迭代次數(shù)，β取0.4較合適。

圖5 抓取手勢樣本庫上殘差隨迭代次數(shù)的變化情況Fig.5 The variation of residual error with iterations in grasping gesture sample database

圖6 ASL樣本庫上殘差隨迭代次數(shù)的變化情況Fig.6 The variation of residual error with the iterations in ASL sample database

3.3 算法的性能比較

分別在兩個手勢庫上從識別率和平均運行時間兩方面對MAOMP算法與OMP、ROMP、SWOMP、SP、SAMP算法進行比較分析。實驗時每類隨機選取50個樣本作為訓(xùn)練集，50個樣本作為測試集，分別提取特征后采用主成分分析法進行降維。另外需設(shè)定各算法的參數(shù)，MAOMP算法中δS=0.2，β=0.4，OMP、ROMP、SWOMP、SP算法的稀疏度設(shè)定為40，SWOMP算法的門限參數(shù)設(shè)定為0.5，SAMP算法的步長設(shè)定為5。

抓取手勢樣本庫上不同匹配追蹤算法的識別率和平均運行時間隨維數(shù)的變化情況分別如圖7、圖8所示。由圖7可以看出，各算法的識別率都隨維數(shù)的增大而增大。低維數(shù)（m≤70）時，MAOMP算法的識別率仍能保持在85%以上，SAMP、SP、SWOMP算法識別率保持在80%～85%，而ROMP和OMP算法則小于80%；高維數(shù)（m＞190）時，MAOMP、SAMP、SP、SWOMP的識別率均達到90%以上，ROMP和OMP算法在85%左右?？傮w上看，同一維數(shù)下MAOMP算法的識別率最高，SAMP算法次之，OMP算法最小。由圖8可以看出，隨著維數(shù)的增大，各算法的平均運行時間逐漸延長。低維數(shù)時，各算法的平均運行時間都較短，在1 ms左右，相差較小。高維數(shù)時，各算法運行時間相差較大，其中維數(shù)為200時，OMP算法的平均運行時間達到28 ms，SAMP算法為19 ms，MAOMP算法為12 ms，其他算法幾乎在10 ms以下?？傮w上看，同一維數(shù)下OMP算法的平均運行時間最長，SAMP算法次之，SWOMP算法最短。

圖7 抓取手勢樣本庫上各算法的識別率隨維數(shù)的變化情況Fig.7 The variation of recognition rate on each algorithm with the dimensionality in grasping gesture sample database

圖8 抓取手勢樣本庫上各算法的平均運行時間隨維數(shù)的變化情況Fig.8 The variation of average run time on each algorithm with the dimensionality in grasping gesture sample database

ASL樣本庫上不同匹配追蹤算法的識別率和平均運行時間隨維數(shù)的變化情況分別如圖9、圖10所示，可以看出，識別率和平均運行時間都隨維數(shù)的增大而增大，由于在ASL樣本庫上選取樣本較多，所以與抓取手勢庫相比，識別率相對較高，平均計算時間相對較長。圖9中，低維數(shù)（m≤70）時，MAOMP、SAMP和SP算法的識別率都在85%以上，SWOMP、ROMP和OMP算法的識別率保持在80%～85%；高維數(shù)（m＞190）時，MAOMP、SAMP、SP、SWOMP的識別率超過90%，ROMP和OMP算法在85%～90%；同一維數(shù)下，MAOMP算法的識別率最高，SAMP算法次之，OMP算法最小。圖10中，在低維數(shù)時各算法的平均運行時間都較短，在2 ms左右，高維數(shù)時各算法運行時間相差較大，其中維數(shù)為200時，OMP算法的平均運行時間達到54 ms，SAMP算法為34 ms，MAOMP算法為25 ms，其他算法都在20 ms以下；同一維數(shù)下，OMP算法的平均運行時間最長，SAMP算法次之，ROMP算法最短。

圖9 ASL樣本庫上各算法的識別率隨維數(shù)的變化情況Fig.9 The variation of recognition rate on each algorithm with the dimensionality in ASL sample database

圖10 ASL樣本庫上各算法的平均運行時間隨維數(shù)的變化情況Fig.10 The variation of average run time on each algorithm with the dimensionality in ASL sample database

綜上所述，OMP算法每次迭代只選取一個原子，導(dǎo)致精度和效率較低；SP、SWOMP和ROMP算法通過改進原子選擇策略，每次直接選取多個原子，簡化了OMP算法，提高了OMP算法的效率，但識別精度易受稀疏度或閾值的影響；SAMP算法通過步長逐步逼近，提高了OMP算法的精度，效率比OMP算法高，但由于依賴于初始步長的設(shè)定且步長固定，使得稀疏度估計不夠準(zhǔn)確，所以其識別率低于MAOMP算法；MAOMP算法在求解前引入了稀疏度的初步估計方法，后續(xù)每個階段步長逐漸減小，使得逼近的稀疏度更加精確，比其他改進的OMP算法要高，平均運行時間也明顯短于OMP算法和SAMP算法，樣本較多、維數(shù)較高時，優(yōu)勢更明顯。

4 結(jié)論

本文基于稀疏表示分類算法，針對稀疏求解算法中各貪婪算法存在精度低、參數(shù)不確定的問題，提出改進的自適應(yīng)正交匹配追蹤（MAOMP）算法。MAOMP算法引入稀疏度估計步驟，通過匹配測試來估計稀疏度初始值，并增加變步長步驟，分階段調(diào)整篩選的原子數(shù)，逼近真實稀疏度。實驗結(jié)果表明，MAOMP算法的性能比其他改進的OMP算法好，樣本較多、維數(shù)較高時的優(yōu)勢更明顯。下一步將加入一些遮擋圖像進行識別來驗證算法的魯棒性。