知識星球（點選上方公眾號，可快速關註）
來源：張醬油
https://www.cnblogs.com/necp-zwl/p/6486326.html
運動標的跟蹤主流演演算法大致分類
主要基於兩種思路：
-
a)不依賴於先驗知識，直接從影象序列中檢測到運動標的，併進行標的識別，最終跟蹤感興趣的運動標的；
-
b)依賴於標的的先驗知識，首先為運動標的建模，然後在影象序列中實時找到相匹配的運動標的。
一．運動標的檢測
對於不依賴先驗知識的標的跟蹤來講，運動檢測是實現跟蹤的第一步。運動檢測即為從序列影象中將變化區域從背景影象中提取出來。運動標的檢測的演演算法依照標的與攝像機之間的關係可以分為靜態背景下運動檢測和動態背景下運動檢測。
（一）靜態背景
1.背景差
2.幀差
3.GMM
4.光流
背景減演演算法可以對背景的光照變化、噪聲幹擾以及週期性運動等進行建模，在各種不同情況下它都可以準確地檢測出運動標的。因此對於固定攝像頭的情形，目前大多數的跟蹤演演算法中都採用背景減演演算法來進行標的檢測。背景減演演算法的侷限性在於它需要一個靜態的固定攝像頭。
（二）運動場
通常情況下，攝像機的運動形式可以分為兩種：a)攝像機的支架固定，但攝像機可以偏轉、俯仰以及縮放; b)將攝像機裝在某個移動的載體上。由於以上兩種情況下的背景及前景影象都在做全域性運動，要準確檢測運動標的的首要任務是進行影象的全域性運動估計與補償。
考慮到影象幀上各點的全域性運動向量雖不盡相同 (攝像機做平移運動除外 )，但它們均是在同一攝像機模型下的運動，因而應遵循相同的運動模型，可以用同一模型引數來表示。
全域性運動的估計問題就被歸結為全域性運動模型引數的估計問題，通常使用塊匹配法或光流估計法來進行運動引數的估計。
塊匹配
基於塊的運動估算和補償可算是最通用的演演算法。可以將影象分割成不同的影象塊，假定同一影象小塊上的運動向量是相同的，透過畫素域搜尋得到最佳的運動向量估算。塊匹配法主要有如下三個關鍵技術：
-
a)匹配法則，如最大相關、最小誤差等
-
b)搜尋方法，如三步搜尋法、交叉搜尋法等。
-
c) 塊大小的確定，如分級、自適應等。
光流法
光流估計的方法都是基於以下假設：影象灰度分佈的變化完全是標的或者場景的運動引起的，也就是說，標的與場景的灰度不隨時間變化。這使得光流方法抗噪聲能力較差，其應用範圍一般侷限於標的與場景的灰度保持不變這個假設條件下。另外，大多數的光流計算方法相當複雜，如果沒有特別的硬體裝置，其處理速度相當慢，達不到實時處理的要求。
二．標的跟蹤
運動標的的跟蹤，即透過標的的有效表達，在影象序列中尋找與標的模板最相似候選標的區位置的過程。簡單說，就是在序列影象中為標的定位。運動標的的有效表達除了對運動標的建模外，標的跟蹤中常用到的標的特性表達主要包括視覺特徵 (影象邊緣、輪廓、形狀、紋理、區域)、統計特徵 (直方圖、各種矩特徵)、變換繫數特徵 (傅裡葉描繪子、自回歸模型)、代數特徵 (影象矩陣的奇異值分解)等。除了使用單一特徵外，也可透過融合多個特徵來提高跟蹤的可靠性.
相似性度量演演算法
對運動標的進行特性提取之後，需要採用一定的相似性度量演演算法與幀影象進行匹配，從而實現標的跟蹤。影象處理與分析理論中，常見的相似性度量方法有歐氏距離、街區距離、棋盤距離、加權距離、巴特查理亞繫數、Hausdorff距離等，其中應用最多和最簡單的是歐氏距離。
搜尋演演算法
標的跟蹤過程中，直接對場景中的所有內容進行匹配計算，尋找最佳匹配位置，需要處理大量的冗餘資訊，這樣運算量比較大，而且沒有必要。採用一定的搜尋演演算法對未來時刻標的的位置狀態進行估計假設，縮小標的搜尋範圍便具有了非常重要的意義。其中一類比較常用的方法是預測運動體下一幀可能出現的位置，在其相關區域內尋找最優點。常見的預測演演算法有Kalman濾波、擴充套件的Kalman濾波及粒子濾波方法等。
Kalman濾波器是一個對動態系統的狀態序列進行線性最小方差估計的演演算法。它透過狀態方程和觀測方程來描述一個動態系統，基於系統以前的狀態序列對下一個狀態作最優估計，預測時具有無偏、穩定和最優的特點，且具有計算量小、可實時計算的特點，可以準確地預測標的的位置和速度，但其只適合於線性且呈高斯分佈的系統。相對於卡爾曼濾波演演算法，粒子濾波器特別適用於非線性、非高斯系統。粒子濾波演演算法是一種基於蒙特卡洛和貝葉斯估計理論的最優演演算法，它以遞迴的方式對測量資料進行序貫處理，因而無須對以前的測量資料進行儲存和再處理，節省了大量的儲存空間。在跟蹤多形式的標的以及在非線性運動和測量模型中，粒子濾波器具有極好的魯棒性。
另一類減小搜尋範圍的演演算法是最佳化搜尋方向。均值漂移演演算法 (Meanshift演演算法 )、連續自適應均值漂移演演算法 (Camshift演演算法 )和置信區域演演算法都是利用無參估計的方法最佳化標的模板和候選標的距離的迭代收斂過程，以達到縮小搜尋範圍的目的。Meanshift演演算法是利用梯度最佳化方法實現快速標的定位，能夠對非剛性標的實時跟蹤，適合於非線性運動標的的跟蹤，對標的的變形、旋轉等運動有較好的適用性。但是 Meanshift演演算法在標的跟蹤過程中沒有利用標的在空間中的運動方向和運動速度資訊，當周圍環境存在幹擾時 (如光線、遮擋 )，容易丟失標的。Camshift演演算法是在Meanshift演演算法的基礎上，進行了一定的擴充套件，結合標的色彩資訊形成的一種改進的均值漂移演演算法。由於標的影象的直方圖記錄的是顏色出現的機率，這種方法不受標的形狀變化的影響，可以有效地解決標的變形和部分遮擋的問題，且運算效率較高，但該演演算法在開始前需要由人工指定跟蹤標的。
標的跟蹤分類
依據運動標的的表達和相似性度量，運動標的跟蹤演演算法可以分為四類：基於主動輪廓的跟蹤、基於特徵的跟蹤、基於區域的跟蹤和基於模型的跟蹤。跟蹤演演算法的精度和魯棒性很大程度上取決於對運動標的的表達和相似性度量的定義，跟蹤演演算法的實時性取決於匹配搜尋策略和濾波預測演演算法。
1、基於主動輪廓的跟蹤
Kass等人提出的主動輪廓模型，即Snake模型，是在影象域內定義的可變形曲線，透過對其能量函式的最小化，動態輪廓逐步調整自身形狀與標的輪廓相一致，該可變形曲線又稱為Snake曲線。Snake技術可以處理任意形狀物體的任意形變，首先將分割得到的物體邊界作為跟蹤的初始模板然後確定表徵物體真實邊界的標的函式，並透過降低標的函式值，使初始輪廓逐漸向物體的真實邊界移動。
基於主動輪廓跟蹤的優點是不但考慮來自影象的灰度資訊，而且考慮整體輪廓的幾何資訊，增強了跟蹤的可靠性。由於跟蹤過程實際上是解的尋優過程，帶來的計算量比較大，而且由於 Snake模型的盲目性，對於快速運動的物體或者形變較大的情況，跟蹤效果不夠理想。
2、基於特徵的跟蹤
基於特徵匹配的跟蹤方法不考慮運動標的的整體特徵，只通過標的影象的一些顯著特徵來進行跟蹤。假定運動標的可以由惟一的特徵集合表達，搜尋到該相應的特徵集合就認為跟蹤上了運動標的。除了用單一的特徵來實現跟蹤外，還可以採用多個特徵資訊融合在一起作為跟蹤特徵。基於特徵的跟蹤主要包括特徵提取和特徵匹配兩個方面。
(1)特徵提取
特徵提取是指從景物的原始影象中提取影象的描繪特徵，理想的影象特徵應具備的特點是：
-
a)特徵應具有直觀意義，符合人們的視覺特性;
-
b)特徵應具備較好的分類能力，能夠區分不同的影象內容;
-
c)特徵計算應該相對簡單，以便於快速識別;
-
d)特徵應具備影象平移、旋轉、尺度變化等不變性。
標的跟蹤中常用的運動標的的特徵主要包括顏色、紋理、邊緣、塊特徵、光流特徵、周長、面積、質心、角點等。提取對尺度伸縮、形變和亮度變化不敏感的有效特徵至今仍是影象處理研究領域中一個比較活躍的方面。
(2)特徵匹配
特徵提取的目的是進行幀間標的特徵的匹配，並以最優匹配來跟蹤標的。常見的基於特徵匹配的跟蹤演演算法有基於二值化標的影象匹配的跟蹤、基於邊緣特徵匹配或角點特徵匹配的跟蹤、基於標的灰度特徵匹配的跟蹤、基於標的顏色特徵匹配的跟蹤等。
基於特徵的跟蹤演演算法的優點在於對運動標的的尺度、形變和亮度等變化不敏感，即使標的的某一部分被遮擋，只要還有一部分特徵可以被看到，就可以完成跟蹤任務；另外，這種方法與 Kalman濾波器聯合使用，也具有很好的跟蹤效果。但是其對於影象模糊、噪聲等比較敏感，影象特徵的提取效果也依賴於各種提取運算元及其引數的設定，此外，連續幀間的特徵對應關係也較難確定，尤其是當每一幀影象的特徵數目不一致、存在漏檢、特徵增加或減少等情況。
3、基於區域的跟蹤
基於區域的跟蹤演演算法基本思想是：
-
a)得到包含標的的模板，該模板可透過影象分割獲得或預先人為確定，模板通常為略大於標的的矩形，也可為不規則形狀;
-
b)在序列影象中，運用相關演演算法跟蹤標的。
這種演演算法的優點在於當標的未被遮擋時，跟蹤精度非常高、跟蹤非常穩定。但其缺點首先是費時，當搜尋區域較大時情況尤其嚴重;其次，演演算法要求標的變形不大，且不能有太大遮擋，否則相關精度下降會造成標的的丟失。近年來，對基於區域的跟蹤方法關註較多的是如何處理模板變化時的情況，這種變化是由運動標的姿態變化引起的，如果能正確預測標的的姿態變化，則可實現穩定跟蹤。
4、基於模型的跟蹤
基於模型的跟蹤是透過一定的先驗知識對所跟蹤標的建立模型，然後透過匹配跟蹤標的進行模型的實時更新。對於剛體標的來說，其運動狀態變換主要是平移、旋轉等，可以利用該方法實現標的跟蹤。但是實際應用中跟蹤的不僅僅是剛體，還有一大部分是非剛體，標的確切的幾何模型不容易得到。
這種方法不易受觀測視角的影響，具有較強的魯棒性，模型匹配跟蹤精度高，適合於機動標的的各種運動變化，抗幹擾能力強，但由於計算分析複雜、運算速度慢，模型的更新較為複雜，實時性較差。準確建立運動模型是模型匹配能否成功的關鍵
1.區域與區域匹配
這種演演算法的優點在於當標的未被遮擋時，跟蹤精度非常高，跟蹤非常穩定。但其缺點首先是費時，當搜尋區域較大時情況尤其嚴重；其次，演演算法要求標的變形不大，且不能有太大遮擋，否則相關精度下降會造成標的的丟失。
2.特徵點（關鍵點）跟蹤
KLT：Shi和Tomasi 在1994年提出的KLT 跟蹤演演算法是一種被廣泛應用的基於特徵點跟蹤演演算法。由於特徵點分佈在整個標的上，因此即使有一部分被遮擋，仍然可以跟蹤到另外一部分特徵點，這也是基於特徵點跟蹤演演算法的優點。
基於特徵點的跟蹤演演算法中，比較困難的問題是當標的發生旋轉或者被遮擋時，如何準確地完成特徵點的提取、儲存、刪除等工作
3.基於主動輪廓的跟蹤演演算法
主動輪廓模型也稱為Snake 模型，這種方法能較精確地跟蹤上標的的輪廓。Snake 模型非常適合可變形標的的跟蹤，如對運動細胞的跟蹤。這種模型與卡爾曼濾波相結合能夠更好地進行跟蹤。Snake模型比較適合單標的的跟蹤，對於多標的跟蹤更多地是採用基於水平集(Level Set)方法的主動輪廓模型
4.光流
Lucas-Kanade稀疏光流calcOpticalFlowPyrLK（利用金字塔）
Horn-Schunck稠密光流calcOpticalFlowHS
稠密光流需要很大的計算量，OpenCV中對此方法做了簡化，即對前後連續幀的一個畫素的鄰域進行匹配，這種方法叫塊匹配。
稀疏光流需要在跟蹤之前指定一組點，如果這些點具有某些明顯特徵，那麼跟蹤就會相對穩定和可靠。可見，其運算量比稠密光流要小很多。
首先利用goodFeaturesToTrack函式得到影象中的強邊界作為跟蹤的特徵點，接下來要呼叫calcOpticalFlowPyrLK函式，輸入兩幅連續的影象，併在第一幅影象裡選擇一組特徵點，輸出為這組點在下一幅影象中的位置。再把得到的跟蹤結果過濾一下，去掉不好的特徵點。再把特徵點的跟蹤路徑標示出來。
（實際效果一般）
5.mean-shift和 camshift
Mean-shift優缺點
meanShift演演算法用於影片標的跟蹤時，採用標的的顏色直方圖作為搜尋特徵，透過不斷迭代meanShift向量使得演演算法收斂於標的的真實位置，從而達到跟蹤的目的。
傳統的meanShift演演算法在跟蹤中有幾個優勢：
-
（1）演演算法計算量不大，在標的區域已知的情況下完全可以做到實時跟蹤；
-
（2）採用核函式直方圖模型，對邊緣遮擋、標的旋轉、變形和背景運動不敏感。
同時，meanShift演演算法也存在著以下一些缺點：
-
（1）缺乏必要的模板更新；
-
（2）跟蹤過程中由於視窗寬度大小保持不變，當標的尺度有所變化時，跟蹤就會失敗；
-
（3）當標的速度較快時，跟蹤效果不好；
-
（4）直方圖特徵在標的顏色特徵描述方面略顯匱乏，缺少空間資訊；
由於其計算速度快，對標的變形和遮擋有一定的魯棒性，所以，在標的跟蹤領域，meanShift演演算法目前依然受到大家的重視。但考慮到其缺點，在工程實際中也可以對其作出一些改進和調整；例如：
-
（1）引入一定的標的位置變化的預測機制，從而更進一步減少meanShift跟蹤的搜尋時間，降低計算量；
-
（2）可以採用一定的方式來增加用於標的匹配的“特徵”；
-
（3）將傳統meanShift演演算法中的核函式固定頻寬改為動態變化的頻寬；
-
（4）採用一定的方式對整體模板進行學習和更新；
CamShift演演算法
CamShift演演算法的全稱是”ContinuouslyAdaptive Mean-SHIFT”，即：連續自適應的MeanShift演演算法。其基本思想是對影片序列的所有影象幀都作MeanShift運算，並將上一幀的結果（即搜尋視窗的中心位置和視窗大小）作為下一幀MeanShift演演算法的搜尋視窗的初始值，如此迭代下去。簡單點說，meanShift是針對單張圖片尋找最優迭代結果，而camShift則是針對影片序列來處理，並對該序列中的每一幀圖片都呼叫meanShift來尋找最優迭代結果。正是由於camShift針對一個影片序列進行處理，從而保證其可以不斷調整視窗的大小，如此一來，當標的的大小發生變化的時候，該演演算法就可以自適應地調整標的區域繼續跟蹤。
在OpenCV自帶的camShift的例子當中，是透過計算標的在HSV空間下的H分量直方圖，透過直方圖反向投影得到標的畫素的機率分佈，然後透過呼叫OpenCV的CAMSHIFT演演算法，自動跟蹤並調整標的視窗的中心位置與大小。該演演算法對於簡單背景下的單標的跟蹤效果較好，但如果被跟蹤標的與背景顏色或周圍其它標的顏色比較接近，則跟蹤效果較差。另外，由於採用顏色特徵，所以它對被跟蹤標的的形狀變化有一定的抵抗能力。
OpenCV自帶例子中的camShift演演算法，可以分為三個部分：
A、計算色彩投影圖（反向投影）：
-
（1）為了減少光照變化對標的跟蹤的影響，首先將影象從RGB顏色空間轉換到HSV顏色空間；
-
（2）對H分量進行直方圖統計，直方圖代表了不同H分量取值出現的機率，或者說可以據此查找出H分量的大小為x時的機率或畫素個數，即，得到顏色機率查詢表；
-
（3）將影象中每個畫素的值用其顏色出現的機率進行替換，由此得到顏色機率分佈圖；
以上三個步驟稱之為反向投影，需要提醒的是，顏色機率分佈圖是一個灰度影象；
B、meanShift尋優
前面提到過meanShift演演算法（http://blog.csdn.net/carson2005/article/details/7337432）是一種非引數機率密度估計方法，它透過不斷迭代計算得到最優搜尋視窗的位置和大小。
C、camShift跟蹤演演算法
前面提到，camShift其實就是在影片序列的每一幀當中都運用meanShift，並將上一幀的meanShift結果作為下一幀的初始值，如此不斷迴圈迭代，就可以實現標的的跟蹤了。
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：
http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
