基于馬爾科夫決策過(guò)程的多目標(biāo)跟蹤算法

王詩(shī)言，吳華東，余 翔

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

目標(biāo)跟蹤是計(jì)算機(jī)視覺(jué)中的一個(gè)重要問(wèn)題。通過(guò)檢測(cè)的方法進(jìn)行跟蹤已廣泛用于異常行為分析和智能交通等許多領(lǐng)域。在多目標(biāo)跟蹤(multiple object tracking，MOT)中，關(guān)鍵是如何有效處理目標(biāo)遮擋和數(shù)據(jù)關(guān)聯(lián)問(wèn)題。解決此問(wèn)題的經(jīng)典解決方案是提取目標(biāo)的單個(gè)特征，例如運(yùn)動(dòng)特征[1-2]，然后計(jì)算特征的相似度，以此來(lái)確定兩個(gè)目標(biāo)是否屬于同一軌跡。該方法具有計(jì)算簡(jiǎn)單，速度快的特點(diǎn)，但跟蹤成功率不高，實(shí)際應(yīng)用效果較差。為了彌補(bǔ)該方法的不足，更好地描述目標(biāo)，研究人員通過(guò)結(jié)合幾種不同的特征進(jìn)行處理，以提高跟蹤器的性能。例如，利用多特征融合的方法[3]，改善了跟蹤效果，同時(shí)還減少了標(biāo)識(shí)切換的總數(shù)。但是，目標(biāo)遮擋問(wèn)題仍然沒(méi)有很好得到解決。

隨著機(jī)器學(xué)習(xí)的興起，結(jié)合了機(jī)器學(xué)習(xí)方法的目標(biāo)跟蹤算法蓬勃發(fā)展，并逐漸超越傳統(tǒng)方法，特別是在提取目標(biāo)特征的處理方法上，具有更大優(yōu)勢(shì)。文獻(xiàn)[4]通過(guò)訓(xùn)練卷積網(wǎng)絡(luò)模型，身份交換(ID switch)的次數(shù)減少了45%。同樣，通過(guò)卷積網(wǎng)絡(luò)提取人體不同部位的特征，然后將其組合，可以獲得對(duì)人體外觀的更好描述[5]。雖然精度得到了進(jìn)一步提高，但是跟蹤速度太慢而不能滿(mǎn)足實(shí)時(shí)要求的問(wèn)題也很明顯。為了處理數(shù)據(jù)關(guān)聯(lián)問(wèn)題，文獻(xiàn)[6]將兩個(gè)圖像片段直接輸入到孿生神經(jīng)網(wǎng)絡(luò)(siamese network)中，并直接輸出兩個(gè)目標(biāo)是否屬于同一軌跡的結(jié)論，但跟蹤效果和速度都不太令人滿(mǎn)意。而最近的評(píng)估結(jié)果表明，基于邊界框跟蹤的性能提升趨近飽和，而基于低層信息(像素級(jí)別)的跟蹤有望進(jìn)一步提升跟蹤器性能[7-9]。

基于上述研究，在多目標(biāo)跟蹤領(lǐng)域，不僅要處理單個(gè)目標(biāo)的消失、遮擋等情況，更要解決多個(gè)目標(biāo)之間互相干擾的問(wèn)題。跟蹤算法能否捕捉目標(biāo)狀態(tài)的改變決定著跟蹤性能的好壞。而馬爾科夫模型能夠有效預(yù)測(cè)多個(gè)狀態(tài)的轉(zhuǎn)移概率，該模型的特點(diǎn)正好能解決多目標(biāo)跟蹤問(wèn)題中的關(guān)鍵難點(diǎn)。由此出發(fā)，本文提出一種基于馬爾科夫決策過(guò)程(Markov decision process，MDP)的多目標(biāo)跟蹤算法，利用目標(biāo)不同狀態(tài)之間的轉(zhuǎn)移關(guān)系，學(xué)習(xí)每個(gè)狀態(tài)特有的策略，解決了多目標(biāo)跟蹤中遮擋和快速運(yùn)動(dòng)的問(wèn)題。圖1為所提算法的流程圖。其中，對(duì)不同狀態(tài)下的MDP策略和分類(lèi)器訓(xùn)練是本文提出算法的重點(diǎn)。在多目標(biāo)跟蹤領(lǐng)域，能否有效捕捉目標(biāo)狀態(tài)改變等信息，很大程度決定了跟蹤器的性能。因?yàn)轳R爾科夫模型能夠有效解決狀態(tài)之間的轉(zhuǎn)移問(wèn)題，因此可將其運(yùn)用到本文提出的算法中來(lái)。本文將在線(xiàn)多目標(biāo)跟蹤建模成馬爾科夫過(guò)程中的決策模型，將一個(gè)目標(biāo)在視頻中從出現(xiàn)到消失的過(guò)程建模成MDP，如圖2。在每個(gè)MDP中的每一個(gè)狀態(tài)，都學(xué)習(xí)對(duì)應(yīng)的策略來(lái)決定狀態(tài)的改變。本文用超像素度量因子和重疊率來(lái)計(jì)算軌跡之間的關(guān)聯(lián)程度。將數(shù)據(jù)關(guān)聯(lián)中的學(xué)習(xí)相似性函數(shù)看作是MDP中的學(xué)習(xí)策略。另外，本文還將目標(biāo)的出現(xiàn)和消失看作是馬爾科夫決策過(guò)程中的狀態(tài)轉(zhuǎn)移，然后使用現(xiàn)有的單目標(biāo)跟蹤方法來(lái)處理這類(lèi)問(wèn)題。通過(guò)2DMOT2015基準(zhǔn)測(cè)試表明，在多目標(biāo)跟蹤精度(multide object tracking accuracy,MOTA)這一指標(biāo)上，本文提出的算法與其他對(duì)比算法相比，具有更高的得分，同時(shí)在跟蹤速度上也有更好的效果。與此同時(shí)，本文提出的算法也能有效解決遮擋和快速運(yùn)動(dòng)問(wèn)題。

圖1 算法流程圖Fig.1 Algorithm flowchart

圖2 多目標(biāo)跟蹤問(wèn)題轉(zhuǎn)化為馬爾科夫決策過(guò)程Fig.2 Multi-target tracking transformed into Markov decision process

1 在線(xiàn)多目標(biāo)跟蹤模型框架

1.1 MDP定義

將每一個(gè)目標(biāo)從出現(xiàn)到消失的整個(gè)過(guò)程建模成一個(gè)馬爾科夫決策過(guò)程，該決策過(guò)程由以下元組構(gòu)成(S,A,T(·),R(·))：

1)s∈S，其中s表示目標(biāo)的狀態(tài)；

2)a∈A，其中a表示目標(biāo)執(zhí)行操作，A表示動(dòng)作集合；

3)T:S×A→S，其中T表示狀態(tài)轉(zhuǎn)移函數(shù)，描述了在每個(gè)目標(biāo)狀態(tài)將要執(zhí)行的操作和將到達(dá)的下一個(gè)狀態(tài)；

4)R:S×A→，其中R表示獎(jiǎng)勵(lì)函數(shù)，定義了在狀態(tài)s情況下，執(zhí)行了操作a后的回報(bào)。

狀態(tài)轉(zhuǎn)移。把MDP中的狀態(tài)分為4個(gè)子集：S=S活躍∪S已跟蹤∪S丟失∪S不活躍。圖3為4個(gè)子集之間的狀態(tài)轉(zhuǎn)移關(guān)系?！盎钴S”狀態(tài)是每個(gè)目標(biāo)的初始狀態(tài)，當(dāng)檢測(cè)到目標(biāo)即進(jìn)入該狀態(tài)?！盎钴S”狀態(tài)可以轉(zhuǎn)換到“已跟蹤”或“不活躍”狀態(tài)。理想情況下，從目標(biāo)檢測(cè)器得到正確結(jié)果后，目標(biāo)將進(jìn)入“已跟蹤”狀態(tài)，當(dāng)發(fā)生錯(cuò)報(bào)、誤報(bào)即進(jìn)入“不活躍”狀態(tài)。進(jìn)入到“已跟蹤”狀態(tài)的目標(biāo)可以繼續(xù)保持該狀態(tài)，若發(fā)生遮擋、從視野中消失等情況，就會(huì)暫時(shí)進(jìn)入“丟失”狀態(tài)。同理，“丟失”狀態(tài)的目標(biāo)或者繼續(xù)保持該狀態(tài)，或者因?yàn)樵俅纬霈F(xiàn)在視野中而進(jìn)入“已跟蹤”狀態(tài)，或者由于已經(jīng)丟失足夠長(zhǎng)的時(shí)間而進(jìn)入到“不活躍”狀態(tài)。最終，“不活躍”狀態(tài)就是每個(gè)目標(biāo)的終止?fàn)顟B(tài)，且不能跳出。

圖3 4個(gè)子集的狀態(tài)轉(zhuǎn)移圖Fig.3 State transition diagram of four subsets

狀態(tài)轉(zhuǎn)移函數(shù)。各個(gè)目標(biāo)狀態(tài)間有7個(gè)可能的轉(zhuǎn)移，圖3所示為各個(gè)狀態(tài)和轉(zhuǎn)移關(guān)系。在MDP中，所有的轉(zhuǎn)移都是確定性的。例如，在“丟失”狀態(tài)上執(zhí)行轉(zhuǎn)移a6，目標(biāo)就會(huì)進(jìn)入到“已跟蹤”狀態(tài)：T(s丟失,a6)=s已跟蹤。

獎(jiǎng)勵(lì)函數(shù)。在提出的MDP框架中，對(duì)獎(jiǎng)勵(lì)函數(shù)根據(jù)不同狀態(tài)進(jìn)行差異化設(shè)計(jì)，其具體參數(shù)由已標(biāo)注的訓(xùn)練樣本通過(guò)不同的方法學(xué)習(xí)得到。

1.2 MDP策略

在馬爾科夫決策過(guò)程中，策略π是一個(gè)從狀態(tài)集合S到動(dòng)作集合A的映射，例如π:S→A。給定目標(biāo)的當(dāng)前狀態(tài)，不同的策略會(huì)決定采取何種狀態(tài)轉(zhuǎn)移動(dòng)作。而在MDP中，策略的學(xué)習(xí)就是為了最大化獎(jiǎng)勵(lì)函數(shù)。

1.2.1 “活躍”狀態(tài)下的策略

在“活躍”狀態(tài)下，MDP需要做出決策：將目標(biāo)檢測(cè)保持在“活躍”狀態(tài)或者轉(zhuǎn)移到“不活躍”狀態(tài)。這個(gè)決策可以被理解為跟蹤之前的預(yù)處理步驟。通常使用諸如非最大抑制或閾值檢測(cè)分?jǐn)?shù)之類(lèi)的策略。用歸一化特征向量φ活躍(s)離線(xiàn)訓(xùn)練一個(gè)二進(jìn)制的支持向量機(jī)(support vector machine)，訓(xùn)練樣本是已標(biāo)注的訓(xùn)練數(shù)據(jù)集。其中，φ活躍(s)包含目標(biāo)的二維坐標(biāo)、寬、高和檢測(cè)得分，定義“活躍”狀態(tài)下的獎(jiǎng)勵(lì)函數(shù)為

(1)

(1)式中：(w活躍,b活躍)定義為SVM的超平面；當(dāng)a=a1時(shí)，y(a)=+1；當(dāng)a=a2時(shí)，y(a)=-1。

1.2.2 “已跟蹤”狀態(tài)下的策略

在“已跟蹤”狀態(tài)下，MDP需要判定是繼續(xù)保持這個(gè)狀態(tài)還是轉(zhuǎn)移到“丟失”狀態(tài)。只要目標(biāo)沒(méi)有發(fā)生遮擋或者始終保持在相機(jī)的視野范圍內(nèi)，就應(yīng)該判定繼續(xù)保持“已跟蹤”狀態(tài)，否則就應(yīng)該標(biāo)記為“丟失”狀態(tài)。在這個(gè)狀態(tài)下的決策選擇，類(lèi)似于單目標(biāo)跟蹤[10]。建立一個(gè)基于超像素的表觀模型來(lái)定義目標(biāo)的置信圖，通過(guò)定義前后幀目標(biāo)的置信圖重疊率和全局平均置信圖來(lái)進(jìn)行判別，當(dāng)該表觀模型能在下一幀成功跟蹤目標(biāo)，表明目標(biāo)繼續(xù)處于“已跟蹤”狀態(tài)，否則進(jìn)入“丟失”狀態(tài)。

(2)

(2)式中，Vobcv(i)∈[-1,+1]，那么基于超像素的表觀模型由4個(gè)因子共同構(gòu)建：聚類(lèi)置信值Vobcv(i)，聚類(lèi)中心fc(i)，聚類(lèi)半徑rc(i)和所屬該聚類(lèi)的所有超像素。每一個(gè)聚類(lèi)里面的超像素的置信值為

(3)

(3)式中,

?r=1,…,Nt；i=1,…,n

(4)

(4)式中，O0和V0為閾值，當(dāng)a=a3時(shí)，y(a)=+1；當(dāng)a=a4時(shí)，y(a)=-1。因此，僅當(dāng)Vavg和O(t,t-1)同時(shí)大于設(shè)定的閾值時(shí)，目標(biāo)繼續(xù)保持“已跟蹤”狀態(tài)，否則就進(jìn)入到“丟失”狀態(tài)。在實(shí)驗(yàn)過(guò)程中，閾值的設(shè)定會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生較大影響。閾值過(guò)高，可能出現(xiàn)漏檢，閾值過(guò)低，會(huì)造成誤檢。本文通過(guò)大量實(shí)驗(yàn)測(cè)試得出，當(dāng)兩個(gè)閾值均為0.85時(shí)，跟蹤效果最佳。

圖4 置信圖流程圖Fig.4 Confidence diagram flow chart

1.2.3 “丟失”狀態(tài)下的策略

在“丟失”狀態(tài)下，MDP需要判定目標(biāo)是保持現(xiàn)有狀態(tài)，還是轉(zhuǎn)移到“已跟蹤”狀態(tài)，或者是“不活躍”狀態(tài)。假定目標(biāo)處于“丟失”狀態(tài)的時(shí)間大于T丟失，那么就標(biāo)記為“不活躍”狀態(tài)并結(jié)束本次跟蹤。在此狀態(tài)下策略選擇的難點(diǎn)，是在轉(zhuǎn)移到“已跟蹤”和保持“丟失”之間做出決定。將上述難點(diǎn)視為數(shù)據(jù)關(guān)聯(lián)(data association)問(wèn)題[11]:為了將“丟失”的目標(biāo)轉(zhuǎn)換到“已跟蹤”狀態(tài)，需要將目標(biāo)和檢測(cè)器檢測(cè)到的結(jié)果進(jìn)行關(guān)聯(lián)檢測(cè)，否則目標(biāo)就保持“丟失”狀態(tài)。

(5)

(5)式中：k是M個(gè)潛在檢測(cè)的索引；當(dāng)a=a6時(shí)，y(a)=+1；當(dāng)a=a5時(shí)，則y(a)=-1。綜上，在“丟失”狀態(tài)下進(jìn)行策略學(xué)習(xí)的任務(wù)簡(jiǎn)化為學(xué)習(xí)決策函數(shù)中的參數(shù)(w,b)。

2 基于馬爾科夫決策過(guò)程的多目標(biāo)跟蹤算法

將MDP的策略/獎(jiǎng)勵(lì)應(yīng)用于多目標(biāo)跟蹤問(wèn)題。在多目標(biāo)跟蹤問(wèn)題中，將每一個(gè)目標(biāo)建模成一個(gè)MDP，并用學(xué)習(xí)到的策略來(lái)跟蹤目標(biāo)。給定一個(gè)新的輸入視頻幀，算法根據(jù)每個(gè)MDP所處的不同狀態(tài)做差異性處理。首先，處于“已跟蹤”狀態(tài)的目標(biāo)，根據(jù)已學(xué)習(xí)好的策略判定其跳躍狀態(tài)：繼續(xù)保持“已跟蹤”狀態(tài)還是轉(zhuǎn)換到“丟失”狀態(tài)。其次，對(duì)于“丟失”狀態(tài)的目標(biāo)，若其檢測(cè)值Vodk與任意一個(gè)“已跟蹤”的目標(biāo)沒(méi)有交集(也就證明該檢測(cè)框不屬于“已跟蹤”)，就利用公式f(Tlt,Vod)=wΤφ(Tlt,Vod)+b計(jì)算“丟失”狀態(tài)與上述檢測(cè)值的相似性得分。再次，利用匈牙利算法[12]對(duì)所求得的相似性分?jǐn)?shù)來(lái)獲得檢測(cè)和“丟失”目標(biāo)之間的分配。根據(jù)分配，與某些目標(biāo)檢測(cè)Vodk具有相關(guān)性的丟失目標(biāo)Tlt將轉(zhuǎn)移到“已跟蹤”狀態(tài)。否則，他們會(huì)繼續(xù)處于“丟失”狀態(tài)。最后，如果視頻中檢測(cè)到新目標(biāo)，其檢測(cè)值為Vodk時(shí)，用該檢測(cè)值作為新目標(biāo)t的初始值。如果根據(jù)所學(xué)策略執(zhí)行了a1，就進(jìn)入“已跟蹤”狀態(tài)，否則進(jìn)入“不活躍”狀態(tài)。算法1詳細(xì)介紹了使用MDP的多目標(biāo)跟蹤算法。需要指出的是，處于“已跟蹤”狀態(tài)的目標(biāo)比處“丟失”狀態(tài)的目標(biāo)具有更高的優(yōu)先級(jí)。

算法1 整體算法流程

1.初始化：Tra←?

2.for視頻序列v中的第l幀

3.for軌跡Tra中的“已跟蹤”目標(biāo)ti

4.根據(jù)策略，將ti轉(zhuǎn)移到下一個(gè)狀態(tài)

5.end

6.for軌跡Tra中的“丟失”目標(biāo)ti

7.for與跟蹤目標(biāo)沒(méi)有任何重疊的檢測(cè)值Vodk

8.f(Tlti,Vodi)=wΤφ(Tlti,Vodi)+b

9.end

10.end

11.使用匈牙利算法對(duì)“丟失”目標(biāo)記性數(shù)據(jù)關(guān)聯(lián)

12.for軌跡Tra中的“丟失”目標(biāo)ti

13.根據(jù)分配的值，將ti轉(zhuǎn)移到下一個(gè)狀態(tài)

14.end

15.for出現(xiàn)新目標(biāo)t，其檢測(cè)值為Vodk

16.為新目標(biāo)t用檢測(cè)值Vodk初始化MDP

17.if跟蹤策略執(zhí)行了狀態(tài)動(dòng)作a1

18.將目標(biāo)t轉(zhuǎn)移到“已跟蹤”

19.Tra←Tra∪{t}

20.else

21.將目標(biāo)t轉(zhuǎn)移到“不活躍”

22.end

23.end

24.end

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)在MOT15[13]基準(zhǔn)測(cè)試數(shù)據(jù)集中評(píng)估了跟蹤器的性能。該基準(zhǔn)測(cè)試評(píng)估具有測(cè)試序列的跟蹤性能，包括帶有移動(dòng)攝像頭的正面視圖場(chǎng)景下的監(jiān)控設(shè)置。評(píng)估指標(biāo)如表1(表中l(wèi)ower表示越低越好，higher表示越高越好)。其中，MOTA包含誤報(bào)數(shù)量、丟失目標(biāo)數(shù)量和身份交換次數(shù)信息，這項(xiàng)指標(biāo)能夠有效反映跟蹤器性能。

表1 多目標(biāo)跟蹤的評(píng)價(jià)指標(biāo)Tab.1 Evaluation for multi-target tracking

圖5是跟蹤結(jié)果的可視化圖像。在圖5中，按照紅橙黃綠青藍(lán)紫的順序分別對(duì)應(yīng)目標(biāo)1，目標(biāo)2，…，目標(biāo)7。在序列ADL-Rundle-1中，在第40幀和第90幀，目標(biāo)4(綠色框)與周?chē)繕?biāo)1(紅色框)的距離較近。LMF和文獻(xiàn)[15]的算法，由于未能正確進(jìn)行數(shù)據(jù)關(guān)聯(lián)，不同目標(biāo)之間的信息相互干擾，導(dǎo)致跟蹤框有所偏移。而本文提出的算法，利用超像素度量因子和重疊率因子作為衡量標(biāo)準(zhǔn)，能夠始終保證跟蹤準(zhǔn)確。在第40，202幀，目標(biāo)6(藍(lán)色框)、目標(biāo)7(紫色框)與周?chē)繕?biāo)具有相似外觀，與本文對(duì)比的兩種算法相比均有不同程度的漂移，甚至跟錯(cuò)了目標(biāo)。

圖5 跟蹤結(jié)果可視化Fig.5 Visualization of tracking results

遮擋方面，在序列TUD-Campus中，目標(biāo)1經(jīng)過(guò)目標(biāo)6遮擋后，對(duì)比算法未能在目標(biāo)1再次出現(xiàn)時(shí)跟蹤上，最終跟錯(cuò)目標(biāo)。對(duì)于發(fā)生遮擋的目標(biāo)，其狀態(tài)如何改變難以確定。而本文提出的算法，將目標(biāo)建模成一個(gè)馬爾科夫決策過(guò)程，充分考慮了狀態(tài)之間的關(guān)聯(lián)，并且利用學(xué)習(xí)策略進(jìn)行狀態(tài)轉(zhuǎn)移，能夠有效處理目標(biāo)遮擋的情況。

本文算法結(jié)合歷史圖像信息，建立了基于超像素的表觀模型，在目標(biāo)快速移動(dòng)時(shí)，同樣有較好的表現(xiàn)。在序列ETH-Crossing中，對(duì)于快速移動(dòng)的目標(biāo)4，提出的算法出現(xiàn)少許偏移，但是相較于對(duì)比算法還是更具魯棒性。

表2展示了本文算法在MOT15數(shù)據(jù)集中對(duì)目標(biāo)跟蹤任務(wù)的9項(xiàng)指標(biāo)對(duì)比結(jié)果?？偟膩?lái)說(shuō)，本文提出的算法將目標(biāo)建模成馬爾科夫決策過(guò)程，并在決策階段加入了基于超像素的表觀模型，同時(shí)引入了全局平均置信值Vavg和置信圖重疊率O(t,t-1)，成功地提升了模型的性能。在MOTA指標(biāo)上，本文算法能夠達(dá)到36.5，高于其他對(duì)比算法。同時(shí)返回較少數(shù)量的身份切換，保持具有競(jìng)爭(zhēng)性的False Negatives。仿真的跟蹤準(zhǔn)確性主要受到大量False Negatives的影響。鑒于對(duì)MOTA 得分的總體影響，檢測(cè)應(yīng)用更大的置信度閾值可能會(huì)增加所述算法的大幅度余量。然而，對(duì)跟蹤輸出的視覺(jué)檢查表明，這些False Negatives主要是由靜態(tài)場(chǎng)景的目標(biāo)檢測(cè)器響應(yīng)產(chǎn)生的。同時(shí)，實(shí)驗(yàn)中沒(méi)有觀察到經(jīng)常在False Negatives 之間變化的軌跡。

表2 4種算法的多目標(biāo)跟蹤評(píng)價(jià)指標(biāo)對(duì)比Tab.2 Comparison of multi-target tracking evaluation indexes of four algorithms

4 結(jié)束語(yǔ)

本文提出了一種基于馬爾可夫決策過(guò)程的多目標(biāo)跟蹤算法。視頻序列中的每一個(gè)目標(biāo)都建模成具有4個(gè)子狀態(tài)空間(“活躍”，“已跟蹤”，“丟失”，“不活躍”)的MDP。目標(biāo)的出現(xiàn)-消失-出現(xiàn)過(guò)程對(duì)應(yīng)MDP中的狀態(tài)轉(zhuǎn)移過(guò)程。作為策略學(xué)習(xí)的一部分，利用增強(qiáng)學(xué)習(xí)方法來(lái)學(xué)習(xí)用于數(shù)據(jù)關(guān)聯(lián)的相似性度量函數(shù)。所提出的算法在MOT15基準(zhǔn)數(shù)據(jù)上進(jìn)行了測(cè)試驗(yàn)證，能夠有效處理遮擋和快速運(yùn)動(dòng)的情況，在速度和準(zhǔn)確性上實(shí)現(xiàn)了較好的提升。