基于圖割理論的尺度自適應人臉跟蹤算法

胡章芳,秦陽鴻

重慶郵電大學 光電信息感測與傳輸技術重點實驗室, 重慶 400065)(*通信作者電子郵箱chinaqinyh@163.com)

基于圖割理論的尺度自適應人臉跟蹤算法

胡章芳,秦陽鴻*

重慶郵電大學 光電信息感測與傳輸技術重點實驗室, 重慶 400065)(*通信作者電子郵箱chinaqinyh@163.com)

針對連續(xù)自適應的Mean-Shift(Camshift)算法跟蹤人臉時尺度過度放縮這一問題,提出了一種基于圖割的Camshift人臉跟蹤算法。首先,在每一幀圖像的Camshift迭代結果內建立圖割區(qū)域,使用高斯膚色模型作為圖割權值分割出圖割區(qū)域內膚色團塊;然后,計算該膚色團大小得到目標真實尺度,并比較與上一幀圖像跟蹤框內膚色團的尺度來判斷是否需要重新跟蹤目標;最后,再以該團塊作為下一幀跟蹤目標。實驗結果表明,基于圖割的Camshift人臉跟蹤算法有效地克服了跟蹤時其他膚色區(qū)域的干擾,能有效地反映人體快速運動中人臉真實尺度變化,同時防止Camshift算法丟失跟蹤目標而陷入局部最優(yōu)解,具有較好的可用性和魯棒性。

圖割;Camshift算法;目標跟蹤;真實尺度;最大流

0 引言

基于視覺的人臉識別是人機交互領域的一個重要研究課題[1]。這種交互方式自然、直觀,其具有廣泛的應用前景。

連續(xù)自適應的Mean-Shift(Continuously Adaptive Mean-Shift, Camshift)是一種常用的跟蹤算法,在跟蹤過程中容易出現(xiàn)窗口尺度過度放縮問題[2]。在Camshift算法中,跟蹤窗口直接影響跟蹤結果,如果跟蹤窗口不能真實反映目標實際尺度的變化,可能會導致丟失跟蹤目標。尺度控制問題決定了Camshift算法的魯棒性。

國內外許多研究學者對跟蹤窗口尺度控制開展了研究。由Li等[3]提出的SURF(Speeded Up Robust Features)融合進Camshift算法有效地跟蹤復雜背景中的目標,但是在跟蹤目標尺度發(fā)生劇烈變化時,容易丟失目標。還有一些基于這種思想的改進方法,如徐建軍等[4]提出了融合Adaboost(Adaptive Boostint)算法來保證跟蹤目標的真實尺度,但是該算法要提取每一幀圖像加入分類器中,導致計算量過大,跟蹤效率大大降低；王鑫等[5]提出將粒子濾波融合Camshift算法中來計算跟蹤窗口大小,該方法能較好地反映真實尺度,但是粒子數(shù)會影響跟蹤效果,粒子數(shù)過低會丟失跟蹤目標,而隨著粒子數(shù)增加,算法運算量也會增加。

為了克服以上算法的不足,本文提出將圖割算法融入Camshift中解決尺度放縮這一問題。首先利用Camshift跟蹤目標得到跟蹤目標位置,再使用跟蹤框內的像素點構造圖割網(wǎng)絡,通過能量函數(shù)計算跟蹤框范圍內的最大流完成圖割。圖割算法使用高斯膚色模型作為能量函數(shù)權值,然后在跟蹤窗口內分割出膚色團塊,最大團塊即是跟蹤目標。實驗結果表明,本文算法實時反映了跟蹤目標的真實尺度,同時實現(xiàn)了實時的、快速的跟蹤。

1 Camshift算法

Camshift是一種使用顏色信息的跟蹤算法,通過提取HSV顏色空間的H分量分布圖進行跟蹤[6]。它的算法流程如下:

1)初始化,手動選擇目標,得到搜索窗W。

2)計算跟蹤目標反向投影圖。

3)根據(jù)反向投影圖和選擇框進行Meanshift迭代,找到跟蹤目標中心。

4)根據(jù)上述搜索窗內的顏色概率分布函數(shù)來重新設定搜索窗的大小。

5)使用迭代出的結果作為跟蹤目標在下一幀圖像中繼續(xù)跟蹤。

2 基于圖割的匹配算法

圖割是基于圖的重新組合和優(yōu)化的思想[7],將一幅圖像中的像素點映射為一個網(wǎng)絡圖,并建立關于標號的能量函數(shù)[8]。由最大流最小割定理可知:可以通過圖像中像素所構造出來的網(wǎng)絡最大流來得到圖的最小割。首先需要構造成能量函數(shù),再將像素點代表的權值代入能量函數(shù)中構造圖像網(wǎng)絡才能得到最大流[9-11]。

設有向圖用G=(V,E)表示,其中V代表圖中節(jié)點的集合。節(jié)點分為兩類:普通節(jié)點P={Pi|i=1,2,…,n}；端節(jié)點S和T，S為前景目標,T為背景。E={(u,v)|u∈P,v∈P}代表圖中邊的集合,每條邊都設有權值ω(u,v)。圖割就是將邊的權值帶入能量函數(shù)中通過計算結果使圖中節(jié)點劃分為兩部分s和t,而分割結果則需要滿足s∈S,t∈T,S∪T=E,S∩T=?。這些邊組成割集S-T,最小割就是割集S-T中邊的權值之和最小的割[12]。

要分割出“目標”,先引入能量函數(shù):

(1)

其中:P表示圖像中像素點的點集;N表示S的鄰域系統(tǒng);Api表示像素Pi的權值,即若用1來表示屬于前景目標,那么就用0來表示背景;Rpi(Api)和δ(Api,Apj) 分別表示將元素pi和邊(pi,pj)標號為目標的權值[13]?？梢酝ㄟ^求得能量函數(shù)最小值來得到最符合真實情況的圖像分割即是目標最小割[14-15]。于是構造能量函數(shù)是圖割應用在目標分割上的一個關鍵步驟。

3 改進的人臉跟蹤算法

在目標跟蹤研究中,Camshift算法具有很強跟蹤性能,被廣泛應用于各種視頻跟蹤系統(tǒng)中。但是當跟蹤目標尺度發(fā)生劇烈變化時,跟蹤窗口就可能出現(xiàn)過度放縮,甚至會丟失跟蹤目標。而圖割理論在圖像分割領域有著較強的分割性能,可以準確分割出跟蹤目標與背景。因此,在Camshift跟蹤出的結果中引入圖割理論,能準確分割出Camshift跟蹤框內真實的跟蹤目標,同時計算出該目標真實大小和位置。

3.1 目標分割

鑒于全局圖割會加大運算量,本文采用局部圖割,使用Camshift迭代出的跟蹤窗口W作為圖割區(qū)域。這種方法不僅提高了算法效率,同時防止了跟蹤場景中膚色相近區(qū)域的干擾。

系統(tǒng)運行Camshift算法后,會產(chǎn)生一個長為h0,寬為w0的初始跟蹤框,其跟蹤中心為(xc,yc)。在跟蹤中心點縱向擴展M(M

跟蹤中心(xc,yc)作為源點S,Camshift跟蹤框內像素點作為有向圖中普通節(jié)點,而其他點作為背景節(jié)點,所以圖割結果就是跟蹤目標和背景的兩個割,如圖1所示。

圖1 圖割示意圖

為了求取精確膚色模型來表示膚色的分布,本文使用高斯膚色模型來作為圖割算法的分割權值,公式如下:

(2)

其中:K代表高斯混合模型中高斯模型個數(shù);Wi表示第i個高斯所占權重值,所有Wi值之和是1；r表示高斯分布的方差;μ表示高斯分布的均值；Σi表示第i個高斯分布的共變異矩陣。式(2)代表參數(shù)(ω,μ,Σ)可用k均值算法來求得,而得到像素點的膚色判斷概率值。

此時把高斯膚色賦值給從點S到每個普通節(jié)點的邊W(pi)上,而相鄰普通節(jié)點之間的權值則為W(pi,pj)。因此能量函數(shù)可以構造如下:

(3)

其中:P表示普通節(jié)點的點集;N表示S的鄰域系統(tǒng)即跟蹤區(qū)域;W(pi)和W(pi,pj)分別表示將元素pi和邊(pi,pj)劃分為目標的代價。計算W中的每個像素的W(pi)和W(pi,pj)。該網(wǎng)絡中E(O)的最大流既是通割集S-T中邊的權值之和最小的割,而分割出的膚色團,也就是跟蹤目標真實位置的點集,如圖2所示。

圖2 膚色團分割示意圖

記錄該幀搜索框內膚色點的數(shù)量,并與上一幀中膚色點數(shù)量比較。當相鄰兩幀膚色點數(shù)差距過大,即可判斷出已丟失跟蹤目標,重新使用該幀運行Camshift算法搜索跟蹤目標。

3.2 尺度提取

為了防止頸部膚色的干擾使尺度偏大,本文選擇膚色團塊橫坐標計算尺度。

在整個視頻區(qū)域內建立坐標系,坐標原點為視頻區(qū)域中的左上角,數(shù)字圖像的列數(shù)和行數(shù)代表坐標系中Y軸和X軸。

通過像素點的四領域判斷圖連通性,來判斷周圍像素點是否是膚色點,并將膚色點集標記為膚色團塊。而團塊中膚色最多的即為最大團塊。

在膚色團內找出中心點處(xc,yc)中yc對應的最左側的像素點的坐標為(x1,yc),然后取出yc+i,yc-i(i=1,2,…,h0)在膚色團中所對應的2h0個橫坐標值,求出x1和這2h0個橫坐標值的均值賦給x1。同時,膚色團最右邊的x2也可用此方法得出,于是得出膚色團的長度w=x2-x1。由于人臉大小的比例是不變的,本文通過計算手動標記的人臉比例大小h0/w0,可以計算出膚色團的高度h=w(h0/w0),于是得到目標真實尺度。

3.3 本文算法基本步驟

本文提出的基于圖割的人臉跟蹤算法步驟如下:

1)手動選取跟蹤目標,得到目標的長為h0,寬為w0;

2)執(zhí)行Camshift,計算目標中心(xc,yc)，同時計算出當前搜索框長為h1,寬為w1;

3)在搜索框區(qū)域內,由跟蹤中心(xc,yc)上下擴展位置作為圖割區(qū)域;

4)比較當前幀與上一幀膚色點數(shù)量,若數(shù)量相差大于上一幀膚色點數(shù)量的1/4,則判斷丟失跟蹤目標,重新執(zhí)行Camshift搜索跟蹤目標;

5)當膚色點對比結果小于1/4,則計算膚色團的長w=x2-x1,寬h=w(h0/w0);

6)得出當前跟蹤目標真實尺度;

7)繼續(xù)讀取下一幀,執(zhí)行步驟2)～5)。

4 實驗與分析

本實驗在Corei3-3220@3.30GHz,內存4.00GB的計算機上采用C++語言編程實現(xiàn)。實驗采用的視頻序列分辨率為320×240。實驗比較Camshift算法、融合粒子濾波的Camshift算法，以及本文算法的跟蹤效率和性能。

從圖3所示的跟蹤情況可看出不同算法的性能：圖3(a)中在第46幀出現(xiàn)了過度放縮,算法跟蹤了臉部以下的區(qū)域；在第99幀出現(xiàn)了手部干擾,使跟蹤框放大到手部區(qū)域。圖3(b)中在第112幀處發(fā)生了丟失跟蹤目標。圖3(c)實時地反映了目標的真實尺度,同時也避免了手出現(xiàn)在跟蹤場景中的干擾。

圖3 三種算法下人臉跟蹤情況

圖4顯示了三種算法來跟蹤人臉的性能圖。中心誤差是跟蹤結果與真實位置之間的歐氏距離,其值越小說明算法尺度控制性能越好。從圖4可以看出,基于圖割的Camshift算法在運行過程中,跟蹤的結果與目標真實坐標之間的差距較小,其尺度控制的性能較為穩(wěn)定；而Camshift算法在控制方面性能相對低,當視頻中出現(xiàn)手的干擾時,跟蹤框遠遠大于人臉真實尺度；而融合粒子濾波的Camshift算法相較本文算法在跟蹤目標時的跟蹤框與真實位置之間的距離也大于本文算法,因此本文算法能有效地反映人體快速運動中人臉真實尺度變化。

本文的基于圖割的Camshift跟蹤算法,由于采用了局部圖割,計算量很小,跟蹤目標單幀用時0.121s；融合粒子濾波的Camshift算法單幀用時相對較長,需要0.231s；而Camshift算法計算時間雖然比本文算法短,僅為0.023s,但是跟蹤性能遠不如本文算法。

圖4 三種算法下人臉跟蹤性能圖

5 結語

Camshift算法具有計算量小、抵抗目標形變、反應迅速等優(yōu)點被很多研究人員應用到目標跟蹤中,但其跟蹤性能被尺度過度放縮這一問題所影響。本文提出的基于圖割的Camshift跟蹤算法根據(jù)圖割出的目標來計算尺度,從而得到目標的真實尺度,并且保證了算法的運算速度。從實驗結果可知:基于圖割的Camshift跟蹤算法能有效地反映跟蹤目標真實的尺度變化。

)

[1]HUZ,WANGY,LUOY.Animprovedcamshift-basedparticlefilteralgorithmforreal-timehandgesturetracking[J].Sensors&Transducers, 2014, 177(8):307-312.

[2] 呂卓紋, 王科俊, 李宏宇, 等.融合Camshift的在線Adaboost目標跟蹤算法[J]. 中南大學學報(自然科學版), 2013, 44(7):231-238.(LYUZW,WANGKJ,LIHY,etal.OnlineAdaboosttargettrakingalgorithmcombinedfusedwithCamshift[J].JournalofCentralSouthUniversity(ScienceandTechnology), 2013, 44(7):231-238.)

[3]LIJ,ZHANGJ,ZHOUZ,etal.ObjecttrackingusingimprovedCamshiftwithSURFmethod[C]//Proceedingsofthe2011IEEEInternationalWorkshoponOpen-sourceSoftwareforScientificComputation.Piscataway,NJ:IEEE, 2011:136-141.

[4] 徐建軍, 張蓉, 畢篤彥, 等. 一種新的AdaBoost視頻跟蹤算法[J]. 控制與決策, 2012, 27(5):681-685.(XUJJ,ZHANGR,BIDY,etal.AnnewAdaBoostvideotrackingalgorithm[J].ControlandDecision, 2012, 27(5):681-685.)

[5] 王鑫, 唐振民. 一種改進的基于Camshift的粒子濾波實時目標跟蹤算法[J]. 中國圖象圖形學報, 2010, 15(10): 1507-1514.(WANGX,TANGZM.Animprovedcamshaftbasedparticlefilteralgorithm,forreal-timetargettraking[J].JournalofImageandGraphics, 2010, 15(10): 1507-1514.)

[6] 厲丹, 田雋, 肖理慶, 等. 基于Camshift自適應多特征模板的視頻目標跟蹤[J]. 煤炭學報, 2013, 38(7): 1299-1304.(LID,TIANX,XIAOLQ,etal.Adaptivemulti-featuretemplatevideotargettrackingbasedonCamshiftalgorithm[J].JournalofChinaCoalSociety, 2013, 38(7): 1299-1304.)

[7]KOLMOGOROVV,BOYKOVY,ROTHERC.Applicationsofparametricmaxflowincomputervision[C]//ICCV2007:Proceedingsofthe2007IEEE11thInternationalConferenceonComputerVision.Piscataway,NJ:IEEE, 2007:1-8.

[8]PRICEBL,MORSEB,COHENS.Geodesicgraphcutforinteractiveimagesegmentation[C]//Proceedingsofthe2010IEEEConferenceonComputerVisionandPatternRecognition.Piscataway,NJ:IEEE, 2010: 3161-3168.

[9] 姜偉, 呂曉琪, 任曉穎, 等.結合區(qū)域生長與圖割算法的冠狀動脈CT血管造影圖像三維分割[J]. 計算機應用, 2015, 35(5):1462-1466.(JIANGW,LYUXQ,RENXY,etal. 3Dsegmentationmethodcombiningregiongrowingandgraphcutforcoronaryarteriescomputedtomographyangiographyimage[J].JournalofComputerApplications, 2015, 35(5):1462-1466.)

[10] 張少娟, 鄒建成.圖割綜述[J]. 北方工業(yè)大學學報, 2010, 22(3):10-16.(ZHANGSJ,ZOUJC.Reviewongraphcuts[J].JournalofNorthChinaUniversityofTechnology, 2010, 22(3):10-16.)

[11] 張鳳軍, 趙嶺, 安國成, 等.一種尺度自適應的Mean-Shift跟蹤算法[J]. 計算機研究與發(fā)展, 2014, 51(1):215-224.(ZHANGFJ,ZHAOL,ANGC,etal.Mean-Shifttrackingalgorithmwithscaleadaptation[J].JournalofComputerResearchandDevelopment, 2014, 51(1):215-224.)

[12]JUANO,BOYKOVY.Activegraphcuts[C]//Proceedingsofthe2006IEEEConferenceonComputerVisionandPatternRecognition.Washington,DC:IEEEComputerSociety, 2006:1023-1029.

[13]STAWIASKIJ,DECENCIEREE.Regionmergingviagraph-cuts[J].ImageAnalysis&Stereology, 2008, 27(1):39-45.

[14]COOKET.Twoapplicationsofgraph-cutstoimageprocessing[C]//DICTA2008:Proceedingsofthe2008DigitalImageComputing:TechniquesandApplications.Washington,DC:IEEEComputerSociety, 2008:498-504.

[15] 段丁娜, 張歡, 邱陳輝, 等. 基于活動輪廓模型的圖像分割算法綜述[J]. 中國生物醫(yī)學工程學報, 2015, 34(4):445-454.(DUANDN,ZHANGH,QIUCH,etal.Areviewofactivecontourmodelbasedimagesegmentationalgorithms[J].ChineseJournalofBiomedicalEngineering, 2015, 34(4):445-454.)

ThisworkispartiallysupportedbytheScientificandTechnologicalResearchProgramofChongqingMunicipalEducationCommission(KJ130512).

HU Zhangfang, born in 1967, M. S., associate professor. Her research interests include communication and information system.

QIN Yanghong, born in 1992, M. S. candidate. His research interests include image processing, pattern recognition.

Scale-adaptivefacetrackingalgorithmbasedongraphcutstheory

HUZhangfang,QINYanghong*

(KeyLaboratoryofOptoelectronicInformationSensingandTransmissionTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

Aiming at the problem of the excessive size-changing while the tracking window is enlarged by traditional Continuously Adaptive MeanShift (Camshift) algorithm in face tracking, an adaptive window face tracking method for Camshift based on graph cuts theory was proposed. Firstly, a graph cut area was created according to the Camshift iteration result of every frame by using graph cuts theory, and the skin lump was found by using Gaussian mixture model as weights of graph cuts. As a result, the tracking window could be updated by the skin lump. Then the real size of the target was obtained by computing the size of skin lump, and whether the target needed to be re-tracked was determined by comparing the size of the skin lump in the tracking window with that in the previous frame. Finally, the skin lump in last frame was used as the tracking target of the next frame. The experimental results demonstrate that the proposed method based on graph cuts can avoid interference of other skin color targets in the background, which effectively reflects the real face size-changing of the human body in rapid movement, and prevents the Camshift algorithm from losing the tracking target and falling into the local optimal solution with good usability and robustness.

graph cuts; Camshift algorithm; target tracking; true measure;max-flow

2016- 08- 31;

2016- 12- 23。 基金項目:重慶市教委科學技術研究項目(KJ130512)。

胡章芳(1969—),女,重慶人,副教授,碩士,主要研究方向:通信與信息系統(tǒng); 秦陽鴻(1992—),男,重慶人,碩士研究生,主要研究方向:圖像處理、模式識別。

1001- 9081(2017)04- 1189- 04

10.11772/j.issn.1001- 9081.2017.04.1189

TP

A