基于二階非線性投票的多目標跟蹤算法

摘 要:提出了基于二階非線性投票的多目標跟蹤算法。該算法通過目標匹配得到同一目標在不同幀中的位置，同時利用特征監測來處理目標的遮擋、分裂問題，并實現目標特征的實時更新。在目標匹配過程中，通過對目標前一幀與當前幀的特征相似性進行投票，得到匹配目標。利用視頻圖像進行實驗，結果表明，該方法對噪聲、陰影、遮擋、分裂等具有良好的魯棒性，較好地實現了多目標的跟蹤。

關鍵詞:二階非線性特征投票; 目標遮擋; 目標分裂; 多目標; 目標跟蹤

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001-3695(2009)09-3560-03

doi:10.3969/j.issn.1001-3695.2009.09.104

Multiple objects tracking based on two-stage nonlinear voting

CUI Rui-fang， FU Li-qin， HAN Yan

(National Key Laboratory for Electronic Measurement Technology， Dept. of Information Engineering， School of Information Communication Engineering， North University of China， Taiyuan 030051， China)

Abstract:This paper proposed a two-stage nonlinear voting-based tracking method. The method used object matching to get objects’ position in different frames， and used feature monitoring to deal with object occlusion， object split and real-time update for objects features. Implementecl objects matching based on the similarity voting of their features in successive frames. Carried out experimental study using image sequences captured in real scene. The experimental results show that the method is robust against noise， shadows， occlusion and split， and it performs multiple objects tracking finely.

Key words:two-stage nonlinear feature voting; object occlusion; object split; multiple objects; objects tracking

目標跟蹤在工業、交通、醫學、軍事、航空航天等領域均有重要應用，解決目標的匹配問題，即在復雜模糊的背景下找到兩個目標的相關性，是多目標跟蹤的關鍵技術。在實際場景拍攝的圖像中要找到目標惟一的相關性是非常困難的，容易導致失敗的原因包括:圖像的變化，如噪聲、遮擋、光照的變化、反射等都可能是目標特征發生變異的干擾因素;非剛性或鏈接(關節)外形目標的出現及其非統一性的特征;多個運動目標，尤其是目標有相似的特征或目標軌跡互相交錯;導致匹配中一個目標對應多個目標的目標分裂或遮擋現象;因噪聲導致的目標錯誤分割。

目標跟蹤方法主要分為基于運動分析和基于圖像匹配的兩類方法，幀間差分法和光流分割法是運動分析的主要方法。幀間差分法簡單，但只適用于靜止背景，為了適應動態背景必須對攝像機運動補償后再進行差分[1];光流分割法具有較強的抗干擾性但計算量大[2]。根據匹配原理，基于圖相匹配的方法可分為區域匹配、特征匹配、模型匹配和頻率域匹配。基于區域匹配的跟蹤能夠獲得較高的定位精度，但是計算量大，難以達到實時性和實時處理目標間遮擋的要求[3];特征匹配即在提取特征后，對特征屬性矢量如點、邊緣、線段、局部能量等進行相關度計算，選取的特征不同受外界影響不同[4，5];模型匹配要根據圖像目標的先驗知識建立模型，計算分析復雜、運算速度慢、模型的更新較為復雜、實時性較差[6];頻率域匹配是將視頻圖像變換到頻率域，然后根據變換系數的幅值或相位來檢測目標的運動。本文提出了一種復雜情況下多目標跟蹤的算法，不需要先驗知識，通過二階的非線性特征投票來建立目標惟一的相關性，解決了多匹配引起的模糊匹配問題，從而實現了兩個目標間的正確匹配。

1 跟蹤方法

跟蹤算法基于目標特征的相似性來跟蹤目標，分為特征提取、特征匹配和特征監測三步來實現，如圖1所示。

1.1 特征提取

對目標進行分割并提取目標的時空特性。根據算法要求選取簡單有效的目標特征，包括大小、形狀、質心、距離、運動。對于當前幀I(n)內的第i個目標Oic(表示為Oic∈I(n))，表示大小的參數包括面積Aic、最大水平距離Wic、最大垂直距離Hic;表示形狀的參數包括包含目標區域的最小矩形BOic、區域比例eic=Hic/Wic、緊密度cic=Aic/(HicWic)，eic具有旋轉和尺度不變性;通過計算包含目標區域的最小矩形BOic的質心來得到目標的質心參數;通過計算兩目標質心間的歐幾里德距離得到目標的距離參數;運動參數包括目標當前幀的位移wic=(wx，wy)，方向δic=(δx，δy)。

1.2 基于投票的目標匹配

在復雜場景中，利用單一特征對目標進行跟蹤是非常困難的，融合目標的多個特征進行目標的匹配和跟蹤是解決這一困難的有效方法[7，8]。用多個特征對兩個目標進行匹配時，問題的關鍵在于如何綜合這些特征而實現可靠的相似性判斷。多數研究者利用加權函數實現多個特征線性融合[9，10]，但線性融合具有以下不足:a)沒有考慮到人類視覺系統的非線性特征(HVS);b)單個特征描述目標的惟一性、不全面性;c)檢測的有效性，即在一定的時間間隔內目標的特征可能發生改變。對此，本文融合目標的多個特征提出非線性融合算法。

本文的非線性投票算法分為兩個步驟:a)對多個目標的特征投票(目標投票)，每個目標Oip∈I(n-1)至少與一個目標Oic∈I(n)相匹配，即建立相關性Mli:Olp→Oic，并產生Mli的置信度;b)對建立多個相關性的多匹配目標投票(相關性投票)，得到每個目標惟一的相關性。當出現分割誤差(遮擋和分裂)時，由于特征可能會隨時間發生變化，每個投票階段根據監測階段分為不同的空間和時間投票，每個子投票分別用相應的投票函數來實現。用投票函數進行投票時相似度s和非相似度q會隨投票的增加而增加，最后比較s和q的數量，決定最終投票結果。如果在I(n-1)中沒有目標與Oic∈I(n)相匹配，即零匹配M0i:→Oic，根據目標Oic的位置定義其為新進入或新出現的目標。如果在I(n)中沒有目標與Olp∈I(n-1)相匹配，即反向零匹配Ml0:Olp→，根據目標Olp的位置定義其為退出或消失的目標。

1.2.1 目標投票

為建立初始的目標相關性，對目標的形狀、大小和距離特征進行投票。用Mli:Olp→Oic表示前一幀I(n-1)中的第l個目標Olp和當前幀I(n)中的第i個目標Oic之間具有相關性，Mli:Olp→/Qic，表示Olp和Oic之間沒有相關性，則

Mli (dlitv)∩(|wxic|

其中:dli為Olp和Oic間的距離;tr為Olp搜索中心區域的半徑:

tr=/R+max (Wlp，Hlp)，150<<500(2)

max表示取最大值;Wlp、Hlp表示Olp的寬和高;wic=(wxic，wyic)表示當Olp和Oic匹配時的位移;wmax表示目標的最大可能位移;δli表示Mli的置信度;s、q表示Olp和Oic相似度和非相似度。

式(1)表明只有Oic和Olp在空間位置上接近，且充分相似(δli>tv)時，Mli才可能成立。當目標發生遮擋時，條件|wxic|

δli=s/v s=q(q-s)/v (s

其中:v是特征投票總數;0

1.2.2 相關性投票

目標投票后，I(n-1)中的目標至少與I(n)中的一個目標匹配，即該階段可能輸出目標的多個相關性。例如，Olp，Omp∈I(n-1)且Oic，Ojc∈I(n)，則可能有{Mli:Olp→Oic and Mlp:Olp→Ojc}或{Mli:Olp→Oic and Mmi:Omp→Oic}，則按式(4)的投票準則解決該類模糊匹配問題:

Mli sli>sljMlj sli

sli、slj分別是Mli和Mlj的相似度，用投票函數來計算比較sli、slj。

1.3 特征監測

通過監測和校正前兩步結果的誤差，找到目標惟一相關性。對遮擋和分裂的校正將產生新的數據可用于更新先前步驟的輸出(見圖1的循環反饋)。例如，校正由于遮擋引起的目標融合后，I(n-1)中原有的目標數據就需要更新，并對新目標進行跟蹤。

1.3.1 監測目標遮擋誤差

當兩個或多個目標粘連或遮擋時會產生目標融合，即包含目標的最小矩形的邊框重疊，此時分割的結果是由所有遮擋目標組成的區域。目標遮擋可能由實際的目標遮擋造成(如目標間互相粘連)或分割誤差造成(如目標的陰影造成的重疊)。

1)檢測目標遮擋 當目標互相粘連或遮擋時，包含目標矩形的四條邊中至少有一條有明顯的向外部的位移，根據式(5)，發生以下情況時定義為目標遮擋:a)目標當前位移方向與BOic的四邊中的一條邊的位移方向有明顯不同;b)Okp的BOic的邊有向外部的位移;c)存在Oip∈I(n-1)在位置上鄰近Okp 。

[(|wx-whr|>tw)∩(whr>0)∩(dkltw)∩(whl<0)∩(dkltw)∩(wvl>0)∩(dkltw)∩(wvu<0)∩(dkl

其中:whr表示包含目標Okp區域的最小矩形BOic右邊列的水平位移;whl表示包含目標Okp區域的最小矩形BOic左邊列的水平位移;wvl表示包含目標Okp區域的最小矩形BOic下邊行的水平位移;wvu表示包含目標Okp區域的最小矩形BOic上邊行的水平位移;dkl表示目標Okp和Olp質心之間的距離;td和tw表示距離和位移閾值。如果檢測到遮擋則標記所有(遮擋及被遮擋)的目標，這種標記可以保證后繼幀中對目標的繼續監測，即使目標完全遮擋(式(5)的遮擋情況不滿足)，這一點也是非常重要的，因為目標可能重新出現。

2)校正目標遮擋 如果檢測到目標遮擋，根據粘連目標的多少將目標Oic分為兩個或更多個目標，并根據I(n-1)和I(n)中相關目標的位移進行目標分離。

假設Okp∈I(n-1)且Olp∈I(n-1)在I(n)中遮擋為Oic且Mkl:Okp→Oic，則在I(n)中Olp會丟失。此時根據式(6)來估計Okp和Olp在I(n)中的位移:

wlp=(f(wcxl，wpxl，wuxl)，f(wcyl，wpyl，wuyl))

wkp=(f(wcxm，wpxm，wuxm)，f(wcym，wpym，wuym))(6)

其中:f(#8226;)表示定義的函數，如取均值或中值函數;wcxl、wpxl、wuxl表示Olp當前幀、前一幀、再前一幀的水平位移;wcyl、wpyl、wuyl表示Olp當前幀、前一幀、再前一幀的垂直位移;wcxm、wpxm、wuxm表示Okp當前幀、前一幀、再前一幀的水平位移;wcym、wpym、wuym表示Okp當前幀、前一幀、再前一幀的垂直位移。

3)遮擋過程中的跟蹤 Oalp，Obkp∈I(n-1)標志為a，b在當前幀I(n)中遮擋為Oic，即Oic∈I(n)且Oic~(Oalp+Obkp)。因為Oic與Oalp或Obkp相似，則在目標投票階段Oic與Oalp或Obkp相匹配。若Mki:Olp→Oic，則在I(n)中將目標Obkp丟失，此外Oic僅包含兩個遮擋目標的可見部分，即面積Aic≤Al+Ak。經過對遮擋目標的預測和分離后，要更新I(n)或I(n-1)中的目標及其特征，并對Oalp和Obkp進行匹配、監測和運動估計。

假設Oalp和Obkp在后繼幀{I(n+1)，…，I(n+f)，I(n+f+1)，…，I(n+f+g)，I(n+f+g+1)，…，I(n+f+h)|1

1.3.2 監測目標分裂誤差

1)檢測目標分裂 目標分割的結果可能將一個目標分為幾個區域，當目標分裂時，BOic的四邊中至少有一條邊會有明顯向內部的位移。假設Okp∈I(n-1)在I(n)中錯誤地分裂為Oic1和Oic2，且Mki1:Okp→Oic1。定義di12是Oic1和Oic2間的距離，w=(wx，wy)是Okp在I(n-2)和I(n-1)之間的當前位移，tw是距離閾值，td是位移閾值。根據式(7)，發生以下情況時定義為目標分裂:a)目標Okp的位移和BOic的四邊中的一條邊的位移方向有明顯不同;b)Okp的BOic的邊有向內部的位移;c)在I(n)中有目標Oic2接近Oic1。

[(|wx-whr|>tw)∩(whr<0)∩(di12tw)∩(whl>0)∩(di12

[(|wy-wvl|>tw)∩(wvl<0)∩(di12tw)∩(wvu>0)∩(di12

2)校正目標分裂 即進行區域融合，一旦檢測到分裂，兩個區域Oic1和Oic2融合為一個目標Oic。區域融合可以基于以下幾種:a)相同的空間特征，如紋理;b)相同的時間特征，如運動;c)空間關系，如包含。本文提出一種基于空間相關、時間一致、目標匹配的融合策略。假設Okp∈I(n-1)在I(n)中錯誤地分為兩個子區域Oic1和Oic2，且有相關性Mki1:Okp→Oic1，滿足以下條件時Oic1和Oic2融合為Oic:a)Mki:Okp→Oic，即目標投票Okp與Oic相匹配;b)Oic1在空間上接近Oic2，且Oic2在空間上接近Okp;c)融合目標Oic在大小上與Okp相似;d)Okp的運動方向沒有顯著變化。融合后，I(n)和I(n-1)中的目標要進行相應更新，如Oic添加到I(n)中，Oic1和Oic2被移除，增加Mki:Okp→Oic等。

本文提出的區域融合的優越性在于目標匹配和區域融合的相互配合，如匹配通過檢測分裂支持區域融合，而區域融合通過提供完整的目標支持匹配，使匹配繼續執行。與先前的融合方法相比較，其先進之處在于它是基于時間融合的，無須假設固定的目標拓撲。

2 實驗和結果分析

本文對海鷗視頻圖像中飛行的多只海鷗進行跟蹤，海鷗的飛行速度和方向具有很大的隨機性，背景較模糊。實驗選取16幀圖像進行跟蹤，每幀圖像都是640×480的RGB圖像。對每幀圖像要從模糊的背景中提取出跟蹤目標，首先將圖像灰度化，預處理去除噪聲和較小而模糊的目標，用數學形態學膨脹后的二值圖像作為獲取圖像特征和目標跟蹤的原始圖像，如圖2~4中的(a)。

圖2是第1幀初始圖像和獲取特征后的目標圖像，結果顯示算法能夠提取目標的質心和包圍目標的最小矩形等特征。圖3和4中分別是第10、11幀有新目標進入(第五個和第六個目標)獲取特征后的目標圖像，該算法能夠識別新進入的目標并對其進行標記，獲取目標的特征。如圖3所示，第二個和第四個目標由于預處理引起錯誤融合，算法通過二階非線性投票能夠正確地分離出由于噪聲引起目標的錯誤融合，得到目標的特征，再通過目標監測更新目標特征，得到匹配目標;如圖4所示，第二個和第四個目標嚴重遮擋，算法通過特征監測能夠正確地分離出嚴重遮擋的目標并實時更新目標特征，順利完成目標匹配，最終根據目標的質心繪制多目標的二維和三維的運動位移。

圖5和6分別是多個目標的x和y方向的運動軌跡。從圖中可以看到，對于在第10幀進入視場的第五個目標、在第11幀進入視場的第六個目標，得到了目標在x和y方向的運動位移，并且對于第11幀，當第二個和第四個目標發生嚴重遮擋時，仍然能夠準確地完成目標匹配，得到目標在x和y方向的位移。該算法得到的多目標運動軌跡的三維圖如圖7所示。其中:x，y軸表示目標在x和y方向的運動位移;z軸表示幀數。表1是多目標的質心值。

圖5~7的軌跡坐標為多目標跟蹤的結果。對比圖5~7和表1可知，跟蹤結果基本與實際相符，跟蹤誤差小。

3 結束語

本文提出一種有噪聲、遮擋、分裂誤差的可靠多目標跟蹤算法，不用模板和模型匹配，獨立于目標的物理位置且對目標的運動和相機位置不加限制，考慮到多個特征多個目標采用目標投票和相關性投票的二階非線性投票算法，并通過監測時間間隔內的目標特征解決遮擋、分割誤差。如果檢測到較大的偏差則假定有遮擋或分割誤差并進行校正。

實驗結果顯示本算法可以實現對多目標的實時跟蹤，可以處理遮擋，目標的出現、進入、消失、退出等情況，對于噪聲、陰影、遮擋、分裂具有良好的魯棒性。由于目標形狀的多變，對于遮擋時目標的精確分離，算法還有待完善。

參考文獻:

[1]DOCKSTADER S L， TEKALP A M. On the tracking of articulated and occluded video object motion[J]. Journal of Real-time Imaging， 2001， 7(5):415-432.

[2]HAN B， DAVIS L. Object tracking by adaptive feature extraction[C]// Proc of International Conference on Image Processing. 2004: 638-644.

[3]KHAN K， SHAH M. Tracking people in presence of occlusion[C]// Proc of Asian Conference on Computer Vision. 2000: 1132-1137.

[4]TAKALA V， PIETIKAINEN M. Multi-object tracking using color，texture and motion[C]// Proc of IEEE Conference on Computer Vision and Pattern Recognition.[S.l.]:IEEE Press，2007:1-7.

[5]KATARE A， MITRA T， BANERJEE A. Content based image retrie-val system for multi object images using combined features[C]// Proc of IEEE International Conference on Computing:Theory and Applications.[S.l.]:IEEE Press，2007.

[6]SEO K H， SHIN J H， KIM W， et al. Real-time object tracking and segmentation using adaptive color snake model[J]. International Journal of Control， Automation， and Systems，2006， 4(2): 236-246.

[7]CAVALLARO A， STEIGER O， EBRAHIMI T. Tracking video objects in cluttered background[J]. IEEE Trans on Circuits Syst Video Technol， 2005， 15(4):575-584.

[8]YANG Tao， LI S Z ， PAN Quan， et al. Real-time multiple objects tracking with occlusion handling in dynamic scenes[C]// Proc of IEEE Conference on Computer Vision and Pattern Recognition.Wa-shington DC: IEEE Computer Society， 2005: 970-975.

[9]付曉薇，方康玲，邱奕敏.一種基于特征代價函數的多目標跟蹤[J].武漢科技大學學報:自然科學版，2004， 27(4):416-418.

[10]AMER A， DUBOIS E， MITICHE A. Rule-based real-time detection of context-independent events in video shots[J]. Journal of Real-time Imaging， 2005，11(3): 244-256.