軌跡樹層次關系模型多攝像機多目標跟蹤研究*

劉冠群，李 婷

1.湖南廣播電視大學 網絡資源系，長沙410004

2.中南大學 信息科學與工程學院，長沙410083

1 引言

多目標跟蹤作為計算機視覺中的一項重要技術，已得到了廣泛研究。近年來，學者提出一系列利用目標外觀和動態信息的在線和批量方法。但是這些方法在視覺監控中容易受到遮擋，因為它們只使用一個攝像頭。特別是在擁擠環境中，比如教室或商店，目標分布密集，容易被各種障礙物遮擋。

為了克服遮擋問題，學者們提出了多攝像機多目標跟蹤（multiple cameras multiple targets tracking，MCMTT）問題。例如，文獻[1]提出一種針對煤礦井下研究場景的多攝像機多目標軌跡跟蹤算法研究，主要針對煤礦井的視頻跟蹤問題進行有效解決。文獻[2]提出基于多伯努利卷積特征多攝像機多目標跟蹤算法，該算法利用卷積算法對視頻特征進行處理，目的是提高算法的跟蹤精度。文獻[3]提出一種基于全局分層關聯網絡的多攝像機多目標跟蹤算法，實現目標跟蹤精度提升。多攝像機多目標跟蹤問題主要分為三類[1-2]：（1）重建/跟蹤方法。通過附加視圖的測量來克服遮擋或背景雜波導致的目標檢測缺失問題。然后應用基于攝像機的跟蹤方法來生成目標的軌跡。例如，文獻[4]采用協同圖在場景中進行目標跟蹤，由于跟蹤區域的量化存在一定的局限性，協同圖存在幻影問題，導致目標位置模糊。然而上述三種方法對背景減法的結果非常敏感。因此，這種算法會受到具有動態或復雜背景的場景的影響[5]。（2）跟蹤/重建方法。試圖將同一目標的軌跡關聯起來，首先用一種基于攝像機的跟蹤方法在每個視圖獨立生成軌跡，然后制定組合問題來關聯這些軌跡。例如，文獻[6]將軌跡關聯問題表述為多維指派問題，這是著名的NP 難題。用一種啟發式算法解決了這個問題，即貪婪的隨機自適應局部搜索過程，但是其只可解決短遮擋問題。文獻[7]采用了高階動力學模型對軌跡的跨視點關聯進行了研究。該算法在沒有標定信息的情況下具有很好的魯棒性。然而，由于高階動態模型之間的比較需要一個運算來找到大矩陣秩，因此算法計算量很大。（3）統一框架。將重建和跟蹤問題表示為統一全局優化問題，通過對整個輸入視頻序列進行批量處理，取得良好性能。例如，文獻[8]嘗試使用統一框架的MCMTT 算法。該框架構建了每臺攝像機的二維跟蹤圖，并構建了不同攝像機檢測到圖像對的三維重建圖。然而，所提出的圖結構過于復雜。文獻[9]提出一種基于超圖方法，用單個圖來表示重構和跟蹤問題，但必須枚舉同時檢測之間所有可能的重構來構造圖。此外，該方法通過二元整數問題公式來求解圖形，算法計算量很大。

盡管基準上的性能很好，但是這些算法都是基于批處理的算法，不能在每幀上提供即時跟蹤結果，且需要大量計算。對于許多應用程序來說，這是嚴重限制。此外，算法只使用測量的幾何信息。因此，當目標接近度增加時，它們在一致性標記方面存在困難。本文旨在提出一種高效不損失性能的在線MCMTT 算法，該算法與目前最先進批處理算法具有可比性。

2 問題描述

2.1 多目標跟蹤問題

給定多目標軌跡檢測中，所有攝像機的一組檢測結果為D=(di|di=(li,si,ci,ti),i=1,2,…,ND)，其中li、si分別表示圖像坐標位置和比例，ci∈(1,2,…,NC)是相機索引，ti表示檢測到di的時間戳，di則表示上述界定圖像位置的第i個檢測。ND是輸入檢測的總數。定義第j個追蹤為，式中是屬于Yj的檢測索引集。假設每個檢測不能由多個目標共享，即對于i≠j，總是滿足。航跡是目標在三維世界坐標系下的估計軌跡。當定義為與跟蹤Tk關聯的跟蹤索引集時，Tk、Zk?D的檢測集可以用中二維跟蹤定義。定義作為在時間t從所有攝像機觀察到的一組軌道檢測。令為目標在時間t的三維估計位置，軌道Tk∈T定義為這些位置估計的序列，式中max({ti|di∈Zk})分別是Tk的起始時間和終止時間。全局假設Hn∈H是一組多目標的估計軌跡，即T的一個子集。將定義為屬于Hn的一組索引時，Hn的定義是。

對于可行全局假設，屬于同一全局假設的任意兩個不同軌道Tk和Tl必須滿足以下相容條件：（1）任何兩條軌道中都沒有共用軌跡，即。（2）避免碰撞，即，式中θs指為避免目標間碰撞所需的最小距離。定義兼容集?，它由兼容軌道的無序索引對組成，即對于所有k,l，滿足條件{k,l}∈?。多目標跟蹤是尋找最優的全局假設H?，在滿足相容條件的可行全局假設中，H?具有最大評估值：

式中，{k,l}∈?，?k,l∈IHn。由于式（1）中問題是NP困難問題，本文提出一種新的在線方案，利用已有解在幀找到式（1）的近似最優解。

2.2 算法框架

圖1 給出該方法總體方案，它由四部分組成：軌跡、跟蹤、全局假設和修剪。在每個攝像頭上，為了在線關聯檢測，設計跟蹤匹配問題的檢測方法。然后，生成新的軌跡或用匹配的結果更新已建立的軌跡集。

Fig.1 Algorithmic framework圖1 算法框架

在全局假設部分，對當前幀中所有軌跡的集合式（1）進行求解。為減少計算量，引用生成模型式（1）的子問題，其包含上一級框架中的KH最佳全局假設集。為了解決NP 難題，采用BLS（Boneh-Lynn-Sshacham）方法，提出了一個良好的初始解和適當的迭代次數，并修改BLS 以生成多個近似最優解。在收集了所有通過解決子問題發現的全局假設之后，將KH最佳全局假設選為Ht。Ht存儲在全局假設部分，用于下一幀，并傳輸到修剪部分。

在修剪部分，根據是否確認一條軌跡，對軌跡應用兩種修剪技術。當一條軌跡的持續時間超過某一長度時，該軌跡即被確認。采用Ht計算每條軌跡的近似全局軌跡概率（approximate global trajectory probability，AGTP），并將其用于每種修剪技術中作為標準。然后，修剪信息被傳遞到軌跡部分，以減少下一幀中的軌跡數量。

2.3 多目標跟蹤匹配驗證

對匹配檢測和跟蹤應用進行驗證，以增強跟蹤健壯性。定義Dt={di|ti=t}是隨時間t新檢測到的結果，Yt-1作為最近檢測時間為t-1 的所有軌跡集，即Yt-1=(Yj|max({ti|i∈Iyj})=t-1)。然后，軌道Yj∈Yt-1與檢測di∈Dt之間匹配度為：

式中，wδ(si)指示與si成比例的相鄰窗口大小，則差距主要是。通過使用以上前向跟蹤，可從中獲得，即前一幀中軌跡的最后一次檢測。

3 軌跡樹層次關系模型

3.1 軌跡模型描述

本節中描述了在線軌跡生成方案，并提出代表每個軌道質量的軌跡分數。此外，還定義軌跡樹，表示軌跡間層次關系。

軌跡關聯：令{Ω1(Y),Ω2(Y),…} 是整個軌跡集Y=(Y1,Y2,…,Yq)的所有可能分區的集合。然后，所提MCMTT 問題目標是找到分區Ωi(Y)，最能描述目標跟蹤。第i個分區定義為是假警報集。表示軌跡集合應來自第i個分區中的第k個目標，稱之為關聯集。定義所有可能的沒有分區索引的關聯集：

為簡化省略參數(Y)，將ωk對應軌跡記為Tk，將ωk的相關檢測集記為Zk。定義三種操作：空間關聯、時間關聯和合并。

操作1（空間關聯）如圖2 中的T2和T7所示，空間關聯是由臨時重疊軌跡之間的關聯來定義的，這些軌跡應該來自同一目標，使用不同的攝像頭。為確定軌跡Yl和Ym是否來自同一目標，提出了空間關聯條件，該條件檢查軌跡中同時檢測之間的距離是否受閾值ε3D的限制，如下所示：

Fig.2 Example of trajectory generation圖2 軌跡生成示例

操作2（時間關聯）同一攝像頭的臨時不重疊軌跡間關聯，或同一目標不同攝像頭間的關聯。對于時間關聯，前向軌跡Yl和后面軌跡Ym須滿足：（1）根據每個目標在每個視圖中最多只生成一個檢測的事實，Yl和Ym須是暫不重疊的，即{ti|di∈Yl}?{tj|?dj∈Ym}=?。（2）目標不能突然改變其位置，因此dp（Yl最后一次檢測）和dn（Ym第一次檢測）在三維空間足夠接近。當vmax被定義為目標在一幀內可移動最大距離時，條件是||Φ(dp)-Φ(dn)||2≤vmax×|tp-tn|。

操作3（合并關聯）如果兩個關聯集的聯合集滿足所有時空關聯條件，則聯合集也是關聯集。這兩個關聯集稱為可合并。其合并操作定義為：（1）如果ωi和ωj可合并，則ωi⊕ωj=ωi?ωj；（2）如果ωi和ωj不可合并，則ωi⊕ωj=?。

3.2 軌跡關系評估模型

考慮四個因素，評估軌跡得分：

（1）重建評估SR(·)，表示軌道位置與檢測相同程度。重建評估基于PZ(·)構建，即在特定時間對目標可能性進行檢測。將Xtk作為t時Tk跟蹤目標位置的隨機變量，則重建分數為：

式中，似然度PZ(·)的計算可參見文獻[10]有關描述進行計算。

（2）連接分數SL(·)，它考慮了軌道連續位置的幾何適宜性。有些運動很難預測，例如行人等，因為它通常是非線性的。因此，只考慮軌道上連續位置鄰近性，以確定連接這些位置是否合適。所提連接分數定義為隨軌道上連續位置之間的距離發生變化，即：

式中，vmax是一個設計參數，用于模擬行人在一幀內可以移動的最大距離。當遠大于vmax時，鏈接視為無效，此時放棄對其跟蹤。參見文獻[11]。

（3）初始評估SI(·)和最終評估ST(·)。如前所述，在可見區域中間突然啟動或終止的軌跡不太可能。為反映趨勢，起始/終止評估定義為：

式中，Ps和Pe分別是目標在可見區域出現和消失的概率。τs和τe是目標與可見區域邊界之間距離的懲罰系數。τl是防止長軌跡終止的懲罰系數。是和可見區域邊界之間的距離。mB是實驗中設定為1 m 的邊界。在起始幀附近開始的軌跡不受起始懲罰，因此其起始評估為lb(Ps)。通過這些起始/終止評估，可以避免目標軌跡中出現過多的碎片。參見文獻[12]。

（4）視覺評估SV(·)，表示與軌道相關的檢測間的視覺相似性。假設目標不會突然改變它的外觀，因此每個視圖中相同軌跡的相鄰檢測應該具有相似的外觀。對任意軌跡Tk的ωk時間關聯處的得分賦值。令是根據其開始時間攝像機c的軌跡有序集合，單位為ωk。檢測的有序對集定義為：

式中，av和τv模型參數隨著檢測之間的時間間隔增加，視覺相似性置信度下降。參見文獻[13]。

最后，利用（1）～（4）所示因素可定義軌跡評估形式：

3.3 全局假設

每個MWCP（maximum weight clique problem）由構成，一組軌跡是當前最佳全局假設候選者，假設先前最佳全局假設是。把稱為相關軌跡集。它包含三種類型軌道：（1）的軌跡；（2）在當前幀中新生成兩個子項軌跡，即；（3）未確認軌跡。

未確認軌跡是比Nconf幀短的軌跡，無法確定它是否為假陽性。因此，不斷將未確認軌跡插入軌跡集，即使這些未確認軌跡不在先前解決方案中。則定義為。則 對 于n=1,2,…,KH，每個的MWCP 問題定義為：

式中，與輸入視頻序列的起始幀Ht-1=?一樣，構造并求解了完整的跟蹤集Tt的單重網絡控制點。當精確求解多路徑控制點時，求解多路徑控制點的計算與軌道數成指數比例。

3.4 算法步驟

將Ht定義為Tt中所有可能的全局假設集時，Ti∈Tt軌跡的GTP（global trajectory probability）定義為：

修剪有零軌跡作為軌跡修剪的第一步。由于KH最佳全局假設定義，零軌跡意味著軌跡不屬于KH最佳全局假設中的任何一個。

對于已確認的軌跡樹，保持每棵樹中的所有軌跡是很難的，因為每棵樹中的軌跡數呈指數增長。因此，將N掃描后退方法應用于已確認的軌道樹。這是基于延遲決策的修剪技術。在找到最佳全局假設后，它會掃描N幀，并根據當前的最佳全局假設確定目標的位置。然后它修剪所有與目標固定位置不兼容的軌跡。從樹結構的角度來看，除了當前最佳全局假設中包含軌跡的分支外，它以前在N幀處修剪每個軌跡樹的分支。在算法1 中總結了本文的在線方案。

算法1軌跡樹層次關系模型

輸入：檢測視頻數據集D。

算法1 中，第1 行是對算法進行參數初始化，第2～第6 行是根據2.3 節內容生成多攝像機多目標跟蹤軌跡，第8 行是對軌跡關聯性進行計算，然后在第9行中，根據計算的軌跡關聯性進行新軌跡生成，第13～第15 行進行最佳軌跡初始化，第20～第22 行是根據3.3 節、3.4 節內容對軌跡結果進行評估，并對其進行軌跡調整和更新。

上述算法中，從計算復雜度角度分析，因為無嵌套迭代過程，因此其計算復雜度是O(N)，具有相對較小的計算復雜度，體現了算法的計算效率。從算法收斂性角度分析，根據第16 行可知，在算法迭代計算過程中，每次選取的是當代進化迭代過程的最佳值，因此該算法可保證多攝像機多目標跟蹤過程的收斂。

4 實驗分析

4.1 實驗設置

（1）實驗硬件：處理器CPU 為i5-6400K 3.2 GHz，內存RAM 為ddr4-2 400 GHz 8 GB，系統為Win10 旗艦版，仿真平臺選取Matlab2012a。

（2）數據集：選取PETS 2009 數據集作為實驗對象，數據集示例見圖3 所示。場景中使用3 個集合：S2.L1、S2.L2 和S2.L3。這些裝置包括4 到7 個不同的視角，重疊室外攝像機視角。每個視圖有數百個幀，以7 frame/s 的速度捕獲10～74 個行人。每個場景都有不同行人密度，從低（S2.L1）到高（S2.L3）。基準數據集還通過Tsai 的攝像機模型提供每個攝像機的固有和外在參數。在評估中，給出每幀感興趣區域內目標位置。

為檢驗所提成本函數參數和條件對性能精度影響，構造新數據集，即pilsun 數據集，包含來自4 個重疊攝像頭的333 frame，每個攝像頭捕捉10 個行人，這些攝像頭以6 frame/s 的速度密集分布在一個小型室內環境中。數據集還為每個攝像頭提供了Tsai的攝像頭模型，以及由手工標記的跟蹤結果生成的地面實況。

（3）參數設置：比較間隔長度Lc=4 frame，靜態特征點閾值δmin=0.05，連續檢測之間的最大允許3D距離εΦ=0.5 m，一幀內目標的最大允許三維高度變化εh=0.3 m，相鄰窗口大小差異ωδ(si)=0.3×si，避免碰撞的最小3D 距離θs=0.3 m，同時檢測最大三維距離ε3D=2.5 m，目標最大三維速度vmax=0.8 m/s，軌跡上允許最大框架間隙δa=9 frame。

（4）作為定量評估的指標，在事件、活動和關系的分類中使用了多對象跟蹤MOTA（multiple object tracking accuracy）和MOTP（multiple object tracking precision）指標，這是MCMTT 最流行指標。

4.2 結果分析

（1）參數影響。所提方法的運行參數設置KH=1,5,10,15,20,25,30 和。研究KH和最大值對計算精度和計算時間的影響。圖4 顯示了處理時間、MOTA 隨參數變化的影響實驗。

Fig.4 Parametric influence experiment圖4 參數影響實驗

（2）算法對比實驗。為了驗證所提求解方案的有效性，將其與變分方案和基線方案進行了比較。圖5 顯示了每個解決方案的定量結果。對比算法選取：文獻[14]僅使用一個MWCP 求解的基線解算方案，沒有來自先前全局假設的反饋信息。文獻[15]采用一個MWCP 求解的基線解算方案，并采用來自先前全局假設的反饋信息。圖6 給出三種對比算法在實驗數據集上的1 幀跟蹤結果示例對比結果。

根據圖5、圖6 實驗結果可知，當KH=1 時，基線方案優于其他方案。然而這是微不足道的，因為其他方案求解的圖形比基線方案小，這意味著它們無法從先前解決方案附近或周圍的局部最優解中逃脫。然而，盡管解決的是較小的圖而不是基線方案，但當KH值較大時，性能會提高。當KH=5 或更大時，建議方案的性能優于基線方案。當KH=5 或更大時，所提算法（沒有初始解決方案）也取得了與基線方案相當的性能。相對于對比算法，本文算法在執行時間和求解精度上均要顯著優于文獻[14]和文獻[15]兩種算法，體現了算法性能優勢。同時，在圖6 實驗結果上可直觀地看出，本文算法對于目標的跟蹤精度更高，可實現對目標的準確識別和追蹤。而在對比算法中，文獻[14]和文獻[15]兩種算法的目標追蹤精度相對較低，與本文算法具有顯著的差異。

Fig.5 Algorithmic contrast experiments圖5 算法對比實驗

Fig.6 Comparison of tracking results between two adjacent frames圖6 前后兩幀跟蹤結果對比

5 結束語

本文提出基于MHT（multi-hypothesis tracking）框架的在線MCMTT 算法，該框架是由MWCP 為軌跡關聯實現的，可以找到多個對象跟蹤，直到當前幀。通過使用軌跡模型和關聯條件，所提跟蹤算法生成優化的候選跟蹤，并拒絕一些不可靠候選跟蹤。為解決多目標跟蹤問題，提出一種在線方案，該方案根據前一框架中過去的全局假設，生成多個具有小軌道集的多目標跟蹤問題。這些子問題的解搜索空間比原來的多目標控制算法小得多，因此該方案大大縮短了求解時間。此外，該方案也比用全軌跡求解多目標控制問題找到更好的解決方案。提出的初始解和迭代次數有助于在迭代次數較少的情況下找到近似最優解。下一步，將重點在算法的收斂性分析方面進行研究，完善算法理論基礎。