meanshift算法概述

1、Mean Shift 概述Mean Shift 簡介Mean Shift 這個概念最早是由Fukunaga等人1于1975年在一篇關(guān)于概率密度梯度函數(shù)的估計中提出來的,其最初含義正如其名,就是偏移的均值向量,在這里Mean Shift是一個名詞,它指代的是一個向量,但隨著Mean Shift理論的發(fā)展,Mean Shift的含義也發(fā)生了變化,如果我們說Mean Shift算法,一般是指一個迭代的步驟,即先算出當(dāng)前點的偏移均值,移動該點到其偏移均值,然后以此為新的起始點,繼續(xù)移動,直到滿足一定的條件結(jié)束.然而在以后的很長一段時間內(nèi)Mean Shift并沒有引起人們的注意,直到20年以后,也就是1

2、995年,另外一篇關(guān)于Mean Shift的重要文獻(xiàn)2才發(fā)表.在這篇重要的文獻(xiàn)中,Yizong Cheng對基本的Mean Shift算法在以下兩個方面做了推廣,首先Yizong Cheng定義了一族核函數(shù),使得隨著樣本與被偏移點的距離不同,其偏移量對均值偏移向量的貢獻(xiàn)也不同,其次Yizong Cheng還設(shè)定了一個權(quán)重系數(shù),使得不同的樣本點重要性不一樣,這大大擴大了Mean Shift的適用范圍.另外Yizong Cheng指出了Mean Shift可能應(yīng)用的領(lǐng)域,并給出了具體的例子.Comaniciu等人34把Mean Shift成功的運用的特征空間的分析,在圖像平滑和圖像分割中Mean

3、Shift都得到了很好的應(yīng)用. Comaniciu等在文章中證明了,Mean Shift算法在滿足一定條件下,一定可以收斂到最近的一個概率密度函數(shù)的穩(wěn)態(tài)點,因此Mean Shift算法可以用來檢測概率密度函數(shù)中存在的模態(tài).Comaniciu等人5還把非剛體的跟蹤問題近似為一個Mean Shift最優(yōu)化問題,使得跟蹤可以實時的進(jìn)行.在后面的幾節(jié),本文將詳細(xì)的說明Mean Shift的基本思想及其擴展,其背后的物理含義,以及算法步驟,并給出理論證明.最后本文還將給出Mean Shift在聚類,圖像平滑,圖像分割,物體實時跟蹤這幾個方面的具體應(yīng)用.Mean Shift 的基本思想及其擴展基本Mean

4、 Shift給定d維空間中的n個樣本點,i=1,n,在點的Mean Shift向量的基本形式定義為:(1)其中,是一個半徑為h的高維球區(qū)域,滿足以下關(guān)系的y點的集合, (2)k表示在這n個樣本點中,有k個點落入?yún)^(qū)域中.我們可以看到是樣本點相對于點的偏移向量,(1)式定義的Mean Shift向量就是對落入?yún)^(qū)域中的k個樣本點相對于點的偏移向量求和然后再平均.從直觀上看,如果樣本點從一個概率密度函數(shù)中采樣得到,由于非零的概率密度梯度指向概率密度增加最大的方向,因此從平均上來說, 區(qū)域內(nèi)的樣本點更多的落在沿著概率密度梯度的方向.因此,對應(yīng)的, Mean Shift向量應(yīng)該指向概率密度梯度的方向. 圖

5、1,Mean Shift示意圖如上圖所示, 大圓圈所圈定的范圍就是,小圓圈代表落入?yún)^(qū)域內(nèi)的樣本點,黑點就是Mean Shift的基準(zhǔn)點,箭頭表示樣本點相對于基準(zhǔn)點的偏移向量,很明顯的,我們可以看出,平均的偏移向量會指向樣本分布最多的區(qū)域,也就是概率密度函數(shù)的梯度方向.擴展的Mean Shift核函數(shù)首先我們引進(jìn)核函數(shù)的概念.定義:代表一個d維的歐氏空間,是該空間中的一個點,用一列向量表示. 的模.表示實數(shù)域.如果一個函數(shù)存在一個剖面函數(shù),即(3)并且滿足:(1) 是非負(fù)的.(2) 是非增的,即如果那么.(3) 是分段連續(xù)的,并且那么,函數(shù)就被稱為核函數(shù).舉例:在Mean Shift中,有兩類核

6、函數(shù)經(jīng)常用到,他們分別是,單位均勻核函數(shù): (4)單位高斯核函數(shù): (5)這兩類核函數(shù)如下圖所示.圖2, (a) 單位均勻核函數(shù) (b) 單位高斯核函數(shù)一個核函數(shù)可以與一個均勻核函數(shù)相乘而截尾,如一個截尾的高斯核函數(shù)為,(6)圖 3 顯示了不同的值所對應(yīng)的截尾高斯核函數(shù)的示意圖.圖3 截尾高斯核函數(shù) (a) (b) Mean Shift擴展形式從(1)式我們可以看出,只要是落入的采樣點,無論其離遠(yuǎn)近,對最終的計算的貢獻(xiàn)是一樣的,然而我們知道,一般的說來,離越近的采樣點對估計周圍的統(tǒng)計特性越有效,因此我們引進(jìn)核函數(shù)的概念,在計算時可以考慮距離的影響;同時我們也可以認(rèn)為在這所有的樣本點中,重要性并

7、不一樣,因此我們對每個樣本都引入一個權(quán)重系數(shù).如此以來我們就可以把基本的Mean Shift形式擴展為: (7)其中:是一個單位核函數(shù)是一個正定的對稱矩陣,我們一般稱之為帶寬矩陣是一個賦給采樣點的權(quán)重在實際應(yīng)用的過程中,帶寬矩陣一般被限定為一個對角矩陣,甚至更簡單的被取為正比于單位矩陣,即.由于后一形式只需要確定一個系數(shù),在Mean Shift中常常被采用,在本文的后面部分我們也采用這種形式,因此(7)式又可以被寫為: (8)我們可以看到,如果對所有的采樣點滿足(1)(2) 則(8)式完全退化為(1)式,也就是說,我們所給出的擴展的Mean Shift形式在某些情況下會退化為最基本的Mean

8、Shift形式.Mean Shift的物理含義正如上一節(jié)直觀性的指出,Mean Shift指向概率密度梯度方向,這一節(jié)將證明Mean Shift向量是歸一化的概率密度梯度.在本節(jié)我們還給出了迭代Mean Shift算法的詳細(xì)描述,并證明,該算法會收斂到概率密度函數(shù)的一個穩(wěn)態(tài)點.概率密度梯度對一個概率密度函數(shù),已知d維空間中n個采樣點,i=1,n, 的核函數(shù)估計(也稱為Parzen窗估計)為,(9)其中是一個賦給采樣點的權(quán)重是一個核函數(shù),并且滿足我們另外定義:核函數(shù)的剖面函數(shù),使得(10);的負(fù)導(dǎo)函數(shù),即,其對應(yīng)的核函數(shù) (11)概率密度函數(shù)的梯度的估計為:(12)由上面的定義, ,上式可以重寫

9、為(13)上式右邊的第二個中括號內(nèi)的那一部分就是(8)式定義的Mean Shift向量,第一個中括號內(nèi)的那一部分是以為核函數(shù)對概率密度函數(shù)的估計,我們記做,而(9)式定義的我們重新記做,因此(11)式可以重新寫為:(14)由(12)式我們可以得出,(15)(15)式表明,用核函數(shù)G在點計算得到的Mean Shift向量正比于歸一化的用核函數(shù)K估計的概率密度的函數(shù)的梯度,歸一化因子為用核函數(shù)G估計的x點的概率密度.因此Mean Shift向量總是指向概率密度增加最大的方向.Mean Shift算法算法步驟我們在前面已經(jīng)指出,我們在提及Mean Shift向量和Mean Shift算法的時候指代不

10、同的概念,Mean Shift向量是名詞,指的是一個向量;而Mean Shift算法是動詞,指的是一個迭代的步驟.我們把(8)式的提到求和號的外面來,可以得到下式,(16)我們把上式右邊的第一項記為,即(17)給定一個初始點,核函數(shù), 容許誤差,Mean Shift算法循環(huán)的執(zhí)行下面三步,直至結(jié)束條件滿足,(1).計算(2).把賦給(3).如果,結(jié)束循環(huán);若不然,繼續(xù)執(zhí)行(1).由(16)式我們知道, ,因此上面的步驟也就是不斷的沿著概率密度的梯度方向移動,同時步長不僅與梯度的大小有關(guān),也與該點的概率密度有關(guān),在密度大的地方,更接近我們要找的概率密度的峰值,Mean Shift算法使得移動的步

11、長小一些,相反,在密度小的地方,移動的步長就大一些.在滿足一定條件下,Mean Shift算法一定會收斂到該點附近的峰值,這一收斂性由下面一小節(jié)給出證明.算法的收斂性證明我們用,來表示Mean Shift算法中移動點的痕跡,由(17)式我們可寫為, (18)與對應(yīng)的概率密度函數(shù)估計值可表示為, (19)下面的定理將證明序列和的收斂性.定理:如果核函數(shù)有一個凸的,單調(diào)遞增的剖面函數(shù),核函數(shù)由式(10)和(11)定義,則序列和是收斂的.證明:由于n是有限的,核函數(shù),因此序列是有界的,所以我們只需要證明是嚴(yán)格遞增的的,即要證明,對所有j=1,2,如果,那么(20)不失一般性,我們可以假設(shè),由(19)

12、式和(10)式,我們可以得到 (21)由于剖面函數(shù)的凸性意味著對所有且,有(22)因為,上式可以寫為,(23)結(jié)合(21)與(23)式,可以得到,(24)由(18)式我們可以得出,(25)由于剖面函數(shù)是單調(diào)遞減的,所以求和項,因此,只要 (25)式的右邊項嚴(yán)格大于零,即.由此可證得,序列收斂為了證明序列的收斂性,對于,(25)式可以寫為(26)現(xiàn)在對于標(biāo)號j,j+1,j+m-1,對(26)式的左右兩邊分別求和,得到(27)其中表示對應(yīng)序列的所有求和項的最小值.由于收斂,它是一個Cauchy序列,(27)式意味著也是一個Cauchy序列,因此,序列收斂.Mean Shift的應(yīng)用從前面關(guān)于Mea

13、n Shift和概率密度梯度的關(guān)系的論述,我們可以清楚的看到,Mean Shift算法本質(zhì)上是一個自適應(yīng)的梯度上升搜索峰值的方法,如下圖所示,如果數(shù)據(jù)集服從概率密度函數(shù)f(x),給定一個如圖初始點,Mean Shift算法就會一步步的移動,最終收斂到第一個峰值點.從這張圖上,我們可以看到Mean Shift至少有如下三方面的應(yīng)用:(1)聚類,數(shù)據(jù)集中的每一點都可以作為初始點,分別執(zhí)行Mean Shift算法,收斂到同一個點算作一類;(2)模態(tài)的檢測,概率密度函數(shù)中的一個峰值就是一個模態(tài),Mean Shift在峰值處收斂,自然可以找到該模態(tài).(3)最優(yōu)化,Mean Shift可以找到峰值,自然可

14、以作為最優(yōu)化的方法,Mean Shift算法進(jìn)行最優(yōu)化的關(guān)鍵是要把最優(yōu)化的目標(biāo)轉(zhuǎn)化成Mean Shift隱含估計的概率密度函數(shù).圖4.Mean Shift算法示意圖Mean Shift算法在許多領(lǐng)域獲得了非常成功的應(yīng)用,下面簡要的介紹一下其在圖像平滑,圖像分割以及物體跟蹤中的應(yīng)用,一來說明其強大的生命力,二來使對上文描述的算法有一個直觀的了解.圖像平滑與分割一幅圖像可以表示成一個二維網(wǎng)格點上p維向量,每一個網(wǎng)格點代表一個象素,表示這是一個灰度圖,表示彩色圖,表示一個多譜圖,網(wǎng)格點的坐標(biāo)表示圖像的空間信息.我們統(tǒng)一考慮圖像的空間信息和色彩(或灰度等)信息,組成一個維的向量,其中表示網(wǎng)格點的坐標(biāo),

15、表示該網(wǎng)格點上p維向量特征.我們用核函數(shù)來估計的分布, 具有如下形式,(28)其中控制著平滑的解析度,C是一個歸一化常數(shù).我們分別用和,i=1,n表示原始和平滑后的圖像.用Mean Shift算法進(jìn)行圖像平滑的具體步驟如下,對每一個象素點,1,初始化,并且使2,運用Mean Shift算法計算,直到收斂.記收斂后的值為3.賦值圖5是原始圖像,圖中4020白框區(qū)域被選中來更好的顯示基于Mean Shift的圖像平滑步驟,圖6顯示了這一區(qū)域的平滑步驟,x, y表示這一區(qū)域內(nèi)的象素點的坐標(biāo),圖6(a)在一個三維空間顯示了各個象素點的灰度值,圖6(b)顯示各點的移動痕跡,黑點是最終收斂值,圖6(c)顯

16、示了平滑后的各象素點的灰度值,圖6(d)是繼續(xù)分割后的結(jié)果.圖5.原始圖像圖6.(a)原始圖像的各象素點灰度值.(b)各象素點的Mean Shift移動路徑.(c)平滑后的各象素點的灰度值.(d)分割后的結(jié)果圖7顯示了圖5經(jīng)過平滑后的結(jié)果,我們可以看到,草地上的草地紋理被平滑掉了,而圖像中邊緣仍然很好的保持著. 圖7平滑后的結(jié)果在基于Mean Shift的圖像平滑中,式(28)中的是非常重要的參數(shù),人們可以根據(jù)解析度的要求而直接給定,不同會對最終的平滑結(jié)果有一定的影響,圖7顯示了這兩個參數(shù)對平滑結(jié)果的影響,我們可以看出, 影響更大一些.圖8,原始圖和平滑后的圖基于Mean Shift的圖像分割

17、與圖像平滑非常類似,只需要把收斂到同一點的起始點歸為一類,然后把這一類的標(biāo)號賦給這些起始點,在圖像分割中有時還需要把包含象素點太少類去掉,圖6(d)顯示分割后的灰度值.圖8,顯示了圖5經(jīng)過分隔后的結(jié)果圖8,分割后的結(jié)果物體跟蹤我們用一個物體的灰度或色彩分布來描述這個物體,假設(shè)物體中心位于,則該物體可以表示為(29)候選的位于的物體可以描述為(30)因此物體跟蹤可以簡化為尋找最優(yōu)的,使得與最相似.與的最相似性用Bhattacharrya系數(shù)來度量分布,即(31)式(31)在點泰勒展開可得,(32)把式(30)帶入式,整理可得,(33)其中,對式(33)右邊的第二項,我們可以利用Mean Shif

18、t算法進(jìn)行最優(yōu)化.在Comaniciu等人的文章中,他們只用平均每幀圖像只用4.19次Mean Shift迭代就可以收斂,他們的結(jié)果很顯示在600MHz的PC機上,他們的程序可以每秒處理30幀352240象素的圖像.下圖顯示了各幀需要的Mean Shift迭代次數(shù).圖9,各幀需要的Mean Shift迭代次數(shù)下圖顯示了Comaniciu等人的跟蹤結(jié)果圖10,基于Mean Shift的物體跟蹤結(jié)果結(jié)論本文回顧了Mean Shift的發(fā)展歷史,介紹了它的基本思想,給出了具體的算法步驟,詳細(xì)證明了它與梯度上升搜索法的聯(lián)系,并給出Mean Shift算法的收斂性證明,最后給出了Mean Shift在圖像平滑,圖像分割以及實時物體跟蹤中的具體應(yīng)用,顯示Mean Shift強大的生命力.參考文獻(xiàn)1The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition (