MOT中改進的目標身份感知網絡流量技術

梅炳夫，肖春霞

(1.廣州市廣播電視大學 人文與工程學院，廣東 廣州 510091；2.武漢大學 計算機學院，湖北 武漢 430072)

0 引 言

多目標跟蹤(multiple object tracking，MOT)[1]是視頻監視、行為預測、運動視頻分析等多種計算機視覺領域的關鍵問題。近期提出的大部分算法均按照如下兩個步驟來解決MOT問題[2]：目標檢測和數據關聯。其中，在數據關聯方面，現有的算法可以分為兩大類：①局部關聯[3]：這類算法屬于時域局部算法，在求解數據關聯問題時只考慮部分幀。雖然該類算法的計算量較小，但是它們容易發生ID交換問題，并且對長期/短期遮擋、姿態變化和攝像機移動時的跟蹤難度很大。②全局關聯[4]：在全局關聯算法中，視頻幀數量有所上升，甚至為了推斷出目標軌跡而一次性處理整個視頻。雖然基于數據關聯的跟蹤算法展示了自身潛力，但仍然存在重大缺陷：算法性能嚴重依賴于目標檢測器的性能。如果目標檢測器的虛警率或漏警率較高，數據關聯將會失敗。為此，本文提出一種改進的多目標跟蹤算法，將一種全局數據關聯策略集成到結構化學習跟蹤器的推理過程中，實現檢測和全局數據關聯的同步。總體來說，本文的貢獻如下：①提出一種綜合了結構化學習和全局數據關聯的多目標跟蹤模型；②提出一種目標身份感知網絡流量技術，并通過拉格朗日松馳策略對其進行高效優化；③采用軟性空間約束取代了傳統目標檢測算法中的非最大貪婪抑制策略[4]，進一步提升了檢測結果；④驗證了本文方法對高難度數據序列的性能要優于其它最新算法。

1 本文算法

假設已知前幾幀中進入場景的目標初始邊界框(通過標注或利用目標檢測算法獲得)，本文方法首先通過結構化學習為每個對象訓練一個模型，并將目標跟蹤問題建模為拉格朗日松馳優化問題，然后提出一種目標身份感知網絡流量技術(target identity-aware network flow，TINF)進行結構化學習的推理。在學習期間，通過搜索使目標身份感知網絡流量代價函數最小化的一組軌跡，確定最被違反約束和序列在下個時間段的最優軌跡，推斷出視頻片斷中所有目標的最佳位置。具體過程如圖1所示，其中，圖1(a)表示本文方法對多個視頻幀采用的密集候選窗口的并集；圖1(b)表示傳統方法[5]獲得的人體檢測結果的并集；圖1(c)表示通過TINF發現并可用于模型更新的最被違反約束；圖1(d)表示本文方法的跟蹤結果。

圖1 多個視頻幀中某一人體的跟蹤過程

2 目標模型

(1)

(2)

(3)

由于Υ中邊界框的可能組合呈幾何數量級，所以對式(2)中的約束進行窮盡搜索不具有可行性。然而，文獻[6]已經證明，通過利用最被違反約束(即可使得分和損失函數之和最大化的一組邊界框)便可在多項式時間內獲得最優解。因此，本文借鑒文獻[6]中尋找最被違反約束時使用的思路來對模型參數w進行學習，獲得模型參數w后，接著尋找下一視頻片斷中所有k個目標的最優軌跡集合。

3 軌跡推斷

已知模型參數w和每個視頻幀的密集重疊邊界框后，本文的目標是為每個目標尋找可使式(1)最大化的一個候選窗口序列(稱為軌跡)。該問題屬于一種全局數據關聯問題，本文首先通過對連續幀中的候選施加某種時域一致性約束來降低其指數級的搜索空間，然后提出一種目標身份感知網絡流量技術(target identity-aware network flow，TINF)，如圖2所示，并通過拉格朗日松馳策略對TINF進行高效優化，最終實現對軌跡的準確推斷。在圖2中，大的圓圈表示每個幀中的所有候選位置(密集分布在整個幀內)。通過k條觀察邊相連的一對節點可表示各個候選位置，一條觀察邊對應一種身份。網絡中有k個源節點和k個匯點，每個源節點或匯點屬于一個目標。每個身份用一種單獨顏色表示。進入各個節點的流量只能取3條觀察邊中的某一條，具體視其所隸屬的源節點(身份)而定。與其它幀的節點相連的過渡邊表示一個目標從某一位置到另一位置的可能移動，且每次移動均關聯一個轉移成本。在起始/匯節點和圖中其它每個節點之間存在一條邊，這是為了考慮人體進入或離開場景這一情況。出于簡便考慮，我們只給出了部分進入/離開邊。

圖2 本文方法對3種身份進行推理時使用的網絡

網絡流量是一個二元指示量，當節點為軌跡一部分時為1，否則為0。利用每個源節點推入單位流量，通過使分配給流量的成本最小化來確定所有目標的軌跡。此外，我們將稍后證明，如果為經過邊界框觀察邊的流量設置上限，便可保證一個候選位置最多只屬于一條軌跡。在下面小節中，我們首先將上述問題建模為拉格朗日松馳優化問題，然后給出用于代替目標檢測算法非最大貪婪抑制策略的空間約束。

3.1 目標身份感知的網絡流量(TINF)

首先構建圖形G(V,E)。對幀t中的每個候選窗口，考慮通過k條不同觀察邊相連的一對節點，這些觀察邊分別對應于一種身份。對幀t中的每個節點vp以及幀t+1中的節點vq，如果vq在vp鄰域內，則這兩個節點間存在一條過渡邊。節點vp的鄰域可定義為

(4)

(5)

(6)

(7)

經過這些邊的流量必須滿足一定約束，才可以切實保證它可以表示真實世界中的軌跡。針對G(V,E)定義的一組約束如下

(8)

(9)

(10)

式(8)中的約束為供應/需求約束，要求到達節點的流量之和等于離開該節點的流量之和。式(10)中的約束將經過各個節點的流量之和的上限設置為1，來規定不同身份的軌跡不會共享同一節點。依據文獻[7]可知，式(7)是一種典型的整數規劃問題(integer programming，IP)，該問題為完全NP難題，在實踐中往往采取松馳策略，將該問題轉化為線性規劃問題(linear programming，LP)進行求解。本文中，我們為該問題提出一種拉格朗日松馳解。我們將證明，對硬性約束松馳后，上述問題在每次迭代時將會化簡成為最優目標跟蹤算法問題，利用動態規劃方法，可在多項式時間內獲得該問題的全局解。此外，本文還通過采用兼顧了空間約束的迭代優化策略進一步提升了跟蹤性能。

3.2 TINF問題的拉格朗日松馳解

本文采用的拉格朗日松馳方法的核心思想是對硬性約束進行放松，并將其放到目標函數中，進而獲得一種簡單近似。我們首先對式(10)中的約束條件進行松弛，引入非負拉格朗日乘子λij。λ表示拉格朗日乘子向量，向量維度等于G(V,E)中的邊數量。式(10)中的約束條件松弛之后，新的目標函數可表示為

(11)

對其進一步簡化后，我們有

(12)

條件為

(13)

(14)

(2)根據式(15)更新拉格朗日乘子

(15)

式中：λq表示第q次迭代時的拉格朗日乘子，θq表示以當前解為起點的步長，且[α]+=max(0,α)。

3.3 空間約束

(16)

(17)

圖3 軌跡混淆現象VS空間約束

我們發現，對高度重疊的兩個節點進行懲罰，有時會導致某一軌跡邊界框的精度較低。因此，我們根據式(1)中的得分函數，只對軌跡得分較低的觀察節點進行懲罰。綜上所述，集成了空間約束的拉格朗日松馳方法如算法1所示。

算法1：TINF的拉格朗日松馳解

輸入：T個幀的候選窗口；每個身份的模型參數(wk)

輸出：K個身份的跟蹤結果

—構建TINF圖G(V,E)

—對拉格朗日乘子和空間約束乘子初始化，λ=0,ρ=0,θ=1,q=1

While未收斂時do

—求解每個身份的最小成本流量(fk)

—更新拉格朗日乘子；

—對空間約束乘子進行更新；

—對邊緣成本進行更新；

—更新步長

q=q+1

End

4 仿真實驗

本文采用目前常用的Parking Lot 1-2序列、TUD Crossing序列、PET序列、以及目標發生大幅關節運動的兩個新型數據序列(Running序列和Dancing序列)等[9]作為測試對象，評估了本文算法的性能。初始化時，我們通過手工標注的方法對目標初始化。對進入場景的每個目標，標注4個初始邊界框。同時給出目標利用預訓練目標檢測算法進行自動初始化的運行結果。對手動標注，目標只初始化一次，不會進行再次初始化。實驗中利用方向梯度直方圖(HOG)和彩色直方圖作為目標的特征。HOG特征描述了目標的邊緣信息，有助于將目標從背景中檢測出來；而彩色直方圖屬于視頻特征，有助于不同目標的鑒別。數據序列被劃分為多個數據段，每個數據段包含20個視頻幀。每次時間跨度結束時，我們將軌跡得分與預定義閾值做比較，進而確定該軌跡是否有效。如果軌跡有效，則將其用于模型更新。

利用目前典型的CLEAR MOT指標(MOTA-MOTP)[10]和軌跡指標(MT，ML，IDS)[11]作為評價標準。其中，MOTP(multiple object tracking precision)指多目標跟蹤的精確度，體現在確定目標位置上的精確度；MOTA(multiple object tracking accuracy)指多目標跟蹤的準確度，體現在確定目標的個數，以及有關目標的相關屬性方面的準確度；MT指成功跟蹤率高于80%的未丟失軌跡的比例；ML指成功跟蹤率低于20%的嚴重丟失軌跡的比例；IDS指跟蹤軌跡的匹配ID的變換次數。CLEAR指標(MOTA-MOTP)將整個視頻看成一個整體，而TBM指標將每個軌跡的行為分開對待。這些指標描述了跟蹤算法的不同方面，因此有必要在比較跟蹤算法性能時將這些指標同時考慮，以便全面掌握各個跟蹤算法的優缺點。表1給出了本文方法與目前較為典型的目標檢測與跟蹤算法(LPD[12],LDA[13],DLP[14],H2T[15],GMCP[16],PF[17],CET[18],DCT[19],GOG[20],STRUCK[21]和SPOT[22]等)的定量比較結果。其中，所有其它算法的設置均為算法作者給出的默認設置。從表1可以看到，本文算法的5種性能指標在大多數情況下都要優于其它的算法。仔細分析其原因可知，這是由于本文算法可在檢測和數據關聯并行化框架下實現多目標跟蹤，通過采用結構化學習策略，總是能推斷出視頻片斷中所有目標的最佳位置，因此性能更好。

表1 不同方法的定量比較結果

為了明確展示本文空間約束的影響，我們分別對包含空間約束和不包含空間約束的數據集運行本文算法，實驗結果見表2。從表2可以看到，當包含空間約束時，本文算法在幾種數據集中的性能都有不同程度地提升。對于目標發生重疊的數據序列，算法增益更為明顯。

表2 支持空間約束和不支持空間約束時本文方法的性能

在初始化時，除了人工標注外，我們還可以采用文獻[8]中的預訓練人體檢測算法進行目標的自動初始化。對每個視頻段，如果連續視頻幀中發生至少4次嚴重重疊的高置信度檢測并且未與任何其它軌跡相關聯，則對新軌跡初始化。我們采用人體檢測效果顯著的Parking Lot 1-2序列和TUD Crossing序列測試了目標自動初始化情況下的本文算法性能，實驗結果見表3。從表3可以看到，采用自動初始化策略時，本文方法的性能并沒有顯著變化，MOTA、MOTP和MT等性能反而略有下降。這主要是因為，與人工標注方法相比，部分序列的部分軌跡起始時間較晚，由于虛警現象增加，MOTA等性能出現下降。

表3 目標進行自動初始化和手動初始化時本文方法的性能

最后，為了比較采用IP或LP時本文拉格朗日松馳方法的復雜性，我們分別部署了本文方法的IP和LP版本。采用文獻[3]中的CPLEX作為優化工具箱，選用Parking Lot 2序列作為實驗對象(采用其它數據序列可得類似結果)。圖4給出了本文方法的3種版本的運行時間比較結果(縱坐標采用對數標度)。從圖4中可以看到，本文優化方法的效率遠高于IP和LP方法。隨著目標數量的增加，3種方法的運行時間都有所上升，但本文拉格朗日松馳方法的運行時間要遠低于IP和LP版本的運行時間。此外，拉格朗日松馳方法的運行時間增長趨勢趨于穩定，這表明本文方法具有較好的魯棒性，能夠在目標數量動態變化的情況下快速地實現目標跟蹤。

圖4 不同方法的運行時間比較

5 結束語

針對現有的目標跟蹤算法的不足，本文提出了一種綜合了結構化學習和全局數據關聯的跟蹤算法。本文方法的核心是為每個目標學習一個模型的結構化學習過程。將推理過程看成全局數據關聯問題，并給出一種目標身份感知網絡流量方法進行求解。實驗結果表明，本文方法在多種場景下的性能均優于傳統的目標跟蹤算法。在下一步研究工作中，我們將對復雜背景下的分層關聯多目標跟蹤問題展開研究，以MOTA為優化目標，擬采用圖分割、邊著色等技術來實現多目標的快速可靠跟蹤。

參考文獻：

[1]JIANG Mingxin,WANG Peichang,WANG Hongyu.Height estimation algorithm based on visual multi-object tracking[J].Acta Electronica Sinica,2015,43(3):591-596(in Chinese).[姜明新,王培昌,王洪玉.基于視頻多目標跟蹤的高度測量算法[J].電子學報,2015,43(3):591-596.]

[2]LU Hong,LI Hongsheng,FEI Shumin,et al.Block-level saliency centroid representation and multi-level association based multi-target tracking[J].Systems Engineering and Electro-nics,2015,37(9):2182-2190(in Chinese).[路紅,李宏勝,費樹岷,等.融合塊顯著質心描述和多級關聯的多目標跟蹤[J].系統工程與電子技術,2015,37(9):2182-2190.]

[3]Shu G,Dehghan A,Oreifej O,et al.Part-based multiple-person tracking with partial occlusion handling[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Press,2016:1815-1821.

[4]Pirsiavash H,Ramanan D,Fowlkes CC.Globally-optimal greedy algorithms for tracking a variable number of objects[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Press,2016:1201-1208.

[6]Sun C,Wang D,Lu H.Person re-identification via distance metric learning with latent variables[J].IEEE Transactions on Image Processing,2016,26(1):23-34.

[7]Türetken E,Benmansour F,Andres B,et al.Reconstructing curvilinear networks using path classifiers and integer programming[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(12):2515-2530.

[8]Girshick R,Donahue J,Darrell T,et al.Region-based convolutional networks for accurate object detection and segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(1):142-158.

[9]Kalogeiton V,Ferrari V,Schmid C.Analysing domain shift factors between videos and images for object detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(11):2327-2334.

[11]Wang X,Türetken E,Fleuret F,et al.Tracking interacting objects using intertwined flows[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(11):2312-2326.

[12]Tang S,Andriluka M,Milan A,et al.Learning people detectors for tracking in crowded scenes[C]//Proceedings of the IEEE International Conference on Computer Vision.Australia:IEEE Press,2013:1049-1056.

[13]Segal AV,Reid I.Latent data association:Bayesian model selection for multi-target tracking[C]//Proceedings of the IEEE International Conference on Computer Vision.France:IEEE Press,2016:2904-2911.

[14]Amit Kumar KC,De Vleeschouwer C.Discriminative label propagation for multi-object tracking with sporadic appearance features[C]//Proceedings of the IEEE International Confe-rence on Computer Vision.France:IEEE Press,2016:2000-2007.

[15]Wen L,Li W,Yan J,et al.Multiple target tracking based on undirected hierarchical relation hypergraph[C]//Procee-dings of the IEEE Conference on Computer Vision and Pattern Recognition.France:IEEE Press,2016:1282-1289.

[16]Zamir AR,Dehghan A,Shah M.Gmcp-tracker:Global multi-object tracking using generalized minimum clique graphs[C]//IEEE International Conference on Computer Vision.Chile:IEEE Press,2015:343-356.

[17]Breitenstein MD,Reichlin F,Leibe B,et al.Robust trac-king-by-detection using a detector confidence particle filter[C]//Proceedings of the IEEE International Conference on Computer Vision.France:IEEE Press,2016:1515-1522.

[18]Vo BN,Vo BT,Phung D.Labeled random finite sets and the Bayes multi-target tracking filter[J].IEEE Transactions on Signal Processing,2014,62(24):6554-6567.

[19]Andriyenko A,Schindler K,Roth S.Discrete-continuous optimization for multi-target tracking[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Press,2012:1926-1933.

[20]Milan A,Roth S,Schindler K.Continuous energy minimization for multitarget tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(1):58-72.

[21]Hare S,Saffari A,Torr PHS.Struck:Structured output tracking with kernels[C]//Proceedings of the IEEE International Conference on Computer Vision.France:IEEE Press,2016:263-270.

[22]Zhang L,Laurens VDM.Structure preserving object tracking[C]//IEEE Conference on Computer Vision and Pattern Re-cognition.USA:IEEE Press,2013:1838-1845.