基于改進CamShift的目標跟蹤系統算法

敖邦乾，楊 莎，劉小雍，葉振環

(1.遵義師范學院工學院，貴州 遵義 563006；2.遵義師范學院物理與電子科學學院，貴州 遵義 563006)

0 引言

無人水面艇(unmanned surface vessel，USV)經常被用于執行特殊且不適合載人的任務，能完成情報收集、環境監測、水面搜救和水文地理勘查等任務，應用十分廣泛。對于正在執行任務的USV進行檢測跟蹤，可以有效實施操作及控制。其中，基于區域的跟蹤[1]對整個圖像區域進行搜索，通過對比運動目標相鄰兩幀的位置變化實現區域跟蹤；基于活動輪廓的算法[2]將運動目標的邊界輪廓作為跟蹤模板，并對輪廓進行實時的跟蹤；基于模型的方法[3]通過對運動模板的外形特征建立2D或3D模型來完成跟蹤任務。這些算法中，基于區域的跟蹤方法需要搜索整個圖像區域，計算量大，實時性較差；基于活動輪廓的跟蹤方法，目標輪廓的更新比較困難；基于模型的跟蹤方法則難以建立精確的模型，且易受外界影響。

基于特征的跟蹤方法[4]通過提取運動目標的物理特征，利用相關的跟蹤算法實現對目標有效的跟蹤，其中，MeanShift是基于迭代收斂到概率最大的局部極大的非參數估計法[5]；Camshift則是對MeanShift的一種改進[6]，通過調整核函數來適應跟蹤目標在圖像中的大小，能有效解決目標變形和遮擋的問題，同時算法對系統資源要求不高，時間復雜度低，在較簡單背景下能夠取得較好的跟蹤效果，但是傳統的CamShift只對HSV中的H分量進行統計分析，易導致跟蹤特征單一，當背景較為復雜或有許多與目標顏色相似像素干擾的情況下，會導致跟蹤失敗，文獻[7]引入S分量，通過構建H-S二維直方圖對原算法進行改進；文獻[8]繼續加入V分量，組成三維直方圖跟蹤模板進一步改進了算法，跟蹤性能得到了進一步的提升，但是這類方法只是單純地考慮顏色直方圖，忽略了目標的空間分布特性。

為了提升目標跟蹤效果的魯棒性，文獻[9]提出將MeanShift與Kalman濾波相結合的跟蹤方法，充分發揮Kalman濾波器的預測功能和MeanShift跟蹤器的搜索功能，提高了跟蹤的精度和實時性；文獻[10]提出了一種改進的CamShift和Kalman組合的目標跟蹤算法，能對被嚴重阻擋或在與目標顏色相近的背景環境下的運動目標進行連續跟蹤。

對于運動的跟蹤目標，當運動目標發生形變或遮擋時，需要進行大量的計算，同時跟蹤的實時性較差，魯棒性不是很強，本文針對以上的問題，提出一種基于目標邊緣檢測的改進CamShift和Kalman濾波相結合的跟蹤算法，改進了當跟蹤目標與環境顏色相近時魯棒性較差的問題，同時對于快速運動及被障礙物遮擋的跟蹤目標也具有很好的跟蹤性能。

1 CamShift目標跟蹤算法

RGB顏色空間對光線較為敏感，為了減少光照變化對檢測目標的影響，將需要檢測跟蹤的目標圖像從RGB顏色空間轉換到HSV顏色空間，轉換后效果如圖1所示，其中，HSV顏色空間的h值計算如下：

圖1 被跟蹤目標原始及轉換后的圖像Fig.1 The original image and converted image of the target

(1)

式(1)中，r(紅色)、g(綠色)、b(藍色)分別表示在RGB顏色空間中的坐標值，其取值為[0, 1]。在HSV顏色空間中，h取值范圍為[0, 360]，它的值被歸一化為介于0和180之間以匹配8位灰度圖像(0，255)，HSV顏色空間的s值為：

(2)

HSV顏色空間的v值為：

(3)

本文算法采用HSV色彩空間進行處理，對于前方目標由于轉向及變速等引起的形狀及顏色變化具有一定的魯棒性，通過分離出其中的H(色調)分量進行該區域的色調直方圖計算，得到目標模板的顏色直方圖，根據獲得的顏色直方圖將原始輸入圖像轉化成顏色概率分布圖像，即輸入圖像在已知目標顏色直方圖的條件下的顏色概率密度分布圖，同時對其進行歸一化處理，如圖2所示。其中包含了目標在當前幀中的相干信息，對于輸入圖像中的每一個像素點，建立目標模型顏色直方圖：

圖2 目標原始及歸一化直方圖Fig.2 The original histogram and normalized histogram

(4)

式(4)中，u,m,δ,|R|分別表示顏色向量、被量化的級數、Kronecker Delta函數和區域R內的像素點個數，h(x,y)為像素點(x,y)色度分量H量化后的值。對于目標區域內的像素，可得到該像素屬于目標像素的概率，而對于非目標區域內的像素，該概率為0，這是一個反向投影過程。

算法設定閾值或最大迭代次數并進行迭代，通過尋找目標中心在當前幀中的位置來進行檢測跟蹤，首先在顏色概率分布圖中選擇搜索窗口的大小和初始位置，然后計算搜索窗口的質心位置。設像素點(x,y)位于搜索窗口內，I(x,y)為顏色直方圖的反向投影圖中該像素點對應的直方圖概率值：

I(x,y)={H(u)|h(x,y)=u},(x,y)∈R

(5)

搜索目標窗口步驟如下：

步驟1 計算零階矩m00，搜索窗口內所有點的概率之和：

(6)

計算一階矩及概率在x,y方向的加權和：

(7)

步驟2 計算搜索窗口的質心(xc,yc)：

(8)

步驟3 設置初始化窗口大小，其中寬度為s，長度為l：

(9)

步驟4 計算二階矩：

(10)

則目標運動窗口的方向為：

(11)

初始化式(9)得到移動跟蹤窗口，根據式(11)提供的運動方向，將其移動到式(8)目標的質心位置，判斷跟蹤窗口的移動距離是否大于設定的閾值，若是，則重復步驟1到步驟4的搜索過程，直到相鄰搜索窗口的質心變化小于給定的閾值或者達到迭代次數的最大值，同時為了實現連續跟蹤，將上一幀圖像搜索窗口的大小、質心作為下一幀搜索窗口的大小和質心，如此循環迭代，則可以完成對運動目標的連續跟蹤，具體流程圖如圖3所示。

圖3 Camshift跟蹤算法流程圖Fig.3 The flow chart of Camshift tracking algorithm

將目標的RGB圖像轉換成HSV圖片空間后，對外界光照變化有了較強的魯棒性，但當運動目標的顏色與運行環境顏色區域比較接近或運動目標被障礙物遮擋時，其跟蹤效果則很容易受到干擾，如圖4所示，在目標附近區域，由于被跟蹤目標與環境顏色比較相似，因此其概率直方圖也混淆有環境顏色的概率，目標的跟蹤窗口有較大的誤差，容易丟失目標，而在遇到被障礙物遮擋時，其跟蹤窗口無法進行均值計算，也很容易丟失目標，需要進一步的優化算法設計。

圖4 跟蹤目標顏色與環境相似直方圖Fig.4 The histogram of similarity between target and environment

2 目標跟蹤算法設計

2.1 目標邊緣算法檢測

本文使用Canny邊緣檢測算法[11]來對跟蹤目標進行邊緣的提取，加強其跟蹤的魯棒性，具體設計如下：

表1 像素點I(x,y)為中心的3×3高斯濾波器Tab.1 3×3 Gaussian filter centered on pixel I (x, y)

(12)

步驟2 沿著x軸和y軸使用Sobel算子(Sx,Sy)來計算圖形中每個像素點的梯度強度和方向，判斷其邊緣是水平、垂直還是對角線的。

(13)

(14)

(15)

(16)

Angle(θ)=arctan(Gy/Gx)

(17)

步驟3 應用非極大值抑制使得邊界變細的同時銳化邊緣部分，消除邊緣檢測算法帶來的雜散響應，對于每個像素，如果它是先前計算的梯度方向的局部最大值M(x,y)，則保留該值;反之，它的像素值會被歸零并且被極大值抑制。

(18)

步驟4 經過步驟3的處理，在保留下來的值中，確認強像素點是否位于邊緣的最終圖中，應用雙閾值檢測來確定真實的和潛在的邊緣，根據經驗設定兩個閾值minVal和maxVal，任何強度梯度高于maxVal的像素都是邊緣，任何強度梯度低于minVal的像素都不是邊緣并丟棄，在minVal和maxVal之間具有強度梯度的像素，只有當它們連接到具有高于maxVal的強度梯度的像素才被認為是邊緣，通過抑制孤立的弱邊緣最終完成邊緣檢測。

Canny邊緣檢測算法能較好地完成環境中物體的輪廓邊緣檢測，但是其對目標以外的物體也能進行無差別的輪廓檢測，如圖5 所示。只有綜合考慮兩種算法，結合它們的優點，才能改進跟蹤效果，本文使用Camshift算法和Canny邊緣檢測算法共同組成目標的跟蹤模板，設計不同的權值ρcs、ρcn，假設跟蹤過程中Camshift算法和Canny算法的反向投影分別為Fcs、Fcn，則加權后得到的合成反向投影為：

圖5 不同環境下跟蹤目標邊緣提取Fig.5 The edge extraction in different environment

(19)

從式(19)可以看出，在跟蹤過程中，加入的Canny邊緣檢測算法和原來的Camshift跟蹤算法共同作用于跟蹤目標，當目標顏色與環境顏色較為相近時，邊緣檢測算法占有較大的權值，可以抑制環境的影響，而當目標顏色與環境不同時，Camshift算法占有較大的權值比重，在總的概率密度分布圖中可以自適應地調整相應的權值來增加系統跟蹤算法的魯棒性。

經過上述設計以后，跟蹤系統對環境顏色的變化不敏感，具有較強的穩定性，但是當跟蹤目標部分或者全部被障礙物遮擋時，上述設計的算法就容易丟失目標，而且上述設計的算法對運動目標的下一步動作無法做出預測，對快速運動的目標的普適性較差。

2.2 Kalman濾波算法

Kalman濾波[12]和粒子濾波[13]是比較常用的兩種預測目標下一幀位置的算法，Kalman濾波是一種線性計算算法，具有計算量小、實時性高等特點，Kalman濾波算法在目標跟蹤領域得到了廣泛的應用，尤其對動態目標的跟蹤檢測，由于其算法很容易控制，并具有較強的魯棒性，在工程上得到了廣泛的應用。該算法的核心為采用信號和噪聲的狀態空間模型，主要是通過在狀態上和時間上的不斷更新來完成對運動目標進行跟蹤，其模型如圖6所示。算法利用系統的觀測值來更新系統的狀態向量，是一種對隨機信號進行最優估計的實時遞推算法，濾波器通過輸入的系統觀測量對隨機信號進行估計，更新后得到的信號作為濾波器的輸出，其不斷地把協方差進行遞歸，從而估算出系統的最優值。

圖6 Kalman濾波模型Fig.6 Kalman filtering model

Kalman濾波預測算法有兩個重要的方程：

系統狀態方程：

X(k)=AX(k-1)+BU(k)+W(k)

(20)

系統測量值方程：

Z(k)=HX(k)+V(k)

(21)

式(20)、式(21)中，X(k)和X(k-1)為k時刻和k-1時刻的狀態向量；Z(k)為k時刻的系統狀態測量向量；A、B、H分別表示狀態轉移矩陣、控制矩陣以及測量矩陣；U(k)為外部輸入控制量；W(k)和V(k)分別表示狀態過程噪聲和測量噪聲，通常應用中假設成零均值高斯白噪聲，服從正態分布，即Noise～Guasian(0,σ)，協方差矩陣分別為R和Q。 算法主要包括預測與更新兩個階段，其對系統的預測公式組為：

1) 狀態預測公式：

X(k|k-1)=AX(k-1|k-1)+BU(k)

(22)

2) 相對應的誤差協方差預測公式：

P(k|k-1)=AP(k-1|k-1)AT+Q

(23)

現在狀態的預測結果更新公式組為：

3) 狀態校正公式:

X(k|k)=X(k|k-1)+
Kg(k)[Z(k)-HX(k|k-1)]

(24)

4) 誤差協方差校正公式：

P(k|k)=[I-Kg(k)H]P(k|k-1)

(25)

5) Kalman增益系數公式：

Kg(k)=P(k|k-1)HT·
[HP(k|k-1)HT+R]-1

(26)

(27)

協方差矩陣Q和R分別為：

(28)

Kalman算法對于運動速度過快或者被遮擋的目標，能夠比較精確地預測其在下一幀視頻圖像中可能出現的位置，很大程度上解決了外界動態環境變化所引起的跟蹤失敗問題，在實際工程應用中具有較大的應用價值。本文基于HSV顏色空間，同時加入Canny邊緣檢測算法改進CamShift跟蹤算法，在對運動目標與環境顏色相近時的檢測跟蹤時，很大地加強了跟蹤檢測的光魯棒性；同時，Kalman算法的加入，使其在高速運動或有障礙物時不至于丟失目標，使其能連續跟蹤，其流程圖如圖7所示。

圖7 本文算法流程圖Fig.7 The flow chart of this article

3 實驗測試及分析

為驗證本文算法的實用性及優越性，設置如表2所示的軟硬件及參數環境，三種算法在正常環境情況下，跟蹤的效率差距不是很大，不影響系統的檢測跟蹤性能，因此本文進行了兩種較極端情況下的仿真測試。

表2 軟硬件環境及相關參數Tab.2 The H/S environment and related parameters

本文使用Bhattacharyya距離[14](BH系數)d(y)和有效幀率[15-16]ω作為其衡量標準。BH系數ρ(0<ρ<1)用于衡量CamShift算法中檢測模塊與目標模塊的相似程度，其值越大，表示其相似度越高，算法跟蹤效果越好；有效幀率ω則表示在目標跟蹤過程中檢測到的有效幀數與總幀數的比值，用來衡量目標跟蹤算法的有效性。而判斷某一幀是否為有效幀的方法仍然可以采用BH系數，設定適當的閾值，當BH系數超過這個閾值時，則認為其為有效幀。

測試1 運動目標顏色與環境顏色相似時測試效果

從圖8可以看出，當跟蹤目標顏色與環境顏色相近時，傳統的CamShift算法仍然可以跟蹤目標，但是其跟蹤窗口會變大，總是要滯后幾幀，隨著顏色的越來越接近，這種滯后會更嚴重，而且當跟蹤目標遇到有與其顏色相近的類似目標時，可能還會檢測到其他目標，導致檢測到的有效幀減少，其測試效果如圖8(a)所示；CamShift和Kalman濾波相結合的算法，由于加入了Kalman濾波預測算法，跟蹤窗口基本接近于物體的物理長寬度，能較好地跟蹤目標，其測試結果如圖8(b)所示；本文算法綜合了CamShift和Kalman濾波的優點，同時加入了跟蹤目標的邊緣檢測算法，因此其跟蹤窗口能實時準確地跟蹤到目標，不存在延時和失真等現象，尤其是在遇到顏色與跟蹤目標顏色相近的障礙物或者其他物體時跟蹤效果更好，采用的顏色直方圖和邊緣檢測算法相結合的算法，對跟蹤目標而言，其是唯一的，因此檢測效果會更好，測試結果如圖8(c)所示。

圖8 不同算法測試效果Fig.8 The test result of different algorithms

對三種算法的BH系數進行了比較，如圖9所示，本文算法中的BH系數達到最高，且在遇到與跟蹤目標顏色相近的其他物體或在跟蹤目標與環境顏色相近的極端情況時，也能達到很好的效果，其BH系數基本保持不變，同時表3中也對比了三種算法的有效幀率，本文算法可以達到對跟蹤目標的完全有效跟蹤，具有良好的穩定性和魯棒性。

圖9 不同算法BH系數Fig.9 BH coefficient of different algorithms

表3 顏色相似時的測試結果Tab.3 The effective frames in similar colors

測試2 有遮擋干擾下的測試結果

在跟蹤目標穿過障礙物時，傳統的CamShift算法在跟蹤目標遇到障礙物時，跟蹤窗口會停留在目標消失的最后位置，并且其窗口也會不停地變化，但是當目標出現在障礙物的前方時，跟蹤窗口還是停留在原來的位置，并不會隨著目標的重新出現而繼續匹配窗口，其測試效果如圖10(a)所示，同時從圖11中也可以看出，其BH系數快速地降為零，目標繼續運動后，CamShift算法失去了目標，可能導致跟蹤失?。籆amShift和Kalman濾波相結合的算法在遇到障礙物時，可以達到較好的效果，其BH系數也可以在跟蹤目標穿過障礙物時，比較快速地恢復到一個穩定的值，同時不會丟失目標，如圖10(b)所示；本文算法中，其BH系數在整個跟蹤過程中都比較穩定，在遇到障礙物時，其值會減小，但是當跟蹤目標重新出現時，跟蹤窗口馬上匹配目標，BH系數也快速地恢復到一個比較穩定的值，不會產生較大的波動，整個跟蹤過程BH系數都很穩定，沒有明顯的波動變化過程，其測試效果如圖10(c)所示。對于復雜環境中經常被障礙物遮擋的跟蹤目標，在整個跟蹤過程中都能表現出很好的跟蹤性能，從表4的對比中也可以看出，本算法的有效率是最高的。

圖10 有障礙物環境測試效果Fig.10 The test results with obstacle

圖11 有障礙物環境下BH系數Fig.11 The BH coefficients of different algorithms

表4 有障礙物時測試結果Tab.4 The effective frames in different algorithms

4 結論

由于環境變化的復雜性，以及光照強度的不斷變化，增加了對特定目標檢測跟蹤的難度，本文提出結合Canny邊緣檢測的改進CamShift跟蹤算法，該算法克服了目標與環境顏色相近時無法檢測或檢測目標誤差較大的難點，同時Kalman算法對目標的預測，尤其是有障礙物時的目標跟蹤，具有較強的魯棒性。仿真測試實驗結果表明，算法極大地改進了原始CamShift算法在目標檢測跟蹤上的缺陷，本文所設計算法的跟蹤效果比較穩定，具有較大的應用價值。