基于數據關聯與軌跡評估的多目標跟蹤

程艷云 朱松豪 Huet Alexis Pierre René

南京郵電大學

0 引言

多目標跟蹤問題可描述為在一系列圖像中同時跟蹤多個移動目標，且能隨著時間推移，確定不同目標的身份。目前基于檢測的多目標跟蹤主要面臨兩個難題：

（1）為每一個目標分配一個唯一的ID標號，或者確定該目標為誤報；

（2）每一個軌跡能夠合理地解釋目標的運動狀態。

以上兩個方面都具有一定的挑戰性，然而目前的研究目標主要集中在解決其中的一個方面，或者另一方面。

數據關聯是一個組合問題，典型的方法是簡化模型或者設定滿足于特定目標函數的近似解。當前是將檢測器響應與目標的實際位置相關聯，從而表示目標的實際軌跡，這不利于建立目標的動態模型，特別是在一些漏檢的圖像幀中，例如長期的目標遮擋。另一方面，目標軌跡的評估還需要考慮動態變化、持久性以及軌跡互斥等因素。由于數據關聯需在高維空間中最小化多模態能量函數，這是一個相當大的挑戰。此外，把待確定的觀測與特定的目標相關聯，也是一個很難完成的任務。

本文從時間和空間的角度建立CRF模型，將目標的數據關聯與軌跡評估整合到同一個CRF模型中，構建離散-連續能量函數，通過求取最小能量確定目標的最佳運動軌跡。本文在借鑒多標號成本的基礎上，提出了融合多模型擬合和全局軌跡特性的多目標跟蹤方案。數據關聯通過CRF模型來實現；此外，還通過空間互斥模型來限制同一物理空間兩個不同的觀測。針對軌跡評估，本文從時間上對相鄰兩幀的目標標號進行約束，軌跡模型采用連續光滑的曲線來表示，同時在連續域中擬合一系列觀測目標。對于給定的一系列軌跡假設，使用帶有貪婪標號移除的α-expansion算法更新標號，以及采用梯度下降法對目標的軌跡進行優化。

1 基于CRF模型的目標標號

與其他常見的前景檢測方法類似，本文基于HOG與LBP聯合特征提取方法，然后使用線性SVM進行前景和背景分割，得到一系列假定的前景觀測D。然后把觀測作為輸入數據，建立CRF模型，具體步驟如下：

（1）將每一個觀測看成一個頂點V，對其分配一個唯一的ID標號；若為背景，則統一標號為?；

（2）將同一幀圖像中的不同觀測用空間互斥邊EX相互連接；

（3）相鄰兩幀圖像，如果觀測之間的兩兩距離小于特定的閾值τ，則使用時間平滑邊ES相互連接；

本文的主要任務包括數據關聯與軌跡評估兩個步驟。數據關聯通過離散多標號CRF模型來表示，而軌跡評估通過連續光滑的曲線模型來表示。此外，從兩個不同方面說明了目標之間的互斥現象。首先從空間上，通過引入競爭檢測二元項來避免數據誤讀現象。然而，僅僅空間上的約束是遠遠不夠的。因此，在時間上也采取了一些互斥方法，當同一時刻的兩個不同目標軌跡發生重疊時，本文還引入了一種新穎的二元共生標號成本。

1.1 符號注釋

D為一系列假設目標，dgt表示第t幀圖像中的目標g，wgt為置信度值。Pgt∈R2為第t幀圖像中某個觀測目標的位置，(xi,yi)為對應的參考平面坐標。T={T1,T2,…,TN}表示所有假設目標軌跡，其數量遠大于場景中目標的實際數量。對于給定的標號集l，ld∈L={1,2,....，N,?}，其中L表示所有假設軌跡的標號集。若某個觀測目標屬于前景，則ld∈L={1,2,....,N}；若為誤報，則 ld=?。表示場景中所有觀測目標的有效軌跡；?=?S∪?X表示所有CRF模型的邊，其中?S表示相鄰兩幀圖像中，所有觀測目標之間距離小于特定閾值τ的時間平滑邊，而?X表示同一幀圖像中不同觀測目標之間的空間互斥邊。

1.2 多目標跟蹤的能量函數

在計算機視覺領域，多標號問題可以被描述成最大后驗估計(MAP)，可以通過由頂點和邊構成的CRF模型G={V,E}來描述，并分別求CRF中頂點和邊的最小能量。鑒于此，本文將每一個檢測到的觀測d∈D看成是CRF模型中的頂點V，兩個相鄰的頂點用一條邊?相互連接。然而，目的不僅僅是預測離散標號集體l，還包括目標的連續軌跡T。本文多目標跟蹤的離散-連續能量函數如公式（1）所示：

其中β，γ，δ表示各部分能量所占的權重，在實際實驗中，可以通過調節能量函數前的權重改變跟蹤的效果。v{Ed(ld,T)}表示軌跡擬合成本，?{ES(ld,ld’),EdX(ld,ld’)}表示由邊 ? 產生的成本，ES(ld,ld’)表示相鄰兩幀屬于同一條?S的標號不同時產生的成本，EdX(ld,ld’)表示同一幀圖像中兩個觀測標號相同時產生的成本，φ{Etr(Ti),EtrX(Ti,Tj)}表示單個軌跡和互斥軌跡共同產生的成本，Etr(Ti)表示單個目標的軌跡成本，EtrX(Ti,Tj)表示互斥軌跡產生的成本。為了方便表示，公式中

目標函數旨在找到一組能使E(T,l)取得最小能量的標號集與跟蹤軌跡的狀態：(T×,l×)=argmin(T,l)E(T,l)，本文先固定標號集l，然后對目標的軌跡進行連續優化；然后再固定軌跡集T的相關參數，對標號l集進行離散優化。首先詳細介紹連續軌跡的表示模型與每一項能量分量。

1.3 軌跡評估

與之前許多單純的離散多目標跟蹤方法相比，本文采用連續的光滑曲線表示目標的運動軌跡，如圖1所示。其中，左端點為起始幀si，右端點為結束幀ei。

圖1 二維連續軌跡模型圖

每個軌跡的二維線條表達式如公式（2）所示：

其中(x,y)T表示目標i在t時刻的位置，對應于圖1中的離散點。

假定每個目標的軌跡具有若干個片段，相關參數通過系數矩陣Ci∈R2cix4來表示。軌跡片段的數量取決于每個目標軌跡的長度F(i)，本文中軌跡片段的數量設置為max(1,[F(i)/15])，其中[.]表示四舍五入，F(i)=ei-si+1。為了抑制軌跡端點處的觀測誤分配給其他軌跡，因此采用外推法進行限制，即t∈[si-Δ,ei+Δ]，本文設置 Δ=3。

假定已經固定了數據關聯項l，于是argminTEl(T)=argminTE(T,l)。因此，軌跡評估的最小能量函數如公式（3）所示：

其中Ed(ld,T)表示帶有標號l的觀測與該目標實際軌跡的擬合程度。Etr(Ti)表示單個目標的軌跡，只有當該軌跡屬于有效軌跡 Tl× 時，即的成本才產生，例如該軌跡中至少有一個觀測目標被標號為前景，標號方式與規范一致。EtrX(Ti,Tj)表示目標i和j軌跡重疊時產生的成本。

（1）擬合軌跡

Ed(ld,T)表示某個觀測目標d∈D屬于該目標軌跡的一元數據成本，衡量標準為該觀測與其軌跡之間的最短距離。此外，該項還能表示該觀測目標是否屬于誤報。為了方便起見，將觀測目標dgt統一用d來表示。定義第t幀圖像中的軌跡擬合成本如公式（4）所示：

其中wgt表示觀測目標的置信度值，pgt表示該觀測的位置，Dis(.)表示距離函數，即觀測目標距離其軌跡的最小距離。當某個檢測結果的標號為l=Φ，此時產生成本λΦ×wgt只與數據關聯有關，表示誤將背景當成目標。

為了使得公式（5）能基于梯度算法進行優化，本文采用可微分的歐氏距離函數，同時為了防止微分后的分母為零，距離函數中加上一個很小的微調參數?=0.1，函數定義如公式（5）：

（2）先驗軌跡

目標i的軌跡先驗能量函數由以下幾個方面組成，如公式（6）所示：

其中Elin(Ti)表示目標i的線速度能量，Eang(Ti)表示目標i的角速度能量，Eper(Ti)表示目標i軌跡的持久性能量，λreg為軌跡修正模型的能量，為了防止迭代過程中的過擬合。上式中的每一項都可微。

所有目標的運動都應該合乎一定的物理限制，即在同一時刻，同一物理空間不可能有兩個觀測目標。本文所用的動態模型是建立在目標的角速度和線速度緩慢變化的基礎上進行的。為了和之前的定義相對應，設x=x(t)，y=y(t)作為參考平面曲線的坐標，x’(t)，y’(t)為一階導數，x’’(t)，y’’(t)為二階導數。

假定行人最可能以大約1.2m/s的勻速移動。如果偏離這個速度，就進行二次懲罰。因此，線速度模型的表達式如公式（7）所示：

除了目標的線速度模型，本文還給出了目標的角速度模型，t時刻目標的角速度通過公式（8）給出：

其中?=0.1，通過以上變形，得到目標i的角動態軌跡模型，如公式（9）所示：

當目標進入特定的跟蹤區域，會產生不同程度的出現或者消失。目標的軌跡總是開始或者終止于預定義感興趣區域的邊界。本文通過以下“sigmoid”函數對軌跡的持久性進行修正，如公式（10）所示：

其中B(Ti1)表示第i條軌跡的起點與最近的跟蹤區域邊界間的距離，B(TiF)表示第i條軌跡的終點與最近的跟蹤區域邊界間的距離。參數u=1/s，試驗中s=35cm。該措施有利于目標遮擋后的軌跡恢復，有效地避免了因遮擋而發生跟蹤軌跡突然中斷的現象。

（3）互斥軌跡

在所有的圖像幀中，不同目標之間的軌跡在空間上不應該重疊。本文引入一種二元標號成本思想。如果同一物理空間中的不同目標軌跡發生重疊，則對該軌跡對進行一定的懲罰，如圖2所示

圖2 不同目標軌跡相互重疊的示意圖

針對每一對有效軌跡Ti,Tj∈Tf×(i≠j)，則產生相應的二元標號成本EtrX(pairwisecost)。當兩個目標比較接近時，對應的懲罰成本接近無窮大，如公式（11）所示。

其中X(Ti,Tj)表示軌跡i與j在時間上的重疊，s=35cm表示檢測框的寬度。

1.4 數據關聯

數據關聯是給每一個觀測d∈D分配一個唯一的ID標號，并確定該觀測屬于某個目標i的軌跡，或者屬于誤報(?)。鑒于此，若把等式(1)中的軌跡假設部分先固定，則數據關聯部分的最小能量公式等價于公式（12）：

其中 ES（ld,ld’）

與EdX(ld,ld’)是由兩種類型的二元邊?=?S∪?X引起的能量。ES（ld,ld’）表示時間平滑邊?S的成本函數，即相鄰兩幀圖像中觀測標號不同時產生的成本。EdX(ld,ld’)表示空間平滑邊?X的成本，即同一幀圖像中出現相同標號時產生的成本。

（1）時間平滑邊?S與空間互斥邊?X

時間平滑邊?S提供數據關聯的時間平滑度。

相鄰兩幀圖像中，如果觀測之間的兩兩距離小于特定的閾值τ，則使用時間平滑邊?S連接，表達式如公式（13）所示：

其中F表示視頻的幀數，該措施使得相鄰兩幀圖像中同一個目標具有相同的標號。在能夠保證足夠的目標動態情況下，閾值τ盡可能的大。

在同一幀圖像中，空間互斥邊?X能夠確保同一幀圖像中每一個觀測目標的標號唯一。另一方面，對于那些非常相似的觀測，采用多個邊也是合理的，因為即使是進行了非最大化壓縮，檢測器有時候也會錯誤的產生來自同一個目標的多個輸出，如公式（14）所示。

其中pit∈R2為觀測dit∈D的坐標（xi,yi），s表示矩形檢測框的寬度。

如圖3所示，綠色結點代表觀測器響應的隨機變量，藍色結點表示二元能量成本，為了方便表示，圖中給出了部分能量。紅色的邊表示時間平滑因子?X，灰色的邊表示空間間互斥因子?S。

圖3 CRF模型的因子圖

（2）數據關聯的能量

數據關聯通常是多目標跟蹤最有挑戰性的一個方面。本文通過多標號CRF模型來闡述數據關聯問題。連接時間鄰域（ld,ld’）∈?S，ld與ld’表示相鄰兩幀具有相同標號的觀測。該時間平滑邊的能量定義如公式（15）所示：

其中δ（.）表示沖激序列，當ld≠lD’時，則產生一定的懲罰 λ?s。

為了防止數據誤讀，本文引入空間互斥邊（d,d’）∈?X確保同一幀圖像中每個目標的標號唯一，空間互斥邊?X的能量定義如公式（16）所示：

其中δ（.）表示沖激序列。同一幀圖像中，如果相鄰目標之間的標號相同，則進行一定的懲罰。

2 離散與連續優化

本文旨在確定每個目標的標號，并確定每個目標的最優軌跡。為了能夠找到公式（1）的強局部最小能量，本文采用離散-連續交替的優化方案來求取目標函數的最小能量。當離散標號的分配發生收斂時（或者迭代次數達到最大），優化步驟停止。接下來對每個部分的優化步驟進行詳細介紹。

2.1 離散標號優化

離散優化旨在尋找一組帶有標號l的目標，并把每個目標分配給唯一的軌跡(來自大量的軌跡假設池)。本文試圖尋找一種方法求解等式(12)的最小能量。然而，等式(12)的二元互斥函數EdX（ld,ld’）為非子模函數；其次，Etr（Ti）引入的全局因子依賴于所有的標號，同時還需要采用一種恰當的方法求解二元標號能量EtrX（Ti,Tj） 。為了最小化標號成本，本文采用α-expansion算法，即把離散多標號問題轉化為只有兩個標號狀態的問題進行求解。

由于 Ed（ld,T）、ES（ld,ld’）以及 EdX（ld,ld’）的能量很容易通過標準的α-expansion算法求得，因此本文重點描述Etr（Ti）與EtrX（Ti,Tj）的能量。假設我們已經通過恰當的方法獲得標號集l，在求取能量的過程中，通過驗證標號l是否會切換成α來確定其有效性，圖中的Sα為輔助節點，用來表示標號的切換情況。這是一種只有兩個狀態的優化問題，其中0表示對應的標號不發生改變，1表示對應的標號l切換為標號α。

如圖4所示，圖4(a)中的δ節點產生的能量用Ed（ld,T）表示，只要δ節點的標號變為α，則產生成本L0，否則成本為0。圖中的紫色與紅色方形節點表示Es（ld,ld’）以及EdX（ld,ld’）產生的能量，即當同一幀圖像中出現兩個相同的標號，或者相鄰兩幀圖像中由時間平滑邊?S相連的標號發生切換時產生的能量。由于此時能量相對較大，可被視為無窮大。

圖4 α-expansion算法示意圖

單個軌跡的成本Etr（Ti）。為了確保只有一半的重疊軌跡被壓縮，因此只在每一對具有相同物理空間的成對軌跡進行懲罰。然而，如何確定哪一個軌跡被懲罰是一個很重要的問題。為了解決該問題，本文采用了基于貪婪標號移除的α-expansion算法，即通過依次全部移除某個標號來檢查能量是否進一步降低。由于能量函數為非子模函數，本文采用偽布爾函數多項式優化算法（QPBO）算法進行每一步α-expansion，對應的因子圖如圖4（b）所示。對于單個軌跡的成本Etr（Ti），圖4（b）中黃色正方形表示目標β的標號切換為γ時產生的成本，記為L×。為了抑制兩個不可能同時存在的標號而導致能量的增加，當且僅當兩個對應的輔助變量同時發生標號切換時，則進行相應的懲罰L××，此時表示兩個不同的目標β和γ同時切換為標號α。通過這種方式獲得的是超子模函數的成本，而等式（12）的成本函數總體上是非子模的。

2.2 連續軌跡優化

由于能量函數的連續部分為非凸函數，但可以通過梯度下降法來進行求解，本文采用梯度下降法（BFGS）。最終的優化結果依賴于初始化軌跡。因此，本文采用連續能量全局最小化函數來表示，如公式（17）所示：

該等式除了Ed’項中的二次懲罰函數Dis(d,d’)=║x-y║2不一樣，其他數據成本等同于上文的式(3)。于是等式（17）就轉化成通過閉合形式求解的加權最小二乘問題，本文采用El×(T)軌跡作為初始化條件。

3 軌跡假設空間

本文采用采用改進的隨機采樣一致性算法（RandomSampleConsensus）擬合直線，優先檢測那些在空間上和時間上更接近的軌跡，并隨機選擇觀測子集。

僅僅依賴于初始的軌跡假設，可能會在一定程度上限制能量的最優解。為了使得優化的過程更加靈活，因此在基于當前解決方案的基礎上，在每一次連續優化迭代結束之后，對軌跡假設的搜索空間進行一定的擴展。本文采用以下3種方法進行擴展軌跡假設空間：（1）對于那些連續超過10幀都沒有檢測到目標的軌跡，則把它分割成兩個較短的軌跡。對于時間間隔不超過t0幀的軌跡片段i與j，則合并成一個新的軌跡，t0可以根據實際情況進行調整，本文t0=25。（2）如果迭代過程中有一兩幀突然出現能量上升，短時間內又恢復正常，則認為當前幀是不可靠的，進一步從場景中移出移除這一幀軌跡。在若干次迭代以后，當新添加軌跡的能量仍然按梯度下降的方向進行，則說明新添加的軌跡比較可靠。（3）及時擴展現有軌跡，即通過移動軌跡的端點（si往前移動，ei向后移動）；或者及時收縮那些沒有目標出現的軌跡，即分別移除原來軌跡端點處的前4幀和后4幀。軌跡假設空間的擴展過程如圖5所示。

圖5 擴展軌跡假設空間示意圖

4 實驗結果

4.1 參數設置

本文對每個參數進行固定調試。輪流固定公式1中β、γ、δ的值，改變另一個變量，判斷對MOTA性能的影響。并根據MOTA指標進行適當調試，其余的兩個參數值同理可得，為了方便調試，β固定為1，圖6給出了其余兩種情況下的評估標準。

圖6 各參數的變化對MOTA指標的影響圖

其中，參數β=1保持不變，分別先固定其他參數值，然后給出單個參數值改變時的影響。圖6中每條曲線均表示MOTA隨參數變化的情況。

從圖6可以得出，某一調節系數的值變化較大時，只要跟蹤結果的MOTA變化不是太大，則均認為該參數是可信的。當MOTA=0時，說明參數的變化對MOTA指標的影響很小。能量函數中的調節在以上4個數據集中，均設置為｛1, 0.03, 0.8｝。

另外，本文還給出了8種相關的參數，通過梯度下降法得到了最高平均MOTA值，表1為具體的參數值。

表1 相關參數值對應表

輪流的改變每個參數的值，取值范圍從0到2，然后再與它們的標準值1相乘，并觀察MOTA性能指標的變化。本文分別先固定其他參數值，然后給出單個參數值改變時的影響，所有參數被分成兩組。

圖7給出了第一組（λreg，λang，λEdX，λEs）參數的變化對整體MOTA性能指標的影響，從圖中可以看出，跟蹤精確度只出現了微小的變化，跟蹤結果的魯棒性較好。需要注意的是，不同的測試視頻序列或者訓練集，參數的重要性可能發生一定的變化。

圖7 第一組參數變化對整體跟蹤性能的影響圖

圖8給出了另一組相關參數（λper，λ?，λEtrX，λlin）。當各自的能量權重下降時，MOTA性能指標受到了很大的影響。因此，有必要把誤標號成本λ?（離群值）、二元標號成本λEtrX以及軌跡持久性成本λper等相關參數考慮在內。其中λ?參數是用來懲罰沒有觀測目標的平凡解。λEtrX防止來自同一個目標的觀測被分配給不同的軌跡，從而減少誤跟蹤的數量。λper確保產生長久的、連續的目標軌跡，減少目標之間的身份切換（IDs）。

圖8 第一組參數變化對整體跟蹤性能的影響圖

4.2 數據集

PETS2009benchmark數據集場景豐富、光照變化較強以及行人姿態變化各異，逐漸成為多目標跟蹤實驗最受歡迎的數據集之一。本文實驗只使用其中部分的視頻序列，由3個可用攝像機校準的視頻序列組成。除了廣泛使用的PETS2L1視頻序列，還包括2個更具有挑戰性的場景：S2L2以及S1L1-2視頻序列。其中S2L1包含8個場景，共有795幀，8個行人，視頻序列的分辨率為768×576；S2L2與S1L1-2視頻序列隨著時間的推移，場景中的行人越來越多，而且場景比較擁擠。其中S1L1-2共有240幀，S2L2共有435幀，視頻圖像序列的分辨率均為768×576。在所有實驗中只使用第一攝像機視點。TUD-Stadtmitt行人數據集是采用低角度攝像機拍攝的行人街道，該數據集的視頻序列共有250幀，圖像分辨率為720×576。

4.3 評估指標

本文著重算法的魯棒性和跟蹤結果的準確性，對目標檢測和跟蹤性能進行評估。性能評估指標包含以下幾方面：

（1）MOTA：目標跟蹤準確度；

（2）MOTP：目標跟蹤精確度；

（3）FAF：每幀中目標誤警的數目；

（4）GT：實際的跟蹤軌跡數目；

（5）MT：絕大多數正確跟蹤的軌跡數目，正確跟蹤的軌跡數目與實際的跟蹤軌跡數目的百分比大于80%；

（6）ML：最大丟失的跟蹤軌跡數目，丟失的跟蹤軌跡數與實際的跟蹤軌跡數目之比小于20%；

（7）Frag：跟蹤過程中，軌跡發生中斷的次數；

（8）IDs：跟蹤軌跡中，目標身份交換的次數。

4.4 對比實驗及分析

本文給出了PETS2009S2L1視頻序列中的對比實驗結果，包含8個運動目標，共有795幀圖像，每一幀圖像的間隔為0.01s。并選出第306幀、319幀和330幀的跟蹤圖像進行效果對比。

結合表2的實驗數據可知，基于SegTrack跟蹤算法在第306幀與319幀之間、第319幀與第330幀之間均出現了不同程度的漏檢和標簽互換。由于第306幀中的18號目標比較擁擠，到了第319幀中標簽互換為48號，第319幀中的32目標在第306幀中出現了漏檢。另外，第33號目標旁邊的行人始終處于漏檢狀態。由于第319幀中的29號目標被物體遮擋，到了第330幀變成了52號目標。因此，該算法的跟蹤性能并不是十分穩定。對于HDA-DVM算法，同樣出現了不同程度的漏檢問題。第306幀中的15號目標由于遮擋原因，到了第319幀出現了漏檢；第319幀中的13號目標到了第330幀出現了漏檢情況，而本文所提算法成功克服了由于遮擋、擁擠造成的漏檢和標簽互換問題。從表2的實驗數據也可以看出，本文所提算法的精確度與準確度都要明顯高于其他兩種方法，而且在最大跟蹤軌跡數MT指標也優于其他兩種算法。

表2 三種跟蹤算法跟蹤性能對比結果表

5 結論

本文提出了一種基于數據關聯與軌跡評估的多目標跟蹤方法。首先，從時間和空間的角度建立CRF模型，并給出標號方式；其次，將目標的數據關聯與軌跡評估整合到同一個CRF模型中，并詳細地介紹了各個能量分量的模型；最后，采用基于貪婪標號移除的ɑ-expansion算法更新標號，以及基于梯度下降法的軌跡優化，并擴展了軌跡假設的空間。最后的實驗結果表明，本文所提算法優于當前先進水平的多目標跟蹤技術。