《simple online and realtime tracking with a deep association metric》DeepSORT論文筆記

DeepSORT: Simple online and realtime tracking with a deep association metric 2017 IEEE ICIP

對SORT論文的解讀可以參見我之前的博文。根據之前Survey中提到的MOT四步驟架構（detection-feature-affinity-association），其實DeepSORT是在affinity相似度計算這一步運用了CNN-based appearance深度特征，而在association比對這一步沒有使用深度方法。

摘要：

• 內建了appearance information來輔助比對 -> 能夠在目标被長期遮擋情況下保持追蹤，有效減少id switch(45%).
• offline pre-training: 離線用大規模的person re-identification資料集對deep association metric作預訓練，使最複雜的計算線上下完成
• online application: establish measurement-to-track associations using nearest neighbor queries(餘弦距離) in visual appearance space

Keywords: Computer Vision, Multiple Object Tracking, Data Association

文章目錄

• 1 Introduction
• 2 SORT with Deep Association Metric
• • 2.1 Track Handling and State Estimation
  • 2.2 Assignment Problem
  • • 2.2.1 Motion
    • 2.2.2 Appearance
    • 2.2.3 Combination of both
  • 2.3 Matching Cascade
  • 2.4 Deep Appearance Descriptor
• 3 Experiments

1 Introduction

SORT算法是一個非常簡單的架構，它采用了faster R-CNN檢測bbox，并直接根據bbox的位置和大小 用卡爾曼濾波作運動估計，以bbox IOU作為相似度度量 用匈牙利算法進行detections和targets的比對。

盡管SORT算法精度不錯且速度很快，但它的缺點是ID switch數量較高(畢竟隻有在運動估計的不确定性很低時，比對才能比較精确，在遮擋情況前後特别容易出錯)。

本文提出同時使用motion和appearance資訊，來作為比對的準則。這可以增強模型在misses和occlusions情況下的魯棒性。

2 SORT with Deep Association Metric

2.1 Track Handling and State Estimation

與SORT算法基本一緻，通過Kalman Filter來更新target state。超過預設最大年齡 A m a x A_{max} Amax​幀沒有比對到detection的target将被從tracker池中删除；每個不能比對到現有targets的detection會被立即初始化一個target添加到tracker池，但在最初的三幀中這些新tracker處于暫定狀态，一旦沒有成功比對到detection就會被立即删除（這可以有效降低false positive）。

不同之處在于略微修改了target state的定義：

( u , v , γ , h , x ˙ , y ˙ , γ ˙ , h ˙ ) (u,v,\gamma,h,\dot{x},\dot{y},\dot{\gamma},\dot{h}) (u,v,γ,h,x˙,y˙​,γ˙​,h˙)

其中， ( u , v ) (u,v) (u,v)是bbox的中心位置， γ \gamma γ是aspect ratio寬高比， h h h是bbox高度，最後四項是它們對應的速度。我們認為 ( u , v , γ , h ) (u,v,\gamma,h) (u,v,γ,h)是直接觀測值，而通過上一時刻位置和速度的最優估計，我們還可以通過線性速度模型得到一個目前狀态的經驗估計值。與SORT的差別是，此處認為寬高比是可線性變化的，而SORT認為是固定常數。此外用高度 h h h來代替之前的scale。

2.2 Assignment Problem

相似度計算分為motion和appearance兩部分，最終相似度是它們的gated權重和。

2.2.1 Motion

先簡單介紹一下馬氏距離。參考資料

馬氏距離是一種有效的計算兩個未知樣本集的相似度的方法或者計算一個樣本點與一個分布的距離。與歐氏距離不同的是它考慮到各種特性之間的聯系（例如：一條關于身高的資訊會帶來一條關于體重的資訊，因為兩者是有關聯的）并且是尺度無關的（scale-invariant），即獨立于測量尺度。

馬氏距離可以衡量一個随機變量和一個分布之間的距離：對于一個均值為 μ = ( μ 1 , μ 2 , μ 3 , … , μ p ) T \mu=(\mu_1,\mu_2,\mu_3,\dots,\mu_p)^T μ=(μ1​,μ2​,μ3​,…,μp​)T，協方差矩陣為 Σ \Sigma Σ的多元随機變量：

x = ( x 1 , x 2 , x 3 , … , x p ) T x = (x_1,x_2,x_3,\dots,x_p)^T x=(x1​,x2​,x3​,…,xp​)T

馬氏距離為:

D M ( x ) = ( x − μ ) T Σ − 1 ( x − μ ) D_M(x) = \sqrt{(x-\mu)^T\Sigma^{-1}(x-\mu)} DM​(x)=(x−μ)TΣ−1(x−μ)

​

本模型使用 (squared) Mahalanobis distance馬氏距離來度量【預測的卡爾曼狀态】和【新檢測到的bbox】之間的距離：

d ( 1 ) ( i , j ) = ( d j − y i ) T S i − 1 ( d j − y i ) (1) d^{(1)}(i,j)=(\boldsymbol{d}_j-\boldsymbol{y}_i)^T\boldsymbol{S}_i^{-1}(\boldsymbol{d}_j-\boldsymbol{y}_i) \tag{1} d(1)(i,j)=(dj​−yi​)TSi−1​(dj​−yi​)(1)

原文解釋是“将第 i i i個track分布投影到度量空間，記為 ( y i , S i ) (\boldsymbol{y}_i,\boldsymbol{S}_i) (yi​,Si​)；将第 j j j個檢測到的bounding box記為 d j \boldsymbol{d}_j dj​”。根據我的了解，應該是用前一幀的target state對目前幀的bbox位置、大小 ( u , v , γ , h ) (u,v,\gamma,h) (u,v,γ,h)進行估計，這是一個多元高斯分布，有均值 y i \boldsymbol{y}_i yi​和方差 S i \boldsymbol{S}_i Si​。而通過detector可以直接得到目前的bbox觀察值 ( u , v , γ , h ) (u,v,\gamma,h) (u,v,γ,h)，這就是上面引言裡所說的随機變量。是以，這個motion的距離度量，其實就是計算“detetor探測到的bbox

随機變量

”與"通過卡爾曼濾波估計的bbox

分布

"之間的距離。

馬氏距離考慮了運動估計的不确定性，因為它将估計位置看作一個分布，計算随機變量和一個分布之間的距離；而不像SORT算法中直接看作準确的一個bbox，用IOU來度量距離。

此外，引入一個門檻值來排除那些距離過大的比對組合，這個決策用一個indicator來表示：

b i , j ( 1 ) = 1 [ d ( 1 ) ( i , j ) ≤ t ( 1 ) ] (2) b_{i,j}^{(1)} = \mathbf{1}\left[d^{(1)}(i,j) \leq t^{(1)}\right] \tag{2} bi,j(1)​=1[d(1)(i,j)≤t(1)](2)

其中 t ( 1 ) = 9.4877 t^{(1)}=9.4877 t(1)=9.4877，這一數值是對四維的變量空間 ( u , v , γ , h ) (u,v,\gamma,h) (u,v,γ,h)在逆卡方分布上要求能達到95%以上的置信度計算出的。這裡我不深究原因，隻簡單當作一個距離度量的門檻值，想了解背後原理的請自行學習。

2.2.2 Appearance

當運動估計的不确定性很低時，使用馬氏距離作為比對準則是合适的。但是我們沒有考慮相機自身的運動和遮擋關系，這些都會使得運動估計的不确定性變高。是以，本論文新引入了appearance特征，作為另一個比對準則。

提取appearance特征非常簡單，我們直接離線預訓練一個CNN，來計算bbox appearance descriptors（其實就是一個特征向量feature embedding），具體訓練方式2.4節會講。線上上使用時，對每個bounding box detection d j \boldsymbol{d}_j dj​，都計算一個外觀描述符 r j \boldsymbol{r}_j rj​，要求 ∥ r j ∥ = 1 \left\| \boldsymbol{r}_j \right\| = 1 ∥rj​∥=1. 此外，對每個track i i i ，我們都儲存它最後 L k L_k Lk​個比對到的detection的外觀描述符，記為 R i = { r k ( i ) } k = 1 L k R_i=\left\{ \boldsymbol{r}_k^{(i)} \right\}_{k=1}^{L_k} Ri​={rk(i)​}k=1Lk​​ ，取 L k = 100 L_k=100 Lk​=100. 那麼， 第 i i i個track和第 j j j個detection在appearance空間的距離度量為它們的外觀描述符的最小餘弦距離：

d ( 2 ) ( i , j ) = m i n { 1 − r j T r k ( i ) ∣ r k ( i ) ∈ R i } (3) d^{(2)}(i,j) = min\left\{ 1-\boldsymbol{r}_j^T\boldsymbol{r}_k^{(i)} | \boldsymbol{r}_k^{(i)} \in R_i \right\} \tag{3} d(2)(i,j)=min{1−rjT​rk(i)​∣rk(i)​∈Ri​}(3)

同樣引入一個門檻值來排除在appearance space距離太大的比對組合：

b i , j ( 2 ) = 1 [ d ( 2 ) ( i , j ) ≤ t ( 2 ) ] (4) b_{i,j}^{(2)} = \mathbf{1}\left[d^{(2)}(i,j) \leq t^{(2)}\right] \tag{4} bi,j(2)​=1[d(2)(i,j)≤t(2)](4)

t ( 2 ) t^{(2)} t(2)的取值是在一個單獨的訓練集上實驗選出的。

2.2.3 Combination of both

度量準則	效果
motion	短期預測，區分度更差
appearance	長期預測，适用于目标在長時間遮擋後恢複比對 re-identification

用權重的方式融合上述兩種度量方法：

c i , j = λ d ( 1 ) ( i , j ) + ( 1 − λ ) d ( 2 ) ( i , j ) (5) c_{i,j} = \lambda d^{(1)}(i,j) + (1-\lambda)d^{(2)}(i,j) \tag{5} ci,j​=λd(1)(i,j)+(1−λ)d(2)(i,j)(5)

用 ( 2 ) ( 4 ) (2)(4) (2)(4)兩式共同gating：

b i , j = ∏ m = 1 2 b i , j ( m ) . (6) b_{i,j} = \prod_{m=1}^2b_{i,j} ^{(m)}.\tag{6} bi,j​=m=1∏2​bi,j(m)​.(6)

λ \lambda λ是一個超參數，我們分發現相機自身運動很多時，設定 λ = 0 \lambda=0 λ=0是一個合理的選擇，即隻考慮appearance資訊。不過，即便是隻使用appearance資訊，也要保留 ( 2 ) (2) (2)式馬氏距離的門檻值gate，來丢棄一些不合适的比對。

2.3 Matching Cascade

作者發現當目标被長時間遮擋時，卡爾曼濾波的估計值不确定性就很大(機率分散在很大的一個空間)，此時我們期望detection與該目标計算的motion馬氏距離偏大。然而恰恰相反，馬氏距離更傾向于不确定的分布(對協方差大的分布，距離小)，這會導緻産生更多fragments和不穩定的追蹤。是以，作者提出了級聯式比對，優先比對那些更頻繁看見(不确定性小)的目标。

從上圖第5行可以看出，級聯比對算法優先比對那些age小的目标。age是一個track距離上一次被成功檢測間隔的幀數，age越小，說明它在越接近目前時間的幀中被檢測到(比對上)過。

這裡第7行的

min_cost_matching

我個人認為是指二部圖的最小權比對，且不要求完美比對，可以通過略微修改的KM算法計算。如了解有不對，麻煩大家指出。KM算法參考

2.4 Deep Appearance Descriptor

作者想得到具有區分性的feature embedding，為此他們離線在大規模的person re-identification dataset上進行CNN預訓練。CNN網絡結構的最後一層加入了batch norm和 l 2 \mathscr{l}2 l2 norm，使最後得到的特征可以投影在機關超平面内（特征向量的模長為1），适用于appearance metric中用到的餘弦距離。

預訓練模型放在作者的Github 倉庫上。

3 Experiments

采用超參數 λ = 0 , A m a x = 30 \lambda=0,A_{max}=30 λ=0,Amax​=30進行實驗。

正如摘要中所說，DeepSORT降低了ID switch的次數（顯然是通過appearance feature的精确比對）。此外，DeepSORT保持了至少30幀的“閑置”目标資訊（SORT隻要一幀不能比對就會直接丢棄目标），而且還有外觀特征輔助re-identification，更容易從長時間的遮擋中恢複原目标的識别。

【一些優化方向】

• FP比較高是一個值得注意的問題。detector間或性地會将一些靜止背景中部分圖案檢測出bbox，而由于我們設定了一個較長的 A m a x A_{max} Amax​，這些圖案也會被認為是一段追蹤軌迹，由此産生FP。如果提高對detector結果置信度的門檻值，可能可以降低FP。
• 運作時間一半被花在appearance特征提取上，畢竟深度網絡計算量大。