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

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

基于Kalman預(yù)測器的改進的CAMShift目標跟蹤

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

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

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

目標跟蹤；Kalman預(yù)測器；目標跟蹤算法；遮擋；搜索區(qū)域

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

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

1 Camshift跟蹤

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

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

② 選擇目標搜索窗。

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

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

⑤ 移動搜索窗的中心位置到質(zhì)心位置。

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

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

2 Kalman預(yù)測器

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

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

Kalman預(yù)測器的狀態(tài)方程：

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

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

Kalman預(yù)測器的觀測方程：

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

Kalman預(yù)測器狀態(tài)更新方程為：

Kalman預(yù)測器狀態(tài)預(yù)測方程為：

Kk為Kalman預(yù)測器的增益矩陣：

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

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

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

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

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

3.1 目標遮擋的判斷[8]

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

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

Bhattacharyya系數(shù)ρ(y)：

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

Bhattacharyya距離d(y)：

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

② 判斷目標被遮擋的程度

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

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

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

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

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

4 實驗結(jié)果

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

4.1 目標被遮擋實驗

① 經(jīng)典的CAMShift跟蹤算法

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

[1] 曾偉，朱桂斌，唐丁丁. 一種基于邊緣特征的地面軍事目標相關(guān)跟蹤方法[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] 邸男，朱明. 一種復(fù)雜背景下的實時目標跟蹤算法[J].中國圖象圖形學(xué)報，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] 牛春峰，劉世平，王中原. 制導(dǎo)炮彈飛行姿態(tài)的卡爾曼濾波估計方法[J]. 中國慣性技術(shù)學(xué)報，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]. 自動化學(xué)報，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—），女，副教授，光電控制技術(shù)重點實驗室客座研究人員，從事多源信息融合、目標檢測跟蹤與識別研究。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

光電控制技術(shù)重點實驗室和航空科學(xué)基金聯(lián)合資助（20135152049）；航天科技創(chuàng)新基金（CASC02）