胡章芳,秦陽(yáng)鴻

重慶郵電大學(xué) 光電信息感測(cè)與傳輸技術(shù)重點(diǎn)實(shí)驗(yàn)室, 重慶 400065)(*通信作者電子郵箱chinaqinyh@163.com)

基于圖割理論的尺度自適應(yīng)人臉跟蹤算法

胡章芳,秦陽(yáng)鴻*

重慶郵電大學(xué) 光電信息感測(cè)與傳輸技術(shù)重點(diǎn)實(shí)驗(yàn)室, 重慶 400065)(*通信作者電子郵箱chinaqinyh@163.com)

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

圖割;Camshift算法;目標(biāo)跟蹤;真實(shí)尺度;最大流

0 引言

基于視覺的人臉識(shí)別是人機(jī)交互領(lǐng)域的一個(gè)重要研究課題[1]。這種交互方式自然、直觀,其具有廣泛的應(yīng)用前景。

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

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

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

1 Camshift算法

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

1)初始化,手動(dòng)選擇目標(biāo),得到搜索窗W。

2)計(jì)算跟蹤目標(biāo)反向投影圖。

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

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

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

2 基于圖割的匹配算法

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

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

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

(1)

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

3 改進(jìn)的人臉跟蹤算法

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

3.1 目標(biāo)分割

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

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

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

圖1 圖割示意圖

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

(2)

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

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

(3)

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

圖2 膚色團(tuán)分割示意圖

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

3.2 尺度提取

為了防止頸部膚色的干擾使尺度偏大,本文選擇膚色團(tuán)塊橫坐標(biāo)計(jì)算尺度。

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

通過像素點(diǎn)的四領(lǐng)域判斷圖連通性,來判斷周圍像素點(diǎn)是否是膚色點(diǎn),并將膚色點(diǎn)集標(biāo)記為膚色團(tuán)塊。而團(tuán)塊中膚色最多的即為最大團(tuán)塊。

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

3.3 本文算法基本步驟

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

1)手動(dòng)選取跟蹤目標(biāo),得到目標(biāo)的長(zhǎng)為h0,寬為w0;

2)執(zhí)行Camshift,計(jì)算目標(biāo)中心(xc,yc)，同時(shí)計(jì)算出當(dāng)前搜索框長(zhǎng)為h1,寬為w1;

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

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

5)當(dāng)膚色點(diǎn)對(duì)比結(jié)果小于1/4,則計(jì)算膚色團(tuán)的長(zhǎng)w=x2-x1,寬h=w(h0/w0);

6)得出當(dāng)前跟蹤目標(biāo)真實(shí)尺度;

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

4 實(shí)驗(yàn)與分析

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

)

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

[2] 呂卓紋, 王科俊, 李宏宇, 等.融合Camshift的在線Adaboost目標(biāo)跟蹤算法[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 王鑫, 唐振民. 一種改進(jìn)的基于Camshift的粒子濾波實(shí)時(shí)目標(biāo)跟蹤算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 2010, 15(10): 1507-1514.(WANGX,TANGZM.Animprovedcamshaftbasedparticlefilteralgorithm,forreal-timetargettraking[J].JournalofImageandGraphics, 2010, 15(10): 1507-1514.)

[6] 厲丹, 田雋, 肖理慶, 等. 基于Camshift自適應(yīng)多特征模板的視頻目標(biāo)跟蹤[J]. 煤炭學(xué)報(bào), 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] 姜偉, 呂曉琪, 任曉穎, 等.結(jié)合區(qū)域生長(zhǎng)與圖割算法的冠狀動(dòng)脈CT血管造影圖像三維分割[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(5):1462-1466.(JIANGW,LYUXQ,RENXY,etal. 3Dsegmentationmethodcombiningregiongrowingandgraphcutforcoronaryarteriescomputedtomographyangiographyimage[J].JournalofComputerApplications, 2015, 35(5):1462-1466.)

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

[11] 張鳳軍, 趙嶺, 安國(guó)成, 等.一種尺度自適應(yīng)的Mean-Shift跟蹤算法[J]. 計(jì)算機(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] 段丁娜, 張歡, 邱陳輝, 等. 基于活動(dòng)輪廓模型的圖像分割算法綜述[J]. 中國(guó)生物醫(yī)學(xué)工程學(xué)報(bào), 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。 基金項(xiàng)目:重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ130512)。

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

1001- 9081(2017)04- 1189- 04

10.11772/j.issn.1001- 9081.2017.04.1189

TP

A