基于在線增量學習的實時人臉跟蹤算法

包　芳　張炎凱,　王士同

1(江陰職業技術學院　江蘇 江陰 214400)2(江蘇省信息融合軟件工程技術研究開發中心　江蘇 江陰 214400)3(江南大學　江蘇 無錫 214000)

?

基于在線增量學習的實時人臉跟蹤算法

包芳1,2張炎凱1,2,3王士同3

1(江陰職業技術學院江蘇 江陰 214400)2(江蘇省信息融合軟件工程技術研究開發中心江蘇 江陰 214400)3(江南大學江蘇 無錫 214000)

摘要提出基于在線增量式極端隨機森林分類器的實時人臉跟蹤算法。算法用在線極端隨機森林分類器實現基于檢測的跟蹤，并結合動態目標框架和P-N學習矯正檢測的錯誤。 實驗結果表明，該算法能夠在不確定背景下對任意人臉實現較長時間段內的穩定快速的實時跟蹤，并能有效排除背景等的干擾,效果較好。

關鍵詞在線增量學習極端隨機森林P-N學習動態目標框架實時人臉跟蹤

0引言

在視頻監控快速普及的情況下，迫切需要遠距離、用戶非配合狀態下的快速識別和跟蹤技術。其中，人臉可以最自然的方式實現快速身份識別、預警和跟蹤。因此，人臉檢測、識別與跟蹤是機器視覺領域的一個研究熱點，國內外學者對此進行了大量的研究。

靜態人臉的檢測與識別技術，基本已成熟，且廣泛應用于考勤、檢票等應用場合中。運動人臉的檢測與跟蹤又分為固定背景與不確定背景兩種情況。固定背景下的運動人臉檢測主要采用AdaBoost系列算法[1,2]，跟蹤則采用Mean-Shift算法[3]和粒子濾波算法[4]兩類框架實現。固定背景下的人臉跟蹤，只能是一種短期的、局限性較強的跟蹤，在實際場合中應用價值并不大。在網絡集成、背景變化的情況下，任意選中需跟蹤人臉，進行長時間穩定跟蹤，才是實際應用所需要的，可供公共交通場所、安全部門等用于特定人員的有效跟蹤，具備極高的實用價值。在任意環境中長期穩定地跟蹤人臉，主要存在以下挑戰：人臉的各類形變；人臉在某些幀中移開，過了一個不確定階段又出現；背景的復雜性和不確定性等。因此，傳統的批量離線機器學習模式已不能解決此類問題，而需要使用在線增量學習模式。

目前，增量學習主要用基于決策樹的算法來實現，特別是基于決策樹的隨機森林算法[5,6]。隨機森林對原始訓練樣本進行采樣替換，算法簡單、快速、穩定適用于各種分類場合。但無論是應用貪婪算法還是統計算法的隨機森林，在增量重構時都需要重新計算最優屬性或統計值，因此需要大量數據作為樣本。

Geutrs等提出的極端隨機森林算法[7]，直接采用原始的訓練樣本，隨機選擇分裂閾值，在分類精度和時間開銷方面，都優于一般隨機森林算法，比較適合于小樣本數據流分類。視頻序列中的人臉跟蹤，屬于典型的小樣本數據流中的兩分類問題，適合用基于極端隨機森林的在線增量學習算法來實現。

另外，P-N學習[8]經常被用于矯正分類器的錯誤。P-experts將那些被分類器標記為負樣本，但根據約束條件應該為正樣本的那些樣本賦予“正”的標簽，并添加到訓練樣本集中；而N-experts則將那些被分類器標記為正樣本，但根據約束條件應該為負樣本的那些樣本賦予“負”的標簽，并添加到訓練樣本集當中。這樣，P-experts增加了分類器的魯棒性，而N-experts則增加了分類器的判別能力。

近年來，基于檢測的跟蹤方法成為研究的熱點。一般這種方法都需檢測器和跟蹤器并行運行，由檢測結果及時重置完善跟蹤，以達到持續跟蹤。檢測算法常用隨機森林分類器，跟蹤則采用光流法等。如上所述，隨機森林算法在增量重構時需要大量樣本，光流法算法復雜，抗噪聲能力一般，均不能適應視頻序列中人臉的實時跟蹤場合。

因此，本文提出應用極端隨機森林分類器進行在線增量式目標檢測，然后應用P-N學習[8]再次提升檢測性能，并構建在線動態目標框架，實時更新目標框架。最后綜合應用檢測和P-N學習的結果，以及距離動態目標模型的相似度，實現人臉在線跟蹤。

1人臉建模和動態目標框架

1.1人臉建模

本文采用2bitBP特征進行人臉建模。這是一種類Harr特征[9]，通過量化，只有4種可能的編碼。因此比較適合于在線監測的場合。

建模過程包括特征類型的確定以及相應的特征取值。假定需要判斷一個Patch塊是否為檢測目標。所謂特征類型，是指在這個Patch在(x,y)坐標，取一個長width，高height的框，這個組合(x,y,width,height)即為相應的特征類型。在已經選定特征類型的情況下，把框左右分成相等的兩部分，分別計算左右兩部分灰度和的大小，會有兩種情況。同樣的，把框分成上下相等的兩部分，也會有兩種情況。于是在分了上下左右后，總共會有4種情況，可以用2 bit來描述這4種情況，即可得到相應的特征取值。

2bitBP特征對外界環境的光照等變化具有良好的魯棒性，但對于人臉自身形態的變化有較高的漏檢率，而基于人臉膚色的模型則對自身形變有很好的魯棒性。因此，本文在后續的P-N學習的約束條件中，利用基于YCgCr顏色空間[10]的膚色檢測模型，保證對形變的魯棒問題。

1.2動態目標框架

本文提出一種動態目標框架，它是歸一化后的正樣本和負樣本的集合，即為本文的訓練集合。設pi+為第i個被添加進去的正樣本，同理pi-為第i個被添加進去的負樣本。

給定任意一個圖像片p和動態目標框架M，定義以下概念：

(1) Patch 塊相似度：采用歸一化積相關算法NCC[11](Normalized Cross-Correlation)計算兩個圖像塊之間的相似度：

S(pi,j)=0.5×(NCC(pi,pj)+1)

(1)

(2) 正樣本相似度：

(2)

(3) 負樣本相似度：

(3)

(4) 最近鄰正樣本相似度：

(4)

由于本文涉及的是任意人臉的跟蹤問題，因此，在第1幀，正樣本為需跟蹤的人臉。然后，在離其最近的掃描窗口內，在1%的范圍內，進行旋轉、偏移等20次幾何變換，這樣就產生了共20個正樣本。負樣本則在所有Patch塊的外部隨機生成。這些帶標記的樣本構成原始的動態目標框架，可以用來訓練原始的極端隨機森林分類器。在后續跟蹤過程中，正負樣本被標記后再依據P-N學習被陸續添加進來。

2基于在線增量式極端隨機森林分類器的人臉檢測

極端隨機森林是由多棵決策樹集成的分類器，它直接采用原始數據作為訓練樣本，并且在每棵樹的決策節點上，隨機選擇分裂閾值。Geutrs等提出的極端隨機森林并不支持在線增量學習，因此，王愛平等提出了支持在線學習的增量式極端隨機森林算法，稱為IERF(Incremental Extremely Random Forest)算法[12]。

IERF算法將新增的在線樣本存儲到葉節點，并通過Gini系數來決定是否需對當前葉節點進行分裂擴展。算法中的每棵決策樹被稱為增量超樹，設輸入為訓練樣本p和樹索引i，輸出為增量超樹ti，其構造步驟如下：

步驟1：

if ti的根節點不存在

//返回根節點

返回一個根節點為R的增量超樹ti，其標記值為p的標記值；

else

//需要分裂

訓練樣本p經分類后落到葉節點L；

將p存儲到L的樣本列表中；

更新L上樣本類別的數量；

if Gini(L)>分裂閾值

構造一個子增量超樹T(見步驟2)；

if L是根節點

將T作為新的根節點；

else

用T替換L成為原父節點的子節點；

endif

刪除葉節點L；

返回增量超樹 ti;

endif

endif

其中，Gini系數是用來衡量樣本集合純度的，設樣本集D共有k個類別，pi為類別i的樣本所占比率。Gini系數計算表達式為：

(5)

當某葉節點上的Gini系數超過一定閾值，則認為此節點上的混亂程度過高，需要繼續分裂，利用當前存儲的樣本構造子增量超樹。

(6)

當用當前存儲的樣本構造子增量超樹時，設輸入的是樣本集合S，輸出的是子增量超樹T。其算法見步驟2。

步驟2：

if |S|

//生成葉節點

生成1個新的葉節點T；

將S中所有樣本存儲在T上；

統計S中所有類別標記的數量分布，也存儲在T上；

返回葉節點T，T的標記值由S的類別標記數量確定；

Else

//生成子樹

將S劃分成2個子集Sl和Sr，決策屬性和分裂測試s*采用Geutrs在文獻[11]中的方法；

根據Sl和Sr，分別構造子增量超樹Tl和Tr;

根據分裂測試s*，生成決策節點T，Tl和Tr分別是其左子樹和右子樹；

返回子增量超樹T；

endif

其中nmin為設定的最小樣本數。

本文對于極端隨機森林的初始化訓練，由第1幀生成的帶標記的目標框架完成。然后，隨著新幀的進入，用掃描窗口處理每幀，掃描窗口的大小同原始框定的人臉，歸一化后構成1個新的圖像塊。每個新圖像塊就是在線增量樣本，由以上算法對其進行標記。最后，極端隨機森林的判決結果由所有增量超樹的結果取概率平均，從而判斷其是否人臉樣本。為了提高檢測速度，在后續過程中，掃描只在每幀的膚色區域內進行，大大提高了檢測速度。

3P-N學習

當按以上算法檢測出人臉樣本后，就應該將其作為正樣本加入動態目標框架。但檢測有可能存在誤檢，因此，在算法中加入了P-N學習模塊，對檢測錯誤進行再次矯正。

P-N學習利用帶標記和不帶標記的樣本之間存在的結構性特征，來逐步訓練并改善分類器分類性能。P-N學習的過程如下：

(1) 準備一個數量較少的訓練樣本集和一個數量很大的測試樣本集。

(2) 利用訓練樣本訓練一個初始分類器，并對先驗約束條件進行相應的設置。

(3) 利用訓練好的初始分類器對測試樣本賦予標記，并找出分類器賦予的標記同約束條件相矛盾的那些樣本。

(4) 根據約束條件，為上述相矛盾的樣本重新賦予標記，將其加入訓練樣本，重新訓練分類器。其中， P-experts將那些被分類器標記為負樣本，但根據約束條件應該為正樣本的那些樣本賦予“正”的標簽，并添加到訓練樣本集中；而N-experts則將那些被分類器標記為正樣本，但根據約束條件應該為負樣本的那些樣本賦予“負”的標簽，并添加到訓練樣本集當中。這樣，P-experts增加了分類器的魯棒性，而N-experts則增加了分類器的判別能力。

本文對于經分類器標記的新樣本，需要確定恰當的約束條件，找出分類器賦予的標記同約束條件相矛盾的那些，加入動態目標框架。從而近一步保障檢測效果。

根據本文涉及的具體領域，首先設置的約束條件為：YCgCr顏色空間中的膚色模型。目前公認YCgCr顏色空間對于膚色的聚類性能是最好的，從視頻序列中圖像的RGB空間向YCgCr空間轉換的公式為：

(7)

其中屬于膚色的范圍，也即為本文的約束條件1為：

(8)

當一個樣本中絕大多數像素滿足以上范圍，而被分類器標注為負，則該樣本被改為正樣本進入動態目標框架。同理，當一個樣本中絕大多數像素不滿足以上范圍，而被分類器標注為正，則該樣本被改為負樣本進入動態目標框架。

其次，人臉的跟蹤有其空間域上的特性，就是目標在一個視頻幀中只可能出現在一個位置。因此，當分類器和約束條件都認可某目標為正，剩余的圖像塊就被認為是負樣本，即本文的約束條件2。

綜上所述，本文的人臉跟蹤算法總結如下：

(1) 在第1幀，手工框定需跟蹤的任意人臉，并以此確定原始的正負樣本集并加入動態目標框架，再利用其訓練原始的極端隨機森林分類器。

(2) 在后續幀，在膚色區域內利用掃描窗口獲取新樣本，并應用在線增量極端隨機森林對其進行標記。然后進入P-N學習模塊，再次確定此樣本的最終標記，并加入動態目標框架。

(3) 在每幀掃描結束后，若有符合約束條件2的樣本，則此樣本的當前位置既為跟蹤的位置。否則，按式(4)計算所有正樣本的最近鄰正樣本相似度，選取值最大的樣本位置作為跟蹤位置，即實現了在線跟蹤。

4實驗結果及分析

根據以上基本的算法思路，在實驗過程中，增加膚色區域搜索、三級變框等實用技巧，獲得了較好的跟蹤準確性和速度。實驗環境為Intel i5-33i7U CPU，4 GB內存，64位操作系統。

具體的實驗步驟如下：

(1) 在出現需跟蹤人臉的時候，框選目標人臉，對框選人臉進行隨機拉伸，旋轉，獲得20個正樣本。在框選區域以外隨機框選20個矩形區域，作為負樣本。將這40個正負樣本RGB圖標準化轉化為20×20的標準像素灰度圖，然后將這些圖轉化為19×19的2 bit特征圖(每2×2個像素組合產生一個2 bit，因此少一維)，以獲得的40個2 bit特征圖為基本數據，建立極端隨機森林分類器。

(2) 從截取人臉的那一幀開始逐幀搜索人臉，每獲取一幀，進行如下操作：

① 膚色區域搜索、三級變框等將RGB圖壓縮為100×100的RGB圖，然后轉化成YCgCr圖，找出Cr∈[Cr0-5,Cr0+5]、Cg∈[Cg0-5,Cg0+5]的所有聯通區域作為膚色區域(下面所有圖中左上角黑白圖區)。按比例還原后，按照每個膚色區域的最邊緣產生方框，作為人臉的搜索區域，有效減少了搜索區域，提高了處理速度。

② 考慮人臉形變和放大縮小，設置三級變框比[1,1;0.8,1;1.3,1;1,0.8;1,1.3]，分別表示不變、長度變窄、長度變寬、寬度變窄、寬度變寬。用上一幀的人臉框的長寬乘以一種邊框比，然后用這個框在所有膚色區域依次掃描獲取框選圖像。用極端隨機森林對每張變框圖像進行快速判斷。每個人臉框，保留其判斷“截圖”，共5個。

③ 對比5個“截圖”，將極端隨機森林判斷最好的截圖作為“當前最好截圖”，并將其2 bit特征圖與之前加入到動態目標框架中的所有樣本進行NCC比較，判斷是否為目標。如果“當前最好截圖”不是目標人臉，則認定沒有檢測到類似人臉區域。若是人臉，再進行如下判斷(含P-N學習和實用技巧)：

a) 由于搜索區域并非完全膚色，因此重新判斷“當前最好截圖”是否依舊符合膚色模型。如不符合，則其作為負樣本，加入增量極端隨機森林，并跳過b)、c)、d)，開始分析下一幀(膚色約束條件，虛線框)。

b) 比較5個“截圖”中NCC判定為正的截圖與“當前最好截圖”的邊框距離。如果超過半個人臉框的距離，則其作為負樣本，加入增量極端隨機森林(唯一性約束條件，虛線框)。

c) 對依舊沒被否定的“截圖”，以其隨機森林判斷結果作為權重，對其截圖位置進行加權平均，得到最終的“加權截圖”。“加權截圖”應該比“當前最好截圖”更好。

d) 如果之前“當前最好截圖”的隨機森林判斷結果中不滿95%的樹同意為人臉，則將“加權截圖”轉化成標準2 bit特征圖，并作為正樣本加入增量極端隨機森林。并且，確定其為當前唯一跟蹤目標位置(實線框)。超過95%同意，則表示“當前最好截圖”跟蹤穩定，也作為當前唯一跟蹤目標位置，但不用加入樣本集。

圖1中各子圖為按照完整算法對單人臉跟蹤的結果，從人臉進入到離開的整個過程中，跟蹤穩定快速。

圖1　完整算法單人臉跟蹤效果圖集

圖2中各子圖為減去P-N學習后的跟蹤結果。可見，缺少了膚色和唯一性兩個約束后，跟蹤基本是不正確和不穩定的。

圖2　無P-N學習的單人臉跟蹤效果圖集

圖3中各子圖為不在動態目標框架進行NCC比較的跟蹤結果，不引入NCC比較，跟蹤速度略有提高，但跟蹤穩定性在總體上不如完整算法。

圖3　無NCC比較的單人臉跟蹤效果圖集

圖4中各子圖為不使用三級邊框時的跟蹤結果，不使用三級變框，會造成跟蹤人臉目標的局部性。

圖4　無三級變框的單人臉跟蹤效果圖集

圖5中各子圖為在學習過程中途，增加其他人臉時，本算法對需跟蹤人臉的跟蹤效果，并且該人臉為側臉，本算法的跟蹤十分穩定。

圖5　完整算法在多人臉中對跟蹤人臉的跟蹤效果圖集

表1為使用完整算法、無P-N學習、無NCC比較、無三級變框和全圖搜索(不是僅在膚色區域搜索)，這五種情況下，視頻中每幀平均處理時間和正確跟蹤率的比較。

表1　五種情況下的幀平均處理速度與正確跟蹤率比較表

綜合考慮跟蹤正確率和速度，本文的完整算法是最優的。在實際應用過程中，一般的實時處理速度要求達到每秒25幀。在用戶認可的誤差范圍內，在本文的完整算法中去掉3級變框或者NCC比較，或者使用更好的處理硬件，可以輕松達到實時跟蹤要求。無P-N學習和全圖搜索的算法則是不能實現跟蹤要求的。可見，本文算法有良好的穩定性和魯棒性。

5結語

本文應用在線的增量式極端隨機森林分類器進行基于檢測的實時跟蹤，在算法中加入了P-N學習提升檢測性能，并提出了動態目標框架的概念。算法綜合應用分類器和P-N學習的結果，以及距離動態目標模型的相似度，確定跟蹤位置，實現任意人臉在線跟蹤。并在算法中加入了應用膚色聯通區域縮小搜索區域、人臉三級變框、加權平均定位等技巧。實驗結果表明，本文算法能夠在不確定背景下對任意人臉實現較長時間段內的穩定快速的實時跟蹤，能夠排除背景和其他人臉的干擾。

本文對目標消失一段時間后再度出現的情況，當目標再次出現后能進行檢測定位，但在目標沒在的時間段內有一定比率的誤測，檢測穩定性不夠。在后續工作中將針對這一應用需求，進一步完善跟蹤處理的算法。

參考文獻

[1] Paul Viola,Micheal Jones.Rapid Object Detection using a Boosted Cascade of Simple Features[C]//Kauai Marriott,Hawaii,Proc of CVPR,2001:511-518.

[2] 鄧亞峰,蘇廣大,傅博.一種基于Adaboost的快速動態人臉檢測算法[J].計算機工程,2006,32(11):222-224.

[3] 王娟,劉教民,孟軍英,等.改進的均值漂移算法在運動目標跟蹤中的研究[J].系統仿真學報,2012,24(9):1896-1899.

[4] 姚海濤,朱福喜,陳海強.一種自適應的PSO粒子濾波人臉視頻跟蹤算法[J].武漢大學學報,2012,37(4):492-495.

[5] Leo Breiman.Random Forests[J].Machine Learning,2001,45(1):5-32.

[6] 劉足華,熊惠霖.基于隨機森林的目標檢測與定位[J].計算機工程,2012,38(13):5-8.

[7] Pierre Geurts,Damien Ernst,Louis Wehenkel.Extremely Randomized Trees[J].Machine Learning,2006,63(2):3-42.

[8] Zdenek Kalal,Tiri Matas,Krystian Mikolajczyk.P-N Learning:Boosrapping Binary Classifiers y Structural Constraints[C]//VCPR2010 proceedings,2010:49-56.

[9] 陳勇飛,劉新民.基于膚色和類Harr特征的人臉圖像的人眼檢測[J].計算機工程與應用,2008,44(33):174-176.

[10] 丁友東,杜曉鳳,李曉強.基于聚類膚色模型的人臉檢測[J].上海大學學報,2007,13(5):511-515.

[11] Rachid Belaroussi,Maurice Milgram.A Comparative Study on Face Detection and Tracking Algorithm[J].Expert System with Applications,2012,39(12):7158-7164.

[12] 王愛平,萬國偉,程志全,等.支持在線學習的增量式極端隨機森林分類器[J].軟件學報,2011,22(9):2059-2074.

REAL-TIME FACE TRACKING ALGORITHM BASED ON ONLINE INCREMENTAL LEARNING

Bao Fang1,2Zhang Yankai1,2,3Wang Shitong3

1(JiangyinPolytechnicCollege,Jiangyin214400,Jiangsu,China)2(InformationIntelligenceFusionResearchEngineeringCenterofJiangsu,Jiangyin214400,Jiangsu,China)3(JiangnanUniversity,Wuxi214000,Jiangsu,China)

AbstractThe paper proposes a real-time face tracking algorithm, which is based on online incremental extremely random forests classifier. The algorithm achieves detection-based real-time tracking using online incremental extremely random forests classifier, and combines dynamic target framework and P-N learning to correct detection errors. Experimental results show, the proposed algorithm can realise fast and stable real-time tracking for any face in a longer period under uncertain background, and can effectively overcome interferences such as background with preferable effect.

KeywordsOnline incremental learningExtremely random forestsP-N learningDynamic target frameworkReal-time face tracking

收稿日期：2014-10-16。江蘇省自然科學基金項目(BK2012128)。包芳，教授，主研領域：人工智能模式識別，神經網絡，模糊系統，在線學習。張炎凱，碩士生。王士同，教授。

中圖分類號TP391.4

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.067