1.Meanshift介紹

Mean shift主要用在圖像平滑和圖像分割（那個跟蹤我現在還不清楚），先介紹一下平滑的原理：

 輸入是一個5維的空間，2維的（x，y）地理坐標，3維的（L，u，v）的顏色空間坐標，當然你原理也可以改寫成rgb色彩空間或者是紋理特征空間。

 先介紹一下核函數，有uniform的，也有高斯的核函數，不管是哪個的，其基本思想如下：簡單的平滑算法用一個模板平均一下，對所有的像素，利用周圍的像素平均一下就完事了，這個mean shift的是基于概率密度分布來的，而且是一種無參的取樣。有參的取樣就是假設所有的樣本服從一個有參數的概率分布函數，比如說泊松分布，正態分布等等，高中生都知道概率公式里面是有參數的，在說一下特征空間是一個5維的空間，距離用歐幾里德空間就可以了，至少代碼里就是這樣實現的，而本文的無參取樣是這樣的：在特征空間里有3維的窗口（想象一下2維空間的窗口），對于一個特征空間的點，對應一個5維的向量，可以計算該點的一個密度函數，如果是有參的直接帶入該點的坐標就可以求出概率密度了，基于窗函數的思想就是考慮它鄰近窗口里的點對它的貢獻， 它假設密度會往密集一點的地方轉移，算出移動之后的一個5維坐標，該坐標并會穩定，迭代了幾次之后，穩定的地方是modes。這樣每一個像素點都對應一個這么一個modes，用該點的后3維的值就是平滑的結果了，當然在算每個點的時候，有些地方可能重復計算了，有興趣的化你可以參考一下源代碼，確實是可以優化的。總結一下mean shift的平滑原理就是在特征空間中向密度更高的地方shift（轉移）。

 其次是怎么利用mean shift分割圖像.先對圖像進行平滑，第2步利用平滑結果建立區域鄰接矩陣或者區域鄰接鏈表，就是在特征空間比較近的二間在2維的圖像平面也比較接近的像素算成一個區域，這樣就對應一個區域的鄰接鏈表，記錄每個像素點的label值。當然代碼中有一個傳遞凸胞的計算，合并2個表面張力很接近的相鄰區域，這個我還沒想怎么明白，希望比較清楚的朋友講一講。最后還有一個合并面積較小的區域的操作，一個區域不是對應一個modes值嘛，在待合并的較小的那個區域中，尋找所有的鄰接區域，找到距離最小的那個區域，合并到那個區域就ok了。

2.Mean-Shift分割原理

Mean-Shift是一種非參數化的多模型分割方法，它的基本計算模塊采用的是傳統的模式識別程序，即通過分析圖像的特征空間和聚類的方法來達到分割的目的。它是通過直接估計特征空間概率密度函數的局部極大值來獲得未知類別的密度模式，并確定這個模式的位置，然后使之聚類到和這個模式有關的類別當中。下面對Mean-Shift算法進行簡介。設S是n維空間X中的一個有限集合，K表示X空間中λ球體的一個特征函數，則其表達式為：其中，x∈X，那么在向量x點處的樣本均值為：Fukunaga和Hostetle等人在其自己的論文中把m(x)-x的差叫做Mean-Shift。Mean-Shift算法實際上就是數據點到樣本均值的重復移動，而且在算法的每一次迭代過程中，對于所有的s∈S，s←m (s)都是同時的。同時，模糊聚類算法還包括最大墑聚類算法以及常用的k均值聚類算法，它們都是Mean-Shift算法的一個有限的特例。Mean-Shift算法作為一種聚類分析方法，由于其密度估計器的梯度是遞增的，而其收斂點即為密度梯度的局部極大值點，這個局部極大值即對應特征空間中的一個模式。Mean-Shift算法對于概率密度函數的估計通常采用Parzen窗函數法，即核密度估計器。在d維空間Rd中，給定n個數據點xi，i=1，2…n，點x的多變量核密度估計器的計算式如式(3)所示。這個估計量可以由核K(x)和一個對稱正定的d×d寬度的矩陣H來表示。一般情況下，具有d個變量的核K(x)是一個滿足以下條件的邊界函數：其中，ck是一個常量。從圖像分割的目的出發，多變量核K (x)采用的是放射狀對稱核Ks(x)=ak,dK1(‖x‖)，其中K1(z)是一個對稱的單變量核，且K (x)滿足下式：其中，ck,d是可使K (x)等于1的歸一化常量。帶寬矩陣H一般選擇對角陣，H=diag[h12，…，h2d]或與單位矩陣H=h2I成比例。H=h2I情況下的一個明顯優點是只需帶寬參數h>0。然而，從式(4)可以看出，首先應確定用于特征空間的歐幾里德矩陣的有效性。若使用一個寬度參數h，則式(3)就會變成如下典型的表示式：將(6)式代入上式，就可以得到一個通用的、用核符號表示的核密度估計式：對有基本密度函數f(x)的一個特征空間，Mean-Shift算法分析的第一步是找到這個密度模式，然后對這個模式進行相關聚類。此模式應該在梯度▽f(x)=0的零點當中，而Mean-Shift程序是不用估計密度，而直接對密度的梯度進行估計，就能定位這些零點。對于Mean-Shift算法的應用與分割，首先，可設xi和zi(i=1，2，…，n)分別為n維空間內的輸人和聯合的空值域內的濾波圖像的像素，Li為分割后的圖像中的第i個像素。那么，其操作可分為以下步驟：(1)運行均值平移濾波程序對圖像進行濾波，并存儲所有d維空間內在zi處的收斂點zi=yi，c。(2)在聯合域中對所有的zi進行分組以描述類，這些類{Cp}p=1…m在空域內較hs較近，在值域內較hr較近。    (3)對于每一個i=1，…，n，并記為：    Li={p|zi∈Cp|}(4)消除在空間區域內少于M個像素的區域。1.2 Mean-Shift方法的分割結果Mean-Shift算法分割的結果如圖1～圖3所示。其中圖1為背景較為簡單的火焰圖像的分割結果，圖2為有手電筒光干擾下的火焰圖像，圖3為有路燈燈光干擾下的火災圖像。三幅圖中的(a)均為原圖，(b)為分割后的結果。可以看出，在三種情況下，該算法都能夠有效的分割出火焰圖像，從而確定火焰區域，以達到目標識別的目的。