一種融合遮擋分割的多目標(biāo)跟蹤算法?

李健勇??，徐連宇

（解放軍95899部隊，北京100085）

一種融合遮擋分割的多目標(biāo)跟蹤算法?

李健勇??，徐連宇

（解放軍95899部隊，北京100085）

復(fù)雜環(huán)境下的多目標(biāo)視頻跟蹤是計算機(jī)視覺領(lǐng)域的一個難點，有效處理目標(biāo)間遮擋是解決多目標(biāo)跟蹤問題的關(guān)鍵。提出了一種融合遮擋分割的多目標(biāo)跟蹤算法，計算每個目標(biāo)的光流速度概率直方圖，反映其運動統(tǒng)計信息；綜合使用外觀、運動、顏色信息構(gòu)造新的像素距離表達(dá)，借助分階段分類思想及K均值聚類技術(shù)進(jìn)行遮擋分割，得到準(zhǔn)確的運動前景像素；在粒子濾波器跟蹤框架下，使用概率外觀模型進(jìn)行多目標(biāo)跟蹤，更好地處理動態(tài)遮擋問題。實驗表明，所提算法解決了復(fù)雜環(huán)境下的多目標(biāo)跟蹤問題。

多目標(biāo)跟蹤；遮擋分割；粒子濾波；概率外觀；光流速度直方圖；K均值聚類

1 引言

多目標(biāo)跟蹤在軍事和民用方面都有著十分廣泛的應(yīng)用，如戰(zhàn)場監(jiān)視、空中多目標(biāo)攻擊、彈道導(dǎo)彈制導(dǎo)、空中交通管制以及機(jī)器人視覺、人機(jī)交互等，因此在過去的20多年中受到了許多發(fā)達(dá)國家的密切關(guān)注。多目標(biāo)跟蹤涉及到計算機(jī)視覺、模式識別和人工智能等領(lǐng)域的核心課題，由于目標(biāo)運動狀態(tài)的非線性與非高斯性、目標(biāo)姿態(tài)的變化、光照以及遮擋等問題，使得視覺目標(biāo)跟蹤是一個具有挑戰(zhàn)性的研究課題，因此，如何在跟蹤中進(jìn)行遮擋處理，克服相似目標(biāo)之間遮擋、交互對跟蹤結(jié)果的影響，成為當(dāng)前一項亟待解決的問題。

目前主流的多目標(biāo)跟蹤方法主要包括多假設(shè)跟蹤器（Multiple Hypothesis Tracker，MHT）［1］以及聯(lián)合概率數(shù)據(jù)關(guān)聯(lián)濾波器（Joint Probabilistic Data Association Filter，JPDAF）［2］，而遮擋使MHT及JPDAF方法中對目標(biāo)的觀測值與實際目標(biāo)出現(xiàn)較大偏差，造成跟蹤結(jié)果偏移甚至錯誤。現(xiàn)有單目固定攝像頭多目標(biāo)跟蹤方法大多將遮擋作為模型的一部分隱含入跟蹤過程中，使用顏色［3］、外觀［4］、運動［5］信息對目標(biāo)建模，但這些模型側(cè)重跟蹤過程中的目標(biāo)描述，對各種遮擋區(qū)分能力較差。目前比較有代表性的遮擋處理方法都簡單假設(shè)目標(biāo)的顏色滿足單高斯或混合高斯分布，沒有考慮到目標(biāo)顏色外觀分布對遮擋處理的重要作用，同時對目標(biāo)在場景中的歷史信息利用較少，導(dǎo)致對顏色相近目標(biāo)之間的相互遮擋處理效果不佳。

針對上述問題，我們把目標(biāo)交互區(qū)域的遮擋分割問題看作前景像素聚類問題，充分利用外觀、顏色及運動的統(tǒng)計信息，使用概率外觀模型［4］描述外觀信息，通過計算目標(biāo)附近的局部光流［6］，建立每個目標(biāo)的光流速度概率直方圖，同時定義了基于外觀與顏色分布的像素距離，采用K均值聚類技術(shù)進(jìn)行遮擋分割，最后在粒子濾波器框架進(jìn)行多目標(biāo)跟蹤。

與目前主流方法相比，我們一方面使用運動信息彌補了概率外觀模型在相似外觀目標(biāo)交互時容易失敗的缺點，另一方面通過分階段遮擋分割得到目標(biāo)更準(zhǔn)確的觀測外觀，提高跟蹤魯棒性。具體貢獻(xiàn)主要體現(xiàn)在以下3個方面：第一，使用局部光流概率直方圖描述目標(biāo)的運動統(tǒng)計信息，并在遮擋分割時考慮到目標(biāo)外觀概率分布；第二，定義了依托外觀及顏色分布的像素距離，并使用K均值聚類判斷目標(biāo)遮擋關(guān)系；第三，僅計算運動目標(biāo)附近的局部光流，同時采用分階段遮擋分割方式，提高運算效率。經(jīng)多組實驗證明，本文提出的算法能夠在兩個甚至多個目標(biāo)之間相互遮擋的情況下完成跟蹤任務(wù)，能夠改進(jìn)單目固定攝像頭下多目標(biāo)跟蹤的效果。

2 概率外觀模型

當(dāng)一個新的目標(biāo)被檢測時，將根據(jù)檢測框內(nèi)容為其初始化一個概率外觀模型［5］，包括與目標(biāo)等大的RGB外觀圖像μn、方差圖像∑n以及前景概率圖像PF，n。將區(qū)域中前景像素直接作為μn的初始化，并對∑n、PF，n分別賦初始值。隨著跟蹤的進(jìn)行，物體外觀發(fā)生變化，按照式（1）策略更新概率外觀模型［5］：

其中，Ωn是第n個目標(biāo)概率外觀模型模板大小，r∈Ωn為像素在概率外觀模板中的坐標(biāo)值，rtl表示當(dāng)前目標(biāo)檢測框左上角點在輸入圖像中的偏移位置，I表示輸入圖像，F(xiàn)表示經(jīng)過前景提取后的二值圖像，運動前景部分為1，靜止部分為0。

外觀似然度函數(shù)可表示為

由圖1可看出，概率外觀模型記錄了一段連續(xù)時間序列內(nèi)目標(biāo)外觀的變化，具有明顯的統(tǒng)計學(xué)意義，概率模板中概率值較大的部分主要集中在軀干所在的中軸線附近，而手臂以及腿部的擺動體現(xiàn)在以相對較小的概率出現(xiàn)在中軸線附近。該模型對光照變化以及攝像頭噪聲有較好的抗干擾能力，能反映目標(biāo)的主要特征（如軀干的外觀），而忽略目標(biāo)變化較快、不易于跟蹤的部分（如快速運動的腿部）。

圖1 概率外觀模型Fig.1 Probabilistic appearancemodel

3 基于粒子濾波的多目標(biāo)跟蹤框架及分階段K均值聚類遮擋分割算法

本部分首先介紹本文算法的總體框架，之后詳細(xì)描述本文所用到的局部光流速度概率模型及遮擋分割算法。

3.1 基于粒子濾波的多目標(biāo)跟蹤框架

總體跟蹤框架如圖2所示，首先采用混合高斯模型對場景背景建模，通過背景差得到運動前景像素塊；然后，計算各跟蹤假設(shè)附近的LK稀疏光流［7］，根據(jù)目標(biāo)局部運動概率模型進(jìn)行遮擋粗分割；第三，依靠目標(biāo)外觀、顏色統(tǒng)計模型，采用K均值聚類方法完成遮擋分割；最后在粒子濾波器跟蹤框架［7－9］下，采用式（2）作為似然度函數(shù)，估計目標(biāo)運動狀態(tài)。

圖2 系統(tǒng)總體框架圖Fig.2 Tracking system framework

3.2 局部光流速度概率模型

連續(xù)視頻序列中，同一運動目標(biāo)的光流速度變化不劇烈，而具有不同運動特征的目標(biāo)在光流速度、方向上有較大差異，因此光流速度能在一定程度上反映出物體的運動信息，可作識別物體遮擋的依據(jù)。為從圖像局部亮度值得到目標(biāo)光流速度，我們采用著名的LK局部光流算法［7］。同時，為進(jìn)一步提高效率，僅計算每個目標(biāo)鄰域的光流速度，并以此為依據(jù)，為每個目標(biāo)建立局部光流速度概率模型，為遮擋粗分割提供統(tǒng)計信息。

假設(shè)光流速度表示為向量v（r，t）＝（Vval（r，t），Vang（r，t）），其中Vval（r，t）、Vang（r，t）分別為光流速度的大小和方向。為體現(xiàn)光流速度的統(tǒng)計規(guī)律，我們構(gòu)造目標(biāo)的局部光流速度概率模型如下所述。

根據(jù)目標(biāo)區(qū)域內(nèi)每個像素的光流向量值，定義局部光流概率直方圖概率分布為

考慮到目標(biāo)區(qū)域內(nèi)并非所有的像素點都具有相同的重要性，我們?yōu)槊總€像素賦權(quán)值PF，m（r），該權(quán)值為第1部分中概率外觀模型的目標(biāo)外觀概率模板，能夠反映出像素點屬于運動目標(biāo)的可信度，使直方圖反映出物體主要部分的運動規(guī)律，減少噪聲及邊緣光流的影響。

如圖3所示，相對而行的兩個目標(biāo)，局部光流速度概率直方圖具有較大差別。從速度方向上看，兩目標(biāo)相對運動，左上角男性目標(biāo)的速度方向主要集中在正角度方向，而右下角女性目標(biāo)則在負(fù)角度方向部分概率值較大，兩者具有較大差別。從速度大小上看，男性目標(biāo)運動速度較快，一部分速度值分布在中等速度范圍內(nèi)，而女性目標(biāo)運動速度較慢，速度大小主要集中在低速區(qū)域?？梢姡鲜鼍植抗饬魉俣雀怕誓Ｐ涂煞从吵鲞\動目標(biāo)的運動信息，該信息與目標(biāo)的顏色信息相獨立，能夠為解決物體之間動態(tài)遮擋提供支持。

圖3 局部光流速度概率直方圖Fig.3 Local optical flow probabilistic histogram

3.3 分階段遮擋分割方法

我們采用分階段遮擋分割方法處理目標(biāo)遮擋問題，避免對大規(guī)模數(shù)據(jù)進(jìn)行聚類處理，以提高跟蹤效率。首先根據(jù)3.2節(jié)中目標(biāo)的局部光流速度概率模型對能運動前景像素進(jìn)行粗分類，處理較易劃分的像素；然后對少數(shù)難以簡單分類的前景像素，定義基于外觀及顏色分布的像素距離，進(jìn)行K均值聚類，得到最終遮擋分割結(jié)果。

我們提出的分階段遮擋分割方法，首先利用目標(biāo)運動的統(tǒng)計信息，采用貝葉斯最大似然估計的方法對需要分割的前景像素進(jìn)行粗分類。

假設(shè)兩目標(biāo)ID1、ID2在t時刻有交互關(guān)系，兩目標(biāo)鄰域內(nèi)像素點光流速度為v（r，t）＝（Vval（r，t），Vang（r，t）），其中r為像素坐標(biāo)，記像素r類別為c（r，t），定義目標(biāo)局部光流概率似然度函數(shù)如式（4）：

定義遮擋粗分類判別標(biāo)準(zhǔn)如式（5）：

其中，TH為閾值，即當(dāng)像素點的光流速度v（r，t）＝（Vval（r，t），Vang（r，t））屬于某目標(biāo)的概率比其屬于其他目標(biāo)的概率高過一定程度時，就認(rèn)定該像素屬于前一目標(biāo)。

我們采用無監(jiān)督學(xué)習(xí)中常用的K均值聚類方法對上階段未能判定出類別的前景像素進(jìn)行聚類。由于上階段使用運動信息無法區(qū)分這些前景像素，因此本部分中選用目標(biāo)的顏色及幾何信息構(gòu)造像素距離。

K均值聚類算法目標(biāo)是最小化全局代價函數(shù)：

其中，n為聚類數(shù)據(jù)個數(shù)，c為類別數(shù)目，xj、μi分別為第j個數(shù)據(jù)點和第i個聚類中心，d（xj，μi）為xj、μi之間的距離。

我們使用顏色信息定義像素聚類距離d（xj，μi）。首先，根據(jù)目標(biāo)的外觀概率模型構(gòu)造目標(biāo)顏色概率直方圖：通過映射函數(shù)h（x）將RGB顏色空間按照3個分量平均劃分成m＝8×8×8個區(qū)間，將目標(biāo)外觀均值模板的像素統(tǒng)計入顏色概率直方圖，考慮到顏色的空間分布情況，每個像素以其在外觀概率模板中的概率值作為在顏色概率直方圖中的權(quán)值，即第n個目標(biāo)在t時刻顏色概率分布pcol，n（t）＝｛pcol，n（t）（u）｝u＝1…m可通過下式計算：

定義基于顏色與外觀的像素聚類距離為

K均值聚類遮擋分割算法可描述如下：

初始化：設(shè)定聚類數(shù)目c為像素附近目標(biāo)個數(shù)，從待聚類前景像素中隨機(jī)取c個作為初始聚類中心；

Do

For所有待分類像素

以式（9）作為距離函數(shù)，按照最近鄰原則分類

更新聚類中心

Until聚類中心不再發(fā)生變化

最終目標(biāo)遮擋分割結(jié)果如圖4所示，第一行為未進(jìn)行任何處理時被遮擋目標(biāo)的前景像素，這些前景像素中包含了大量不屬于該目標(biāo)的信息，會對基于概率外觀模型的粒子跟蹤系統(tǒng)產(chǎn)生如下兩個影響：一是粒子后驗概率計算時，前景中存在大量不屬于目標(biāo)的像素，極大影響概率外觀似然度計算；二是在概率外觀模型模板更新階段，會把一部分遮擋物體的信息保存入概率外觀模型，導(dǎo)致概率外觀模型的誤差，從而產(chǎn)生跟蹤錯誤。而圖中第二行是進(jìn)行兩步遮擋分割后被遮擋目標(biāo)的運動前景像素，很大程度上排除了遮擋的影響，運動前景能夠較準(zhǔn)確地反映出被遮擋目標(biāo)的信息，有利于改善跟蹤結(jié)果。

圖4 最終遮擋分割結(jié)果Fig.4 Final result of occlusion segmentation

4 結(jié)論

本文在概率外觀模型以及局部光流速度概率模型的基礎(chǔ)上，提出了一種融合遮擋分割的多運動目標(biāo)跟蹤算法。針對不同運動目標(biāo)局部光流速度有差異的特點，充分利用目標(biāo)顏色、外觀以及運動信息，采用先粗分類再對困難區(qū)域細(xì)致聚類的分階段聚類方法，借用K均值聚類技術(shù)，較好地完成了跟蹤過程中的遮擋分割任務(wù)，并在粒子濾波跟蹤器框架下，實現(xiàn)了多目標(biāo)跟蹤。通過對目標(biāo)遮擋分割結(jié)果的比對表明，該算法能夠?qū)崿F(xiàn)在運動前景能夠滿足復(fù)雜場景下多目標(biāo)跟蹤任務(wù)，尤其對目標(biāo)間動態(tài)遮擋問題有較好的效果。

［1］Reid D.An algorithm for trackingmultiple targets［J］.IEEE Transactions on Automatic Control，1979，24（6）：843－854.

［2］Bar-Shalom Y，Scheffe M.Joint Probabilistic Data Association for Multiple Targets in Clutter［C］//Proceedings of the Second International Conference on Information Sciences and Systems.Greece：IEEE，1979：1－5.

［3］Zhao T，Nevatia R.Trackingmultiple humans in complex situations［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（9）：1208－1221.

［4］Yang J，Vela PA，Shi Z，et al.Probabilistic Multiple People Tracking through Complex Situations［C］//Proceedingsof the 11th IEEE International Workshop on PETS.Miami：IEEE，2009：79－86.

［5］Kristan M，Pers J，Kovacic S，et al.A local-motion-based probabilistic model for visual tracking［J］.Pattern Recognition，2009，42（9）：2160－2168.

［7］袁廣林，薛模根，韓裕生，等.基于自適應(yīng)多特征融合的mean shift目標(biāo)跟蹤［J］.計算機(jī)研究與發(fā)展，2010，47（9）：1663－1671. YUAN Guang-lin，XUE Mo-gen，HAN Yu-sheng，et al. Mean ShiftObject Tracking Based on Adaptive Multi-Features Fusion［J］.Journal of Computer Research and Development. 2010，47（9）：1663－1671.（in Chinese）

［8］Wang Zhaowen，Yang Xiaokang，Xu Yi，etal.CamShiftguided particle filter for visual tracking［J］.Pattern Recognition Letters，2009，30（4）：407－413.

［9］Isard M，Blake A.Condensation-Conditional density propagation for visual tracking［J］.International Journal of Computer Vision，1998，29（1）：5－28.

李健勇（1971—），男，河北冀州人，碩士，高級工程師，主要研究方向為指揮自動化和軟件項目管理；

LI Jian-yong was born in Jizhou，Hebei Province，in 1971.He is now a senior engineerwith the M.S.degree.His research interests include C4ISR and projectmanagement.

Email：ljy1qaz＠126.com

徐連宇（1984—），男，遼寧營口人，碩士，助理工程師，主要研究方向為指揮自動化。

XU Lian-yu was born in Yingkou，Liaoning Province，in 1984. He is now an assistantengineerwith the M.S.degree.His research direction is C4ISR.

A M ulti-target Tracking Algorithm Com bined w ith Occlusion Segmentation

LIJian-yong，XU Lian-yu
（Unit95899 of PLA，Beijing 100085，China）

Multi-target tracking in complex scenes is one of themost complicated problems in computer vision. Handling the occlusion between objects is the key issue inmulti-target tracking.An occlusion segmentation-based algorithm is presented to trackmultiple people through complex situationswhich are captured by staticmonocular cameras.In the proposed algorithm，the probabilistic histogram of each object′s optical flow vector is calculated，then thismotion statistic information alongwith the color and appearance information isused to constructa new expression of pixel distance，finally stepwise classification and K-means clusteringmethod are taken advantages of to accomplish occlusion segmentation.Object is handled by a particle filter-based tracking framework，and a probabilistic appearancemodel is used to find the bestparticle.Results show that the proposed approach can improve the performance of the original probabilistic appearancemodel and handle dynamic occlusion better.

multi-target tracking；occlusion segmentation；particle filter；probabilistic appearance；optical flow histogram；K-means clustering

TN97；TP391.4

A

1001－893X（2013）02－0172－05

10.3969/j.issn.1001－893x.2013.02.012

2012－05－16；

2012－10－15 Received date：2012－05－16；Revised date：2012－10－15

??通訊作者：ljy1qaz＠126.com Corresponding author：ljy1qaz＠126.com