0 引言

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

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

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

1 目標(biāo)檢測

　　1.1 自適應(yīng)增強檢測算法

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

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

　　1.2 引入自適應(yīng)增強檢測算法的目的

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

2 基于形狀上下文和粒子濾波的多目標(biāo)跟蹤

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

　　2.1 形狀上下文特征提取

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

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

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

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

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

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

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

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

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

　　2.2 粒子濾波

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

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

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

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

　　粒子的權(quán)重通過以下公式進行更新：

　　通常認(rèn)為目標(biāo)狀態(tài)滿足馬爾科夫性，且狀態(tài)轉(zhuǎn)移與觀測值相互獨立，則重要性分布可簡化為一階馬爾科夫過程q(Xt|X1:t-1，Y1:t)=p(Xt|Xt-1)，相應(yīng)地，權(quán)重更新公式變?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ù)權(quán)值的大小對粒子進行重采樣。

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

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

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

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

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

　　(2)粒子初始化：設(shè)置每個目標(biāo)的粒子狀態(tài)和權(quán)重。

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

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

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

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

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

3 實驗分析

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

　　3.1 冰球運動場的實驗結(jié)果

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

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

　　3.2 交叉路口的實驗結(jié)果

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

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

4 總結(jié)

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