基于Kalman預測器的改進的CAMShift目標跟蹤

閆鈞華，陳少華，艾淑芳，李大雷，段 賀

(1. 南京航空航天大學 航天學院，南京 210016；2. 光電控制技術重點實驗室，洛陽 471009；3. 中國電子科技集團公司 第二十八研究所，南京 210007)

基于Kalman預測器的改進的CAMShift目標跟蹤

閆鈞華1,2，陳少華3，艾淑芳2，李大雷2，段 賀1

(1. 南京航空航天大學 航天學院，南京 210016；2. 光電控制技術重點實驗室，洛陽 471009；3. 中國電子科技集團公司 第二十八研究所，南京 210007)

CAMShift目標跟蹤算法遇到目標被遮擋時容易陷入局部最大值，對快速運動目標容易跟蹤失敗，且無法從失敗中復原。針對該問題，利用Kalman預測器改進CAMShift算法。首先利用Kalman預測器預測下幀圖像中目標的位置，以此位置為中心確定CAMShift算法進行目標跟蹤的搜索區域；然后利用目標匹配時的Bhattacharyya系數及目標大小來判斷目標是否被遮擋以及被遮擋的程度。如果沒有被遮擋，則用CAMShift算法得到的目標位置更新Kalman預測器中參數；如果遮擋不嚴重，則用Kalman預測器的預測值作為目標的位置和大小，且用該組值更新Kalman預測器中參數；如果遮擋非常嚴重，則用Kalman預測器的預測值作為目標當前位置，目標大小為固定值，用該組值更新Kalman預測器中參數。實驗結果表明，改進算法能夠準確地跟蹤被遮擋目標和快速運動目標。

目標跟蹤；Kalman預測器；目標跟蹤算法；遮擋；搜索區域

運動目標跟蹤在軍事、工業生產、日常生活中都有著廣泛的應用，如軍事目標跟蹤[1]、交通路口監控等等。Bradski[2]把MeanShift算法應用在連續序列圖像的臉部跟蹤中，并稱其為CAMShift算法，其結果表明此算法對不規則目標運動、圖像噪聲、虛假目標、光線變化都有較好的適應性，而且算法的實時性很好。CAMShift[3]是一種有效的統計迭代算法，它在目標表示上比傳統的均值漂移算法更加簡單，且便于進行模型的組合。經典的CAMShift算法以顏色直方圖為目標表示模型，通過迭代求解加權圖的質心來跟蹤目標，在背景簡單的情況下能夠取得較好的跟蹤效果，但是遇到噪聲干擾或目標被遮擋等問題時容易陷入局部最大值，同時對快速運動目標往往跟蹤失敗，且無法從失敗中復原[4]。

本文基于Kalman預測器對CAMShift跟蹤算法做出改進[5]，利用Kalman預測器預測下幀圖像中目標的位置，以此位置為中心確定CAMShift算法進行目標跟蹤的搜索區域[6]。利用目標匹配時的 Bhattacharyya系數及目標大小來判斷目標是否被遮擋，針對目標被遮擋的程度采取相應的處理方法。

1 Camshift跟蹤

Bradski在 MeanShift算法的基礎上提出了CAMShift算法，該算法自動調節窗口大小以適應被跟蹤目標由于形變所造成的在圖像中大小的變化，從而可以有效的解決目標形變問題。CAMShift算法運算步驟如下：

① 讀取一幀圖像（非HSV轉換成HSV的顏色空間），提取HSV三通道圖像的Hue通道。

② 選擇目標搜索窗。

③ 計算這個搜索區域的顏色直方圖，歸一化得到概率分布圖I(x,y)，并將它作為查找表，將Hue通道圖像上每一個像素點用它的像素值所對應的概率代替，得到概率投影圖。

④ 在概率投影圖上，根據搜索窗的大小，中心位置，計算搜索窗的質心位置(xc,yc)

⑤ 移動搜索窗的中心位置到質心位置。

⑥ 判斷中心位置是否收斂，如果不收斂，則返回④，根據新的搜索窗繼續計算質心位置，直到收斂。如果收斂則根據軸向得到目標橢圓區域大小(w, l)，此時區域的中心位置和大小就是目標在當前幀中的位置和大小，返回①，重新得到一幀新圖像，并利用當前所得到的中心位置和區域大小進入③，在新的圖像幀進行搜索。

經典CAMShift算法單獨用于目標跟蹤存在局限性，因此基于Kalman預測器改進CAMShift算法，利用Kalman預測器預測目標的位置，提高跟蹤運動目標的速度。

2 Kalman預測器

Kalman預測器是一個在誤差協方差最小準則下的最優估計方法，計算量小，實時性高，能利用實際的運動參數不斷修正未來運動狀態的估計值，提高估計精度，兼顧實時性和穩健性[7]。場景中的目標在每一幀圖像中的位置構成了目標運動的軌跡，引入Kalman預測器的目的就是根據當前幀中目標位置點的信息預測下一幀中目標的可能位置，且 CAMShift跟蹤算法需要設定目標搜索區域的位置和大小，所以Kalman預測器中的狀態變量Xk和觀測值Zk分別為：

式中，xk、yk表示目標的質心坐標，wik、hk表示目標橢圓區域外切矩形的寬和高，vx,k、vy,k、vw,k、vh,k分別表示k時刻四者的變化速度，ax,k、ay,k、aw,k、ah,k分別表示k時刻四者的加速度。

Kalman預測器的狀態方程：

式中，Xk是一個12×1維向量，表示在離散時刻k的狀態向量，是不可觀測的；Ak,k-1描述從tk-1時刻到tk時刻的狀態轉移矩陣，12×12維。

式中，Δt表示連續兩幀圖像間的間隔，本文取1幀；Wk-1是tk-1時刻狀態的隨機干擾，12×1維向量，本文采用互不相關的零均值標準正態白噪聲序列。

Kalman預測器的觀測方程：

式中，Hk是tk時刻的觀測矩陣，4×12維；Vk是tk時刻的觀測噪聲向量4×1維，本文采用互不相關的零均值標準正態白噪聲序列。

Kalman預測器狀態更新方程為：

Kalman預測器狀態預測方程為：

Kk為Kalman預測器的增益矩陣：

Kalman預測器預測了目標的位置，有效地克服了目標運動速度快、少量相近背景干擾、目標被部分遮擋所導致的跟蹤失敗。

3 基于Kalman預測器的改進的CAMShift目標跟蹤算法

CAMShift跟蹤算法的當前搜索窗口是根據上一步得到的結果自適應的進行調整，故其可以自適應的跟蹤動態變形的目標。當目標快速運動時，會導致目標與當前搜索窗口沒有連接，造成目標丟失。當目標被較嚴重的遮擋或完全遮擋時，CAMShift跟蹤算法得到的目標位置點是不準確的，會造成跟蹤錯誤目標。因為當前搜索窗口中不含有再次出現的真實目標，所以當真實目標再次出現時，使用CAMShift跟蹤算法跟蹤不到真實目標。

針對于此，本文基于Kalman預測器改進CAMShift目標跟蹤算法，對每幀圖像得到的當前搜索窗口的位置進行預測和修正，從而能夠跟蹤快速運動的目標，且當目標發生大面積的遮擋時能夠使用目標的預測值代替 CAMShift跟蹤算法計算得到的目標跟蹤位置，直至目標再次完全出現。基于Kalman預測器的改進的CAMShift目標跟蹤算法框圖如圖1所示。

圖1 基于Kalman預測器的改進的CAMShift目標跟蹤算法框圖Fig.1 Block diagram of the improved CAMShift target tracking algorithm based on Kalman predictor

3.1 目標遮擋的判斷[8]

CAMShift目標跟蹤算法是基于直方圖的跟蹤算法。直方圖作為一種統計特性，其本身對目標的旋轉和形變不敏感，這使得CAMShift目標跟蹤算法本身對目標的背景變化以及部分遮擋有較好的魯棒性。當目標被遮擋的面積較大時，CAMShift目標跟蹤算法就會失效。因為目標點少了，CAMShift跟蹤算法根據目標點計算“質心”時，對質心的作用變小了，所以得到的質心值不再向目標偏移。本文基于 Kalman預測器改進CAMShift目標跟蹤算法，需要對目標的遮擋情況作出判斷，判斷目標何時開始被遮擋以及被遮擋的程度如何。Bhattacharyya距離d(y)非常適合衡量兩個直方圖之間的相似程度，其值越小表示兩個直方圖越匹配；CAMShift跟蹤算法計算得到的目標面積是當前目標的大小。據此本文采用Bhattacharyya距離以及CAMShift跟蹤算法計算得到的目標面積判斷目標何時開始被遮擋以及被遮擋的程度。

① 判斷目標何時開始被遮擋

Bhattacharyya系數ρ(y)：

式中，pu(y)為目標模型的顏色直方圖，qu(y)為跟蹤圖像中當前目標子圖的顏色直方圖。

Bhattacharyya距離d(y)：

設定一個閾值Tb，如果滿足d(y)＜Tb，則說明目標沒有被遮擋。如果滿足d(y)≥Tb，則說明目標開始被遮擋。本文中Tb取0.4。

② 判斷目標被遮擋的程度

CAMShift跟蹤算法計算得到的目標橢圓區域大小(w, l)為目標面積area，這是當前跟蹤圖像中目標的大小。如果area＞min area，則說明遮擋不嚴重；如果滿足area＜min area，則說明遮擋非常嚴重。本文中min area是這樣確定的：對目標沒有被遮擋前的20幀圖像，利用CAMShift跟蹤算法計算得到目標的面積 area，從中選取一個最小值，這個最小值的 40﹪即為 min area。如果目標運動速度快，可以增大目標沒有被遮擋前的圖像幀數以確定mina rea。

3.2 基于Kalman預測器的改進的CAMShift目標跟蹤算法流程圖

本文針對目標快速運動，目標被遮擋這兩類問題對CAMShift算法進行了相應的改進。對于目標被遮擋問題，采用Bhattacharyya距離以及CAMShift跟蹤算法計算得到的目標面積判斷目標何時開始被遮擋以及被遮擋的程度；基于Kalman預測器對目標快速運動以及被遮擋過程中的目標位置進行預測[9-10]。具體的流程圖如圖2所示。

圖2 基于Kalman預測器的改進的CAMShift目標跟蹤算法流程圖Fig.2 Flowchart of the improved CAMShift target tracking algorithm based on Kalman predictor

基于Kalman預測器的改進的CAMShift目標跟蹤算法流程圖針對目標的質心位置和目標被遮擋進行預測和判斷。由CAMShift跟蹤算法根據相應的目標顏色模型計算得到目標的質心位置，根據跟蹤的結果判斷目標是否被遮擋。首先根據目標的質心位置和目標大小得到目標橢圓區域，然后計算目標模型的顏色直方圖與目標橢圓區域的當前目標子圖的顏色直方圖兩者的Bhattacharyya距離。據此判斷目標是否被遮擋，如果d(y)＜Tb，則說明目標沒有被遮擋。利用CAMShift算法得到的目標位置更新Kalman預測器，同時預測下一幀的目標位置和大小。如果d(y)≥Tb，則說明目標開始被遮擋，此時不利用CAMShift算法得到的目標位置更新Kalman預測器，而將Kalman預測器根據上一幀圖像預測得到的目標位置和大小作為當前幀的目標位置和大小，同時預測下一幀的目標位置和大小。當已經判斷目標被遮擋時，需進一步判斷目標被遮擋的程度。根據 CAMShift跟蹤算法計算得到的當前跟蹤圖像中目標的大小area判斷目標被遮擋的程度，如果area＞min area，則說明遮擋不嚴重；此時將當前跟蹤圖像中的目標位置和大小記錄到lastrect（目標橢圓區域外切矩形的寬和高分別為lastrect.width 和lastrect.height），同時將Kalman預測器根據上一幀圖像預測得到的目標位置和大小作為觀測值 Zk，修正 Kalman預測器的參數，再預測下一幀目標的位置和大小。如果area＜min area，則說明遮擋非常嚴重，此時Kalman預測器中的觀測值Zk中wik=lastrect.width，hk=lastrect.height，目標的質心位置(xk, yk)為 Kalman預測器根據上一幀圖像預測得到的目標位置，修正Kalman預測器的參數，再預測下一幀目標的位置和大小。在此過程中需要判斷目標連續被嚴重遮擋的幀數累加值 k是否已經達到極限K0，如果k＜K0，則說明雖然目標被遮擋，但是仍然在可以接受的范圍內，跟蹤繼續；如果k＞K0，則說明目標連續被嚴重遮擋的時間非常長，可能已經錯誤跟蹤或者丟失目標，則終止跟蹤。

4 實驗結果

本文實驗源程序在VC++6.0環境下開發，針對目標被遮擋、目標快速運動進行實驗。

4.1 目標被遮擋實驗

① 經典的CAMShift跟蹤算法

實驗結果如圖3所示。從實驗中可以看到CAMShift跟蹤算法可以抗部分遮擋，當目標被完全遮擋時不能持續跟蹤目標。當目標再次出現時，如果目標在上次消失的地方出現，則能再次跟上目標（如圖(a)所示）；如果目標從其它地方再次出現，則不能再次跟蹤目標(如圖(b)所示)。這主要是由于CAMShift跟蹤算法容易陷入局部極大值中，只能搜索到與搜索區有交集的目標。由于經典CAMShift算法的搜索區域在目標消失之后會變得非常小，只能在小的搜索區中搜索是否有目標出現，當目標從其它地方出現時，目標不在該搜索區域中，故不能搜索到目標。只有當目標再次出現在搜索區域中，才能再次跟上目標。

圖3 目標被遮擋時經典CAMShift算法目標跟蹤效果圖Fig.3 Effect diagram of the classic CAMShift target tracking algorithm with targets occluded

② 基于Kalman預測器的改進的CAMShift目標跟蹤算法

實驗結果如圖4所示，其中圖4(a)所示實驗針對目標靜止時被遮擋，圖4(b)所示實驗針對目標運動時被遮擋。針對(a)的情況，Kalman預測器得到的參數中目標的位置基本不變，而CAMShift算法根據當前的位置得到的目標大小如果變化較大或 Bhattacharyya距離 d(y)≥Tb，則說明已經發生了遮擋，此時更新Kalman預測器，同時將Kalman的預測值作為搜索窗口的位置。針對(b)的情況，當目標進入的較多時，則其結果使用Kalman預測值替代。在目標被完全遮擋的過程中，CAMShift算法一直在運算，但是由于其 Bhattacharyya距離大于0.4及目標面積非常小，此時使用Kalman的預測值作為結果值，直到目標從右邊再次出現時。當目標出現到了一半時，Bhattacharyya距離小于0.4以及目標的面積已經大于閾值，則使用CAMShift的跟蹤結果作為目標最終的位置。在目標被遮擋時，如果連續幾幀出現CAMShift的目標面積小于最小面積min area，則使用固定大小的搜索區域和固定的目標大小。

從實驗中可以看出，在目標被遮擋時，經典的CAMShift算法對于遮擋和非遮擋同樣處理，因此目標被遮擋時的跟蹤效果不好；改進的CAMShift算法結合了Kalman預測器，可以有效地判斷目標何時開始被遮擋以及被遮擋的程度，適當地擴大目標的搜索窗口及用 Kalman的預測值來確定搜索窗口的位置等，保證目標再次出現時能夠很快地被捕捉到。

圖4 目標被遮擋時改進的CAMShift算法目標跟蹤效果圖Fig. 4 Effect diagram of target tracking with the improved CAMShift algorithm when the target is occluded

4.2 目標快速運動時被遮擋實驗

實驗結果如圖 5所示：當汽車快速運動并且被路燈遮擋時，基于Kalman預測器的改進的CAMShift目標跟蹤算法能夠準確有效地跟蹤目標。算法針對經典CAMShift跟蹤算法的局部最大值的缺點，引入了Kalman預測器進行改進。Kalman預測器利用目標運動的規律很好地預測出下一幀目標的搜索區域，在目標被遮擋時仍然能夠準確地跟蹤目標。

圖5 目標快速運動時被遮擋改進的CAMShift算法目標跟蹤效果圖Fig.5 Effect diagram of target tracking with the improved CAMShift algorithm when the target is moving fast and occluded

5 結 論

本文針對目標幀間位移過大時導致目標在搜索區域內消失的問題，利用Kalman預測器預測下幀圖像中目標的位置，以此位置為中心確定搜索區域，采用CAMShift算法進行目標跟蹤搜索。利用目標匹配時的Bhattacharyya系數及目標大小來判斷目標是否被遮擋：如果沒有被遮擋，則將CAMShift算法得到的目標位置作為測量值代入Kalman預測器中更新參數；如果遮擋不嚴重，則用Kalman預測器的預測值作為目標的位置和大小，且將該組值作為測量值代入Kalman預測器中更新參數；如果遮擋非常嚴重，則用Kalman預測器的預測值作為目標當前位置，目標大小為固定值，將該組值作為測量值代入Kalman預測器中更新參數。實驗結果表明，基于Kalman預測器的改進的CAMShift目標跟蹤算法能夠準確地跟蹤被遮擋目標。

[1] 曾偉，朱桂斌，唐丁丁. 一種基于邊緣特征的地面軍事目標相關跟蹤方法[J]. 通信對抗，2009(4)：14-17.

ZENG Wei, ZHU Gui-bin, TANG Ding-ding.A correlation tracking method based on edge feature of ground military target[J]. Communication Countermeasures, 2009(4): 14-17. [2] Bradski G R. Real-time face and object tracking as a component of a perceptual user interface[C]//Proceeding of IEEE Workshop on Applications of Computer Vision，Princeton,NJ,USA,Oct 19-21,1998.Washington D C,USA：IEEE Computer Society，1998：214-219.

[3] Bradski G R. Computer vision face tracking for use in a perceptual user interface[J]. Intel Technology Journal (51535-864X), 1998, 2(2): 1-15.

[4] 邸男，朱明. 一種復雜背景下的實時目標跟蹤算法[J].中國圖象圖形學報，2009，13(9)：1758-1765.

DI Nan, ZHU Ming. An algorithm for real-time tracking target in complex environment[J]. Journal of Image and Graphics, 2009, 13(9): 1758-1765.

[5] Wang Zhaowen, Yang Xiaokang, Xu Yi, Yu Songyu. CamShift guided particle filter for visual tracking[J]. Pattern Recognition Letters, 2009, 30(4): 407-413.

[6] 牛春峰，劉世平，王中原. 制導炮彈飛行姿態的卡爾曼濾波估計方法[J]. 中國慣性技術學報，2012，20(5)：510-514.

NIU Chun-feng, LIU Shi-ping, WANG Zhong-yuan.Approach of Kalman filtering estimation of guided projectile attitude[J].Journal of Chinese Inertial Technology, 2012, 20(5): 510-514.

[7] Ruiming Liu, Xuelong Li, Lei Han, Jiao Meng. Track infrared point targets based on projection coefficient templates and non-linear correlation combined with Kalman prediction[J]. Infrared Physics & Technology, 2013, 57(3): 68-75.

[8] 儲珺，杜立輝，汪凌峰，潘春洪. 基于局部背景感知的目標跟蹤[J]. 自動化學報，2012，38(6)：1985-1995.

CHU Jun, DU Li-hui, WANG Ling-feng, PAN Chunhong.Local background-aware target tracking[J].Acta Automatica Sinica, 2012, 38(6): 1985-1995.

[9] Karavasilis V, Nikou C, Likas A. Visual tracking using the Earth mover's distance between Gaussian mixtures and Kalman filtering[J]. Image and Vision Computing, 2011, 29(4): 295-305.

[10] Mazinan A H, Amir-Latifi A. Applying mean shift, motion information and Kalman filtering approaches to object tracking[J]. ISA Transactions, 2012, 51(5): 485- 497.

Target tracking with improved CAMShift based on Kalman predictor

YAN Jun-hua1,2, CHEN Shao-hua3, AI Shu-fang2, LI Da-lei2, DUAN He1

(1. College of Astronautics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China; 2. Science and Technology on Electro-optic Control Laboratory, Luoyang 471009, China; 3. The 28th Research Institute of China Electronics Technology Group Corporation, Nanjing 210007, China )

CAMShift(Continuously Adaptive Mean Shift) target tracking algorithm is liable to fall into a local maxima when the target is occluded, and is prone to failure when the targets move fast, and can not be recovered from the failure.To solve this problem, the CAMShif algorithm is improved by using Kalman predictor.First, the position of the target in the next frame image is predicted by using the Kalman predictor and this position is used as the center to determine the searching area of CAMShift target tracking algorithm. Then the Bhattacharyya coefficient of target matching and the size of the target are utilized to determine whether the target is occluded and the degree of occlusion.If not occluded, the parameters of Kalman predictor are updated by the position of the target with CAMShift algorithm.If the occlusion is not serious, the current location and size of the target are determined by the predictive values of Kalman predictor, and this set of values are used to update the parameters of Kalman predictor.If the occlusion is very serious, the current location is determined by the predictive values of the Kalman predictor and the target size is a fixed value, then this set of values are used to update the parameters of Kalman predictor.The experimental results show that the improved algorithm is able to accurately track the occluded and/or fast moving targets.

target tracking; Kalman predictor; target tracking algorithm; occlusion; searching area

閆鈞華（1972—），女，副教授，光電控制技術重點實驗室客座研究人員，從事多源信息融合、目標檢測跟蹤與識別研究。E-mail：yjh9758@126.com

1005-6734(2014)04-0536-07

10.13695/j.cnki.12-1222/o3.2014.04.021

TP391. 4

A

2014-03-14；

2014-07-17

光電控制技術重點實驗室和航空科學基金聯合資助（20135152049）；航天科技創新基金（CASC02）