多目標(biāo)跟蹤中基于結(jié)構(gòu)化學(xué)習(xí)的目標(biāo)身份感知網(wǎng)絡(luò)流量技術(shù)研究

張新琳,張 銳

(駐馬店職業(yè)技術(shù)學(xué)院，河南 駐馬店 463000)

0 引 言

多目標(biāo)跟蹤(Multi-Target Tracking, MOT)[1,2]是視頻監(jiān)視、行為預(yù)測、運(yùn)動視頻分析等多種計(jì)算機(jī)視覺領(lǐng)域的關(guān)鍵問題。近期提出的大部分算法均按照如下2個(gè)步驟來解決MOT問題：目標(biāo)檢測和數(shù)據(jù)關(guān)聯(lián)。在檢測階段，利用事先訓(xùn)練好的目標(biāo)檢測器來確定每個(gè)視頻幀中的潛在目標(biāo)位置。確定潛在目標(biāo)位置后，數(shù)據(jù)關(guān)聯(lián)階段對潛在目標(biāo)進(jìn)行修剪，并在圖像間形成軌跡。其中，在目標(biāo)檢測方面，段玉瑤等[3]針對生豬多目標(biāo)跟蹤過程中豬舍內(nèi)光照情況復(fù)雜、生豬間遮擋等問題，開發(fā)了一套基于計(jì)算機(jī)視覺技術(shù)的多目標(biāo)檢測與跟蹤方法。該方法將灰度差分、s通道差分和幀間差分所獲取的差分圖像相融合，能夠有效消除陰影對跟蹤的影響，跟蹤準(zhǔn)確率大于85%。劉紅亮等[4]提出一種航跡恒虛警的目標(biāo)檢測跟蹤一體化算法。它可以大大提高目標(biāo)檢測概率，同時(shí)也可以保證目標(biāo)突然消失時(shí)航跡能夠以較高的概率結(jié)束。針對標(biāo)記點(diǎn)處理方法用于多目標(biāo)跟蹤時(shí)效果不佳的問題，陳家紅等[5]提出一種多目標(biāo)聯(lián)合檢測跟蹤算法。在有高斯噪聲情況下，與其他跟蹤算法相比，該算法的檢測和跟蹤相似度最高，在衛(wèi)星圖像序列和自采集視頻中的精度和召回率也最高，整體性能較優(yōu)。

在數(shù)據(jù)關(guān)聯(lián)方面，現(xiàn)有的算法可以分為兩大類：1)局部關(guān)聯(lián)[6,7]：這類算法屬于時(shí)域局部算法，在求解數(shù)據(jù)關(guān)聯(lián)問題時(shí)只考慮部分幀。雖然該類算法的計(jì)算量較小，但是它們?nèi)菀装l(fā)生ID交換問題，并且對長期/短期遮擋、姿態(tài)變化和攝像機(jī)移動時(shí)的跟蹤難度很大。2)全局關(guān)聯(lián)[8,9]：在全局關(guān)聯(lián)算法中，視頻幀數(shù)量有所上升，甚至為了推斷出目標(biāo)軌跡而一次性處理整個(gè)視頻。雖然基于數(shù)據(jù)關(guān)聯(lián)的跟蹤算法展示了自身潛力，但仍然存在重大缺陷：算法性能嚴(yán)重依賴于目標(biāo)檢測器的性能。如果目標(biāo)檢測器的虛警率或漏警率較高，數(shù)據(jù)關(guān)聯(lián)將會失敗。為此，本文提出一種改進(jìn)的多目標(biāo)跟蹤算法，將一種新的全局?jǐn)?shù)據(jù)關(guān)聯(lián)策略集成到結(jié)構(gòu)化學(xué)習(xí)跟蹤器的推理過程中，實(shí)現(xiàn)檢測和全局?jǐn)?shù)據(jù)關(guān)聯(lián)的同步。總體來說，本文的貢獻(xiàn)如下：(1)提出一種綜合了結(jié)構(gòu)化學(xué)習(xí)和全局?jǐn)?shù)據(jù)關(guān)聯(lián)的新的多目標(biāo)跟蹤模型；(2)提出一種新的目標(biāo)身份感知網(wǎng)絡(luò)流量技術(shù)，并通過拉格朗日松馳策略對其進(jìn)行高效優(yōu)化；(3)采用軟性空間約束取代了傳統(tǒng)目標(biāo)檢測算法中的非最大貪婪抑制策略[8]，進(jìn)一步提升了檢測結(jié)果；(4)驗(yàn)證了本文方法對高難度數(shù)據(jù)序列的性能要優(yōu)于其他最新算法。

1 本文算法

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

圖1 多個(gè)視頻幀中某一人體的跟蹤過程示例

2 目標(biāo)模型

(1)

(2)

(3)

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

3 軌跡推斷

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

圖2 本文方法對3種身份進(jìn)行推理時(shí)使用的網(wǎng)絡(luò)

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

3.1 目標(biāo)身份感知的網(wǎng)絡(luò)流量(TINF)

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

(4)

(5)

(6)

(7)

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

(8)

(9)

(10)

式(8)中的約束為供應(yīng)/需求約束，要求到達(dá)節(jié)點(diǎn)的流量之和等于離開該節(jié)點(diǎn)的流量之和。式(10)中的約束將經(jīng)過各個(gè)節(jié)點(diǎn)的流量之和的上限設(shè)置為1，來規(guī)定不同身份的軌跡不會共享同一節(jié)點(diǎn)。依據(jù)文獻(xiàn)[12]可知，式(7)是一種典型的整數(shù)規(guī)劃問題(Integer Programming, IP)，該問題為完全NP難題，在實(shí)踐中往往采取松馳策略，將該問題轉(zhuǎn)化為線性規(guī)劃問題(Linear Programming, LP)進(jìn)行求解。本文中，我們?yōu)樵搯栴}提出一種拉格朗日松馳解。我們將證明，對硬性約束松馳后，上述問題在每次迭代時(shí)將會化簡成為最優(yōu)目標(biāo)跟蹤算法問題，利用動態(tài)規(guī)劃方法，可在多項(xiàng)式時(shí)間內(nèi)獲得該問題的全局解。此外，本文還通過采用兼顧了空間約束的迭代優(yōu)化策略進(jìn)一步提升了跟蹤性能。

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

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

(11)

對其進(jìn)一步簡化后，我們有：

(12)

條件為：

(13)

(14)

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

(15)

其中λq表示第q次迭代時(shí)的拉格朗日乘子，θq表示以當(dāng)前解為起點(diǎn)的步長，且[α]+=max(0,α)。

圖3 軌跡混淆現(xiàn)象VS空間約束

3.3 空間約束

(16)

(17)

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

算法1:TINF的拉格朗日松馳解輸入:T個(gè)幀的候選窗口;每個(gè)身份的模型參數(shù)(wk)輸出:K個(gè)身份的跟蹤結(jié)果—構(gòu)建TINF圖G(V,E)—對拉格朗日乘子和空間約束乘子初始化,λ=0,ρ=0,θ=1,q=1While 未收斂時(shí) do —求解每個(gè)身份的最小成本流量(fk) —更新拉格朗日乘子;

λq+1ij=λqij+θq(∑Kkfkij-1) + —對空間約束乘子進(jìn)行更新; ρq+1ij=[ρqij+θq[(yti∩ytj)-0.5]+exp((yti∩ytj)-0.5)/2]+ —對邊緣成本進(jìn)行更新; cq+1,kij=ckij+λq+1ij+ρq+1ij —更新步長 θq+1=1q q=q+1End

4 仿真實(shí)驗(yàn)

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

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

表1 不同方法的定量比較結(jié)果

為了明確展示本文空間約束的影響，我們分別對包含空間約束和不包含空間約束的數(shù)據(jù)集運(yùn)行本文算法，實(shí)驗(yàn)結(jié)果如表2所示。從表2可以看到，當(dāng)包含空間約束時(shí)，本文算法在幾種數(shù)據(jù)集中的性能都有不同程度地提升。對于目標(biāo)發(fā)生重疊的數(shù)據(jù)序列，算法增益更為明顯。

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

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

表3 目標(biāo)進(jìn)行自動初始化和手動初始化時(shí)本文方法的性能

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

圖4 不同方法的運(yùn)行時(shí)間比較

5 結(jié) 語

針對現(xiàn)有的目標(biāo)跟蹤算法的不足，本文提出了一種綜合了結(jié)構(gòu)化學(xué)習(xí)和全局?jǐn)?shù)據(jù)關(guān)聯(lián)的新的跟蹤算法。本文方法的核心是為每個(gè)目標(biāo)學(xué)習(xí)一個(gè)模型的結(jié)構(gòu)化學(xué)習(xí)過程。將推理過程看成全局?jǐn)?shù)據(jù)關(guān)聯(lián)問題，并給出一種目標(biāo)身份感知網(wǎng)絡(luò)流量方法進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，本文方法在多種場景下的性能均優(yōu)于傳統(tǒng)的目標(biāo)跟蹤算法。在下一步研究工作中，我們將對復(fù)雜背景下的分層關(guān)聯(lián)多目標(biāo)跟蹤問題展開研究，以 MOTA為優(yōu)化目標(biāo)，擬采用圖分割、邊著色等技術(shù)來實(shí)現(xiàn)多目標(biāo)的快速可靠跟蹤。