MeanShift算法(二)之運動目標跟蹤

根據上篇文章，MeanShift算法(一)，了解了MeanShift算法的最基本理論。推導了如何利用核密度估計函數和密度梯度估計以及輪廓函數得到mean shift向量。可是有了這么一個理論總需要把它應用在某個領域里吧。那么現在就開始進入MeanShift運動目標跟蹤的世界。以前在別人的博客里看見有人說MeanShift算法現在已經不常用了，貌似被淘汰了，真假難辨？就算是真的，學習這一種算法那也能為以后理解其它算法打下一定基礎。在運動目標跟蹤領域，Kalman Filter, Particle Filter 和 MeanShift是我目前唯一知道的幾種方法了，如果有牛人知道其它更有效的方法，還望不吝賜教！！我想這個也因應用場景不同跟蹤效率和精確度等也不一樣吧。本文大多部分來自其他文章，起到一個總結作用。。。

再談MeanShift的應用：

MeanShift可以應用在很多領域，比如聚類，圖像平滑，圖像分割。尤其是應用在目標跟蹤領域，其跟蹤算法是通過計算候選目標與目標模板之間相似度的概率密度分布，然后利用概率密度梯度下降的方向來獲取匹配搜索的最佳路徑，加速運動目標的定位和降低搜索的時間，因此在目標實時跟蹤領域有著很高的應用價值。該算法由于采用了統計特征，因此對噪聲有很強的魯棒性；由于是一個單參數算法，容易作為一個模塊和別的算法集成；采用核函數直方圖建模，對邊緣阻擋、目標的旋轉、變形以及背景運動都不敏感；同時該算法構造了一個可以用MeanShift算法進行尋優的相似度函數。由于MeanShift本質上是最陡下降法，因此其尋優過程收斂速度快，使得該算法具有很好的實時性。

均值漂移在目標跟蹤中的應用：

一：目標模型的描述

1）在起始幀，通過鼠標確定一個包含所有目標特征的橢圓，稱為被跟蹤目標的目標區域，這個區域也是核函數作用的區域，區域大小等于核函數的帶寬；

2）對目標區域進行描述，常用的方法是按照直方圖的方式將像素的值域分成k個區間。每個區間按照值域的大小對應一個特征值。然后求出圖像的像素值取每個特征值的概率；

3）對在初始幀圖像中目標區域內所有的像素點，計算每個特征值的概率，可稱為目標模型的描述。

目標區域的中心為x_{0，假設其中有n個像素用{xi}i=1…n表示。特征值得的個數為m個，則目標模型特征值為u=1...m，其概率密度估計為：}

加入高斯核函數后為：

在有些文獻文獻中，上式被寫為如下形式：

幾點說明：

1）特征值概率密度估計函數兩種寫法中本質都一樣，個人認為第二種寫法更好理解。因為b(x_i)是顏色灰度級的索引函數，與特征值u作比較，和u相等為1，否則為0；

2）k(x)為函數的輪廓函數。由于遮擋或者背景的影響，目標模型中心附近的像素比外物像素更可靠。k(x)給中心像素一個大的權值，而遠離中心的像素給一個小的權值；

3）C是一個標準化的常量系數，使得；

4）由此可以得到基于圖像灰度特征的顏色直方圖。

二：候選模型的描述(candidate model)

運動目標在第二幀及以后的每幀中可能包含目標的區域稱為候選區域，其中心坐標為y，也是核函數的中心坐標。該區域中的象素用{x_i}_{i=1…nh(h為下標)表示。對目標候選模型的特征u=1...m的概率密度表示為：}

其中為標準化常量。

三：相似性函數(similarity function)

模板區域：

候選區域：

相似性函數的定義：

根據Bhattacharyya系數：

相似性函數描述目標模型和候選模型之間的相似程度，在理想情況下兩個模型的概率分布是完全一樣的。其值在0到1之間，若值越大則兩個模型越相似。

四：目標定位

為使f(x)最大，將當前幀的目標中心先定位為前一幀中目標中的位置y_{0；從這一點開始尋找最優匹配的目標，其中心為y。可將f(x)展開為：}

由于第一項獨立于y之外且數值小于1，因此這里忽略不計。根據

，

第二項可以表示為：

，由此化為關于y的密度估計函數。

其中：。

_{類似于核函數密度估計，只是多了一個權值w，使得相關性函數的取值最大。令：}

_計算f_{n,K的mean shift向量，這樣就可以得到候選區域中y0移向真實區域y的向量：}

_{其中。值得注意的是，一般在一幀中找到目標的位置，需要MeanShift算法從開始若干次迭代才能得到。}

_{化簡：截個圖，下圖的意思是因為核函數都是徑向對稱函數，由于Epanechnikov核和高斯核的輪廓函數都是各向同性，所以可將y1化為：}

_{對上圖理解水平有限，還需思考。。。}

五：整個算法流程

1)在當前幀以y0為起點，計算候選目標的特征{p_u(y0)}u=1，2…..m；
2)計算候選目標與目標的相似度；
3)計算權值{w_i}i=1,2…..m;
4)利用MeanShift算法，計算目標新位置
；

5)若，則停止；否則y0←y1轉步驟2)。

限制條件：新目標中心需位于原目標中心附近。

_{六：MeanShift算法的優缺點}

優點：

1) 算法復雜度小；
2) 是無參數算法，易于與其它算法集成；
3) 采用加權直方圖建模，對目標小角度旋轉、輕微變形和部分遮擋不敏感等。

缺點：

1) 搜索窗的核函數帶寬保持不變；
2) 缺乏必要的模板更新算法；
3) 目標的運動不能過快；

4) 當顏色區域為均勻的時候，對h來說相似性是不變的；