0 引言

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

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

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

1 目標檢測

　　1.1 自適應增強檢測算法

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

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

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

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

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

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

　　2.1 形狀上下文特征提取

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

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

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

　　hi(k)=#{q≠pi：(q-pi)∈bin(k)}(1)

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

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

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

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

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

　　2.2 粒子濾波

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

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

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

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

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

　　通常認為目標狀態(tài)滿足馬爾科夫性，且狀態(tài)轉移與觀測值相互獨立，則重要性分布可簡化為一階馬爾科夫過程q(Xt|X1:t-1，Y1:t)=p(Xt|Xt-1)，相應地，權重更新公式變?yōu)?img src="http://files.chinaaet.com/images/2015/08/17/6357542442004400009600399.jpg" title="[~9(H[WB26F_X1}X@BE[JMU.jpg" alt="[~9(H[WB26F_X1}X@BE[JMU.jpg"/>。為避免粒子的退化而根據(jù)權值的大小對粒子進行重采樣。

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

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

　　2.3 算法的執(zhí)行過程

　　算法的具體執(zhí)行過程如下：

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

　　(2)粒子初始化：設置每個目標的粒子狀態(tài)和權重。

　　(3)預測：根據(jù)狀態(tài)轉移公式預測粒子狀態(tài)。

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

　　(5)更新：更新粒子權重，并對權值進行歸一化。依據(jù)最大后驗準則，確定t+1時刻的目標位置。

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

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

3 實驗分析

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

　　3.1 冰球運動場的實驗結果

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

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

　　3.2 交叉路口的實驗結果

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

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

4 總結

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

參考文獻

　　[1] GODEC M，ROTH P M，BISCHOF H.Hough-based trackingof non-rigid objects[J].Computer Vision and Image Under-standing，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 fragments-based tracking using the integral histogram[C].Computer Vision and Pattern Recognition，2006 IEEE Computer Soci-ety Conference on.IEEE，2006，1：798-805.

　　[4] WU Y，LIM J，YANG M H.Online object tracking：A ben-chmark[C].Computer Vision and Pattern Recognition (CVPR)，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 Com-

　　puter 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 minimiza-tion[C].Computer Vision，2009 IEEE 12th International

　　Conference on，IEEE，2009：1436-1443.

　　[8] KALAL Z，MATAS J，MIKOLAJCZYK K.Pn learning：Boot-strapping binary classifiers by structural constraints[C].Computer Vision and Pattern Recognition(CVPR)，2010 EEE 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] PREZ 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 of Computer and System Sciences.2003，66(4)：671-687.

　　[12] CANDES E J，TAO T.Near-optimal signal recovery from mation 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 Recogni-tion 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: multi-ple-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 semimultiple-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 SoConference on，IEEE，1997：697-703.

　　[18] BELONGIE S，MALIK J，PUZICHA J.Shape matching andobject recognition using shape contexts[J].Pattern Analysisand 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 boostedcascade of simple features[C].IEEE Conference on Com-puter Vision and Pattern Recognition.2001，1(1)：511-518.

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

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

　　[24] MORI G，BELONGIE S，MALIK J.Efficient shape match-ing 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 clas-sification 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.