結(jié)合角點(diǎn)特征的CamShift目標(biāo)跟蹤算法研究

劉美枝，楊 磊，高 海

(山西大同大學(xué)物理與電子科學(xué)學(xué)院，山西大同037009）

運(yùn)動(dòng)目標(biāo)跟蹤一直以來(lái)都是機(jī)器視覺(jué)的一個(gè)重要研究方向，但是，環(huán)境背景和目標(biāo)姿態(tài)發(fā)生變化，或者多目標(biāo)出現(xiàn)相互干擾等因素都會(huì)加大目標(biāo)跟蹤的難度。在目標(biāo)跟蹤過(guò)程中，選用較好的目標(biāo)特征和合適的搜索算法很重要。目標(biāo)跟蹤算法主要從提高搜索匹配的速度和精度兩個(gè)方面來(lái)對(duì)運(yùn)動(dòng)目標(biāo)的性能加以提高[1]。CamShift（Continuosly Adaptive Mean-Shift）算法是一種經(jīng)典的運(yùn)動(dòng)目標(biāo)跟蹤算法，但該算法僅僅依靠目標(biāo)的顏色特征，當(dāng)出現(xiàn)相近顏色的目標(biāo)或背景時(shí)，都會(huì)使跟蹤發(fā)生漂移，甚至失效。針對(duì)該問(wèn)題，本文通過(guò)融合角點(diǎn)特征對(duì)CamShift算法進(jìn)行改進(jìn)，進(jìn)而實(shí)現(xiàn)目標(biāo)準(zhǔn)確穩(wěn)定地跟蹤。

1 Harris角點(diǎn)檢測(cè)算法

角點(diǎn)[2]是圖像的一個(gè)重要局部特征，Harris角點(diǎn)在光照、噪聲、旋轉(zhuǎn)、平移及灰度變化時(shí)具有不變性，所以在目標(biāo)跟蹤領(lǐng)域有著重要的意義[3-5]。Harris 角點(diǎn)最直觀的解釋就是，在兩個(gè)相互垂直的方向，都有較大變化的點(diǎn)，數(shù)學(xué)描述如下。首先，定義自相關(guān)函數(shù)：

在Harris角點(diǎn)檢測(cè)中，使用的是高斯窗口，wu,v表示的是高斯窗口中的權(quán)重。I為灰度值，E(x,y)表示的是圖像偏移導(dǎo)致窗口內(nèi)像素的平均變化。若窗口不變，則E(x,y)為x,y的函數(shù)。Harris 角點(diǎn)是當(dāng)(x,y)在兩個(gè)相互垂直的方向上，E(x,y)取較大值的點(diǎn)。

若令D(x,y)=Ix+u,y+v-Iu,v，則D(x,y)在原點(diǎn)(0,0)Taylor展開(kāi)，得到

顯然有D(0,0)=Ix,y-Ix,y=0 ，將高階無(wú)窮小0(x2,y2)忽略，可以將

代入自相關(guān)函數(shù)

從而有

其中

那么E(x,y)可表示為

由于

那么A，B分別表示x,y方向窗口中圖像的一階差分平方和，C表示窗口中x方向與y方向一階差分的乘積。用sobel 算子[6-9]求一階差分，即I?(-1,0,1)和I?(-1,0,1)T。那么可得到H矩陣，該矩陣是對(duì)E(x,y)的Hessian 矩陣的近似?？山柚l率域研究，令

從而得到H是Hessian 矩陣的另一種表達(dá)，由于求導(dǎo)運(yùn)算并不嚴(yán)格，所以只能認(rèn)為這是一種近似。Harris 可以對(duì)任意方向統(tǒng)計(jì)，對(duì)于一個(gè)給定方向，只要取到合適(x,y)，就能統(tǒng)計(jì)(x,y)對(duì)應(yīng)角度上窗口灰度值發(fā)生的變化。

如何去計(jì)算這個(gè)合適的(x,y)呢，對(duì)每一個(gè)角度都去計(jì)算，顯然是不合適的。這要從Harris 角點(diǎn)的定義來(lái)考慮，前面已經(jīng)說(shuō)過(guò)Harris角點(diǎn)是當(dāng)(x,y)取兩組相互垂直的值時(shí)，E(x,y)都取得較大值對(duì)應(yīng)的點(diǎn)。所以，首先考慮找出使E(x,y)取最大值的(x,y)，如果該方向E(x,y)有較大的取值，再考慮其垂直方向。

要判斷一個(gè)點(diǎn)是否為特征點(diǎn)，本質(zhì)上是要求該點(diǎn)的H矩陣，以及H矩陣的兩個(gè)特征值的分布情況。

1.1 Harris角點(diǎn)檢測(cè)步驟

應(yīng)用Harris角點(diǎn)檢測(cè)方法提取圖像中角點(diǎn)的過(guò)程可以分成以下幾步：

1）計(jì)算每一幀圖像中像素點(diǎn)在水平方向和垂直方向上的梯度，以及兩者乘積的運(yùn)算結(jié)果，得到一個(gè)如下所示的M矩陣：

2）對(duì)圖像進(jìn)行高斯濾波，重新得到M矩陣。

3）計(jì)算圖像上對(duì)應(yīng)的每一個(gè)像素點(diǎn)的R值

式中：α為經(jīng)驗(yàn)值，取值范圍介于[0.04,0.06]。

4）選取局部極值點(diǎn)。特征點(diǎn)反映的是局部范圍內(nèi)R極大值對(duì)應(yīng)的像素點(diǎn)。

5）設(shè)定閾值，選取一定的角點(diǎn)。

1.2 Harris角點(diǎn)匹配

在實(shí)際應(yīng)用中，由于目標(biāo)遮擋，形變等易造成部分角點(diǎn)丟失，而且由于Harris 角點(diǎn)檢測(cè)算法是通過(guò)手動(dòng)設(shè)置閾值，實(shí)驗(yàn)發(fā)現(xiàn)：當(dāng)取大閾值時(shí)，其提取的角點(diǎn)較準(zhǔn)確，但是不能完全反映目標(biāo)的角點(diǎn)信息；當(dāng)取小閾值時(shí)，易產(chǎn)生虛假角點(diǎn)。在這樣的情況下，兩幅圖像提取到的角點(diǎn)個(gè)數(shù)不一定相等，這時(shí)就很有必要對(duì)它們進(jìn)行角點(diǎn)匹配，得出一一對(duì)應(yīng)的角點(diǎn)對(duì)。

傳統(tǒng)的NCC 匹配算法[10-12]計(jì)算量比較大，復(fù)雜度較高，而且會(huì)產(chǎn)生誤匹配等問(wèn)題。本文在NCC匹配的基礎(chǔ)上進(jìn)行改進(jìn)，使用距離約束減少搜索的范圍，距離約束的前提條件是認(rèn)為兩幅圖像的相對(duì)位置和旋轉(zhuǎn)角度變化均不大，認(rèn)為兩幅圖像的投影點(diǎn)的位置也相差不大。若要在圖像I2中找出與圖像I1匹配的特征點(diǎn)時(shí)，只需要計(jì)算I1在I2中給定范圍內(nèi)的特征點(diǎn)的NCC值，對(duì)不在范圍之內(nèi)的特征點(diǎn)則不予計(jì)算。

采用BGNCC方法的匹配步驟如下：

1）第一幅圖像I1中的特征點(diǎn)記為di,i=1,2…m1 ，坐標(biāo)表示為在第二幅圖像I2中對(duì)應(yīng)坐標(biāo)位置的(-4n,4n)鄰域內(nèi)搜索特征點(diǎn)（可能無(wú)，一個(gè)或多個(gè)），記為dj，若存在特征點(diǎn)，以第一幅圖像I2中特征點(diǎn)di的n×n區(qū)域?yàn)槠ヅ浯翱谟?jì)算與第二幅圖像I2中特征點(diǎn)dj,j=1,2…m2 的等大小的窗口的相關(guān)系數(shù)。設(shè)定閾值a，若Cjj大于a，將滿足條件的特征點(diǎn)即為匹配點(diǎn)，依次類(lèi)推得到第一組匹配點(diǎn)集。

2）根據(jù)互匹配原理，按照上面的方法搜索第二幅圖像I2中特征點(diǎn)dj,j=1,2…m2 在第一幅圖像I1中的匹配點(diǎn)，得到第二組匹配點(diǎn)集。

3）（第一組特征點(diǎn)集）?（第二組特征點(diǎn)集），至此完成特征點(diǎn)匹配。

圖1是通過(guò)對(duì)兩幅圖像采用雙向最大歸一化相關(guān)系數(shù)進(jìn)行特征點(diǎn)匹配的結(jié)果圖。

圖1 圖像角點(diǎn)匹配結(jié)果

由圖1 兩幅圖像的匹配結(jié)果可知，在相鄰兩幀圖像中目標(biāo)變化緩慢的情況下，采用雙向最大歸一化相關(guān)系數(shù)進(jìn)行特征點(diǎn)匹配，在很大程度上可以去除一部分虛假角點(diǎn)，有利于目標(biāo)進(jìn)行正確的匹配。

2 結(jié)合角點(diǎn)特征的Camshift算法

本文采用結(jié)合角點(diǎn)特征和顏色特征的Cam-Shift 目標(biāo)跟蹤算法，僅用經(jīng)過(guò)匹配后的每個(gè)特征點(diǎn)周?chē)鶱×N的區(qū)域建立目標(biāo)的相關(guān)模型，那么得到的新的目標(biāo)模型以少量特征點(diǎn)信息表示目標(biāo)區(qū)域的主要特征。由于Harris 角點(diǎn)檢測(cè)算法和匹配算法的復(fù)雜度較高[7]，采用少量的關(guān)鍵點(diǎn)信息在一定程度上降低了整個(gè)算法的復(fù)雜度，增強(qiáng)目標(biāo)與背景的可分性，加速目標(biāo)的收斂，減少迭代次數(shù)。下面是結(jié)合角點(diǎn)特征的CamShift 算法的流程圖，其中k表示幀數(shù)，初始值為0。其算法流程圖如圖2所示。

圖2 結(jié)合角點(diǎn)的CamShift算法流程圖

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)環(huán)境為Windows XP 系統(tǒng)，在Visual Studio2010 下編程實(shí)現(xiàn)。測(cè)試的視頻為室內(nèi)顏色相近的多目標(biāo)在短時(shí)間相互干擾的跟蹤情況。在實(shí)驗(yàn)中，目標(biāo)的初始位置通過(guò)手動(dòng)標(biāo)記，先后采用傳統(tǒng)CamShift 跟蹤算法和本文算法進(jìn)行跟蹤，通過(guò)對(duì)比跟蹤結(jié)果，驗(yàn)證本文算法的可行性。

圖3 是采用傳統(tǒng)CamShift 跟蹤算法的跟蹤結(jié)果，從圖中可以看出，當(dāng)兩輛小車(chē)相距較遠(yuǎn)時(shí)，跟蹤情況良好，從第58幀開(kāi)始，兩輛顏色相近的小車(chē)慢慢靠近，跟蹤框開(kāi)始漂移，到第72幀跟蹤框包含了兩輛小車(chē)，整個(gè)跟蹤失敗。這是由于兩輛小車(chē)的顏色相近，而CamShift跟蹤算法只是簡(jiǎn)單的依據(jù)顏色信息進(jìn)行跟蹤，所以就會(huì)出現(xiàn)跟蹤漂移，誤差累積到一定程度，出現(xiàn)跟蹤失效。

圖3 傳統(tǒng)CamShift跟蹤算法的跟蹤結(jié)果

圖4 是采用本文跟蹤算法的跟蹤結(jié)果，從圖中可以看出，開(kāi)始目標(biāo)相距較遠(yuǎn)時(shí)，跟蹤效果與傳統(tǒng)算法相似，都可以完成準(zhǔn)確有效地跟蹤，當(dāng)目標(biāo)慢慢靠近時(shí)，跟蹤框稍有形變，但形變不大，跟蹤過(guò)程中可以自適應(yīng)地調(diào)整跟蹤框的大小和形狀，順利完成跟蹤。由此可知本文算法與傳統(tǒng)算法相比，在很大程度上減少了背景信息，充分利用目標(biāo)信息，使得較短時(shí)間相互靠近的目標(biāo)能夠完全分離。通過(guò)上面的實(shí)驗(yàn)可知，加入角點(diǎn)特征可以改善由于顏色特征產(chǎn)生的跟蹤的不穩(wěn)定現(xiàn)象，提高了目標(biāo)跟蹤的魯棒性。

圖4 本文跟蹤算法的跟蹤結(jié)果

表1是對(duì)實(shí)驗(yàn)分別采用原始的CamShift算法和基于角點(diǎn)的CamShift算法的跟蹤性能比較結(jié)果。

表1 跟蹤算法性能比較

由表1知，改進(jìn)后算法的平均誤差相比傳統(tǒng)的CamShift 跟蹤算法有所減少，但由于Harris 角點(diǎn)的提取和匹配過(guò)程的計(jì)算量比較大，復(fù)雜度較高，所以導(dǎo)致基于Harris角點(diǎn)的CamShift 跟蹤算法的每幀的迭代次數(shù)和平均處理時(shí)間比傳統(tǒng)的CamShift跟蹤算法大。

4 結(jié)論

本文采用基于角點(diǎn)特征和顏色特征的CamShift目標(biāo)跟蹤算法。首先進(jìn)行Harris 角點(diǎn)提取，由于Harris 角點(diǎn)的提取過(guò)程中，閾值是人為設(shè)定的，而且受周?chē)h(huán)境的影響，每一幀中提取出來(lái)的角點(diǎn)的個(gè)數(shù)是不固定的，為了剔除虛假角點(diǎn)，確定目標(biāo)的真實(shí)角點(diǎn)，采用BGNCC角點(diǎn)匹配方法，提取匹配后的角點(diǎn)特征周?chē)鶱×N區(qū)域，將此區(qū)域設(shè)為感興趣區(qū)域并生成直方圖，將生成的直方圖轉(zhuǎn)化為概率密度反向投影，最后利用MeanShift 算法搜索目標(biāo)。實(shí)驗(yàn)結(jié)果表明該算法能夠有效解決多目標(biāo)運(yùn)動(dòng)時(shí)產(chǎn)生的干擾現(xiàn)象。