1、Meanshift算法的概述及其應(yīng)用直觀描述直觀描述完全相同的桌球分布完全相同的桌球分布感興趣區(qū)域感興趣區(qū)域質(zhì)心質(zhì)心Mean Shift矢量矢量目的：找出最密集的區(qū)域Meanshift介紹 Meanshift算法是Fukunaga于1975年提出的。直到1995年， Yizong Cheng針對(duì)離x越近的采樣點(diǎn)對(duì)x周圍的統(tǒng)計(jì)特性越有效，定義了一族核函數(shù)。同時(shí)他認(rèn)為所有的樣本點(diǎn)重要性不同，設(shè)定了一個(gè)權(quán)重系數(shù)，擴(kuò)大了Meanshift的使用范圍。其思想概括起來(lái)就是：利用概率密度的梯度爬升來(lái)尋找局部最優(yōu)。輸入一個(gè)在圖像的范圍，然后Meanshift算法迭代（朝著重心迭代）直到滿足要求為止。 Mean

2、shift的基本形式為： 是一個(gè)半徑為h的高維球區(qū)域，k表示n個(gè)樣本點(diǎn)有k個(gè)落入Sh中。hihSxiMxxkx)(1)(hS4核函數(shù)說(shuō)明 對(duì)在d維歐式空間中，x表示該空間中的一個(gè)點(diǎn)，用一列向量x表示，K(x)表示該空間的核函數(shù)，其定義為： 這里：K(X) 稱核函數(shù)，k(x)為非增的分段連續(xù)剖面函數(shù)，標(biāo)準(zhǔn)化常量c,d,為正，且k(x)積分為1。2|)(|c)(xdkXK平均的偏移量會(huì)指向樣本點(diǎn)最密的方向，也就是概率密度函數(shù)梯度方向，引入核函數(shù)和權(quán)重系數(shù)后得到：nixixnxhM1)(1)(niixwxixhGnixixxwxixhGxhMi1)()(1)()()()(G(x)是一個(gè)單位核函數(shù)，H

3、是一個(gè)正定dxd的對(duì)稱矩陣，又稱帶寬矩陣。w(xi)是采樣點(diǎn)xi的權(quán)重)(2/ 1(2/ 1)(xixHGHxxhGi通常H取為正比于單位矩陣的對(duì)角陣即 ;h為核函數(shù)的帶寬,為一確定在系數(shù)，常用的單位核函數(shù)G（x）如下：分別是單位均勻核函數(shù)和單位高斯核函數(shù)；前面公式可寫(xiě)為：這里可以看到若W(xi)=1, G(x)=1時(shí)，就轉(zhuǎn)化成了meanshift基本形式。 EhH2niiiniixihxwhxxGxxwhxxGxMi11)()()()()()(多維空間下的無(wú)參密度估計(jì)（以下是證明Meanshift向量Mh(x)總是向密度增加的方向漂移）：在d維歐式空間X中，x表示該空間中的一個(gè)點(diǎn)， 表示該空

4、間中的核函數(shù), f(x)的概率密度函數(shù)為:核函數(shù)K(X)的剖面函數(shù)為k(x),且K(x)的負(fù)倒數(shù)為g(x),即 其對(duì)應(yīng)的核函數(shù)為2|)(|)(xkXK )(xkxgniidniiixwhxwhxxKxf11)()()()(2|)(|)(xgXG上式對(duì)x求導(dǎo)，得到概率密度函數(shù)的梯度函數(shù) fK(x):niidniiiiKxwhxwhxxGxxxf1212)()()()(2)()()(2)()()()()()()(22112122xMxfhxwhxxGxwhxxGxxxwhxwhxxGhhGniiiniiiiniidniii以G(x)為核函數(shù)的概率密度函數(shù)用核函數(shù)G在x點(diǎn)的Meanshift向量該式

5、表明用核函數(shù)G在x點(diǎn)得到的Meanshift向量正比于歸一化的用核函數(shù)K估計(jì)的概率密度梯度(歸一化因子即分母為用核函數(shù)G估計(jì)的x點(diǎn)概率密度)。數(shù)據(jù)最密集的地方，對(duì)應(yīng)于概率密度最大的地方。對(duì)概率密度求梯度，梯度的方向就是概率密度增加的方向，從而也就是向最密集的方向漂移。由上式可得：)()(21)(2xfxfhxMGKh 對(duì)目標(biāo)進(jìn)行跟蹤時(shí)，可以把圖片想象成一張概率密度圖。圖像輸入后是一個(gè)目標(biāo)圖像的直方圖（也可以認(rèn)為是目標(biāo)圖像），還一個(gè)輸入是當(dāng)前圖像就是你要跟蹤的全圖，輸出大小與全圖一樣大，它上像素點(diǎn)表征著一種概率，就是全圖上這個(gè)點(diǎn)是目標(biāo)圖像一部分的概率。如果這個(gè)點(diǎn)越亮，就說(shuō)明這個(gè)點(diǎn)屬于物體的概率越

6、大。現(xiàn)在我們明白了這原來(lái)是一張概率圖了。當(dāng)用meanshift跟蹤時(shí)，輸入的原來(lái)是這樣一幅圖像，如此可以實(shí)現(xiàn)對(duì)目標(biāo)的跟蹤。 關(guān)鍵：反向投影關(guān)鍵：反向投影 如果一幅圖像的區(qū)域中顯示如果一幅圖像的區(qū)域中顯示的是一種結(jié)構(gòu)紋理或者一個(gè)獨(dú)特的物體，那么這個(gè)區(qū)域的的是一種結(jié)構(gòu)紋理或者一個(gè)獨(dú)特的物體，那么這個(gè)區(qū)域的直方圖可以看作一個(gè)概率函數(shù)，給出的是某個(gè)像素屬于該直方圖可以看作一個(gè)概率函數(shù)，給出的是某個(gè)像素屬于該紋理或物體的概率。所謂反向投影就是首先計(jì)算某一特征紋理或物體的概率。所謂反向投影就是首先計(jì)算某一特征的直方圖模型，然后使用模型去尋找測(cè)試圖像中存在的該的直方圖模型，然后使用模型去尋找測(cè)試圖像中存在的

7、該特征特征。下面我們看一下mean shift算法的步驟 hmx給定一個(gè)初始點(diǎn)x,核函數(shù)G(x), 容許誤差 ,Mean Shift算法循環(huán)的執(zhí)行下面三步,直至結(jié)束條件滿足,計(jì)算把 賦給 . 如果 , 結(jié)束循環(huán);若不然,循環(huán)執(zhí)行( )hmx( )hmxx( )hm xx 上面的步驟也就是不斷的沿著概率密度的梯度方向移動(dòng),同時(shí)步長(zhǎng)不僅與梯度的大小有關(guān),也與該點(diǎn)的概率密度有關(guān),在密度大的地方,更接近我們要找的概率密度的峰值,Mean Shift算法使得移動(dòng)的步長(zhǎng)小一些；相反,在密度小的地方,移動(dòng)的步長(zhǎng)就大一些.在滿足一定條件下,Mean Shift算法一定會(huì)漂移到該點(diǎn)附近的峰值。均值漂移在目標(biāo)跟蹤

8、中應(yīng)用1：目標(biāo)模型敘述2：候選目標(biāo)敘述3: 相似型函數(shù)比較4：目標(biāo)定位5：整個(gè)算法流程u在起始幀，通過(guò)鼠標(biāo)確定一個(gè)包含所有目標(biāo)特征的矩形，稱為被跟蹤目標(biāo)的目標(biāo)區(qū)域，這個(gè)目標(biāo)區(qū)域也是核函數(shù)作用的區(qū)域，區(qū)域的大小等于核函數(shù)的帶寬。u對(duì)目標(biāo)區(qū)域進(jìn)行描述，常用的方法是按照直方圖的方式將圖像像素的值域等分成k個(gè)區(qū)間，每個(gè)區(qū)間按照值域的大小對(duì)應(yīng)一個(gè)特征值。然后求出圖像的像素值取每個(gè)特征值的概率。u對(duì)在初始幀圖像中目標(biāo)區(qū)域內(nèi)所有的象素點(diǎn)，計(jì)算每個(gè)特征值的概率，我們稱為目標(biāo)模型的描述。目標(biāo)模型的描述目標(biāo)模型的描述目標(biāo)區(qū)域的中心為 ，假設(shè)其中有n個(gè)象素用 表示，特征值的個(gè)數(shù)為m個(gè) ,則目標(biāo)模型的特征值 的概率密

9、度估計(jì)為： 為核函數(shù)的輪廓函數(shù)，由于遮擋或者背景的影響，目標(biāo)模型中心附近的象素比外物象素更可靠， 對(duì)中心的象素給一個(gè)大的權(quán)值，而遠(yuǎn)離中心的象素一個(gè)小的權(quán)值 總得作用是判斷目標(biāo)區(qū)域中象素的值是否屬于第u個(gè)特征值。b(xi)是灰度值索引函數(shù)。屬于該特征則值為1，否則為0(pdf)。 C是一個(gè)標(biāo)準(zhǔn)化的常量系數(shù)，使得 于是我們得到了基于圖像灰度特征的顏色直方圖。 1.11muuumuqqq運(yùn)動(dòng)目標(biāo)在第二幀及以后的每幀中可能包含目標(biāo)的區(qū)域稱為候選區(qū)域，其中心坐標(biāo)為y，也是核函數(shù)的中心坐標(biāo)。該區(qū)域中的象素用 表示。對(duì)候選區(qū)域的描述我們成為目標(biāo)候選模型，候選模型的特征值 的概率密度為： 其中 是標(biāo)準(zhǔn)化常量候

10、選模型的描述 1.11muuumup ypyp相似性函數(shù)的比較相似性函數(shù)的比較 1,mp ypypy1,mqqq模板區(qū)域模板區(qū)域:候選區(qū)域候選區(qū)域:相似性函數(shù)相似性函數(shù): ,?fyfp yq 1,mpypypy1,mqqq q pyy11 Bhattacharyya 系數(shù) 1cosTmyuuupyqfypy qpyq相似性函數(shù)描述目標(biāo)模型和候選模型之間的相似程度，在理想情況下兩個(gè)模型的概率分布是完全一樣的。我們使用Bhattacharyya系數(shù)作為相似性函數(shù)其值在0到1之間。 的值越大，表示兩個(gè)模型越相似，在當(dāng)前幀中不同的候選區(qū)域計(jì)算得到的候選模型，使得 最大候選區(qū)域即是在本幀中目標(biāo)的位置。目

11、標(biāo)定位為使 最大，將當(dāng)前幀的目標(biāo)中心先定位為前一幀中目標(biāo)中的位置 ，從這一點(diǎn)開(kāi)始尋找最優(yōu)匹配的目標(biāo)，其中心為y。先計(jì)算目標(biāo)候選模型 ，對(duì) 在 處進(jìn)行泰勒級(jí)數(shù)展開(kāi)，Bhattachcyarya系數(shù)可近似為：其中：類似于核函數(shù)密度估計(jì)，不過(guò)多了一個(gè)權(quán)值wi。使 式最大，就是要求 式最大，可以計(jì)算 的Mean Shift向量，這樣我們就可以得到候選區(qū)域中心 移向真實(shí)目標(biāo)區(qū)域y的向量:=值得注意的是，一般在一幀中找到目標(biāo)的位置，需要Mean Shift算法從開(kāi)始若干次迭代才能得到。其中算法過(guò)程 (1).初始化搜索窗 (2).計(jì)算搜索窗的顏色概率分布（反向投影） (3).運(yùn)行meanshift算法，獲得搜索窗新的大小和位置。 (4).在下一幀視頻圖像中重新搜索窗的大小和位置， 進(jìn)行相似度匹配， 再跳轉(zhuǎn)到(2)繼續(xù)進(jìn)行，直 到 。( )hm xxMeanshift優(yōu)缺點(diǎn)：優(yōu)點(diǎn)1.算法計(jì)算量不大，在目標(biāo)區(qū)域已知的情況下完全可以做到實(shí)時(shí)跟蹤2.采用核函數(shù)直方圖模型，對(duì)邊緣遮擋、目標(biāo)旋轉(zhuǎn)、變形和背景運(yùn)動(dòng)不敏感缺點(diǎn)：1.缺乏必要的模板更新2.跟蹤過(guò)程中由