結合角點特征的CamShift目標跟蹤算法研究

劉美枝，楊 磊，高 海

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

運動目標跟蹤一直以來都是機器視覺的一個重要研究方向，但是，環境背景和目標姿態發生變化，或者多目標出現相互干擾等因素都會加大目標跟蹤的難度。在目標跟蹤過程中，選用較好的目標特征和合適的搜索算法很重要。目標跟蹤算法主要從提高搜索匹配的速度和精度兩個方面來對運動目標的性能加以提高[1]。CamShift（Continuosly Adaptive Mean-Shift）算法是一種經典的運動目標跟蹤算法，但該算法僅僅依靠目標的顏色特征，當出現相近顏色的目標或背景時，都會使跟蹤發生漂移，甚至失效。針對該問題，本文通過融合角點特征對CamShift算法進行改進，進而實現目標準確穩定地跟蹤。

1 Harris角點檢測算法

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

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

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

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

代入自相關函數

從而有

其中

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

由于

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

從而得到H是Hessian 矩陣的另一種表達，由于求導運算并不嚴格，所以只能認為這是一種近似。Harris 可以對任意方向統計，對于一個給定方向，只要取到合適(x,y)，就能統計(x,y)對應角度上窗口灰度值發生的變化。

如何去計算這個合適的(x,y)呢，對每一個角度都去計算，顯然是不合適的。這要從Harris 角點的定義來考慮，前面已經說過Harris角點是當(x,y)取兩組相互垂直的值時，E(x,y)都取得較大值對應的點。所以，首先考慮找出使E(x,y)取最大值的(x,y)，如果該方向E(x,y)有較大的取值，再考慮其垂直方向。

要判斷一個點是否為特征點，本質上是要求該點的H矩陣，以及H矩陣的兩個特征值的分布情況。

1.1 Harris角點檢測步驟

應用Harris角點檢測方法提取圖像中角點的過程可以分成以下幾步：

1）計算每一幀圖像中像素點在水平方向和垂直方向上的梯度，以及兩者乘積的運算結果，得到一個如下所示的M矩陣：

2）對圖像進行高斯濾波，重新得到M矩陣。

3）計算圖像上對應的每一個像素點的R值

式中：α為經驗值，取值范圍介于[0.04,0.06]。

4）選取局部極值點。特征點反映的是局部范圍內R極大值對應的像素點。

5）設定閾值，選取一定的角點。

1.2 Harris角點匹配

在實際應用中，由于目標遮擋，形變等易造成部分角點丟失，而且由于Harris 角點檢測算法是通過手動設置閾值，實驗發現：當取大閾值時，其提取的角點較準確，但是不能完全反映目標的角點信息；當取小閾值時，易產生虛假角點。在這樣的情況下，兩幅圖像提取到的角點個數不一定相等，這時就很有必要對它們進行角點匹配，得出一一對應的角點對。

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

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

1）第一幅圖像I1中的特征點記為di,i=1,2…m1 ，坐標表示為在第二幅圖像I2中對應坐標位置的(-4n,4n)鄰域內搜索特征點（可能無，一個或多個），記為dj，若存在特征點，以第一幅圖像I2中特征點di的n×n區域為匹配窗口計算與第二幅圖像I2中特征點dj,j=1,2…m2 的等大小的窗口的相關系數。設定閾值a，若Cjj大于a，將滿足條件的特征點即為匹配點，依次類推得到第一組匹配點集。

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

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

圖1是通過對兩幅圖像采用雙向最大歸一化相關系數進行特征點匹配的結果圖。

圖1 圖像角點匹配結果

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

2 結合角點特征的Camshift算法

本文采用結合角點特征和顏色特征的Cam-Shift 目標跟蹤算法，僅用經過匹配后的每個特征點周圍N×N的區域建立目標的相關模型，那么得到的新的目標模型以少量特征點信息表示目標區域的主要特征。由于Harris 角點檢測算法和匹配算法的復雜度較高[7]，采用少量的關鍵點信息在一定程度上降低了整個算法的復雜度，增強目標與背景的可分性，加速目標的收斂，減少迭代次數。下面是結合角點特征的CamShift 算法的流程圖，其中k表示幀數，初始值為0。其算法流程圖如圖2所示。

圖2 結合角點的CamShift算法流程圖

3 實驗結果及分析

實驗環境為Windows XP 系統，在Visual Studio2010 下編程實現。測試的視頻為室內顏色相近的多目標在短時間相互干擾的跟蹤情況。在實驗中，目標的初始位置通過手動標記，先后采用傳統CamShift 跟蹤算法和本文算法進行跟蹤，通過對比跟蹤結果，驗證本文算法的可行性。

圖3 是采用傳統CamShift 跟蹤算法的跟蹤結果，從圖中可以看出，當兩輛小車相距較遠時，跟蹤情況良好，從第58幀開始，兩輛顏色相近的小車慢慢靠近，跟蹤框開始漂移，到第72幀跟蹤框包含了兩輛小車，整個跟蹤失敗。這是由于兩輛小車的顏色相近，而CamShift跟蹤算法只是簡單的依據顏色信息進行跟蹤，所以就會出現跟蹤漂移，誤差累積到一定程度，出現跟蹤失效。

圖3 傳統CamShift跟蹤算法的跟蹤結果

圖4 是采用本文跟蹤算法的跟蹤結果，從圖中可以看出，開始目標相距較遠時，跟蹤效果與傳統算法相似，都可以完成準確有效地跟蹤，當目標慢慢靠近時，跟蹤框稍有形變，但形變不大，跟蹤過程中可以自適應地調整跟蹤框的大小和形狀，順利完成跟蹤。由此可知本文算法與傳統算法相比，在很大程度上減少了背景信息，充分利用目標信息，使得較短時間相互靠近的目標能夠完全分離。通過上面的實驗可知，加入角點特征可以改善由于顏色特征產生的跟蹤的不穩定現象，提高了目標跟蹤的魯棒性。

圖4 本文跟蹤算法的跟蹤結果

表1是對實驗分別采用原始的CamShift算法和基于角點的CamShift算法的跟蹤性能比較結果。

表1 跟蹤算法性能比較

由表1知，改進后算法的平均誤差相比傳統的CamShift 跟蹤算法有所減少，但由于Harris 角點的提取和匹配過程的計算量比較大，復雜度較高，所以導致基于Harris角點的CamShift 跟蹤算法的每幀的迭代次數和平均處理時間比傳統的CamShift跟蹤算法大。

4 結論

本文采用基于角點特征和顏色特征的CamShift目標跟蹤算法。首先進行Harris 角點提取，由于Harris 角點的提取過程中，閾值是人為設定的，而且受周圍環境的影響，每一幀中提取出來的角點的個數是不固定的，為了剔除虛假角點，確定目標的真實角點，采用BGNCC角點匹配方法，提取匹配后的角點特征周圍N×N區域，將此區域設為感興趣區域并生成直方圖，將生成的直方圖轉化為概率密度反向投影，最后利用MeanShift 算法搜索目標。實驗結果表明該算法能夠有效解決多目標運動時產生的干擾現象。