基于二階直方圖的改進(jìn)型均值偏移跟蹤算法

陳善靜,楊 華,曾 凱,杜石明,張 紅

(1.脈沖功率激光技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,安徽合肥 230037;2.電子工程學(xué)院,安徽省紅外與低溫等離子體重點(diǎn)實(shí)驗(yàn)室,安徽合肥 230037;3.電子工程學(xué)院物理教研室,安徽合肥 230037)

0 引言

近年來在目標(biāo)跟蹤領(lǐng)域,以無參數(shù)核密度估計(jì)為基礎(chǔ)的均值偏移算法以其算法簡單、收斂速度快、目標(biāo)跟蹤準(zhǔn)確等優(yōu)勢(shì)而越來越受到大家的重視[1]。均值偏移算法又叫Mean-shift算法,是一種以目標(biāo)的顏色直方圖為特征的自適應(yīng)梯度搜索匹配跟蹤算法。它從任意一點(diǎn)出發(fā),以顏色直方圖的相似性最大為原則沿著核密度的梯度上升方向,以自適應(yīng)的步長進(jìn)行搜索[2-3],最終收斂于核密度估計(jì)函數(shù)的局部極大值處即目標(biāo)的真實(shí)位置。

但是由于顏色直方圖描述的是目標(biāo)的全局統(tǒng)計(jì)信息,忽略了目標(biāo)像素間的空間結(jié)構(gòu)信息,當(dāng)兩個(gè)顏色分布相似但空間結(jié)構(gòu)不一樣的目標(biāo)出現(xiàn)時(shí),Mean-shift跟蹤算法不能區(qū)別兩個(gè)目標(biāo),容易導(dǎo)致跟蹤失敗。為此,學(xué)者們提出了新的改進(jìn)方法。文獻(xiàn)[4—5]提出了描述目標(biāo)的特征稱為空間-顏色特征,不但考慮目標(biāo)像素點(diǎn)的顏色信息,而且還考慮像素點(diǎn)之間的空間關(guān)系。這種特征的跟蹤算法能較好地區(qū)別目標(biāo)。文獻(xiàn)[6]提出了融合顏色和邊緣信息的跟蹤算法取得了較好的跟蹤效果。但這種算法計(jì)算比較費(fèi)時(shí),或者被限制到單一的形狀模型。文獻(xiàn)[7]提出利用邊緣方位柱狀圖進(jìn)行跟蹤,這種邊緣特征計(jì)算有效而且不易受光照變化的影響,能提供比單一輪廓更豐富的特征,但是這種算法在利用Sobel算子或Prewitt算子等邊緣梯度算子求邊緣特征的時(shí)候,很容易受背景的影響,邊緣特征十分不穩(wěn)定。為了提高均值偏移算法的穩(wěn)定性和抗局部遮擋能力,本文提出了基于二階直方圖的均值偏移算法。

1 均值偏移原理和二階直方圖基本概念

1.1 均值偏移基本原理

假設(shè)d維空間Rd中的樣本集合{xi}i=1,…,n,在點(diǎn) x處,使用有界核函數(shù) K(x),窗半徑 h的多變量核密度估計(jì)由式(1)計(jì)算

定義函數(shù)g(x)=-k′(x)。由g(x)可以導(dǎo)出新的核G(x)=Cg(‖x‖2),C是歸一化因子。由該核函數(shù)的多變量密度估計(jì)可以推導(dǎo)出

‖?‖為歐式距離。進(jìn)而可以得到核密度梯度估計(jì)

式中

式(4)被稱為mean-shift向量。它表明在x處,使用核G計(jì)算的mean-shift向量正比于使用核K得到的歸一化的密度梯度估計(jì)。歸一化要依靠使用核G計(jì)算的x處的密度估計(jì)。因此mean-shift向量總是指向密度增大的最大方向。反復(fù)地進(jìn)行如下兩步,就是mean-shift過程:

1)計(jì)算 mean-shift向量Mh,G(x);

2)用Mh,G(x)平移核G(x)

1.2 二階直方圖基本概念

二階直方圖又叫空間顏色柱狀圖(Spatiograms),它是對(duì)顏色直方圖的一種改進(jìn)直方圖,它以顏色直方圖為基礎(chǔ)。顏色直方圖只包含了顏色分布信息,而二階直方圖在包含顏色信息的前提下包含了像素的顏色空間均值向量和顏色空間協(xié)方差矩陣。二階直方圖與顏色直方圖相比不僅考慮像素點(diǎn)的顏色值并且考慮像素點(diǎn)間的空間關(guān)系,包含更豐富的目標(biāo)信息。所以抗干擾性和抗局部遮擋能力更強(qiáng)和受光照影響更小,魯棒性更強(qiáng)[8]。

顏色空間均值向量表示為:

顏色空間協(xié)方差矩陣為:

2 二階顏色直方圖對(duì)均值偏移算法的改進(jìn)

2.1 顏色直方圖Bhattacharyya系數(shù)

一階顏色直方圖即顏色直方圖,一般而言圖像像素的值域是RGB顏色空間,按照直方圖的方式將RGB顏色空間的每個(gè)子空間R、G或者B空間分成k個(gè)相等的空間,每個(gè)空間稱為一個(gè)bin,構(gòu)成特征空間,特征空間中特征值的個(gè)數(shù)(即 bin的個(gè)數(shù))為m=k3。

在mean-shift跟蹤算法中,用Bhattacharyya系數(shù)作為相似性函數(shù),其定義為:

δ[b(x i)-u]表示候選目標(biāo)的顏色直方圖特征。Bhattacharyya系數(shù)的值在0～1之間,其值越大表示兩個(gè)模型越相似,如圖1所示。

2.2 基于二階顏色直方均值偏移向量

二階直方圖是一種包含了圖像像素的顏色、空間分布信息的統(tǒng)計(jì)特征表示方法。與一階的顏色直方圖相比它包含了顏色空間均值向量和顏色空間協(xié)方差矩陣,如圖2所示。

因此利用二階直方圖改進(jìn)的Bhattacharyya系數(shù)可以表示為:

圖1 顏色直方圖Fig.1 Color histogram

圖2 融合顏色空間分布的顏色直方圖Fig.2 Color histogram fusing color spatial distribution

由基于二階直方圖的均值偏移向量可以得到目標(biāo)的跟蹤點(diǎn)為:

3 基于二階直方圖的均值偏移向量的可行性證明

由均值偏移算法跟蹤算法的基本原理可知,二階直方圖的均值偏移向量只有在指向融入顏色空間均值向量和顏色空間協(xié)方差矩陣的Bhattacharyya系數(shù)梯度變化最大值時(shí),跟蹤算法才能快速收斂到跟蹤目標(biāo)真實(shí)位置上。因此下面我們將從理論上證明二階直方圖的均值偏移向量的方向?yàn)榛诙A直方圖的Bhattacharyya系數(shù)梯度變化最大值的方向。首先對(duì)包含二階直方圖的Bhattacharyya系數(shù)在p(y0)和θ(y 0)處做二階泰勒級(jí)數(shù)展開:

將wu代入上兩式分別求導(dǎo)得

4 仿真驗(yàn)證

為了驗(yàn)證本文改進(jìn)后算法的優(yōu)越性,通過計(jì)算機(jī)編程進(jìn)行了模擬實(shí)驗(yàn)。在實(shí)驗(yàn)中,電腦配置為P4 2.8 GHz CPU,512 MB內(nèi)存,Windows XP操作系統(tǒng)和VC++6.0的開發(fā)平臺(tái)。其中k=16,為了對(duì)比跟蹤下效果,把mean-shift跟蹤算法模塊與改進(jìn)后的二階直方圖跟蹤算法模塊做到了一個(gè)程序里。初始幀時(shí)通過手動(dòng)選取視頻圖像中的目標(biāo)建立目標(biāo)模板,以后兩種算法從同一坐標(biāo)位置開始各自的跟蹤運(yùn)算。其中黑色框?yàn)槭褂胢ean-shift跟蹤算法跟蹤到的目標(biāo)位置,白色框?yàn)槭褂枚A直方圖跟蹤算法得到的目標(biāo)位置。圖3為兩種跟蹤算法的跟蹤效果對(duì)比圖。

圖3 Mean-shift跟蹤算法與基于二階直方圖改進(jìn)型跟蹤算法跟蹤效果對(duì)比圖Fig.3 Comparative picture of mean-shift tracking algorithm and the improved tracking algorithm based on second order histogram tracking effect

通過觀察對(duì)比圖3兩種跟蹤算法的效果圖可以發(fā)現(xiàn):

1)基于二階直方圖的改進(jìn)型mean-shift跟蹤算法的抗局部遮擋能力明顯比未改進(jìn)的mean-shift算法抗局部遮擋能力強(qiáng)。

2)在圖3的第140幀處跟蹤目標(biāo)已經(jīng)大部分被書遮擋,此時(shí)的mean-shift跟蹤算法整個(gè)跟蹤區(qū)域內(nèi)只有小部分真實(shí)目標(biāo)顏色相近,整個(gè) Bhattacharyya系數(shù)受到較大影響,降低到0.4～0.5左右,不能準(zhǔn)確定位目標(biāo)。基于二階直方圖的改進(jìn)型mean-shift跟蹤算法此時(shí)在跟蹤區(qū)域內(nèi)也只有較小的一部分真實(shí)目標(biāo)顏色相近,這塊小的藍(lán)色目標(biāo)區(qū)域集中分布在跟蹤框的左下部,而選擇的目標(biāo)模板的左下部同樣為藍(lán)色,此時(shí)跟蹤框左下部區(qū)域與模板左下部區(qū)域正好匹配,在程序中由顏色空間均值向量和顏色空間協(xié)方差矩陣所決定的w u對(duì)Bhattacharyya系數(shù)進(jìn)行了修正,提高了Bhattacharyya系數(shù)的數(shù)值,增加了定位的準(zhǔn)確性。

3)在圖3第180幀是可以看到使用wu修正后的Bhattacharyya系數(shù)即使在只有很小的一塊區(qū)域與模板顏色相同且此區(qū)域空間分布與模板相近時(shí)跟蹤框都能跟蹤上目標(biāo)。

4)在圖3第280幀時(shí)可以看到基于二階直方圖的改進(jìn)型 mean-shift跟蹤算法同樣保持了 meanshift算法優(yōu)良的收斂性,當(dāng)遮擋消失后跟蹤框能很快地移動(dòng)到跟蹤目標(biāo)上,準(zhǔn)確地跟蹤目標(biāo)。

通過觀察對(duì)比圖4—圖6兩種跟蹤算法中的Bhattacharyya系數(shù)隨時(shí)間變化和在140幀圖像時(shí)Bhattacharyya系數(shù)空間分布可以發(fā)現(xiàn):

1)圖4為Bhattacharyya系數(shù)隨時(shí)間變化曲線,從圖中可以看出,在100幀處,跟蹤目標(biāo)開始被桌面的書部分遮擋,傳統(tǒng)的mean-shift跟蹤算法的Bhattacharyya系數(shù)在此時(shí)快速下降,當(dāng)基于二階直方圖的mean-shift跟蹤算法由于包含顏色空間分布信息,即使被嚴(yán)重遮擋時(shí)候Bhattacharyya系數(shù)變化也比較小。

2)圖5、圖6為第140幀時(shí)目標(biāo)區(qū)域Bhattacharyya系數(shù)空間分布情況圖,由圖3可見,在第140幀時(shí)目標(biāo)受到嚴(yán)重遮擋,傳統(tǒng)的mean-shift跟蹤算法的Bhattacharyya系數(shù)在目標(biāo)區(qū)域普遍較低,而基于二階直方圖的mean-shift跟蹤算法的Bhattacharyya系數(shù)融合了顏色空間均值向量和顏色空間協(xié)方差矩陣因此在此情況下目標(biāo)區(qū)域數(shù)Bhattacharyya系數(shù)值下降不是很大,Bhattacharyya系數(shù)曲面的峰值比較明顯,有利于提高跟蹤的穩(wěn)定性和抗遮擋能力。

圖4 兩種跟蹤算法Bhattacharyya系數(shù)變化曲線Fig.4 Two curves of Bhattacharyya coefficient for both tracking algorithms

圖 5 mean-shift跟蹤算法在第140幀時(shí)目標(biāo)區(qū)域Bhattacharyya系數(shù)分布圖Fig.5 Bhattacharyya coefficient distribution of mean-shift tracking algorithm in the target area in the 140th

圖6 基于二階直方圖的改進(jìn)型跟蹤算法在第140幀時(shí)目標(biāo)區(qū)域Bhattacharyya系數(shù)分布圖Fig.6 Bhattacharyya coefficient distribution of improved tracking algorithm based on second-order histogram in the target area in the 140th

5 結(jié)論

本文應(yīng)用二階直方圖改進(jìn)了均值偏移跟蹤算法,在顏色直方圖中引入了顏色空間均值向量和顏色空間協(xié)方差矩陣,使顏色直方圖不僅包含了目標(biāo)的顏色信息還包含了目標(biāo)顏色的空間分布的信息。仿真表明:改進(jìn)后的均值偏移算法具有更強(qiáng)的抗遮擋能力,對(duì)目標(biāo)跟蹤更加準(zhǔn)確穩(wěn)定。

[1]虞旦,韋巍,張遠(yuǎn)輝.基于多特征空間的均值漂移算法[J].模式識(shí)別與人工智能,2009,22(4):666-672.YU Dan,WEI Wei,ZHANG YuanHui.Mean shift tracking algorithm based on multi-feature space[J].PR&AI,2009,22(4):666-672.

[2]常發(fā)亮,趙瑤,陳振學(xué),徐建光.基于Mean Shif t和自適應(yīng)預(yù)測(cè)的非剛性目標(biāo)跟蹤算法[J].控制與決策,2009,24(12):1 821-1 825.CHANG Faliang,ZHAO Yao,CHEN Zhenxue,XU Jianguang.Non-rigid object tracking algorithm based on mean shif t and adaptive prediction[J].Control and Decision,2009,24(12):1 821-1 825.

[3]Comaniciu D,Ramesh V,Meer P.Kernel-based object tracking[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2003,25(5):564-577.

[4]Yang C,Duraiswami R,Davis L.Efficient mean-shift tracking via a new similarity measure[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA,United States:IEEE,2005:176-183.

[5]Wang H,Suter D,Schindler K.Effective appearancemodel and similarity measure for particle filtering and visual tracking[C]//Proceedings of 9th European Conference on Computer Vision.Graz,Austria:2006:606-618.

[6]Perez P,Vermaak J,Blake A.Datafusion for visual tracking with particles[J].Proceedings of the IEEE,2004,92(3):495-513.

[7]Yang C,Duraiswami R,Davis L.Fast multiple object tracking via a hierarchical particle filter[C]//Proceedings of IEEE International Conference on Computer Vision.Beijing,China:IEEE,2005:212-219.

[8]Birchfield S T,Rangarajan S.Spatiograms versus histograms for region-based tracking[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA,United States:IEEE,2005:1 158-1 163.