運動目標(biāo)跟蹤主流算法大致分類

運動目標(biāo)跟蹤主流算法大致分類

主要基于兩種思路：

• a)不依賴于先驗知識，直接從圖像序列中檢測到運動目標(biāo)，并進行目標(biāo)識別，最終跟蹤感興趣的運動目標(biāo)；

• b)依賴于目標(biāo)的先驗知識，首先為運動目標(biāo)建模，然后在圖像序列中實時找到相匹配的運動目標(biāo)。

一．運動目標(biāo)檢測

對于不依賴先驗知識的目標(biāo)跟蹤來講，運動檢測是實現(xiàn)跟蹤的第一步。運動檢測即為從序列圖像中將變化區(qū)域從背景圖像中提取出來。運動目標(biāo)檢測的算法依照目標(biāo)與攝像機之間的關(guān)系可以分為靜態(tài)背景下運動檢測和動態(tài)背景下運動檢測。

（一）靜態(tài)背景

1.背景差

2.幀差

3.GMM

4.光流

背景減算法可以對背景的光照變化、噪聲干擾以及周期性運動等進行建模，在各種不同情況下它都可以準(zhǔn)確地檢測出運動目標(biāo)。因此對于固定攝像頭的情形，目前大多數(shù)的跟蹤算法中都采用背景減算法來進行目標(biāo)檢測。背景減算法的局限性在于它需要一個靜態(tài)的固定攝像頭。

（二）運動場

通常情況下，攝像機的運動形式可以分為兩種：a)攝像機的支架固定，但攝像機可以偏轉(zhuǎn)、俯仰以及縮放;?b)將攝像機裝在某個移動的載體上。由于以上兩種情況下的背景及前景圖像都在做全局運動，要準(zhǔn)確檢測運動目標(biāo)的首要任務(wù)是進行圖像的全局運動估計與補償。

考慮到圖像幀上各點的全局運動矢量雖不盡相同?(攝像機做平移運動除外?)，但它們均是在同一攝像機模型下的運動，因而應(yīng)遵循相同的運動模型，可以用同一模型參數(shù)來表示。

全局運動的估計問題就被歸結(jié)為全局運動模型參數(shù)的估計問題，通常使用塊匹配法或光流估計法來進行運動參數(shù)的估計。

塊匹配

基于塊的運動估算和補償可算是最通用的算法?？梢詫D像分割成不同的圖像塊，假定同一圖像小塊上的運動矢量是相同的，通過像素域搜索得到最佳的運動矢量估算。塊匹配法主要有如下三個關(guān)鍵技術(shù)：

• a)匹配法則，如最大相關(guān)、最小誤差等

• b)搜索方法，如三步搜索法、交叉搜索法等。

• c)?塊大小的確定，如分級、自適應(yīng)等。

光流法

光流估計的方法都是基于以下假設(shè)：圖像灰度分布的變化完全是目標(biāo)或者場景的運動引起的，也就是說，目標(biāo)與場景的灰度不隨時間變化。這使得光流方法抗噪聲能力較差，其應(yīng)用范圍一般局限于目標(biāo)與場景的灰度保持不變這個假設(shè)條件下。另外，大多數(shù)的光流計算方法相當(dāng)復(fù)雜，如果沒有特別的硬件裝置，其處理速度相當(dāng)慢，達不到實時處理的要求。

二．目標(biāo)跟蹤

運動目標(biāo)的跟蹤，即通過目標(biāo)的有效表達，在圖像序列中尋找與目標(biāo)模板最相似候選目標(biāo)區(qū)位置的過程。簡單說，就是在序列圖像中為目標(biāo)定位。運動目標(biāo)的有效表達除了對運動目標(biāo)建模外，目標(biāo)跟蹤中常用到的目標(biāo)特性表達主要包括視覺特征?(圖像邊緣、輪廓、形狀、紋理、區(qū)域)、統(tǒng)計特征?(直方圖、各種矩特征)、變換系數(shù)特征?(傅里葉描繪子、自回歸模型)、代數(shù)特征?(圖像矩陣的奇異值分解)等。除了使用單一特征外，也可通過融合多個特征來提高跟蹤的可靠性.

相似性度量算法?

對運動目標(biāo)進行特性提取之后，需要采用一定的相似性度量算法與幀圖像進行匹配，從而實現(xiàn)目標(biāo)跟蹤。圖像處理與分析理論中，常見的相似性度量方法有歐氏距離、街區(qū)距離、棋盤距離、加權(quán)距離、巴特查理亞系數(shù)、Hausdorff距離等，其中應(yīng)用最多和最簡單的是歐氏距離。

搜索算法?

目標(biāo)跟蹤過程中，直接對場景中的所有內(nèi)容進行匹配計算，尋找最佳匹配位置，需要處理大量的冗余信息，這樣運算量比較大，而且沒有必要。采用一定的搜索算法對未來時刻目標(biāo)的位置狀態(tài)進行估計假設(shè)，縮小目標(biāo)搜索范圍便具有了非常重要的意義。其中一類比較常用的方法是預(yù)測運動體下一幀可能出現(xiàn)的位置，在其相關(guān)區(qū)域內(nèi)尋找最優(yōu)點。常見的預(yù)測算法有Kalman濾波、擴展的Kalman濾波及粒子濾波方法等。

Kalman濾波器是一個對動態(tài)系統(tǒng)的狀態(tài)序列進行線性最小方差估計的算法。它通過狀態(tài)方程和觀測方程來描述一個動態(tài)系統(tǒng)，基于系統(tǒng)以前的狀態(tài)序列對下一個狀態(tài)作最優(yōu)估計，預(yù)測時具有無偏、穩(wěn)定和最優(yōu)的特點，且具有計算量小、可實時計算的特點，可以準(zhǔn)確地預(yù)測目標(biāo)的位置和速度，但其只適合于線性且呈高斯分布的系統(tǒng)。相對于卡爾曼濾波算法，粒子濾波器特別適用于非線性、非高斯系統(tǒng)。粒子濾波算法是一種基于蒙特卡洛和貝葉斯估計理論的最優(yōu)算法，它以遞歸的方式對測量數(shù)據(jù)進行序貫處理，因而無須對以前的測量數(shù)據(jù)進行存儲和再處理，節(jié)省了大量的存儲空間。在跟蹤多形式的目標(biāo)以及在非線性運動和測量模型中，粒子濾波器具有極好的魯棒性。

另一類減小搜索范圍的算法是優(yōu)化搜索方向。均值漂移算法?(Meanshift算法?)、連續(xù)自適應(yīng)均值漂移算法?(Camshift算法?)和置信區(qū)域算法都是利用無參估計的方法優(yōu)化目標(biāo)模板和候選目標(biāo)距離的迭代收斂過程，以達到縮小搜索范圍的目的。Meanshift算法是利用梯度優(yōu)化方法實現(xiàn)快速目標(biāo)定位，能夠?qū)Ψ莿傂阅繕?biāo)實時跟蹤，適合于非線性運動目標(biāo)的跟蹤，對目標(biāo)的變形、旋轉(zhuǎn)等運動有較好的適用性。但是?Meanshift算法在目標(biāo)跟蹤過程中沒有利用目標(biāo)在空間中的運動方向和運動速度信息，當(dāng)周圍環(huán)境存在干擾時?(如光線、遮擋?)，容易丟失目標(biāo)。Camshift算法是在Meanshift算法的基礎(chǔ)上，進行了一定的擴展，結(jié)合目標(biāo)色彩信息形成的一種改進的均值漂移算法。由于目標(biāo)圖像的直方圖記錄的是顏色出現(xiàn)的概率，這種方法不受目標(biāo)形狀變化的影響，可以有效地解決目標(biāo)變形和部分遮擋的問題，且運算效率較高，但該算法在開始前需要由人工指定跟蹤目標(biāo)。

目標(biāo)跟蹤分類?

依據(jù)運動目標(biāo)的表達和相似性度量，運動目標(biāo)跟蹤算法可以分為四類：基于主動輪廓的跟蹤、基于特征的跟蹤、基于區(qū)域的跟蹤和基于模型的跟蹤。跟蹤算法的精度和魯棒性很大程度上取決于對運動目標(biāo)的表達和相似性度量的定義，跟蹤算法的實時性取決于匹配搜索策略和濾波預(yù)測算法。

1、基于主動輪廓的跟蹤

Kass等人提出的主動輪廓模型，即Snake模型，是在圖像域內(nèi)定義的可變形曲線，通過對其能量函數(shù)的最小化，動態(tài)輪廓逐步調(diào)整自身形狀與目標(biāo)輪廓相一致，該可變形曲線又稱為Snake曲線。Snake技術(shù)可以處理任意形狀物體的任意形變，首先將分割得到的物體邊界作為跟蹤的初始模板然后確定表征物體真實邊界的目標(biāo)函數(shù)，并通過降低目標(biāo)函數(shù)值，使初始輪廓逐漸向物體的真實邊界移動。
基于主動輪廓跟蹤的優(yōu)點是不但考慮來自圖像的灰度信息，而且考慮整體輪廓的幾何信息，增強了跟蹤的可靠性。由于跟蹤過程實際上是解的尋優(yōu)過程，帶來的計算量比較大，而且由于?Snake模型的盲目性，對于快速運動的物體或者形變較大的情況，跟蹤效果不夠理想。

2、基于特征的跟蹤

基于特征匹配的跟蹤方法不考慮運動目標(biāo)的整體特征，只通過目標(biāo)圖像的一些顯著特征來進行跟蹤。假定運動目標(biāo)可以由惟一的特征集合表達，搜索到該相應(yīng)的特征集合就認為跟蹤上了運動目標(biāo)。除了用單一的特征來實現(xiàn)跟蹤外，還可以采用多個特征信息融合在一起作為跟蹤特征。基于特征的跟蹤主要包括特征提取和特征匹配兩個方面。

(1)特征提取

特征提取是指從景物的原始圖像中提取圖像的描繪特征，理想的圖像特征應(yīng)具備的特點是：

• a)特征應(yīng)具有直觀意義，符合人們的視覺特性;

• b)特征應(yīng)具備較好的分類能力，能夠區(qū)分不同的圖像內(nèi)容;

• c)特征計算應(yīng)該相對簡單，以便于快速識別;

• d)特征應(yīng)具備圖像平移、旋轉(zhuǎn)、尺度變化等不變性。

目標(biāo)跟蹤中常用的運動目標(biāo)的特征主要包括顏色、紋理、邊緣、塊特征、光流特征、周長、面積、質(zhì)心、角點等。提取對尺度伸縮、形變和亮度變化不敏感的有效特征至今仍是圖像處理研究領(lǐng)域中一個比較活躍的方面。

(2)特征匹配

特征提取的目的是進行幀間目標(biāo)特征的匹配，并以最優(yōu)匹配來跟蹤目標(biāo)。常見的基于特征匹配的跟蹤算法有基于二值化目標(biāo)圖像匹配的跟蹤、基于邊緣特征匹配或角點特征匹配的跟蹤、基于目標(biāo)灰度特征匹配的跟蹤、基于目標(biāo)顏色特征匹配的跟蹤等。

基于特征的跟蹤算法的優(yōu)點在于對運動目標(biāo)的尺度、形變和亮度等變化不敏感，即使目標(biāo)的某一部分被遮擋，只要還有一部分特征可以被看到，就可以完成跟蹤任務(wù)；另外，這種方法與?Kalman濾波器聯(lián)合使用，也具有很好的跟蹤效果。但是其對于圖像模糊、噪聲等比較敏感，圖像特征的提取效果也依賴于各種提取算子及其參數(shù)的設(shè)置，此外，連續(xù)幀間的特征對應(yīng)關(guān)系也較難確定，尤其是當(dāng)每一幀圖像的特征數(shù)目不一致、存在漏檢、特征增加或減少等情況。

3、基于區(qū)域的跟蹤

基于區(qū)域的跟蹤算法基本思想是：

• a)得到包含目標(biāo)的模板，該模板可通過圖像分割獲得或預(yù)先人為確定，模板通常為略大于目標(biāo)的矩形，也可為不規(guī)則形狀;

• b)在序列圖像中，運用相關(guān)算法跟蹤目標(biāo)。

這種算法的優(yōu)點在于當(dāng)目標(biāo)未被遮擋時，跟蹤精度非常高、跟蹤非常穩(wěn)定。但其缺點首先是費時，當(dāng)搜索區(qū)域較大時情況尤其嚴(yán)重;其次，算法要求目標(biāo)變形不大，且不能有太大遮擋，否則相關(guān)精度下降會造成目標(biāo)的丟失。近年來，對基于區(qū)域的跟蹤方法關(guān)注較多的是如何處理模板變化時的情況，這種變化是由運動目標(biāo)姿態(tài)變化引起的，如果能正確預(yù)測目標(biāo)的姿態(tài)變化，則可實現(xiàn)穩(wěn)定跟蹤。

4、基于模型的跟蹤

基于模型的跟蹤是通過一定的先驗知識對所跟蹤目標(biāo)建立模型，然后通過匹配跟蹤目標(biāo)進行模型的實時更新。對于剛體目標(biāo)來說，其運動狀態(tài)變換主要是平移、旋轉(zhuǎn)等，可以利用該方法實現(xiàn)目標(biāo)跟蹤。但是實際應(yīng)用中跟蹤的不僅僅是剛體，還有一大部分是非剛體，目標(biāo)確切的幾何模型不容易得到。

這種方法不易受觀測視角的影響，具有較強的魯棒性，模型匹配跟蹤精度高，適合于機動目標(biāo)的各種運動變化，抗干擾能力強，但由于計算分析復(fù)雜、運算速度慢，模型的更新較為復(fù)雜，實時性較差。準(zhǔn)確建立運動模型是模型匹配能否成功的關(guān)鍵

1.區(qū)域與區(qū)域匹配

這種算法的優(yōu)點在于當(dāng)目標(biāo)未被遮擋時，跟蹤精度非常高，跟蹤非常穩(wěn)定。但其缺點首先是費時，當(dāng)搜索區(qū)域較大時情況尤其嚴(yán)重；其次，算法要求目標(biāo)變形不大，且不能有太大遮擋，否則相關(guān)精度下降會造成目標(biāo)的丟失。

2.特征點（關(guān)鍵點）跟蹤

KLT：Shi和Tomasi 在1994年提出的KLT 跟蹤算法是一種被廣泛應(yīng)用的基于特征點跟蹤算法。由于特征點分布在整個目標(biāo)上，因此即使有一部分被遮擋，仍然可以跟蹤到另外一部分特征點，這也是基于特征點跟蹤算法的優(yōu)點。

基于特征點的跟蹤算法中，比較困難的問題是當(dāng)目標(biāo)發(fā)生旋轉(zhuǎn)或者被遮擋時，如何準(zhǔn)確地完成特征點的提取、保存、刪除等工作

3.基于主動輪廓的跟蹤算法

主動輪廓模型也稱為Snake 模型，這種方法能較精確地跟蹤上目標(biāo)的輪廓。Snake 模型非常適合可變形目標(biāo)的跟蹤，如對運動細胞的跟蹤。這種模型與卡爾曼濾波相結(jié)合能夠更好地進行跟蹤。Snake模型比較適合單目標(biāo)的跟蹤，對于多目標(biāo)跟蹤更多地是采用基于水平集(Level Set)方法的主動輪廓模型

4.光流

Lucas-Kanade稀疏光流calcOpticalFlowPyrLK（利用金字塔）

Horn-Schunck稠密光流calcOpticalFlowHS

稠密光流需要很大的計算量，OpenCV中對此方法做了簡化，即對前后連續(xù)幀的一個像素的鄰域進行匹配，這種方法叫塊匹配。

稀疏光流需要在跟蹤之前指定一組點，如果這些點具有某些明顯特征，那么跟蹤就會相對穩(wěn)定和可靠?？梢?，其運算量比稠密光流要小很多。

首先利用goodFeaturesToTrack函數(shù)得到圖像中的強邊界作為跟蹤的特征點，接下來要調(diào)用calcOpticalFlowPyrLK函數(shù)，輸入兩幅連續(xù)的圖像，并在第一幅圖像里選擇一組特征點，輸出為這組點在下一幅圖像中的位置。再把得到的跟蹤結(jié)果過濾一下，去掉不好的特征點。再把特征點的跟蹤路徑標(biāo)示出來。

（實際效果一般）

5.mean-shift和 camshift

Mean-shift優(yōu)缺點

meanShift算法用于視頻目標(biāo)跟蹤時，采用目標(biāo)的顏色直方圖作為搜索特征，通過不斷迭代meanShift向量使得算法收斂于目標(biāo)的真實位置，從而達到跟蹤的目的。

傳統(tǒng)的meanShift算法在跟蹤中有幾個優(yōu)勢：

• （1）算法計算量不大，在目標(biāo)區(qū)域已知的情況下完全可以做到實時跟蹤；

• （2）采用核函數(shù)直方圖模型，對邊緣遮擋、目標(biāo)旋轉(zhuǎn)、變形和背景運動不敏感。

同時，meanShift算法也存在著以下一些缺點：

• （1）缺乏必要的模板更新；

• （2）跟蹤過程中由于窗口寬度大小保持不變，當(dāng)目標(biāo)尺度有所變化時，跟蹤就會失??；

• （3）當(dāng)目標(biāo)速度較快時，跟蹤效果不好；

• （4）直方圖特征在目標(biāo)顏色特征描述方面略顯匱乏，缺少空間信息；

由于其計算速度快，對目標(biāo)變形和遮擋有一定的魯棒性，所以，在目標(biāo)跟蹤領(lǐng)域，meanShift算法目前依然受到大家的重視。但考慮到其缺點，在工程實際中也可以對其作出一些改進和調(diào)整；例如：

• （1）引入一定的目標(biāo)位置變化的預(yù)測機制，從而更進一步減少meanShift跟蹤的搜索時間，降低計算量；

• （2）可以采用一定的方式來增加用于目標(biāo)匹配的“特征”；

• （3）將傳統(tǒng)meanShift算法中的核函數(shù)固定帶寬改為動態(tài)變化的帶寬；

• （4）采用一定的方式對整體模板進行學(xué)習(xí)和更新；

CamShift算法

CamShift算法的全稱是”ContinuouslyAdaptive Mean-SHIFT”，即：連續(xù)自適應(yīng)的MeanShift算法。其基本思想是對視頻序列的所有圖像幀都作MeanShift運算，并將上一幀的結(jié)果（即搜索窗口的中心位置和窗口大?。┳鳛橄乱粠琈eanShift算法的搜索窗口的初始值，如此迭代下去。簡單點說，meanShift是針對單張圖片尋找最優(yōu)迭代結(jié)果，而camShift則是針對視頻序列來處理，并對該序列中的每一幀圖片都調(diào)用meanShift來尋找最優(yōu)迭代結(jié)果。正是由于camShift針對一個視頻序列進行處理，從而保證其可以不斷調(diào)整窗口的大小，如此一來，當(dāng)目標(biāo)的大小發(fā)生變化的時候，該算法就可以自適應(yīng)地調(diào)整目標(biāo)區(qū)域繼續(xù)跟蹤。

在OpenCV自帶的camShift的例子當(dāng)中，是通過計算目標(biāo)在HSV空間下的H分量直方圖，通過直方圖反向投影得到目標(biāo)像素的概率分布，然后通過調(diào)用OpenCV的CAMSHIFT算法，自動跟蹤并調(diào)整目標(biāo)窗口的中心位置與大小。該算法對于簡單背景下的單目標(biāo)跟蹤效果較好，但如果被跟蹤目標(biāo)與背景顏色或周圍其它目標(biāo)顏色比較接近，則跟蹤效果較差。另外，由于采用顏色特征，所以它對被跟蹤目標(biāo)的形狀變化有一定的抵抗能力。

OpenCV自帶例子中的camShift算法，可以分為三個部分：

A、計算色彩投影圖（反向投影）：

• （1）為了減少光照變化對目標(biāo)跟蹤的影響，首先將圖像從RGB顏色空間轉(zhuǎn)換到HSV顏色空間；

• （2）對H分量進行直方圖統(tǒng)計，直方圖代表了不同H分量取值出現(xiàn)的概率，或者說可以據(jù)此查找出H分量的大小為x時的概率或像素個數(shù)，即，得到顏色概率查找表；

• （3）將圖像中每個像素的值用其顏色出現(xiàn)的概率進行替換，由此得到顏色概率分布圖；

以上三個步驟稱之為反向投影，需要提醒的是，顏色概率分布圖是一個灰度圖像；

B、meanShift尋優(yōu)

前面提到過meanShift算法（http://blog.csdn.net/carson2005/article/details/7337432）是一種非參數(shù)概率密度估計方法，它通過不斷迭代計算得到最優(yōu)搜索窗口的位置和大小。

C、camShift跟蹤算法

前面提到，camShift其實就是在視頻序列的每一幀當(dāng)中都運用meanShift，并將上一幀的meanShift結(jié)果作為下一幀的初始值，如此不斷循環(huán)迭代，就可以實現(xiàn)目標(biāo)的跟蹤了。