基于形狀上下文和粒子濾波的多目標跟蹤*

祁淑霞

（山東政法學院 信息學院，山東 濟南250014）

基于形狀上下文和粒子濾波的多目標跟蹤*

祁淑霞

（山東政法學院 信息學院，山東 濟南250014）

目標跟蹤是計算機視覺領域里研究的熱點和難點。提出一種基于形狀上下文和粒子濾波的多目標跟蹤算法，通過在跟蹤過程中融入目標檢測信息來處理目標進入與離開場景問題和目標重疊與分離問題。首先，采用自適應增強檢測算法對視頻區域中的目標進行檢測；然后，利用形狀上下文特征來建立被跟蹤目標的外觀模型；最后，利用粒子濾波方法進行粒子的選擇和目標的跟蹤。實驗證明，提出的算法能夠有效處理目標進入與離開場景的問題和目標重合與分離的問題，在單一背景和復雜背景下都能進行較為準確的跟蹤，還能一定程度上處理部分遮擋問題。

多目標跟蹤；目標檢測；形狀上下文特征；粒子濾波

0　引言

目標跟蹤是計算機視覺領域的一個重要研究方向，在智能監控、智能交通、視頻檢索和人機交互等方面具有重要的應用價值。同時，目標跟蹤也引起了國內外學者的廣泛關注和研究，提出了多種目標跟蹤算法。但是由于視頻中目標的形變、光照變化、遮擋、背景混淆等因素的影響[1-4]，創建一個能夠抵抗外界因素干擾，并且具有魯棒性和高效性的目標跟蹤算法，仍然是一項極具挑戰的任務。

目標外觀模型的建立是目標跟蹤算法的一個重要組成部分，一個高效的且合適的外觀模型能大大提高目標跟蹤算法的性能[5-8]。文獻[3]利用分塊的策略來建立待跟蹤目標的外觀模型，用以處理目標姿勢的變化和部分遮擋問題。文獻[7]對目標進行稀疏表示，能夠很好地處理部分遮擋、光照和姿勢的變化。文獻[9]同時利用目標和背景區域的特征，運用多個弱分類器增強的算法進行目標的跟蹤。文獻[10]基于圖像顏色特征和粒子濾波算法來進行目標跟蹤，雖然顏色特征的提取比較容易，但是當跟蹤目標的顏色和背景顏色非常相近時，就會導致跟蹤的失敗。文獻[11-12]提出基于壓縮感知理論的跟蹤算法，并且證明，從高維尺度圖片中隨機提取的低維特征可以有效地保留圖片內在的辨別能力，使得目標跟蹤過程實現起來更加方便。文獻[13-16]中基于多實例學習框架提出的跟蹤算法，可以有效地處理目標跟蹤中正樣本位置模糊問題。這些跟蹤方法都是針對單目標設計，對于多目標跟蹤的研究還相對較少，然而現實生活中，很多情況下需要同時跟蹤多個目標。

通常，在復雜環境中的多目標跟蹤問題往往充滿了更多不確定性因素[17]，例如目標的消失與出現、目標的重疊與分離。進行多目標跟蹤，首先自動檢測出所感興趣的目標，然后對這些目標進行特征表示，建立外觀模型，最后運用搜索策略在視頻序列中搜索定位目標，同時伴隨目標變化不斷更新模型。鑒于在目標發生遮擋或漂移的情況下，局部特征表現出的優勢，本文采用形狀上下文特征[18]建立目標的外觀模型。由于實際問題的復雜性，目標跟蹤面臨的多是非線性非高斯問題，粒子濾波算法在解決非線性非高斯問題上具有很大優越性，因此被廣泛應用于目標跟蹤領域[10，19-20]。 本文結合形狀上下文和粒子濾波算法，提出一種基于形狀上下文特征和粒子濾波的多目標跟蹤算法。實驗證明本文提出的算法在實時性和準確性方面都有優勢。

1　目標檢測

1.1自適應增強檢測算法

級聯的自適應增強檢測算法[21]最初用于人臉檢測，效果顯著。其主要思想是，首先對多個弱分類器根據其區分正負樣本的能力進行權值分配，為分類效果好的弱分類器分配相對大的權值，反之給予小的權值；其次把分類效果好的弱分類器組合成強分類器，然后根據其分類效果重新分配新的權值，如此循環直至形成分類效果魯棒的強分類器；最后，用訓練好的強分類器對篩選好的haar特征進行目標的檢測與分類。本文采用自適應增強檢測算法，訓練一個級聯的分類器進行目標檢測。在待檢測場景中采集包含目標的眾多圖像區域，歸一化到相同尺寸作為訓練正樣本。為了加快正樣本采集的速率，需使用一種簡單高效的策略，即在靠近中心的位置以低強度提取樣本，外圍區域以高強度提取樣本。需要注意的是，以這種策略產生的樣本數據進行訓練不是最理想的，在邊緣處會產生一些錯分的正樣本。而人工選擇一個更大的訓練集會訓練出更好的增強的分類器，但是在場景混亂或目標重疊區域仍然會失效。負樣本則從目標周圍不包含目標的背景區域中采集。

圖1展示了自適應增強檢測算法在冰球場數據集中的檢測結果。(a)和(b)為自適應增強檢測算法對于冰球運動員進行的精確檢測結果。不難看出，自適應增強檢測算法在冰球場場景中具有很好的檢測效果。其中，對于視頻中的新增目標、重疊目標和不同大小的目標，該算法也實時地給出了準確的檢測。

圖1　冰球運動員的檢測結果

1.2引入自適應增強檢測算法的目的

對運動目標進行跟蹤，經常會遇到某個目標進入或離開場景的情況，一個好的多目標跟蹤算法需要能夠準確檢測出目標何時離開或進入場景，并刪除或添加目標跟蹤框。因此本文在跟蹤中引入自適應增強檢測算法來解決這個問題，利用自適應增強檢測算法檢測出可能包含目標的小區域，結合粒子濾波最終確定目標位置。實驗證明，加入檢測算法能夠有效避免目標偏移，特別是，當運動目標進入和離開運動場景時，都可以很好地對目標進行檢測定位和跟蹤目標框的移除，實現了對運動目標的實時跟蹤。

2　基于形狀上下文和粒子濾波的多目標跟蹤

本節詳細介紹基于形狀上下文和粒子濾波的多目標跟蹤算法。在目標跟蹤的過程中，首先提取目標區域的形狀上下文特征作為目標模板，然后搜索候選目標區域，比較其形狀上下文特征與目標模板的相似性，最相似的候選目標區域即確定為目標的當前位置。

2.1形狀上下文特征提取

目標跟蹤問題可以被看作是目標模板與候選目標之間的匹配問題。形狀上下文算法在衡量形狀相似性和形狀匹配方面表現出良好的特性，因此本文使用形狀上下文描述符表示目標的外觀模型。

采用邊緣檢測算法檢測出被跟蹤目標的輪廓，從中采集n個特征點來表示目標的整個形狀結構，采集的特征點越多，越能展現目標的形狀細節。這些特征點有些分布在目標輪廓上，有些分布在目標輪廓內部。圖2展示了特征點的采集過程。圖2(a)為視頻中的一幀原始圖像，圖2(b)是對原始圖進行邊緣檢測的結果，圖2(c)中方框里的點為采集的目標的特征點。

圖2　特征點的選取過程

對于形狀[18，22]中的任一特征點 pi，通過計算其余特征點在每個組距的分布，建立其在極坐標下的直方圖hi，如圖3所示，hi定義如下：

第一個形狀中的特征點pi與第二個形狀中的特征點qj之間的匹配成本為：

其中，K表示組距的數目，hi和hj分別表示在 pi和 qj處的形狀上下文直方圖。

兩個形狀匹配的總成本可由最小化這些特征點的匹配成本得到：

該最小化問題可以采用 Hungarian方法[23]在 O(N3)的時間內解決，但是這對于目標跟蹤問題來說時間消耗太大，因此本文使用的改進的形狀上下文特征[24]來減少時間的開銷。假設目標模板包含s個形狀上下文直方圖，從候選目標中隨機地選取r個形狀上下文直方圖，則目標模板與候選目標的匹配成本轉化該s個目標模板形狀上下文直方圖與r個候選目標形狀上下文柱狀圖之間的匹配成本。通常s大約是r的20倍，因此該方法的速度將會比之前大大提高。

如圖3所示，(a)是無遮擋的圖像，(b)是有遮擋的圖像，(c)是用來計算形狀上下文柱狀圖的極坐標，(d)、(e)和(f)是分別表示矩形、圓形和三角形處的形狀上下文柱狀圖。由圖可以看出，矩形點和圓點所表示形狀上下文柱狀圖非常相似，在原圖像中也是一致對應的點，這樣形狀上下文特征就可以很好地處理遮擋問題。

圖3　形狀上下文的計算

2.2粒子濾波

粒子濾波由于其在解決非線性非高斯問題的優越性，被廣泛應用于目標跟蹤中。粒子濾波的思想基于蒙特卡洛方法，采用一組隨機狀態粒子來逼近狀態的后驗概率密度函數。令Xt表示t時刻的目標狀態，Yt表示t時刻的觀測值，則在貝葉斯框架下，后驗概率密度 p(Xt|Y1:t)可通過如下遞歸過程來獲得[10]：

其中，Y1:t-1={Y1，Y2，…，Yt-1}，p(Yt|Xt)表示觀測模型[25]。

粒子濾波算法包括預測和更新兩個操作階段。預測階段，由1～(t-1)時刻的觀測值估計t時刻的狀態：

其中，后驗概率分布 p (Xt|Y1:t)可由被賦予不同重要性權重(i-1，…，n)的 n 個粒子(i=1，…，n)近似估計得到，并且，這 n 個粒子服從重要性分布 q (Xt|X1:t-1，Y1:t)，其權重滿足

粒子的權重通過以下公式進行更新：

通常認為目標狀態滿足馬爾科夫性，且狀態轉移與觀測值相互獨立，則重要性分布可簡化為一階馬爾科夫過程 q(Xt|X1:t-1，Y1:t)=p(Xt|Xt-1)，相應地，權重更新公式變為。為避免粒子的退化而根據權值的大小對粒子進行重采樣。

本文中使用矩形框來表示目標[26]，粒子在 t時刻的狀態被定義為Xt=(xt，yt，st)，xt和 yt表示矩形框的中心坐標，st表示矩形框的尺寸。粒子的狀態轉移采用二階自回歸模型：

其中，V表示高斯噪音，分布為V～N(0，σ)。

2.3算法的執行過程

算法的具體執行過程如下：

(1)利用自適應增強檢測算法對于動態的運動目標進行檢測。

(4)提取特征：根據式(1)提取每個目標的每個粒子的形狀上下文特征。

(6)粒子重采樣：根據權重的大小進行粒子的重采樣過程。

(7)t=t+1，轉到步驟(3)。

3　實驗分析

本文選取了如下兩個應用場景對提出的多目標跟蹤算法進行實驗，一個是冰球運動的比賽現場；另一個是交叉路口的視頻監控。

3.1冰球運動場的實驗結果

圖4展示了本文提出的算法對于冰球運動員的比賽場景中的跟蹤效果。從圖中可以看出，該算法對每個目標的檢測跟蹤效果都很好，最重要的是，即使場景中出現的運動目標非常多以及環境稍微復雜的情況下，本算法可以成功地適應場景中發生的一些改變，并且可以對此及時做出調整和繼續保持跟蹤?？梢娫撍惴▽τ陬愃朴谶\動員比賽的快速運動場景中的多目標跟蹤具有一定的準確性和魯棒性。

圖4(a)顯示一位運動員將要進入拍攝場景，圖4(b)顯示兩幀后該運動員進入場景后的跟蹤結果?？梢钥闯?，當新目標將要進入比賽場景中時，自適應增強算法可以在兩幀的時間內快速檢測出該目標即將進入比賽場景中，在自適應增強檢測算法對此做出目標檢測后，就可以立即指派粒子對這個新的運動員進行定位和跟蹤。圖4(c)和4(d)展示了運動員離開拍攝場景的跟蹤效果?？梢钥闯?，當自適應增強算法檢測出該運動員要離開場景時，算法可以迅速做出相應的回應，放棄對他的檢測和跟蹤。

圖4　冰球運動場的跟蹤效果

3.2交叉路口的實驗結果

圖5展示了本文提出的算法對交叉路口的行人進行檢測跟蹤效果，可以看出，無論是在新的行人進入，還是兩人的重疊與分離的情形，本文的算法都能進行比較準確的跟蹤。從圖5(a)中可以看出，在行人較多，背景較為復雜的情況下，該算法依然能夠將監控區域內行人全部檢測出來并進行跟蹤。圖5(b)中當有新的目標進入時，該算法能準確檢測出目標并進行跟蹤。圖5(b)和5(c)中右邊兩個行人由重疊的到發生分離的過程，也可以被很好地檢測出來，然后把目標框分離成兩個跟蹤框，并且做出相應目標的跟蹤。從圖中還可以看出，當中間的行人經過電線桿遮擋時，對于該行人的跟蹤依然存在且繼續，并沒有發生目標跟丟情況，可見本文的算法也能一定程度處理目標遮擋問題。

圖5　交叉路口行人的跟蹤效果

從上述實驗可以看出，本文提出的基于形狀上下文和粒子濾波的多目標跟蹤算法加入了自適應增強的檢測算法對多個目標進行檢測跟蹤，具有很好的自適應檢測能力和目標跟蹤的功能。本文的算法能處理目標進出場景的情形，對于應用場景的適應性較強，而且能處理遮擋和復雜背景問題。

4　總結

本文提出的基于形狀上下文和粒子濾波的多目標跟蹤算法充分利用自適應增強檢測算法的優勢，結合形狀上下文特征，融入粒子濾波方法中，能有效處理目標進入與離開場景的問題和目標重合與分離的問題，在單一背景和復雜背景下都能進行較為準確的跟蹤，還能有效處理部分遮擋問題。下一步研究的重點是在保證實驗效果的同時，進一步提高算法的執行效率。

[1]GODEC M，ROTH P M，BISCHOF H.Hough-based tracking of non-rigid objects[J].Computer Vision and Image Understanding，2013，117(10)：1245-1256.

[2]SONG L，WANG Y.Multiple target counting and tracking using binary proximity sensors:bounds,coloring,and filter[C]. Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing，ACM，2014：397-406.

[3]ADAM A，RIVLIN E，SHIMSHONI I.Robust fragmentsbased tracking using the integral histogram[C].Computer Vision and Pattern Recognition，2006 IEEE Computer Society Conference on.IEEE，2006，1：798-805.

[4]WU Y，LIM J，YANG M H.Online object tracking：A benchmark[C].Computer Vision and Pattern Recognition(CVPR)，2013 IEEE Conference on.IEEE，2013：2411-2418.

[5]ROSS D，LIM J，LIN R S.YANG M H.Incremental learning for robust visual tracking[J].International Journal of Computer Vision，2008，77(1)：125-141.

[6]GRABNER H，LEISTNER C，BISCHOF H.Semi-supervised on-line boosting for robust tracking[M].Computer Vision-ECCV 2008，Springer Berlin Heidelberg，2008：234-247.

[7]MEI X，LING H.Robust visual tracking using l1 minimization[C].Computer Vision，2009 IEEE 12th International Conference on，IEEE，2009：1436-1443.

[8]KALAL Z，MATAS J，MIKOLAJCZYK K.Pn learning：Bootstrapping binary classifiers by structural constraints[C]. Computer Vision and Pattern Recognition(CVPR)，2010 IEEE Conference on，IEEE，2010：49-56.

[9]AVIDAN S.Ensemble tracking[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2007，29(2)：261-271.

[10]PéREZ P，HUE C，VERMAAK J，et al.Color-based probabilistic tracking[M].Computer vision-ECCV 2002，Springer Berlin Heidelberg，2002：661-675.

[11]ACHLIOPTAS D.Database-friendly random projections: Johnson-Lindenstrauss with binary coins[J].Journal ofComputer and System Sciences.2003，66(4)：671-687.

[12]CANDES E J，TAO T.Near-optimal signal recovery from random projections:Universal encoding strategies[J].Information Theory，IEEE Transactions on，2006，52(12)：5406-5425.

[13]ZHOU Q H，LU H，YANG M H.Online multiple support instance tracking[C].Automatic Face&Gesture Recognition and Workshops(FG 2011)，2011 IEEE International Conference on，IEEE，2011：545-552.

[14]BABENKO B，YANG M H，BELONGIE S.Robust object tracking with online multiple instance learning[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2011，33(8)：1619-1632.

[15]LEISTNER C，SAFFARI A，BISCHOF H.Miforests:multiple-instance learning with randomized trees[C].European Conference on Computer Vision(ECCV).Crete，Greece. 2010，1：29-42.

[16]ZEISL B，LEISTNER C，SAFFARI A，et al.On-line semisupervised multiple-instance boosting[C].Computer Vision and Pattern Recognition(CVPR)，2010 IEEE Conference on.IEEE，2010：1879-1879.

[17]INTILLE S S，DAVIS J W，BOBICK A F.Real-time closed-world tracking[C].Computer Vision and Pattern Recognition，1997.Proceedings，1997 IEEE Computer So ciety Conference on，IEEE，1997：697-703.

[18]BELONGIE S，MALIK J，PUZICHA J.Shape matching and object recognition using shape contexts[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2002，24 (4)：509-522.

[19]ISARD M，BLAKE A.Condensation—conditional density propagation for visual tracking[J].International Journal of Computer Vision，1998，29(1)：5-28.

[20]RUI Y，CHEN Y.Better proposal distributions：object tracking using unscented particle filter[C].IEEE Conference on Computer Vision and Pattern Recognition(CVPR).2001，2(2)：786-793.

[21]VIOLA P，JONES M.Rapid object detection using a boosted cascade of simple features[C].IEEE Conference on Computer Vision and Pattern Recognition.2001，1(1)：511-518.

[22]GUI Y，SU A，DU J.Point-pattern matching method using SURF and shape context[J].Optik-International Journal for Light and Electron Optics，2013，124(14)：1869-1873.

[23]PAPADIMITRIOU C H，STEIGLITZ K.Combinatorial optimization：algorithms and complexity[M].Courier Dover Publications，1998.

[24]MORI G，BELONGIE S，MALIK J.Efficient shape matching using shape contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(11)：1832-1837.

[25]MEI X，LING H.Robust visual tracking and vehicle classification via sparse representation[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2011，33(11)：2259-2272.

[26]QU M，PANG E，LIU R，et al.Object tacking based on shape context features and particle filter[J].Journal of Information and Computation Science，2012，9(7)：1905.

Multiple target tracking using shape context features and particle filter

Qi Shuxia
(School of Information，Shandong University of Political Science and Law，Jinan 250014，China)

Target tracking is still a hot and difficult research topic in computer vision.In this paper,we proposed a novel multiple target tracking method,which is based on shape context features and particle filter.Our method is proposed to deal with problems of the target objects entering(or leaving)the scene and overlap(or separation)by incorporating Adaboost detection.First, we adopt Adaboost detection algorithm for detecting multiple objects.Then,the target appearance model is builded by using the shape context features.Finally,we apply particle filter to choosing target particles and tracking objects in videos.The experiments indicate that the proposed method can effectively deal with the issue of targets entering(or leaving)the scene and targets overlap(or separation),and exactly track the targets which is under both single and complex background.And the proposed method also can handle partial occlusion on some extent.

multiple-target tracking；target detection；shape context features；particle filter

TP391

A

0258-7998(2015)01-0156-05

10.16157/j.cnki.0258-7998.2014120102017

山東政法學院科研規劃項目（2014Z02B）

（2014-11-11）

祁淑霞（1973-），女，碩士，講師，主要研究方向：計算機應用技術、圖像處理，E-mail：qishx@126.com。