HCHUNGW的部落格

8.4 目標跟蹤（上）——DeepSORT原理

前言

目標跟蹤技術可以用於人流量計數和車流量計數等，能夠幫助人們更好地瞭解和掌握一個地區的交通狀況和人流狀況。這些計數功能有以下幾個價值和意義：

1. 交通規劃：通過瞭解車流量，可以更好地規劃交通路線和疏導車流，提高交通效率，減少擁堵，從而減少交通事故的發生。
2. 商業決策：通過瞭解人流量，可以更好地瞭解商業活動的熱點區域，從而制定更加有效的行銷策略和經營計畫，提高商業效益。

目標跟蹤（object tracking）定義是，在視頻序列中識別目標並賦予唯一標識，同時跟蹤目標在視頻序列中的位置。在自動駕駛、監控、人機交互等領域都有應用。

目標跟蹤常用的策略是TBD（Tracking-by-Detecton），又稱DBT（Detection-Based-Tracking）。即在每一幀進行目標檢測，再利用目標檢測的結果來進行目標跟蹤，這一步稱為資料關聯（Data Assoiation）。與之相對的，是DFT（Detection-Free Tracking）， DFT使用較少。

根據目標的數量，目標跟蹤可分為單目標跟蹤（Sing-Object Tracking）與多目標跟蹤（Multi-Object Tracking），目前MOT研究較多，並且MOT可覆蓋SOT。

根據處理時效性，又可分為線上跟蹤（Online）與離線跟蹤（Offline），離線跟蹤是指可以使用後續幀的資訊來預測當前幀，在視頻分析中可用。線上跟蹤是只能採用前序幀資訊與當前幀資訊，這是目前主流方案。

本案例中的目標跟蹤屬於多目標跟蹤、線上跟蹤、TBD。

通過簡單定義，可以知道，目標跟蹤分兩步

1. 檢測：找出當前幀中的目標，即目標檢測
2. 關聯匹配：將當前目標與歷史幀中的目標進行關聯與匹配

檢測可以採用各類目標檢測演算法，關聯匹配可以採用deepsort演算法。

本案例將詳細介紹DeepSORT演算法原理，並基於yolov5實現車流量統計代碼。

DeepSORT演算法流程

DeepSORT演算法發表於2017年，其是SORT的改進版。SORT(Simple Online and Realtime Tracking)於2016年發表，主要基於卡爾曼濾波和匈牙利演算法實現。

DeepSORT演算法則是對SORT加入了Deep Association Metric進行特徵提取與匹配，是目前精度與速度都不錯的跟蹤演算法。

SORT論文速讀：提出了基於卡爾曼濾波和匈牙利演算法的目標跟蹤策略，同時發現好的目標檢測器，可以大幅度提升MOT精度，高達18.9個百分點。SORT實現分為4個步驟，分別對應3.1-3.4，目標檢測模型得到目標框；採用卡爾曼濾波進行軌跡框的預測；採用匈牙利演算法對目標框與軌跡框進行匹配；最後基於匹配結果，刪除舊軌跡框，添加新軌跡框。（論文只有5頁，核心內容第三章僅半頁紙，但不妨礙它是優秀的工作）

DeepSORT論文速讀：基於SORT，DeepSORT最大特點是引入了deep association metric，即採用CNN提取目標框中圖像特徵，來進行匹配。同時，涉及了級聯匹配策略，有了更好的准入、准出機制，對目標的跟蹤更精細、合理。

目標跟蹤的過程相當複雜，為了能瞭解全過程，這裡通過具體案例，一步一步發現問題，然後學習DeepSORT的解決方案，最後匯總。

為了將複雜的問題描述清楚，有必要對名詞進行一些解釋。

檢測框（dets）：由目標檢測模型輸出的框，包含框的位置資訊，物體類別資訊，是該物體的概率資訊

跟蹤框（tracks）：跟蹤模組認為是有價值的檢測框。跟蹤框中有兩種，一個是正式框，一個是預備框。論文中稱為confirmed, unconfirmed， 這裡借鑒正式黨員、預備黨員的叫法，應該好理解一些。

預備框（unconfirmed）：潛在的跟蹤框，只在演算法內部記錄，當達到一定條件，轉為正式跟蹤框，才能被演算法輸出，在螢幕上繪製出來。

正式框（confirmed）：目標跟蹤演算法的輸出，回顧定義，目標跟蹤需要在視頻序列中識別目標並賦予唯一標識，即輸出框應當包含檢測框資訊、唯一標識。

假設世界上沒有目標跟蹤演算法，需要我們自己構思，需求是在在連續幀中將檢測到的物體關聯起來，實現目標跟蹤。

現在有個行人跟蹤任務，如圖所示

第一幀：檢測器只有一個檢測框，因此賦予它唯一標識，再採用卡爾曼濾波演算法進行跟蹤框座標的輸出。

第二幀：檢測器輸出兩個框，如何將2個檢測框與1個跟蹤框進行匹配，獲得行人1在第二幀當中的跟蹤框。這時可以借助匈牙利演算法，它是求解任務分配問題的組合優化演算法。

匈牙利演算法可以很好的將檢測框1與前序跟蹤框1匹配上，然後對前序跟蹤框1進行更新(採用卡爾曼濾波)，獲得當前跟蹤框1。

對於檢測框2，沒有找到與其匹配的前序跟蹤框，所以認為它是新進入的，給它創建一個新跟蹤框即可。因此，當前跟蹤框應有兩個。

第三幀：又來了一個人，檢測到了3個框，因此重複第二幀的任務，採用檢測框更新採用卡爾曼濾波)跟蹤框的資訊，同時為王五註冊新的身份ID——行人3。

第四幀：張三離開了圖像，檢測器只檢測到2個框，2個檢測框去匹配3個跟蹤框，自然會有一個跟蹤框匹配不上，這裡顯然是行人1，因此沒有匹配上的跟蹤框需要被刪除，最終輸出兩個跟蹤框。

以此類推，新來檢測框匹配已有跟蹤框，匹配不上，則增加跟蹤框，同理，已有跟蹤框沒有匹配到新的檢測框，認為它離開了，需要刪除跟蹤框。

到這裡，一個基礎的目標跟蹤框架出來了，有了新增跟蹤框機制、刪除跟蹤框機制。這就是大名鼎鼎的SORT演算法的流程，對於匹配細節和跟蹤框的座標更新

SORT很好的解決檢測框如何與跟蹤框對上號，同時有了新增、刪除跟蹤框機制，但是對於常見的問題沒有得到很好的解決，例如：

1. 檢測器漏檢：檢測器在某一幀漏檢是很常見的現象，假設第二幀中，張三漏檢了，第二幀會將張三的身份ID——行人1給刪除。第三幀中的張三將會被認為是新來的，無法匹配到他是行人1。
2. 檢測器誤檢：檢測器在某一幀錯誤的將背景檢測為了行人，根據SORT演算法，會被背景賦予一個跟蹤框，這是很不合理的。

為了讓目標跟蹤演算法輸出的跟蹤框更穩定，DeepSORT引入了預備框、正式框機制，可以很好的解決漏檢、誤檢帶來的不穩定。

對於新增，要考察一下框是否是真的，通常用3幀的時間來考察，當發現框連續3幀都存在，那麼認為它是一個好的框，演算法批准框稱為正式框。這樣可以很好的過濾掉一些”沒有耐心“的框。這樣對於某一幀，某兩幀的誤檢，是很好的過濾方法。

對於刪除，要考察一下框是否真的離開，畢竟框也是經過了准入審查的，通常不會一瞬間就離開，此時給它連續30次機會，連續30幀裡邊發現它都不在了，將它永久開除。

綜合上述理解，DeepSORT流程解釋如下：

DeepSORT核心——匹配過程

匹配過程指的是，如何將檢測框與跟蹤框匹配上，讓每一個檢測框都能找到與之對應的跟蹤框。若沒有找到，則認為是新進入的物體，會創建新跟蹤框。

deepsort的匹配過程分兩部分。

首先，基於外觀特徵和馬氏距離，為正式框進行匹配，方法是級聯匹配（matching cascade），用到的優化方法是匈牙利演算法。

然後，基於bbox座標和IoU，為預備框進行匹配，採用剩餘檢測框與剩餘跟蹤框（未匹配和預備框）匹配，用到的優化方法是匈牙利演算法。

外觀特徵與bbox座標對應：表示的是對於一個物體，要用什麼特徵表示TA，是1128的向量？還是14的向量？

馬氏距離與IoU對應：表示兩個特徵之間"相近"程度的衡量，只有衡量了兩個特徵之間的距離，後續才能用優化演算法優化距離最短的匹配方案

匈牙利演算法作用：將N個A與M個B，採用特徵向量描述以及距離度量方法，可以得到N*M的距離代價矩陣，即A中每一個元素與B中每一個元素之間的距離。隨後用匈牙利演算法找到最優匹配。

級聯匹配

級聯匹配的思想是分70級進行匹配，級的概念指距離當前幀的遠近，第一級（level）採用所有檢測框， 和僅被記錄了一次的正式框（if tracks[k].time_since_update == 1 + level），以此迴圈70次。

因為越新的目標，越有可能與檢測框匹配上，存在太久的目標可能離開了。級聯匹配可以解決一部分身份交換問題。

級聯匹配中，傳入了：

distance_metric：基於外觀特徵（CNN提取出來的512維特徵向量）的舉例度量函數

max_distance：當距離大於max_distance時，認為是不匹配的

tracks：跟蹤框

detections：檢測框

track_indices_l：本輪需要匹配的跟蹤框的index

unmatched_detections：本輪需要匹配的檢測框的index

# code/chapter-8/tracking/deep_sort/deep_sort/sort/linear_assignment.py 的matching_cascade函數

for level in range(cascade_depth):

    if len(unmatched_detections) == 0:  # No detections left

        break

    track_indices_l = [

        k for k in track_indices

        if tracks[k].time_since_update == 1 + level  # 為每個跟蹤框記錄它被更新的次數，優先選擇新跟蹤框進行匹配， 1+0

    ]

    if len(track_indices_l) == 0:  # Nothing to match at this level

        continue

    # ============================ 核心部分：匹配 ================================

    matches_l, _, unmatched_detections = \

        min_cost_matching(

            distance_metric, max_distance, tracks, detections,

            track_indices_l, unmatched_detections)

    matches += matches_l

Copy

級聯匹配中採用的是跟蹤框的歷史特徵清單與檢測框進行匹配，如跟蹤框已經檢測到了18次，會得到18個特徵向量，新的檢測框有30個，則會得到18*30的矩陣。

然後在第0維選擇最小值，得到1*30的距離矩陣，最終判斷是否有匹配上的檢測框。

Tracker --> _match()  --> gated_metric() 下的：

cost_matrix = self.metric.distance(features, targets)

跳轉到：deep_sort/sort/nn_matching.py 的 NearestNeighborDistanceMetric.distance()

cost_matrix = np.zeros((len(targets), len(features)))

for i, target in enumerate(targets):

    cost_matrix[i, :] = self._metric(self.samples[target], features)

跳轉到：

def _nn_cosine_distance():

    distances = _cosine_distance(x, y)   # 18*30的矩陣

return distances.min(axis=0)  # 選擇距離最小的特徵； 如18*1，選擇18個跟蹤框中與第一個檢測框距離最近的；以此類推得到1*30.

# 由此可見，檢測框與目標的所有歷史特徵向量進行距離計算，挑選最近那個特徵的距離作為評判距離。

Copy

級聯匹配之後，會有未匹配的檢測框，未匹配的正式框（如果被記錄70次以上，是無法進行匹配的），以及預備框。

接下來用IoU測量檢測框與跟蹤框之間的相似性，很好理解，IoU越大，它倆越有可能是一個物體。

IoU匹配

IoU匹配的代碼位於：code/chapter-8/tracking/deep_sort/deep_sort/sort/tracker.py 的_match()函數，

同理採用的min_cost_matching進行匹配，傳入的有iou_cost度量函數，max_iou_distance用於過濾，跟蹤框，檢測框，需要匹配的跟蹤框的index，需要匹配的檢測框的index。

# Associate remaining tracks together with unconfirmed tracks using IOU.

iou_track_candidates = unconfirmed_tracks + [

    k for k in unmatched_tracks_a if

    self.tracks[k].time_since_update == 1]

unmatched_tracks_a = [

    k for k in unmatched_tracks_a if

    self.tracks[k].time_since_update != 1]

matches_b, unmatched_tracks_b, unmatched_detections = \

    linear_assignment.min_cost_matching(

        iou_matching.iou_cost, self.max_iou_distance, self.tracks,

        detections, iou_track_candidates, unmatched_detections)

Copy

匈牙利演算法

無論是級聯匹配還是IoU匹配，最後都會用到min_cost_matching函數，其中匹配的核心代碼是：

# code/chapter-8/tracking/deep_sort/deep_sort/sort/linear_assignment.py min_cost_matching()

row_indices, col_indices = linear_assignment(cost_matrix)  # 匈牙利演算法求解，得到配對的（raw, col）

Copy

這裡使用了scipy庫的linear_sum_assignment實現，可返回最優匹配的座標，到底匈牙利演算法是如何解決分配問題，下面進行介紹。

匈牙利演算法是1955年美國數學家哈樂德·庫恩（(W.W.Kuhn)），基於匈牙利數學家康尼格(D.Kőnig)提出的康尼格定理，提出求解二分圖最大匹配的一種方法。

二分圖（ Bipartite graph，二部圖）是圖論中一種模型，指的是有A，B兩個節點集合，存在一系列邊，邊的兩端不能再同一個集合，簡單說就是A只能和B相連，反之亦然。

為了求解分配問題，需要對二分圖中每種可能進行代價描述，稱之為代價矩陣（係數矩陣、變換矩陣等等）。

下麵借鑒視頻中的內容，簡要介紹匈牙利解決二分圖最大匹配問題。

假設有一本說明書，需要翻譯成4種語言，現在有4個人，他們對每個語言的熟悉程度不同，因此如何分配任務，就是一個典型的二分圖最大匹配問題。

首先，可以根據任務進行量化，得到目標函數min Z。

然後，設置約束條件，一個人選一個語言，一個語言只能被一個人選擇。

最後，得到右下角的方程式。

匈牙利演算法實現步驟是：

1. 畫圈，劃0：對代價矩陣每行減去最小值，使得其出現0；然後對列進行同樣操作，使得其出現0；
2. 試指派尋找最優解：0表示最優解，一行只有一個0的話，肯定優先考慮分配。
3.  
   1. 因此按行找僅有一個0的行，並且分配，分配之後，行已經被分配，因此對應的行需要刪除。
   2. 同理對列操作。
   3. 若還存在沒有標記的0元素，且找不到獨立0元素的行(列)，從剩餘0元素最少的行(列)開始，比較這行0元素所在列中0元素的數目，選擇0元素最少的那列的這個0元素畫圈，同時劃去該行該列其餘0元素。（如繞口令一般，這裡推薦看視頻）
4. 打勾，畫圈：沒有畫圈的行打√，打勾行含劃0元素的列打√，打√列含畫圈0元素的行打√，未打√的行畫橫線，打√的列畫分隔號。
5. 增加0元素：尋找未被直線覆蓋部分的最小元素，打 √的行減最小元素，打 √ 的列加最小元素。
6. 重複執行2-4，直到找到n個位於不同行不同列的0元素。

其核心思想是用增廣路求最大匹配，這裡的行列操作實際是將增廣路的思想轉換為矩陣的表達，因此單純觀察匈牙利演算法的矩陣解法，是很難理解其原因，建議通過圖論、運籌學的基礎知識去瞭解匈牙利演算法求解過程。

更多目標跟蹤中的匈牙利演算法講解推薦：

匈牙利演算法&KM演算法

目標跟蹤初探（DeepSORT）

代碼細節：

對於代價矩陣，行是tracks， 列是dets，匹配上的框才會有index返回。

DeepSORT核心——更新輸出過程

卡爾曼濾波

由於目標檢測演算法的不穩定，直接用目標檢測輸出的檢測框來表示目標位置的精度不佳，常常會看到框的抖動。

為了讓框更穩定的描述物體的位置，deepsort中採用了卡爾曼濾波演算法（Kalman filtering）來對目標位置進行輸出。

卡爾曼濾波演算法是斯坦利·施密特(Stanley Schmidt)在1958年提出的，當時要解決的是阿波羅飛船的導航問題，可以用於估計飛船的位置，是一個很好的運動估計。

隨後，卡爾曼濾波廣泛應用在天文，宇航，氣象等領域。

卡爾曼濾波可以解決的核心問題是，在一個線性動態系統中，可以基於歷史資訊與當前輸入資訊，很好的估計當前最優資訊，當前最優資訊就是卡爾曼濾波的輸出，它可以很好的過濾掉雜訊（必須是高斯雜訊）。

這裡的歷史資訊，可以理解為跟蹤框（tracks）（上一幀），當前輸入資訊是目標檢測演算法輸出的檢測框（dets），而當前時刻deepsort要輸出的目標的位置，是dets+tracks經過卡爾曼濾波演算法的輸出，即一個當前最優資訊，是一個預測的、估計的值。

為了對卡爾曼濾波有進一步認識，這裡簡要介紹卡爾曼濾波思想和概念。對於細節，推薦閱讀圖說卡爾曼濾波，， 從放棄到精通！卡爾曼濾波從理論到實踐~

這裡借用視頻中的公式進行講解過程，公式中更細節內容，可以參考卡爾曼濾波的五大公式

x：觀測物件，例如衛星的座標，圖像中目標的座標，水壺中的溫度等。

x：觀測物件，例如衛星的座標，圖像中目標的座標，水壺中的溫度等。

t：表示時刻

-：表示估計值

^：表示估計，由於x都是帶著^的，這裡可以不加以區分

F：狀態轉移矩陣

P：協方差矩陣

K：卡爾曼增益，用於權衡，歷史資訊與當前輸入資訊的重要程度。

對於目標跟蹤演算法的輸出，是公式4，公式4也是最核心的內容，其餘公式都在為公式4服務的。

為了理解公式4，借鑒文章如何通俗直白地理解卡爾曼濾波演算法的講解。

假設，有兩台電子秤，分別進行測量一瓶水，得到的結果如圖所示。

由圖可知，電子秤不是絕對精准的，存在一定誤差，不過當前觀測值分別是160和170，那麼如何融合兩個資料？ 最簡單的是 M = (A+B)/2 = 165。

求平均的設想裡，有一個重要前提是，認為A和B的貢獻是一樣的，重要程度是一樣的，因此各占50%的權重。

如果，A的精度更高，B精度差一些，即A的方差小一些，B方差大。這時，平均就不合適了，應該讓精度高的觀測值的權重更高。

權重的計算，需要考慮誰更重要，即方差更小，所以可以通過方差的比較獲得權重分配。

A 測量結果 為 160 +- 3， B 測量結果 為 170 +- 9，可知A 的測量結果精度是 B 測量結果精度的 3倍。

這個公式是理解上述公式4的關鍵，通過將A提取出來，變為單獨一項，就可以很好的衡量，基於A，要如何變更，得到最優估計值。

這裡的變更加號的右邊，B-A乘以一個權重，這個權重就是卡爾曼濾波中的卡爾曼增益K。其中B就是目標檢測演算法輸出的dets，A是tracks。

而卡爾曼增益K的計算，需要依靠協方差矩陣P。

DeepSORT 小結

到此，總結一下卡爾曼濾波過程，當前幀跟蹤框的資訊由卡爾曼濾波器在更新階段輸出。

更新階段需要使用到：當前幀檢測框， 基於上一幀跟蹤框的預測值，並且加權得到。

其中，上一幀跟蹤框的預測值來自公式1。代碼中是： self.tracker.predict()。

有了基於上一幀跟蹤框的預測值，再輸入dets，就可以得到當前幀跟蹤框資訊，代碼中是： self.tracker.update(detections)。

在代碼中，卡爾曼濾波器維護mean和covariance，分別表示公式中的預測值x，協方差矩陣P。

self.mean, self.covariance = kf.predict(self.mean, self.covariance)  # mean即bbox的座標資料

self.mean, self.covariance = kf.update(self.mean, self.covariance, detection.to_xyah())

Copy

到這裡，deepsort原理有了大概的描述，更多細節仍需要到代碼中觀察，這裡做一個簡要回顧。

跟蹤框的輸出：

為了更穩定，採用了卡爾曼濾波演算法，將當前幀檢測框資訊，結合卡爾曼濾波對當前幀的預測，兩者共同作用，得到輸出。

目標的匹配：

為了讓檢測框找到對應的，合適的跟蹤框，把它轉化為二分圖最大匹配問題，可以用匈牙利演算法很好的求解。

同時，為了匹配更精准，減少身份交換，deepsort先進行新目標框的匹配（僅限前70級，級表示被跟蹤的次數），然後再進行基於IoU的匹配。

跟蹤框准入准出：

為了避免漏檢、誤檢等短暫的不穩定因素，設計了預備框和正式框的概念。經過3次考驗，可轉正，經過30次機會仍不靠譜（未檢測到），開除X籍。