孫 瑾 杜官明

(南京航空航天大學民航學院 南京 211106)

1 引 言

多目標跟蹤(Multi-Object Tracking, MOT)一直是計算機視覺領域一個非?；钴S的研究課題，它是很多視覺任務的基礎工作，例如智能監(jiān)控、視覺導航和運動分析等，具有廣闊的應用前景。相對于單目標跟蹤，多目標跟蹤過程中存在著目標數(shù)量和類型不確定、目標相互干擾和遮擋等復雜情況，導致跟蹤過程中出現(xiàn)目標丟失、目標身份(IDentification, ID)頻繁轉換等問題。因此多目標跟蹤問題也一直是一個具有挑戰(zhàn)性的課題。

近年來由于目標檢測[1,2]技術的巨大進步，基于檢測的多目標跟蹤技術(Tracking By Detection,TBD)取得了很多成果。TBD借助先進檢測器獲取每幀目標對象，基于對目標的位置預測，通過提取目標特征將相鄰幀的同一目標關聯(lián)以實現(xiàn)對目標的持續(xù)追蹤。數(shù)據(jù)關聯(lián)是其中最重要的環(huán)節(jié)，在不同幀目標的各種匹配中尋找最佳匹配，該過程可看作是一個分配問題求最優(yōu)解的過程。隨著目標數(shù)增加，計算復雜度增加，同時當目標被干擾和遮擋時，會出現(xiàn)匹配錯誤和跟蹤丟失情況，因此當前研究主要集中在數(shù)據(jù)關聯(lián)算法優(yōu)化上。Zhong等人[3]針對目標位置和速度隨時間變化具有非線性特征，采用粒子濾波通過近似非線性系統(tǒng)后驗分布提高數(shù)據(jù)關聯(lián)魯棒性，但其準確性依賴于粒子數(shù)目，需要高昂的計算代價。Bewley等人[4]使用匈牙利算法，在跟蹤預測目標和檢測目標組成的二分圖上逐幀求解最大匹配實現(xiàn)目標關聯(lián)，但最大匹配不唯一，會導致匹配錯誤；為提高魯棒性，Wu等人[5]引入相關濾波跟蹤器，并采用分組關聯(lián)：先將檢測目標與具有較高濾波響應的跟蹤目標利用匈牙利算法進行關聯(lián)，再與低響應跟蹤目標關聯(lián)，算法計算量大；Liu等人[6]基于長短期記憶網(wǎng)絡(Long Short-Term Memory, LSTM)模塊中強記憶成分進行目標的分配預測，解決復雜情況下的漏檢以提高關聯(lián)準確度；為降低逐幀關聯(lián)中誤差累積造成軌跡漂移，Lenz等人[7]、Schulter等人[8]和Li等人[9]構建了最小代價流的數(shù)據(jù)關聯(lián)框架，將相鄰幀間目標相似性轉化為網(wǎng)絡流費用，通過最小費用流算法找到最優(yōu)關聯(lián)。作為多目標跟蹤中的關鍵步驟，數(shù)據(jù)關聯(lián)引起了廣泛關注，但現(xiàn)有方法大都基于相鄰幀的局部關聯(lián)，一旦出現(xiàn)遮擋，會出現(xiàn)目標丟失或者ID轉換。

為有效解決遮擋問題，很多方法采用兩級關聯(lián)方式，即考慮較短時間序列內(nèi)目標較為穩(wěn)定，依據(jù)目標檢測結果，先在較短視頻序列內(nèi)對目標進行數(shù)據(jù)關聯(lián)形成軌跡片段(tracklet)，再對軌跡片段進一步關聯(lián)，最終形成目標完整軌跡[10]。相對于目標的完整軌跡，軌跡片段可以認為是目標的一段初級(low-lever)軌跡，即軌跡片段的生成可以認為是初級的數(shù)據(jù)關聯(lián)。早期主要基于目標間的交并比(Intersection Over Union, IOU)[10-12]進行關聯(lián)，但當目標間距離較近或出現(xiàn)遮擋時，IOU方法容易引起關聯(lián)錯誤；Zamir等人[13]考慮相鄰幀的同一目標具有相似的外觀特征，提取目標外觀信息生成軌跡片段，但外觀特征依然對遮擋敏感；為此，Wen等人[14]在外觀特征基礎上聯(lián)合運動信息關聯(lián)目標生成軌跡片段，有效區(qū)分擁擠場景中具有相似外觀的空間接近目標；Choi[15]基于光流信息提出聚合局部流描述符(Aggregate Local Flow Descriptor, ALFD)特征計算目標間的相似度生成軌跡片段，但ALFD的權重由目標之間的重疊度決定，易受遮擋影響；為克服不同目標距離接近時由于重疊導致的關聯(lián)錯誤，Shen等人[16]利用目標IOU和最小成本流提高軌跡片段生成的準確性；Nahon等人[17]先利用IOU進行目標關聯(lián)獲得初始軌跡片段，當兩個軌跡片段出現(xiàn)重疊時需進一步分割，該方法能夠減少目標ID轉換次數(shù)，但當目標長時間距離較近或遮擋時跟蹤準確性下降；Wu等人[18]構建基于點云的軌跡片段生成卷積神經(jīng)網(wǎng)絡(Point Cloud based Tracklet Convolutional Neural Network, PC-TCNN)，利用連續(xù)幀中目標時空一致性特征生成軌跡片段。Dai等人[19]聯(lián)合外觀、時間和位置信息計算相鄰幀目標的相似度，使用匈牙利算法生成軌跡片段。可以看出，現(xiàn)有軌跡片段生成方法也主要通過有限時域內(nèi)相鄰目標間的相似度匹配實現(xiàn)。

關聯(lián)的準確性直接影響跟蹤的準確性?，F(xiàn)有方法主要基于時空一致性，根據(jù)最大匹配度(或最小匹配距離)進行關聯(lián)，即根據(jù)時間順序在相鄰幀選擇匹配度最大的目標進行關聯(lián)。但最大匹配未必為準確匹配，一旦發(fā)生相似目標接近或者遮擋時，會產(chǎn)生錯誤關聯(lián)，造成跟蹤中斷產(chǎn)生碎片跟蹤，或直接導致跟蹤失敗。為清楚說明，圖1顯示了目標a和b的運動軌跡。其中，目標a在第k幀出現(xiàn)，第k+1～第k+4幀被遮擋，第k+5和第k+6幀重新可見，實心點1,7和8分別表示a在第k幀、第k+5～第k+6幀出現(xiàn)的位置，紅色虛線表示a的軌跡；目標b在第k+1～第k+5幀出現(xiàn)的位置由實心點2～6表示，目標b軌跡如紅色實線所示。實心點顏色代表目標的特征屬性，顏色相似度表明歸屬于同一目標的可能性?，F(xiàn)有方法主要關注相鄰幀目標的成對相似性，因此盡管實心點1和2分屬不同目標，但出現(xiàn)在相鄰幀，又具有較高的相似性，故1和2關聯(lián)后產(chǎn)生了錯誤的軌跡，如藍色實線所示。當目標a在第k+5幀重新出現(xiàn)時，則作為新目標進行標記和跟蹤，形成碎片軌跡，如黑色實線所示。

圖1 局部和全局數(shù)據(jù)關聯(lián)說明

因此，遮擋情況下，現(xiàn)有局部關聯(lián)方法很容易造成目標丟失和目標ID轉換。為實現(xiàn)魯棒跟蹤，本文提出基于次模優(yōu)化的軌跡片段生成方法。首先，將目標關聯(lián)轉化為運籌學中的設施選址問題(Facility Location Problem, FLP)；其次，采用互補特征，并融合運動信息提高目標匹配準確度；最后，引入次模理論，根據(jù)次模函數(shù)性質，通過具有約束的次模最大化算法在視頻片段全局內(nèi)選擇目標實現(xiàn)數(shù)據(jù)關聯(lián)。具有約束的次模最大化算法在有近似保證的前提下可以達到近似最優(yōu)的性能，因而所提算法可以有效提高跟蹤準確性。同時，通過全局間的關聯(lián)可以應對各種干擾和遮擋情況，提高跟蹤魯棒性。

2 設施選址及次模函數(shù)

設施選址問題是運籌學中優(yōu)化組合領域一類重要的問題，在確定選址對象、選址目標數(shù)、成本函數(shù)以及存在的約束條件前提下，以總成本最低或總服務最優(yōu)或社會效益最大化為總目標確定設施數(shù)量、位置等。設施選址問題模型為

其中，i∈C，代表客戶集合C中任意客戶，j∈F，代表設施集合F中為客戶提供服務的設施；每個設施j對應一個非負的開放費用fj；設施j為客戶i服務產(chǎn)生的利潤為cij；xij表示設施j是否為客戶i提供服務，根據(jù)約束條件式(5)，xij∈{0,1}，xij=1表示設施j為客戶i提供服務，否則xij=0；yj∈{0,1}，yj=1表示開放設施j，否則yj=0； z為目標函數(shù)，表示獲得的總收益；q為開設的最大設施數(shù)量。設置選址問題是在有限設施集合中選擇開放哪些設施使得開啟這些設施的成本費用和對客戶服務產(chǎn)生的利潤總和達到最大[20,21]。約束條件式(2)：保證每個客戶都能被服務；約束條件式(3)：xij≤ yj保證只有開放的設施才能為客戶提供服務。約束條件式(4)將最多開放的設施數(shù)量限制為q。設施選址問題可以看作是在設施集合中選擇一個最優(yōu)子集，將客戶分配到每個設施，使設施開放成本和為客戶服務獲得的利潤總和最大。設施選址問題是一個經(jīng)典的NP-難問題，近似算法是解決NP-難問題的重要方法之一。很多學者已經(jīng)證明設施選址問題中總利潤函數(shù)，即式(1)滿足次模性[22,23]，利用次模最大化可以獲得近似解。

次模性(submodularity)又稱子模性、亞模性等，是集合函數(shù)的一個屬性。對于有限集合V，A?B?V，元素a∈V B，對于集合函數(shù)H: 2V→R，如果滿足

則函數(shù)H滿足次模性，具有邊際效益遞減(diminishing returns)性質[24]。

根據(jù)次模函數(shù)性質[25]，當函數(shù)滿足次模性和單調性，且在定義域上值域非負時，與最優(yōu)解相比，使用貪婪算法可獲得至少(1-1/e)≈63%的近似解。文獻[26]通過在各種大規(guī)?，F(xiàn)實世界數(shù)據(jù)集和實例上進一步證明貪婪算法得到的近似解其近似比α(Approximation Ratio, AR)幾乎總是超過85%，并且經(jīng)常超過95%，即近似解Sapp相對于最優(yōu)解Sopt滿足：α·Sopt≤ Sapp≤Sopt。因此，有效解決了設施選址這類NP-難問題并可達到近似最優(yōu)的性能。

3 次模優(yōu)化的軌跡片段生成

本文將視頻片段第1幀檢測目標作為初始目標，視為設施選址問題中的客戶集合；其余幀的檢測目標作為候選集合，視為設施選址問題中設施集合。初始目標與其余幀檢測目標之間的相似度作為設施滿足客戶需求所獲得利潤，軌跡片段的生成可以看作對每個初始目標(客戶)，在候選集合(設施集合)中選擇與初始目標相似的目標，即選擇設施以滿足客戶需求獲得最大利潤。因此，軌跡片段生成問題轉化為設施選址問題，即為每個初始目標在候選集合中根據(jù)相似性選擇最優(yōu)子集，該問題可以通過次模最大化函數(shù)來解決[22,23]。因此本文利用次模優(yōu)化實現(xiàn)目標關聯(lián)生成軌跡片段，一方面利用次模函數(shù)性質，使用貪婪算法得到接近最優(yōu)解的近似解，保證關聯(lián)準確度，另一方面，突破時域相鄰目標間的局部關聯(lián)限制，在候選集合全局范圍內(nèi)實現(xiàn)目標關聯(lián)，有效解決遮擋問題。

3.1 軌跡片段生成問題轉化

將視頻V分割成L個視頻片段，即V={V1,V2, ···, Vi, ···, VL}，每個視頻片段幀數(shù)為K。以第m個視頻片段為例，構造圖G=(Dm, Em)說明軌跡片段的生成過程，如圖2所示，Dm為第m個視頻片段檢測出的目標集合，目標間連線e∈Em代表目標間的關系，本文選擇目標相似度進行關系度量，同一幀目標間不進行關聯(lián)，則Dm表示為

圖2 軌跡片段生成過程示意圖

軌跡片段生成就是根據(jù)初始目標在候選集合選擇相似度最優(yōu)子集，即將Rm根據(jù)與初始目標相似度劃分為不同子集。以相似度作為設施滿足客戶需求所獲得的利潤，軌跡片段生成問題轉化為設施選址問題，根據(jù)式(1)-式(6)，本文將設施選址問題應用于軌跡片段生成

其中，Rm目標總數(shù)為N； xij∈{0,1}，若Rm中所選目標j屬于初始目標i的軌跡片段，xij=1，否則xij=0；sij是初始目標i與候選集合中目標j之間的相似性；開放設施j的成本?j設為固定值γ，本文γ=0。約束條件式(10) 保證視頻片段中所有目標都能被分配到對應軌跡片段中，即屬于某個子集；約束條件式(11)保證每個軌跡片段長度不長于視頻幀數(shù)K，即保證至多有K個檢測目標組成一個軌跡片段；約束條件式(12)保證每個視頻幀最多只有1個檢測目標被選入當前軌跡片段，即同一幀中不可能有兩個目標同屬一個軌跡片段。利潤函數(shù)z滿足次模性[22,23]。

3.2 目標特征提取

根據(jù)式(9)進行目標關聯(lián)，首先要計算目標相似度。跟蹤過程中目標姿態(tài)、尺度，環(huán)境光照等會發(fā)生變化，單一特征表征目標能力有限。本文通過實驗發(fā)現(xiàn)方向梯度直方圖(Histogram of Oriented Gradient, HOG)與顏色名(Color Name, CN)特征具有很好的互補性：HOG對光照變化魯棒，但對目標形變敏感，顏色特征易受光照影響，但在目標形變下較為穩(wěn)定。因此本文選取CN和HOG特征進行目標表征。

顏色、形狀相似目標間會產(chǎn)生互相干擾，如圖3(a1)TUD-Stadtmitte數(shù)據(jù)集第50幀目標4與圖3(a2)第52幀目標匹配時，與第52幀最左邊目標(實際對應第50幀目標6)相似度(0.972)高于與第52幀最右邊目標(實際對應第50幀目標4)相似度(0.968)，使第50幀目標4與第52幀最左邊目標發(fā)生錯誤關聯(lián)?？紤]目標在視頻片段(本文設為10幀)所屬時間內(nèi)運動范圍有限，若兩個目標距離較遠，分屬不同目標的可能性較大，因此本文利用運動信息，改造Sigmoid函數(shù)設計權重系數(shù)λ提高匹配準確度，λ隨著目標間距離增大而降低，示意圖如圖4，則目標相似性度量sij表示為

圖3 權重系數(shù)λ加入前后跟蹤結果對比

圖4 相似度權重系數(shù)λ

其中，w為每個初始目標檢測框寬度，由檢測算法給出；x代表兩個目標間距離，通過計算目標檢測框中心距離獲得；分別代表初始目標集第i個目標和候選目標集第n幀第j個目標的CN和HOG特征相似度。圖3(b1)和圖3(b2)顯示了加入權重系數(shù)后可以有效避免相似目標干擾下的錯誤關聯(lián)。

3.3 次模最大化

本文將軌跡片段生成問題轉化為設施選址問題，設施選址問題是一個NP-難問題，但滿足次模性。根據(jù)第2節(jié)所述，采用貪婪算法可以有效解決設施選址這類NP-難問題并能獲得接近最優(yōu)解的近似解。因此本文利用次模優(yōu)化將軌跡片段生成過程進一步轉化為

其中，sij是初始目標(客戶)i與候選集合中目標j(設施)之間的相似性，開放設施j的成本?j為固定值γ，本文γ=0。NA代表選擇候選目標的最大數(shù)量(開放設施的最大數(shù)量)，K是視頻片段幀數(shù)，N是全部候選目標數(shù)量。根據(jù)次模函數(shù)性質，采用貪婪算法，對每一個初始目標，在候選目標集合中選擇與其具有最大相似度的目標構成子集A，該子集中的目標組成對應初始目標的軌跡片段。

為清楚描述利用次模優(yōu)化生成軌跡片段的過程，選取TUD-Stadtmitte數(shù)據(jù)集第17～32幀含遮擋情況的視頻片段進行說明，如圖5所示。提取視頻片段第1幀目標作為初始目標集Sm，其余視頻幀目標組成候選目標集Rm，紅色實心點代表Rm中各個目標。根據(jù)式(14)計算每個初始目標與候選目標的相似度，選取相似度最大的目標。以17幀初始目標集第2個目標為例，與其相似度最大的是第18幀目標2，故首先選取，此時根據(jù)約束條件式(12)，即1個軌跡片段在同一幀中最多選取1個目標，故將第18幀其他目標從Rm剔出，后續(xù)只在19～32幀中選擇；第2次計算發(fā)現(xiàn)與第19幀目標2相似度最大，則選擇歸入當前軌跡片段中，同理將第19幀其他目標從Rm剔出。以此類推，后續(xù)依次選擇第32幀目標2，第20幀目標2。由于遮擋，初始目標2與第22～31幀任意目標相似度均小于閾值α，故在第22～31幀沒有獲得匹配目標，獲得的匹配對象是，圖5中帶陰影紅色點所示。最后依據(jù)目標所在幀的時間序列獲得初始目標的軌跡片段為?，F(xiàn)有方法在目標遮擋后受局部相鄰幀關聯(lián)的限制，在第32幀目標再出現(xiàn)時可能會作為新目標分配新的ID。為此很多方法，例如DeepSORT[27]需要設定額外的步驟和參數(shù)處理遮擋問題。本文方法則基于次模理論通過候選目標集中的全局關聯(lián)直接克服遮擋問題。

上述過程說明了視頻片段中一個初始目標的軌跡片段生成，從候選目標集合中刪除該軌跡片段所包含目標，再對其他初始目標依次做相應處理獲得對應軌跡片段。值得注意的是，視頻片段初始目標集合匹配完成后，候選集合中可能還有未匹配目標，代表視頻片段中間幀新出現(xiàn)的目標，此時以這些新目標作為初始目標依次進行匹配關聯(lián)。最終生成視頻片段Vm的軌跡片段集合Tm={,,...}，其中表示第m個視頻片段Vm中的第j個軌跡片段。整個過程如算法1所示。

4 實驗結果與分析

為驗證本文算法的跟蹤效果，首先在多個公開數(shù)據(jù)集上與常用軌跡片段生成算法進行定性比較，然后基于多目標跟蹤挑戰(zhàn)賽(Multiple Object Tracking Challenge, MOT Challenge)評價指標[28]進行定量評估。

4.1 實驗數(shù)據(jù)集

本文選取公開數(shù)據(jù)集MOT17,PETS09-S2L1和TUD進行實驗。 MOT17由7個訓練集和7個測試集組成，包含夜間、高密度行人、快速運動場景圖像序列，每個序列分別使用尺度相關池化(Scale Dependent Pool, SDP)、可變形組件模型(Deformable Part Model, DPM)和快速區(qū)域卷積神經(jīng)網(wǎng)絡(Faster Region-based CNN, Faster-RCNN)獲得目標檢測結果；PETS09是行人交通數(shù)據(jù)集，包括不同場景下S0,S1,S2,S3 4個子集，本文選用常用于行人跟蹤的PETS09-S2L1進行實驗；TUD主要用于擁擠場景下的行人多目標檢測和跟蹤，其中TUDStadtmitte和TUD-Crossing是低視角下拍攝的繁忙步行街場景，包括頻繁的遮擋情況。

4.2 定性評估

為驗證算法在遮擋情況下的跟蹤效果，在上述3個基準數(shù)據(jù)集分別選擇含遮擋情況的3個視頻序列進行實驗。最小代價流是目前軌跡片段生成的常用方法，與本文方法的對比實驗結果如圖6-圖8所示。最小代價流方法在遮擋情況下出現(xiàn)了目標ID轉換和丟失情況：圖6(a2) MOT17數(shù)據(jù)集第6幀目標13丟失；圖7(a1) TUD-Crossing數(shù)據(jù)集第40幀目標4被遮擋后在圖7(a3)所示第50幀重新出現(xiàn)后被認定為新目標12，發(fā)生目標ID轉換；圖8(a1) PETS09-S2L1數(shù)據(jù)集第51幀目標2在圖8(a2)所示第54幀被遮擋，圖8(a3)第61幀重新出現(xiàn)后被認定為新目標8，目標ID發(fā)生轉換。相比較，本文方法在上述情況下保持目標ID 不變，實現(xiàn)魯棒跟蹤。

算法1 基于次模優(yōu)化的軌跡片段生成

圖6 MOT17-02數(shù)據(jù)集實驗結果對比

圖7 TUD-Crossing數(shù)據(jù)集實驗結果對比

圖8 PETS09-S2L1數(shù)據(jù)集實驗結果對比

4.3 定量評估

軌跡片段作為初級軌跡，直接關系到多目標跟蹤完整軌跡的準確性。本文將軌跡片段進一步關聯(lián)成完整軌跡，利用MOT Challange跟蹤評價指標對算法性能進行定量評估。其中包括算法跟蹤準確性(Multiple Object Tracking Accuracy, MOTA)的評價；算法的關聯(lián)性能IDF1綜合考慮目標ID的準確率和召回率；算法跟蹤精度(Multiple Object Tracking Precision, MOTP)評估；跟蹤目標ID轉換次數(shù)(IDentity Switches, IDS)計算；跟蹤過程中各目標至少有 80%的視頻幀能被正確跟蹤的軌跡占總軌跡的占比(Mostly Tracked, MT)統(tǒng)計；丟失軌跡的占比(Mostly Lost, ML)統(tǒng)計，其中丟失軌跡為至多有 20%的視頻幀能被正確跟蹤的軌跡。

表1和表2顯示了不同數(shù)據(jù)集上的算法跟蹤性能比較結果。其中↑表示數(shù)據(jù)越高越好，↓表示數(shù)據(jù)越小越好。跟蹤結果與檢測器精度直接相關，為公平比較，本文與參與比較的近年來主要的MOT算法全部采用數(shù)據(jù)集提供的檢測結果進行跟蹤性能比較，各個算法的實驗數(shù)據(jù)由相關文獻提供。表1 PETS09-S2L1和TUD數(shù)據(jù)集上，目標主要為行人，外觀相似，存在頻繁遮擋，對跟蹤器的魯棒性提出了很大的挑戰(zhàn)，結果顯示本文方法均產(chǎn)生最高的MOTA和最低的IDS，說明本文方法可以很好地解決目標遮擋導致的ID轉換問題，實現(xiàn)魯棒跟蹤。在表2 MOT17數(shù)據(jù)集中本文方法在MOTA和IDF1兩個指標上超越了大多數(shù)方法，其中兩項指標上表現(xiàn)較好的方法都是采用卷積網(wǎng)絡跟蹤模型，需要優(yōu)化調整模型參數(shù)，與這些方法相比，本文算法對參數(shù)依賴性小，計算簡單。在上述基準數(shù)據(jù)集上本文方法IDS指標最低或接近最低，實現(xiàn)了較低的目標ID轉換次數(shù)，同時有更多的物體被準確追蹤(高MT和低ML)。

表1 PETS09-S2L1和TUD數(shù)據(jù)集跟蹤性能對比

表2 MOT17數(shù)據(jù)集跟蹤性能對比

5 結 論

本文采用兩級關聯(lián)方式，通過生成軌跡片段構建目標的完整軌跡實現(xiàn)多目標跟蹤，提出次模優(yōu)化框架下軌跡片段生成方法，在全局范圍內(nèi)利用次模最大化選擇最優(yōu)子集生成軌跡片段。在MOT17,PETS09-S2L1和TUD基準數(shù)據(jù)集上的定性和定量實驗中，本文方法表現(xiàn)出較好的對干擾和遮擋的處理能力，同時與現(xiàn)有方法相比，也取得了具有競爭力的跟蹤性能。