一  什麼是視覺目標跟蹤

視覺目標跟蹤的定義

在計算機視覺領域中並沒有對視覺目標跟蹤（簡稱跟蹤，下同）的唯一定義。通常來說，跟蹤的目標是視頻幀或圖像中的某個區域或物體，不需要其語義信息（類別等），此概念被形象地描述爲“萬物跟蹤”。同時，也存在一些特例，通常被應用在一些特定場景中對已知類型物體的跟蹤，例如工廠流水線監控中對某些特定產品的跟蹤（如零部件等）。

很多學者對跟蹤有着不同的闡釋，包括：“跟蹤是視頻序列中識別感興趣區域 (region of interest) 的過程”[1]，或者“給定目標在視頻中某一幀的狀態（位置、尺寸等），跟蹤是估計 (estimate) 該目標在後續幀中的狀態”[2]等。這些定義看似大相徑庭，但其實有很多共同點。通過提取這些共同點，我們將跟蹤問題定義爲：

跟蹤是在一個視頻的後續幀中找到在當前幀中定義的感興趣物體 (object of interest) 的過程。

可以發現，上述定義主要關注跟蹤的三方面問題，即“找到”、“感興趣物體”、和“後續幀”。注意，這裏的當前幀可以是視頻中的任意一幀。通常來說，跟蹤是從視頻的第二幀開始的，第一幀用來標記目標的初始位置 (ground truth)。下面，我們利用博爾特參加男子百米短跑的例子來解釋這三方面問題。

圖1. 博爾特參加男子百米短跑的視頻截圖[3]

視覺目標跟蹤的基本原理

“找到”：如何locate博爾特？

假設在視頻上一幀我們找到了博爾特所在的位置，我們要做的是在當前幀中繼續找到博爾特所在的位置。如前所述，視覺是跟蹤問題（視覺目標跟蹤）的限定條件，其帶來了可以利用的性質。在這裏，我們可以利用的de facto rules是：在同一段視頻中，相同的物體在前後兩幀中的尺寸和空間位置不會發生巨大的變化[4]。比如我們可以做出如下判斷：博爾特在當前幀中的空間位置大概率會在跑道中，而幾乎不可能在旁邊的草坪內。也就是說，如果我們想知道博爾特在當前幀中的空間位置，我們只需要在跑道中生成一些候選位置，然後在其中進行尋找即可。上述過程引出了跟蹤中一個重要的子問題，即candidate generation，通常被表述爲候選框生成。

“感興趣物體”：如何shape博爾特？

博爾特就是圖像中個子最高，並且穿着黃色和綠色比賽服的人。但是，我們忽略了一個問題，就是我們對於博爾特的“定義”其實已經包含了很多高度抽象的信息，例如個子最高，還有黃色和綠色的比賽服。在計算機視覺領域中，我們通常將這些高度抽象的信息稱之爲特徵。對於計算機而言，如果沒有特徵，博爾特和草坪、跑道、或者圖像中其他對於人類有意義的物體沒有任何區別。因此，想讓計算機對博爾特進行跟蹤，特徵表達/提取 (feature representation/extraction) 是非常重要的一環，也是跟蹤中第二個重要的子問題。

“後續幀”：如何distinguish博爾特 (from others) ？

在這裏，我們將“後續幀”關注的問題定義爲如何利用前一幀中的信息在當前幀中鑑別 (distinguish) 目標。我們不僅需要在“後續幀”中的每一幀都能完成對目標的跟蹤，還強調連續幀之間的上下文關係對於跟蹤的意義。直觀理解，該問題的答案非常簡單：在當前幀中找到最像上一幀中的跟蹤結果的物體即可。這就引出了跟蹤中第三個重要的子問題：決策 (decision making)。決策是跟蹤中最重要的一個子問題，也是絕大多數研究人員最爲關注的問題。通常來說，決策主要解決匹配問題，即將當前幀中可能是目標的物體和上一幀的跟蹤結果進行匹配，然後選擇相似度最大的物體作爲當前幀的跟蹤結果。

聯繫

在上述三個小節中我們分別介紹了跟蹤基本原理中的三個子問題：候選框生成、特徵表達/提取、及決策。需要注意的是，這三個子問題並非彼此獨立。有時候，決策問題的解決方案會包含更爲精確的候選框生成和/或更爲抽象的特徵提取，利用端到端 (end-to-end) 的思想解決跟蹤問題，來提高跟蹤系統和算法的性能。這在近幾年流行的基於深度學習的跟蹤算法中非常常見[1]。

視覺目標跟蹤的應用

從某種意義來說，在回答“視覺目標跟蹤有哪些應用”的問題之前，我們應該先討論學術研究方法論中“爲什麼”的問題，即“爲什麼要做視覺目標跟蹤”。

跟蹤在計算機視覺科學的經典應用領域，包括安防領域（車輛跟蹤、車牌識別等）、監控領域（人臉識別、步態識別等）、巡檢領域（無人機追蹤、機器人導航等）、以及新興的智慧生活（人機交互、VR/AR等）、智慧城市（流量監測等）、以及智慧工業（遠程醫療等）等。 跟蹤問題的主要應用可以總結爲：

跟蹤主要應用於對視頻或連續有語義關聯的圖像中任意目標的空間位置、形狀和尺寸的獲知。

作爲檢測算法的補充，其可以在視頻或連續有語義關聯的圖像中提供目標的空間位置，降低整個系統的複雜度（例如檢測僅應用於視頻第一幀識別出目標，以及後續幀中的某些幀來確定目標位置，然後在其餘幀中應用跟蹤確定目標位置）。

二  如何進行視覺目標跟蹤

視覺目標跟蹤的系統架構

候選框生成、特徵表達/提取、和決策構成了一條完整的邏輯鏈路。具體來說，對於視頻中的每一幀（通常不包括第一幀），跟蹤的系統流程可以用圖3中的架構來表示：

圖3. 視覺跟蹤系統架構[4, 有改動]

如圖所示，在跟蹤系統中，上一幀（含跟蹤結果，如圖中input frame）和當前幀會被作爲系統輸入，然後分別經過運動模型 (motion model)、特徵模型 (feature model)、和觀測模型 (observation model)，最終作爲當前幀對目標位置的預測 (final prediction) 輸出。其中，候選框生成、特徵表達/提取、和決策三個子問題分別在上述三個模型中被解決，其輸入與輸出的對應關係如表1。

表1. 視覺跟蹤系統架構中各模型的輸入與輸出

注意，圖3中的跟蹤系統架構應用了假設檢驗 (hypothesis testing) 模型。該模型是統計推斷中的常用方法，其基本原理是先對系統的特徵做出某種假設，然後通過研究抽樣的統計分佈，判斷應該接受還是拒絕此假設。該模型能夠很好地應用於跟蹤問題，即假設當前幀的某個候選框是預測目標，然後通過特徵表達/提取和決策，來判斷該候選框是否可以作爲當前幀目標位置的合理預測。

運動模型 — where?

1）目標表達形式

目標在當前幀中的大概位置是運動模型中主要被解決的問題，即候選框生成 (where)。在討論如何生成的問題之前，我們首先需要明確的是什麼是候選框。候選框是對於目標包圍盒 (bounding box) 的假設 (hypothesis)。此處的表達與特徵模型中的特徵表達有所區別，其關注的主要是如何在視頻幀或圖像中“描繪”目標。常見的表達形式如圖4所示。

圖 4. 視覺跟蹤目標常用表達方式[5]

如圖所示，目標可以被矩形框 (4c)、骨架 (4f)、或輪廓 (4h) 等不同形式所表達。其中，廣泛被計算機視覺研究中所採用的是如4(c)中的矩形框（即bounding box，一譯包圍盒）表達。這種表達形式的優點包括易生成（如最小外接矩形）、易表達（如左上角+右下角座標，或中心點座標+寬高）、易評估（如IOU (intersection over union)，一譯交併比）等。 詳 細的信 息 見[5]。

2）De facto rules：尺寸變化小，位置移動慢

在確定好目標的表達形式（候選框）後，接下來我們需要關注如何生成候選框。在很多學術文章中，深度學習訓練過程中的正負樣本生成有時也被稱作候選框生成。這種候選框生成和我們在該小節中討論的候選框生成是兩個概念。下面介紹兩種候選框生成分別是什麼，以及如何區分，避免混淆。

• 推理過程：即圖3中的系統流程，用於預測當前幀的目標位置，任何跟蹤算法都需要。在該過程中，運動模型生成候選框，然後經過特徵模型進行特徵表達/提取，將含有特徵的候選框輸入觀測模型進行決策（對目標位置的預測）。如視覺目標跟蹤的定義一節所述，de facto rules 是在同一段視頻中，相同的目標在前後兩幀中的尺寸和空間位置不會發生巨大的變化。基於此，我們可以大大減少候選框的數量和種類，即我們只需要在上一幀預測的目標位置附近生成和其尺寸近似的候選框，從而提高整個跟蹤系統的效率。

• 訓練過程：通常在基於判別式方法的跟蹤算法中需要，屬於跟蹤系統學習如何區分目標和非目標的過程，將在視覺目標跟蹤的算法分類一節中詳述。在該過程中，所謂的候選框生成應該被稱作“正負樣本生成”。在這裏，正樣本可以近似地理解爲目標，負樣本可以近似地理解爲非目標的干擾項，例如背景或其他像目標但不是目標的物體。爲了提高該類算法的跟蹤系統對於正負樣本的判別能力，在生成負樣本時通常會在整個圖像中尋找，而不僅限於上一幀預測的目標位置附近。

總結來說，候選框生成被應用在推理過程，用來生成當前幀目標的潛在位置；正負樣本生成被應用在基於判別式方法的跟蹤算法的訓練過程，用來生成正負樣本訓練跟蹤系統，使得系統習得區分目標與分目標的能力。

3）運動模型系統架構與分類

圖5示出了運動模型的系統架構以及如何得到候選框的方法分類。如圖所示，前一幀（第n幀）中預測目標的位置被輸入模型中，輸出當前幀（第n+1幀）的候選框。這些候選框可能有位置變化、尺度變化、和旋轉等，如圖中綠色和橙色虛線框所示。

圖 5. 運動模型系統架構與分類

在運動模型中，主要的候選框生成方法有如下三種：

a) 概率採樣 (probabilistic sampling)

通過仿射變換生成候選框。具體來說，假設輸入的上一幀預測目標的位置矩形框座標爲  、仿射變換的參數矩陣爲   、以及輸出的（一個）候選框的座標爲   ，則

其中，  中的參數包括候選框位置變換、尺度變換、旋轉變換、和長寬比變換等信息，仿射變換的示例如圖5所示。這裏，概率體現在上述參數都是符合某種概率分佈（通常是高斯分佈）的隨機變量，而採樣則體現在生成不同數量的候選框。

b) 滑窗 (sliding window)

如圖6所示，以某個形狀和大小的結構元素（形象地被稱之爲窗）在當前幀中按一定的空間間隔移動，每次移動後覆蓋的圖像中的相應像素即爲生成的候選框。通常來說，通過此種方法生成的候選框和前一幀的矩形框相比僅有位置變換，其他變化（如旋轉變換）需要進行額外的處理。

圖 6. 劃窗生成候選框示例

c) 循環移位 (circulant shift)

如圖7所示，如果我們將上一幀預測的目標位置的矩形框中的像素按照某種排列變成圖中base sample所示，那麼每次右移一個像素，即可生成一個候選框的對應排列。通過生成該排列的反變換，即可得到一個候選框。通常來說，通過此種方法生成的候選框和前一幀的矩形框相比僅有位置變換（如旋轉變換），其他變化需要進行額外的處理。值得強調的是，循環移位是滑窗的一個特例，但是其在基於相關濾波的跟蹤算法中與快速傅里葉變換 (fast Fourier transformation) 結合能夠極大地提高算法效率，使其無需再使用傳統的滑窗操作生成候選框，因此在此被單列出來。

圖 7. 循環移位生成候選框示例[6]

特徵模型 — how look like?

1）什麼是圖像特徵

對於人類來說，圖像特徵是對於圖像的直觀感受。對於計算機來說，圖像特徵是圖像內的一些區域/整個圖像和其他區域/其他圖像的差異。常用的圖像特徵包括顏色特徵、形狀特徵、空間特徵、紋理特徵、以及在深度學習中通過卷積神經網絡得到的深度特徵等。博爾特的黃色和綠色的比賽服即屬於顏色特徵，而個子高則結合了空間特徵和紋理特徵。通常來說，特徵越“深”（抽象且不直觀的的特徵，如深度特徵），對目標的判別能力越好；反之，特徵越“淺”（具體且直觀的特徵，如顏色等），對目標的空間位置信息保留越好。因此，特徵表達/提取通常需要在兩者之間做權衡，才能達到更好的跟蹤效果。

2）什麼是圖像特徵表達

瞭解什麼是圖像特徵之後，特徵表達/提取要解決的問題是如何來描述這些特徵，即用計算機能夠理解的語言來描述這些特徵的數學特性的一個或多個維度。常用的特徵表達/提取方法包括樸素方法（naive，如像素值）、統計方法（statistics，如直方圖）、和變換（transformation，如像素值的梯度）等。

特徵和特徵表達被統稱爲特徵模型。特徵模型可以對從運動模型中得到的候選框進行分析，得到相應的候選框特徵表達/提取，如圖8所示。

圖 8. 特徵模型 = 特徵 + 表達/提取

3）特徵模型的分類

圖9示出了如何得到對特徵進行表達/提取的方法分類。可以看到的是，在應用卷積神經網絡 (CNN) 得到深度特徵 (deep) 之前，手工的 (hand-crafted) 特徵表達/提取方法是跟蹤問題中對於圖像特徵進行處理的主流方法，其包括上述提到的各種特徵和表達方式。在諸多特徵和表達方式中，應用最多的是顏色特徵和梯度直方圖。顏色特徵比較容易理解，其不僅符合人類對於圖像的直觀理解，同時也是最簡單的計算機表徵圖像的方法，即像素值。梯度直方圖是關於梯度的直方圖，其中梯度是圖像像素值在某個特定空間方向上的變化，例如水平相鄰像素之間的像素值差；而直方圖是一種常用的數據分佈的圖像表示，可以直觀地表示出一組數據在其取值範圍內的數量變化。請各位同學參考[7]獲取更多關於圖像特徵的信息。目前，基於深度學習的方法逐漸成爲跟蹤問題研究的主流，其通過卷積神經網絡 (CNN) 得到的深度特徵 (deep) 極大地提高了跟蹤算法對目標的判別能力，所達到的性能也超過應用手工特徵的跟蹤算法。

圖 9. 特徵與特徵表達/提取方法的分類

觀測模型 — which?

1）如何做決策

在觀測模型中，如何在諸多候選框中選出一個作爲我們對目標位置在當前幀的預測是在觀測模型需要解決的主要問題，即做決策（“哪一個”）。直觀理解，我們只需要在當前幀的候選框中找出最“像”前一幀的預測目標的候選框就可以，然而最“像”並不是僅有一種定義。

通常來說，在計算機視覺領域中解決最“像”問題可以被歸類爲匹配問題，即在候選框中找到和前一幀目標最爲匹配的那個。匹配問題是整個跟蹤問題的核心，也是絕大多數跟蹤算法解決的主要的問題，其解決方案的效果直接影響整個跟蹤算法的性能。有時候，即使在候選框生成和特徵表達/提取方面做得不夠好，例如候選框的形狀和尺寸與實際有出入，或提取的特徵的判別程度不高，優秀的匹配算法也可以在一定程度上彌補前兩個模型中存在的不足，維持跟蹤算法的整體性能。

2）如何做匹配

前述中提到的最“像”或匹配問題在本質上是一個相似度度量 (similarity measurement) 問題。在解決相似度問題的時候，我們需要一個衡量機制，來計算兩個相比較的個體的相似度。在跟蹤問題中，被比較的個體通常是候選框和前一幀的預測結果（或者是ground truth），而衡量機制可以被抽象成距離 (distance)。這裏的距離不僅僅是空間距離，即框與框之間在圖像中相隔多少個像素，還包括兩個概率分佈的距離。

由於空間距離相對好理解，我們在這裏僅對概率分佈距離稍作解釋：每一幀的跟蹤結果是一個預測值，即每一個候選框是目標的概率。如果綜合所有候選框，就可以構成一個概率分佈。從概率分佈的角度理解匹配問題，跟蹤問題就轉換成在當前幀尋找和上一幀的候選框概率分佈“最接近”的一組候選框分佈，該“最接近”即是概率分佈距離。常用的空間距離有Minkowski distance（Manhattan distance和Euclidean distance是其特殊情況），常用的概率分佈距離有Kullback–Leibler (KL) 散度、Bhattacharyya distance、交叉熵、以及Wasserstein distance等。參考[8]。

3）觀測模型系統架構與分類

圖10示出了觀測模型的系統架構。如圖所示，前一幀（第n幀）中預測的目標位置、當前幀（第n+1幀）的候選框、和候選框的特徵被輸入模型，輸出當前幀（第n+1幀）的預測結果（目標位置）。這些候選框可能有位置變化、尺度變化、和旋轉等，如圖中綠色和橙色虛線框所示。

圖 10. 觀測模型系統架構

圖11示出了觀測模型的模塊拆解和分類。如圖所示，觀測模型的核心模塊是匹配 (match)。對於匹配方法的分類，業界的主流觀點是：生成式方法 (generative) 和判別式方法 (discriminative)[1, 2, 4, 9]。這兩種方法的主要區別在於是否有背景信息的引入。具體來說，生成式方法使用數學工具擬合目標的圖像域特徵，並在當前幀尋找擬合結果最佳（通常是擬合後重建誤差最小的）的候選框。而判別式方法則是不同的思路，其將目標視爲前景，將不包含目標的區域視爲背景，從而將匹配問題轉換成了將目標從背景中分離的問題。

對比起來，判別式方法具有更好的判別能力，即將目標和其他干擾項區分開的能力，這也是這一類匹配方法得名的由來。作爲上述觀點的論據支撐，應用判別式方法的跟蹤算法的性能已經大幅度超越應用生成式方法的跟蹤算法，成爲學術界研究的主流方向[9]。總結來說，生成式方法把跟蹤問題建模成擬合或多分類問題，而判別式方法把跟蹤問題定義爲二分類問題。

圖 11. 觀測模型的模塊拆解和分類

此外，在圖11中我們注意到還有兩個虛線框示出的模塊，分別代表特徵表達/提取 (feature representation/extraction) 和更新 (update)。在這裏，虛線表示這兩個步驟不是必須被執行的。對於有的算法而言，通過特徵模型得到的特徵會被進一步抽象，來獲取目標更深層次的特徵信息，然後再被送進匹配模塊執行匹配算法。同時，更新的步驟也非必須的，其存在的意義是獲得更爲準確的預測結果。

具體來說，匹配算法得到了一系列的參數，應用這些參數即可對當前幀的目標位置進行預測。如果在後續所有幀的預測過程中都應用這些參數，可能會出現的結果是預測趨向不準確，最終導致跟蹤的失敗。其可能的原因包括累積誤差、外因（如遮擋、光照變化）、以及內因（如目標外觀變化、快速運動）等。如果引入更新模塊，在每若干幀之後根據之前的預測結果更新匹配算法的參數，則可以減小誤差，提高跟蹤的準確性。

視覺目標跟蹤的算法分類

跟蹤算法根據其觀測模型被分爲兩大類：生成式方法 (generative) 和判別式方法 (discriminative)。值得注意的是，在這裏我們強調分類的依據是觀測模型，是爲了將整個跟蹤系統架構中的不同模型解耦合。具體來說，即使兩個算法分別應用了生成式方法和判別式方法作爲相似度匹配的解決方案，其可能都應用了相同的特徵，例如顏色直方圖。如果我們將應用在跟蹤算法中的特徵作爲分類的依據，這兩個算法應該被歸爲一類。很顯然，這是另一種算法分類的角度，但是卻存在將兩個大相徑庭的算法歸爲一類的可能性。

在這裏，我們並非否認按照特徵分類的合理性，而是將關注的重點放在算法本質上的區別，即其觀測模型。然而，大多數跟蹤算法的綜述文章都直接將跟蹤算法簡單的分爲生成式和判別式，並沒有強調這僅僅是其觀測模型，讓人產生爲什麼應用了相同特徵的算法會被歸爲不同的類別的疑問。這種不明確對於剛開始接觸跟蹤領域的同學是不友好的。

在明確了我們分類的前提之後，圖12示出了我們對於跟蹤算法的分類以及各分類下的一些經典算法。值得注意的是，在這裏我們僅將分類細化到第二層，即將生成式和判別式做進一步分類。根據不同算法的具體細節，圖中的分類可以繼續深化，但是這有別於此文的宗旨，即對跟蹤問題的系統性的概括。

圖 12. 跟蹤算法根據觀測模型的分類和舉例

關於生成式方法，其核心思想即衡量前一幀的預測目標與當前幀候選框的相似度，然後選擇最爲相似的候選框作爲當前幀的跟蹤結果（即預測目標在當前幀的位置）。生成式方法被進一步分成下述三類：

1）空間距離 (spatial distance)

即用空間距離衡量相似度的解決方案，通常利用最優化理論將跟蹤問題轉換成空間距離最小化問題。利用此方法的經典算法包括IVT (Incremental learning Visual Tracking) [10] 和ASLA(Adaptive Structural Local sparse Appearance model tracking) [11]。其算法的核心思想是：計算當前幀候選框的像素灰度值與上一幀預測目標的像素灰度值之間的Euclidean distance，然後取距離最小的候選框作爲當前幀的預測目標。在特徵提取時應用了奇異值分解等技術來減小計算複雜度。

2）概率分佈距離 (probabilistic distribution distance)

即用概率分佈距離衡量相似度的解決方案，通常利用最優化理論將跟蹤問題轉換成概率分佈距離最小化問題。利用此方法的經典算法包括CBP (Color-Based Probabilistic) [12]和FRAG (robust FRAGments-based) [13]。其算法的核心思想是：計算當前幀候選框的顏色直方圖分佈與上一幀預測目標的顏色直方圖分佈之間的Bhattacharyya distance，然後取距離最小的候選框作爲當前幀的預測目標。

3）綜合 (combinatorial)

這部分解決方案以MeanShift[14]和CamShift算法爲代表，其模糊了對於相似度匹配的距離衡量，甚至沒有顯式地候選框生成過程，而是借鑑了機器學習中meanshift聚類算法的思想，在每一幀中利用上一幀預測目標的顏色直方圖分佈，計算該幀中相應位置的像素的顏色直方圖分佈，然後進行聚類得到其分佈的均值，其對應的像素位置是該幀中預測目標的中心位置，然後加上候選框寬高等信息即可得到當前幀預測目標的空間位置。在MeanShift算法中，寬高信息是固定的，因此其無法應對目標尺度和旋轉變化，而CamShift通過將圖像矩引入相似度匹配[7]，得到目標尺度和旋轉信息，進一步提高了算法的性能。

如前所述，判別式方法側重於將目標視作前景，然後將其從其它被視作背景的內容中分離出來。從某種程度上來說，判別式方法應用了分類算法的思想，將跟蹤問題轉換成二分類問題。衆所周知，基於經典機器學習（即不包含深度學習的機器學習）和深度學習的算法對於分類問題有着非常出色的表現，因此，這些算法的思想被引入跟蹤問題的解決方案是非常自然的事情。此外，判別式方法的本質仍然是解決匹配問題，而一種解決匹配問題非常有效的方法就是相關 (correlation)，即用一個模板與輸入進行相關操作，通過得到的響應（輸出）來判斷該輸入與模板的相似程度，即相關性。因此，基於相關操作的算法也同樣被引入跟蹤問題的解決方案。判別式方法被進一步分成下述三類：

1）經典機器學習方法 (machine learning)

應用機器學習算法的思想將目標作爲前景從背景中提取出來的方法。利用此方法的經典算法包括STRUCK (STRUCtured output tracking with Kernels) [15]和Tracking-Learning-Detection (TLD) [16]。STRUCK和 TLD算法分別採用經典機器學習算法中的支持向量機 (support vector machine) 和集成學習 (ensemble learning) 進行分類，並採取了一系列優化方法來提高算法的性能。

2）相關濾波方法 (correlation filter)

應用相關操作計算候選框與預測目標匹配度的方法。

3）深度學習方法 (deep learning)

上述提到的應用深度學習算法的思想將目標作爲前景從背景中提取出來的方法。

更多優秀的跟蹤算法參見[1, 2, 4, 5, 9, 23]。我們將上述提到的算法總結在表2中，包括了被應用在這些算法中的運動模型、特徵模型、和觀測模型。表2體現了我們對整個跟蹤系統架構中的不同模型的解耦合。通過表2我們可以清晰地瞭解每個算法在不同模型中應用了哪些方法，這有助於我們從不同的角度對算法進行分類，提煉同類算法中的共同點，以及對不同類算法進行有效地區分和對比。

表2. 跟蹤算法總結

下圖展示了[17]對於跟蹤算法的總結：

圖 13. 跟蹤算法總結[24]

三  如何評估視覺目標跟蹤性能

評估指標

在前面兩章討論的內容中，我們已經在不經意間用到了一些評估跟蹤算法性能的指標，例如精度，速度等。在計算機視覺領域中，最常用的衡量指標是精確率 (precision) 、召回率 (recall)、以及F值 (F-score)、幀率 (FPS) 等。在此，我們簡單對前兩個指標進行介紹：這兩個指標源自於統計學，關注的是對正負樣本分類的情況。簡單來說，精確率被定義爲所有被預測成正樣本的樣本中真實的正樣本比率，而召回率被定義爲所有真實的正樣本中被預測成正樣本的樣本比率。

在跟蹤問題中，也有類似的定義。跟蹤系統和算法廣泛應用矩形框 (bounding box) 的原因之一就是易評估，其評估的核心就是交併比，即IOU (intersection over union)。IOU有如下定義：

較大的IOU值從一定程度上反應了兩個進行比較的矩形框貼合程度較高。如果我們用預測目標的矩形框和ground truth的矩形框計算IOU，我們就可以知道跟蹤算法的效果：IOU越大，表示跟蹤的效果越好。

VOT (visual object tracking) 競賽中從2013年開始舉辦，目前已經發展成評估跟蹤算法的主流標準，VOT中比較重要的兩個指標是accuracy和robustness。實際上，競賽中採用的第一指標是EAO，即expected accuracy overlap，是對accuracy的一種加權求和，其本質仍然是accuracy。Accuracy有如下定義：

即計算每一幀預測目標的矩形框與ground truth的矩形框之間的IOU，然後對所有幀求和再做平均。其中N是總幀數，可以是一段視頻的總幀數，也可以是多段視頻，或者多段視頻重複測試多次。Robustness有如下定義：

即跟蹤失敗的幀數與總幀數的比值，其中跟蹤失敗定義爲當前幀預測目標的矩形框與ground truth的矩形框的IOU爲0。

上述兩個指標從兩個方面體現了跟蹤算法的性能：accuracy體現了當跟蹤成功時，算法的精確度有多高，即找準目標的位置的概率，側重算法的精確性；robustness則體現了算法找到目標位置的概率，側重算法的魯棒性。有了這兩個指標，不同的算法就可以在同一套衡量標準下進行比較。

評估數據集

除了評估指標以外，另一個對於跟蹤算法評估非常重要的部分就是數據集。VOT競賽不僅提供了評估指標，其本身的數據集也是評估跟蹤算法的一個權威的數據集。除此之外，常用的評估數據集還包括OTB [2]、UAV123 [18]、以及GOT-10K [19] 等。不同的數據集對於評估指標有着不同的定義，但是其思想都和評估指標一節中提到的accuracy和robustness有着一定的共同點：即全面考慮算法的精確性和魯棒性。

除了不同的評估指標，不同的數據集之間通常也有共同點，同時也是衡量一個數據集是否適合作爲評估數據集的標準：視頻數量充足、目標類別豐富、以及標註信息準確。如果沒有充足的視頻和足夠豐富的目標類別，算法的性能很容易發生過擬合，即在少量的視頻和/或類別中表現很好，但是在其他視頻和/或類別中表現欠佳，因此無法準確地衡量出算法的真實性能。標註信息的準確性則不言而喻，它直接影響到評估的正確性。對於其他類型的數據集，例如作爲訓練算法使用的數據集，包括ImageNet [20]、COCO [21]等，如果能夠滿足上述條件，也可以拓展成爲評估數據集。

評估示例

我們以最新的2019年VOT 競賽 (VOT challenge 2019) 作爲跟蹤算法評估的示例。表3展示了競賽的節選結果 [9]。通用的競賽流程是：競賽組委會開放報名通道，參賽者可以通過該通道提交算法代碼，然後組委會統一收集代碼，再評估數據集上進行測試，最後將競賽結果以報告或白皮書的形式公佈。

表 3. VOT challenge 2019結果節選

表3中的體現了參賽算法在該年的評估數據集上取得的結果，包括了EAO、accuracy、和robustness等指標。通常，競賽結果是依據EAO進行排名的，不過結果中也會標註各單項指標的前三名，如表3中用圓圈標記的數字。

四  結語

目前，基於深度學習的算法逐漸成爲視覺目標跟蹤研究的主流。除了文中介紹的算法之外，無監督學習、元學習 (meta learning)、和其他人工智能領域的前沿算法也被引入視覺目標跟蹤的學術研究。此外，基於深度學習的視覺目標跟蹤算法也逐漸被應用在工業界，通過包括模型壓縮在內的優化方法有效地降低其算法複雜度，從而達到並超越目前適合於實際計算機視覺應用的跟蹤算法的性能。

參考

[1] Fiaz, Mustansar, et al. "Handcrafted and deep trackers: Recent visual object tracking approaches and trends." ACM Computing Surveys (CSUR) 52.2 (2019): 1-44.

[2] Wu, Yi, Jongwoo Lim, and Ming-Hsuan Yang. "Object tracking benchmark." IEEE Transactions on Pattern Analysis and Machine Intelligence 37.9 (2015): 1834-1848.

[3] VOT2018 dataset, http://www.votchallenge.net/vot2018/dataset.html.

[4] Wang, Naiyan, et al. "Understanding and diagnosing visual tracking systems." Proceedings of the IEEE international conference on computer vision. 2015.

[5] Yilmaz, Alper, Omar Javed, and Mubarak Shah. "Object tracking: A survey." ACM computing surveys (CSUR) 38.4 (2006): 13-es.

[6] Henriques, João F., et al. "High-speed tracking with kernelized correlation filters." IEEE transactions on pattern analysis and machine intelligence 37.3 (2014): 583-596.

[7] Gonzalez, Rafael C., Richard E. Woods, and Steven L. Eddins. Digital image processing using MATLAB. Pearson Education India, 2004.

[8] Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT Press, 2016.

[9] Li, Xi, et al. "A survey of appearance models in visual object tracking." ACM transactions on Intelligent Systems and Technology (TIST) 4.4 (2013): 1-48.

[10] Ross, David A., et al. "Incremental learning for robust visual tracking." International journal of computer vision 77.1-3 (2008): 125-141.

[11] Jia, Xu, Huchuan Lu, and Ming-Hsuan Yang. "Visual tracking via adaptive structural local sparse appearance model." 2012 IEEE Conference on computer vision and pattern recognition. IEEE, 2012.

[12] Pérez, Patrick, et al. "Color-based probabilistic tracking." European Conference on Computer Vision. Springer, Berlin, Heidelberg, 2002.

[13] Adam, Amit, Ehud Rivlin, and Ilan Shimshoni. "Robust fragments-based tracking using the integral histogram." 2006 IEEE Computer society conference on computer vision and pattern recognition (CVPR'06). Vol. 1. IEEE, 2006.

[14] Comaniciu, Dorin, Visvanathan Ramesh, and Peter Meer. "Kernel-based object tracking." IEEE Transactions on pattern analysis and machine intelligence 25.5 (2003): 564-577.

[15] Hare, Sam, et al. "Struck: Structured output tracking with kernels." IEEE transactions on pattern analysis and machine intelligence 38.10 (2015): 2096-2109.

[16] Kalal, Zdenek, Krystian Mikolajczyk, and Jiri Matas. "Tracking-learning-detection." IEEE transactions on pattern analysis and machine intelligence 34.7 (2011): 1409-1422.

[17] https://github.com/foolwood/benchmark_results.

[18] Mueller, Matthias, Neil Smith, and Bernard Ghanem. "A benchmark and simulator for uav tracking." European conference on computer vision. Springer, Cham, 2016.

[19] Huang, Lianghua, Xin Zhao, and Kaiqi Huang. "Got-10k: A large high-diversity benchmark for generic object tracking in the wild." IEEE Transactions on Pattern Analysis and Machine Intelligence (2019).

[20] Russakovsky, Olga, et al. "Imagenet large scale visual recognition challenge." International journal of computer vision 115.3 (2015): 211-252.

[21] Lin, Tsung-Yi, et al. "Microsoft coco: Common objects in context." European conference on computer vision. Springer, Cham, 2014.

電子書下載

15分鐘開發AI視覺應用

如何實現人體屬性識別、人體計數、人臉搜索？ 如何快速識別公共場所誰沒有戴口罩？如何通過 智能檢測保證圖片的內容安全？ 本書帶你 零門檻搞定人臉識別、口罩識別、圖片內容安全應用，開放百餘種 AI 算法，讓你快速上手！

點 擊”閱讀原文“立即下載吧 ~

關注 機器智能

把握未來可能

戳我，下載電子書。