基于改進CAMShift的運動目標跟蹤算法

劉 超，惠 晶

LIU Chao,HUI Jing

江南大學 輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122

Key Laboratory of Advanced Process Control for Light Industry-The Education Ministry,Jiangnan University,Wuxi,Jiangsu 214122,China

1 引言

智能視頻分析技術(shù)已成為計算機視覺領(lǐng)域中的一個重要問題，其中目標跟蹤技術(shù)應用范圍廣泛，在人機交互、物體識別、視頻監(jiān)控等方面發(fā)揮著重要作用[1]。

MeanShift目標跟蹤算法以其無需參數(shù)、計算量小，對目標變形、旋轉(zhuǎn)變化適應性強等特點得到普遍的重視和廣泛的研究[2-3]，而CAMShift在其基礎(chǔ)之上增添了自適應大小的功能[4]。Comaniciu等通過顏色加權(quán)直方圖描述目標，用Bhattacharrya系數(shù)度量候選目標和模型之間的相似度，能夠通過較少的迭代次數(shù)收斂到目標的真實位置[5]。Chu等人結(jié)合幀差法實現(xiàn)了CAMShift自動跟蹤[6]，由于幀差法僅提取了部分的輪廓邊緣，使目標內(nèi)部產(chǎn)生孔洞，往往造成目標提取不完整或者包含背景，使顏色特征混入了更多雜色而降低跟蹤質(zhì)量[7]。李忠海等將CAMShift與粒子濾波相結(jié)合，用以對小目標實現(xiàn)跟蹤[8]。

目標顏色與背景顏色的可分性對CAMShift的跟蹤效果影響較大。當搜索窗口中包含背景顏色信息時，傳統(tǒng)方法會將屬于背景的像素誤判為目標像素，從而引入跟蹤誤差；隨著誤差的積累，可能導致跟蹤失敗。在跟蹤過程中如果目標被逐漸遮擋，搜索窗口的尺寸會不斷減小甚至導致目標丟失，當目標重新出現(xiàn)后，也無法恢復對目標的跟蹤。針對以上存在的問題，本文擴展和改進了傳統(tǒng)的CAMShift算法，給出將非線性核密度估計、Kalman濾波和CAMShift相結(jié)合的抗遮擋的目標跟蹤解決方案。

2 核密度估計和CAMShift跟蹤算法

2.1 核密度估計

核密度估計是一種概率密度估計方法[9]。既不需要事先假定特征密度分布的形式，也不需要設置模型參數(shù)及參數(shù)優(yōu)化。只要樣本充足，核密度估計就能漸進收斂于任何一個概率密度函數(shù)[10]。核密度估計的目的是在已知一定數(shù)量的樣本點的情況下，盡量地逼近一個未知概率密度分布函數(shù)[11]。在核密度估計中發(fā)揮作用的單元是眾多具有相同尺度與形態(tài)的核函數(shù)。

假設xi(i=1，2，…，N)為未知概率密度分布產(chǎn)生的維度為d的N個樣本點，xi∈Rd。核密度估計函數(shù)可以表示為：

其中KH為核函數(shù)，可以表示為H為d×d大小的正定帶寬矩陣。當簡化帶寬矩陣為單參數(shù) h時，式（1）可變?yōu)椋?/p>

多維變量的核函數(shù)KS可以通過每個維度下單變量核函數(shù)Kj的乘積計算來表示：

2.2 基于非線性核密度估計的目標檢測

已知一組由 N幅圖像組成的序列，定義 xi∈{x1，x2，…，xN}為圖像中任意一個位置的像素點在第i時刻的色彩強度。對于當前t時刻此像素點的觀測值xt而言，其分布函數(shù) p(xt)的核密度估計則可定義為：

其中，K為選擇的核函數(shù)，滿足性質(zhì)K(t) ≥0和∫K(t) dt=1。由于圖像一般為多通道彩色圖像，所以樣本點均為多維數(shù)據(jù)（比如RGB圖像擁有3個色彩通道），利用公式（2）和（3），可以把具有d維核函數(shù)用每個色彩通道的核函數(shù)乘積來表示：

雖然普遍認為高斯核函數(shù)在樣本點有限的時候能夠獲得比較好的核密度估計，但是計算量過大，給實際應用帶來不利影響[12]。相對于高斯核函數(shù)而言，Epanechnikov函數(shù)同樣具有鐘形函數(shù)的形態(tài)，卻可以大大減少計算量，提高運算速度。選擇Epanechnikov函數(shù)作為核函數(shù)的概率密度估計函數(shù)為：

公式（6）是估計三通道彩色圖像像素值的概率密度分布的最終表達式。指定Th為一個固定的閾值與計算得到的估計值進行比較決策，將此像素值離散化為前景（foreground）或者背景（background）。當所有像素點都遍歷完畢，就得到二值檢測圖像。

2.3 CAMShift跟蹤算法

CAMShift算法主要通過視頻圖像中運動物體的顏色信息來達到跟蹤的目的[13]。算法思想如下：（1）初始化搜索窗口；（2）把搜索窗口圖像轉(zhuǎn)化為顏色概率圖并求質(zhì)心；（3）移動搜索窗口中心到其質(zhì)心處，重新搜索直到窗口中心與質(zhì)心間的移動距離小于預設的閾值或者運算次數(shù)達到預設值；（4）重復（2）、（3）步驟至跟蹤結(jié)束。

設(u，v)為搜索窗口中的像素點坐標，I(u，v)是投影圖中對應(u，v)點的灰度值。定義搜索窗口的零階矩M00和一階矩M10、M01分別如下：

可以求得當前搜索窗口的質(zhì)心位置為：

然后調(diào)整搜索窗口的大小，并將搜索窗口的中心移動到質(zhì)心。直到窗口中心與質(zhì)心間的移動距離小于預設的閾值或者運算次數(shù)達到預設值，則認為滿足收斂條件，進入下一幀圖像進行新的目標搜索。相對于當前幀，下一幀中搜索窗口的長度l和寬度w分別按下式更新。

其中：

CAMShift算法以逐幀處理視頻序列的方式完成目標的連續(xù)跟蹤[14]。

3 非線性核密度估計與CAMShift相結(jié)合的運動目標跟蹤

非線性核密度估計對樣本數(shù)據(jù)用核函數(shù)進行估計，選出概率密度最大的樣本數(shù)據(jù)作為背景。該方法能適應不同的場景，不同于混合高斯模型。它充分利用最近的歷史幀信息來表示背景模型，能夠適應復雜的像素分布密度，克服像素值在短時間內(nèi)頻繁變化，得到準確的估計。CAMShift算法通過視頻圖像中運動物體的顏色信息來達到跟蹤的目的，它采用目標的顏色直方圖作為搜索特征，通過不斷迭代均值偏移向量使得算法收斂于目標的真實位置，從而實現(xiàn)跟蹤。將兩者結(jié)合，在背景減法的基礎(chǔ)上用CAMShift做目標跟蹤，能提高跟蹤準確性，易于實現(xiàn)且運行速度快，能夠達到實時跟蹤的目的。

圖1是算法流程圖，上面的虛線框是核密度估計過程，左下的虛線框是Kalman濾波過程，右下的虛線框是CAMShift算法執(zhí)行過程。首先用像素級非線性核密度估計算法檢測運動目標，通過檢測得到的二值圖像進行連通區(qū)域分析提取感興趣目標。然后用提取的感興趣目標建立目標直方圖并初始化目標作為CAMShift的輸入，CAMShift算法用來在下一幀搜索目標。收斂的搜索結(jié)果用以更新Kalman濾波然后預測下一幀目標的狀態(tài)。下一幀在預測位置附近進行CAMShift搜索目標，能夠減少運算量，提高效率。跟蹤過程中，用非線性核密度估計的檢測結(jié)果輔助目標直方圖的更新。采用非線性核密度估計提取感興趣目標，能實現(xiàn)運動目標的自動跟蹤并能去除背景顏色，為下步建立只包含前景顏色的目標直方圖提供保障。由于目標位置不會突變，CAMShift算法僅在Kalman濾波預測位置附近搜索目標，能夠保證在搜索準確率不變的前提下減少運算量、提高效率。CAMShift搜索結(jié)果用以更新Kalman濾波，相當于用真實位置更新Kalman濾波，提高預測準確率。

圖1 改進CAMShift目標跟蹤算法流程圖

3.1 感興趣目標的獲得及直方圖的建立

在原圖中選擇一個包含運動目標的初始窗口建立直方圖，使得初始窗口不僅包含了跟蹤目標，還混入了背景顏色信息。針對上述問題給出將背景減法與CAMShift相結(jié)合的方法。運用非線性核密度估計先對視頻中的運動目標進行檢測，該模型能很好地處理光照變化的影響，適應在噪聲環(huán)境下目標的復雜運動和場景長時間的變化。檢測后得到了包含完整目標的最小窗口作為CAMShift的初始窗口，并將檢測出的前景像素相同位置的原圖像素信息建立直方圖。不僅使CAMShift實現(xiàn)了跟蹤自動化，也有效地去除了背景顏色信息的干擾。本文的解決方案如下：

（1）運用非線性核密度估計方法采用多幀建立背景模型并對當前幀（圖2（a））進行目標檢測，得到二值圖像（圖 2（b））。

（2）對檢測得到的目標進行連通區(qū)域分析，畫出包圍目標的最小窗口，如圖2（c），記錄該窗口的坐標。

（3）將二值圖2（b）與原圖2（a）相比較，如果二值圖中的某位置像素值為255，則原圖的同位置像素值保持不變；如果二值圖中的某位置像素值為0，則原圖的同位置像素值也變?yōu)?。得到圖2（d）。

（4）把圖2（d）轉(zhuǎn)化到HSV空間并提取H分量。

（5）把步驟（2）得到的窗口坐標作為CAMShift的初始窗口坐標，并對圖2（d）此窗口內(nèi)的像素H分量建立直方圖，由于去除V和S值較低的部分，建立的直方圖不統(tǒng)計框內(nèi)黑色像素，只包含目標像素的H分量。

圖2 非線性核密度估計檢測結(jié)果

3.2 直方圖的更新

通過上述五步實現(xiàn)了CAMShift的自動化跟蹤，并建立了不包含背景顏色信息的目標顏色直方圖[15]。接下來就是用CAMShift對目標進行跟蹤，并且非線性核密度估計與CAMShift相結(jié)合來更新直方圖，以適應目標顏色的變化。用一個物體的色彩分布來描述這個物體，假設物體中心位于x0，則該物體可以表示為：

候選的位于y的物體可以描述為：

因此物體跟蹤可以簡化為尋找最優(yōu)的y，使得 pu(y)與qu最相似。 pu(y)與qu的相似性用Bhattacharrya系數(shù) ρ^(y)來度量，ρ^(y)越大，表示候選目標與模板目標越匹配[16]，即

如果沒有發(fā)生遮擋并且Bhattacharyya系數(shù) ρ大于某一閾值Th則認為跟蹤得到的候選目標即為模板目標，此時利用候選目標的H分量直方圖更新模板目標直方圖，即

由于非線性核密度估計的前景檢測方法計算量較大，所以選擇定時更新，即每6幀運行一次目標檢測計算并更新一次目標直方圖。

3.3 抵抗目標遮擋

Bhattacharyya系數(shù)表征當前跟蹤到的候選目標直方圖與模板目標直方圖的相似度。當Bhattacharyya系數(shù)減小到一定的閾值并且目標大小急劇減少時，說明跟蹤目標可能發(fā)生了遮擋。若目標披遮擋，搜索窗口的尺寸將不斷變小，此時難以判定跟蹤物體的位置并可能出現(xiàn)當目標重新出現(xiàn)后難以恢復跟蹤的情況。

當發(fā)生遮擋時的跟蹤策略為：假如第k幀目標發(fā)生遮擋，則在k-1幀還沒發(fā)生遮擋，此時不更新目標直方圖，并且用k-1幀跟蹤到的目標框大小及位置預測k幀的跟蹤框。這里有兩種情況，分析如下：

Case 1：當發(fā)生部分遮擋時，假設實線框 A為第k幀跟蹤到的跟蹤框，虛線框B為實際的跟蹤框，框B的大小為第k-1幀沒發(fā)生遮擋時跟蹤得到的跟蹤框大小，它們的可能位置如圖3（a）所示。根據(jù)跟蹤框附近位置非線性核密度估計方法檢測的二值圖中白色連通區(qū)域的位置，可認為發(fā)生了某種情況的遮擋，用這種情況的跟蹤框B代替跟蹤得到的跟蹤框A，即為實際可能的目標位置。

Case 2：如圖3（b）所示當發(fā)生完全遮擋時，此時Bhattacharyya系數(shù)會急劇減小，跟蹤框的大小也會急劇變化，用此前沒發(fā)生遮擋時跟蹤得到的跟蹤框大小代替當前幀的跟蹤框大小，跟蹤框的中心設定為非線性核密度估計檢測得到的二值圖像中沒發(fā)生遮擋時跟蹤得到的跟蹤框附近白色連通區(qū)域的中心位置。

圖3 兩種目標遮擋情況

由于直方圖一直沒有更新，當目標重新出現(xiàn)時仍能搜索得到跟蹤框，并且Bhattacharyya系數(shù)大于某一閾值，說明遮擋已經(jīng)結(jié)束。對符合條件的跟蹤塊進行背景減法與CAMShift相結(jié)合的運動目標跟蹤，即恢復正常目標的無遮擋跟蹤過程。

4 運動目標跟蹤仿真實驗

本文實驗均在2.5 GHz*2 CPU、1 GB內(nèi)存的PC機上進行，采用VC++6.0開發(fā)環(huán)境；對AVSS 2007、PETS 2003等圖像序列測試跟蹤算法。

如圖4所示，在AVSS 2007序列中對序列中的一輛紅色車進行跟蹤，圖中藍色矩形框為Kalman濾波的預測目標狀態(tài)（包括位置和寬高等），紅色矩形框為CAMShift的跟蹤結(jié)果。從結(jié)果可以看出，CAMShift的跟蹤結(jié)果能提供完美的觀測值來修改運動目標的預測狀態(tài)；Kalman濾波不僅能發(fā)現(xiàn)汽車的正確位置，適應性也隨著車的增大而逐漸擴大。

圖4 AVSS 2007序列運動目標跟蹤結(jié)果

為了展示本文提出算法的優(yōu)越性，分別采用傳統(tǒng)CAMShift跟蹤算法和本文提出的跟蹤算法對PETS2003視頻序列進行檢測，序列分辨率為720×576，目標在運動過程中存在遮擋；測試時每5幀采樣一次，得到原圖的第345、350、355、360、363、375、380、385、390幀圖像，在第350幀兩個運動員之間發(fā)生了局部遮擋，在第363幀目標幾乎被完全遮擋，在385幀遮擋結(jié)束。當?shù)?63幀目標被完全遮擋后，由于傳統(tǒng)CAMShift跟蹤算法不更新直方圖，跟蹤了臨近的另一個穿紅衣服的運動員，導致跟蹤失敗，如圖5所示。

圖5 傳統(tǒng)CAMShift目標跟蹤結(jié)果

圖6展示了采用本文提出的改進CAMShift算法跟蹤結(jié)果，圖中兩個運動員突然向右運動，此時Kalman濾波器產(chǎn)生了一個不準確的結(jié)果，如圖6（f）。然而本文算法設計的Kalman濾波器有自適應的性質(zhì)，它會根據(jù)當前CAMShift的跟蹤結(jié)果調(diào)整濾波器的參數(shù)，使得預測的位置逐步趨向于CAMShift的跟蹤結(jié)果，如圖6（g）～（i）；每次CAMShift算法均在Kalman濾波預測位置附近搜索，提高運算速度。跟蹤過程中算法的平均運行時間為88.9ms，算法完全能夠滿足實時的要求，目標跟蹤軌跡如圖7所示。

圖6 改進CAMShift目標跟蹤結(jié)果

圖7 PETS 2003目標的跟蹤軌跡

5 結(jié)束語

本文擴展和改進了傳統(tǒng)的CAMShift算法，將核密度估計、Kalman濾波器、CAMShift與遮擋策略相結(jié)合，給出一種以前景檢測為輔，CAMShift為主的目標跟蹤方法，實現(xiàn)了運動目標的自動跟蹤。當目標正常跟蹤時，用非線性核密度估計的檢測結(jié)果對目標直方圖進行自適應更新；當檢測到目標發(fā)生遮擋時，用前面遮擋前的目標尺寸和位置修正當前跟蹤結(jié)果的目標尺寸及位置；當目標遮擋結(jié)束，重新運用核密度估計與CAMShift相結(jié)合的跟蹤策略進行跟蹤。實驗結(jié)果證明了給出的算法兼具效率和準確，并且有比較強的魯棒性。

[1]侯志強，韓崇昭.視覺跟蹤技術(shù)綜述[J].自動化學報，2006，32（4）：603-617.

[2]吳慧敏，鄭曉勢.改進的高效Camshift跟蹤算法[J].計算機工程與應用，2009，45（27）：178-180.

[3]Brox T，Rousson M，Deriche R.Colour，texture，and motion in levelsetbased segmentation and tracking[J].Image and Vision Computing，2010，28（3）：376-390.

[4]Yang Changjiang，Duraiswami R，Davis L.Efficient meanshifttracking via a new similarity measure[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2005：176-183.

[5]Chu Hongxia，Ye Shujiang，Guo Qingchang，et al.Object tracking algorithm based on CAMShift algorithm combinating with difference in frame[C]//IEEE International Conference on Automation and Logistics，2007：51-55.

[6]Dai Guojun，Zhang Yun.A novel auto-CAMShift algorithm use in object tracking[C]//CCC2008，2008：369-373.

[7]Elgammal A，DuraiswamiR，HarwoodD，etal.Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[J].Proc of the IEEE，2002，90（7）：1151-1163.

[8]李忠海，王莉，崔建國.基于Camshift和Particle Filter的小目標跟蹤算法[J].計算機工程與應用，2011，47（9）：192-195.

[9]Scott D W.Multivariate density estimation[M].New York：Wiley-Interscience，1992.

[10]Comaneci D，Meer P.Meanshift：a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603-619.

[11]Jeyakar J，Venkatesh Babu R，Ramakrishnan K R.Robust object tracking with background-weighted local kernels[J].Computer Vision and Image Understanding，2008，112（3）：296-309.

[12]McHugh J M，Konrad J，Saligrama V，et al.Foregroundadaptive background subtraction[J].IEEE Signal Processing Letters，2009，16（5）：390-393.

[13]徐蕭蕭，楊浩，陳宗海.一種基于改進CamShift的目標跟蹤算法[J].系統(tǒng)仿真技術(shù)及其應用，2009（11）：851-854.

[14]Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

[15]劉曼華，朱秀麗.基于改進CAMShift的多目標自動跟蹤[J].河南大學學報，2010，40（5）：525-528.

[16]寧紀鋒，姜光，吳成柯.CAMSHIFT與基于核的目標跟蹤算法的比較與分析[J].計算機工程與應用，2009，45（28）：177-179.