Mean shift和粒子濾波算法

Meanshift基本原理

Meanshift這個(gè)概念最早由Fukunaga等人于1975年在一篇關(guān)于概率密度梯度函數(shù)的估計(jì)中提出來(lái)的，最初的含義就是偏移的均值向量，但隨著Meanshift理論的發(fā)展，其含義也發(fā)生了變化，其含義一般是指一個(gè)迭代的步驟，即先算出當(dāng)前的偏移的均值，移動(dòng)到其均值，然后依次為新的起始點(diǎn)，繼續(xù)移動(dòng)，知道滿足一定的條件結(jié)束?，F(xiàn)在是1頁(yè)\一共有49頁(yè)\編輯于星期一核函數(shù)例子：Obviously,wewouldliketogeneratetwogroupscorrespondingtothetwopartsofthefeaturespaceinwhichwehaveahighdensityofpointsHowcanwecapturethisnotionof“highdensity”----kerneldensityestimation現(xiàn)在是2頁(yè)\一共有49頁(yè)\編輯于星期一核函數(shù)Letusdefineakernelfunction:K(X),withtheproperties:Kdecaystozerofarfrom0Kismaximumat0Kissymmetric現(xiàn)在是3頁(yè)\一共有49頁(yè)\編輯于星期一核函數(shù)例子:Uniform:現(xiàn)在是4頁(yè)\一共有49頁(yè)\編輯于星期一核函數(shù)例子現(xiàn)在是5頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的基本形式給定d維空間R^d中n個(gè)樣本點(diǎn)Xi,i=1,2,3,….n,在x點(diǎn)的Meanshift向量的基本形式定義為：（1）其中，Sh是一個(gè)半徑為h的高維球區(qū)域，滿足一下關(guān)系的y點(diǎn)的集合，即：（2）現(xiàn)在是6頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的基本形式

K表示在這n個(gè)樣本點(diǎn)xi中，有k個(gè)點(diǎn)落入Sh區(qū)域中?？梢钥闯?，式（1）中（xi-x）是樣本點(diǎn)xi相對(duì)于點(diǎn)x的偏移向量，式(1)定義的Meanshift向量Mh(x)就是對(duì)落入?yún)^(qū)域Sh中的k個(gè)樣本點(diǎn)相對(duì)于點(diǎn)x的偏移向量求和然后再平均。從直觀上看，如果樣本點(diǎn)xi從一個(gè)概率密度函數(shù)f(x)中采樣得到，由于概率密度梯度指向概率密度增加最大的方向，Sh區(qū)域內(nèi)的樣本點(diǎn)更多的落在沿著概率密度梯度的方向上。因此，Meanshift向量應(yīng)該指向概率密度的方向?，F(xiàn)在是7頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的擴(kuò)展形式從式(1)中可以看出，只要是落入Sh的采樣點(diǎn)，無(wú)論其離基準(zhǔn)點(diǎn)遠(yuǎn)近，其對(duì)最終的偏移向量計(jì)算的貢獻(xiàn)是一樣的，然而一般來(lái)說(shuō)，離基準(zhǔn)點(diǎn)越近的采樣點(diǎn)對(duì)估計(jì)基準(zhǔn)點(diǎn)周?chē)慕y(tǒng)計(jì)特性越有效，因此，將核函數(shù)的概念引入均值漂移，在計(jì)算偏移向量Mh(x)時(shí)可以考慮距離的影響。同時(shí)，在所有的樣本點(diǎn)xi中，其重要性并不一樣，因此還需對(duì)每個(gè)樣本引入一個(gè)權(quán)重系數(shù)。由此得到Meanshift的擴(kuò)展形式：現(xiàn)在是8頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的擴(kuò)展形式（3）現(xiàn)在是9頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的擴(kuò)展形式現(xiàn)在是10頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟給定一個(gè)初始點(diǎn)x，核函數(shù)g(x)，誤差門(mén)限設(shè)為，則Meanshift算法循環(huán)的執(zhí)行下面步驟，直到結(jié)束條件滿足：

(1)計(jì)算Meanshift向量m(x)(2)將m(x)賦給x；

(3)如果則結(jié)束循環(huán)；否則，繼續(xù)執(zhí)行步驟(1)；以上步驟即是不斷地沿著概率密度的梯度方向移動(dòng)，同時(shí)，步長(zhǎng)不僅與梯度的大小有關(guān)，也與該點(diǎn)的概率密度有關(guān)，在密度較大處，更接近要尋找的概率密度的峰值，因此Meanshift算法的移動(dòng)步長(zhǎng)會(huì)比較??；相反，移動(dòng)的步長(zhǎng)就會(huì)增大?，F(xiàn)在是11頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟現(xiàn)在是12頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟現(xiàn)在是13頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟現(xiàn)在是14頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟現(xiàn)在是15頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟現(xiàn)在是16頁(yè)\一共有49頁(yè)\編輯于星期一Meanshift的算法步驟現(xiàn)在是17頁(yè)\一共有49頁(yè)\編輯于星期一應(yīng)用應(yīng)用現(xiàn)在是18頁(yè)\一共有49頁(yè)\編輯于星期一粒子濾波理論粒子濾波是指：通過(guò)尋找一組在狀態(tài)空間中傳播的隨機(jī)樣本對(duì)概率密度函數(shù)p(xk|zk)進(jìn)行近似，以樣本均值代替積分運(yùn)算，從而獲得狀態(tài)最小方差估計(jì)的過(guò)程，這些樣本稱為粒子，采用數(shù)學(xué)語(yǔ)言描述如下：對(duì)于平穩(wěn)的隨機(jī)過(guò)程，假定k-1時(shí)刻系統(tǒng)的后驗(yàn)概率密度為p(xk-1|zk-1)，依據(jù)一定原則選取n個(gè)隨機(jī)樣本點(diǎn)，k時(shí)刻獲得測(cè)量信息后，經(jīng)過(guò)狀態(tài)和時(shí)間更新過(guò)程，n個(gè)粒子的后驗(yàn)概率密度可近似為p（xk|zk），隨著粒子數(shù)目的增加，粒子的概率密度函數(shù)逼近狀態(tài)的概率密度函數(shù)，粒子濾波估計(jì)即達(dá)到了最優(yōu)貝葉斯估計(jì)的效果?，F(xiàn)在是19頁(yè)\一共有49頁(yè)\編輯于星期一2.1貝葉斯濾波原理貝葉斯濾波原理的實(shí)質(zhì)是試圖用所有已知信息來(lái)構(gòu)造系統(tǒng)狀態(tài)變量的后驗(yàn)概率密度，即用系統(tǒng)狀態(tài)轉(zhuǎn)移模型預(yù)測(cè)狀態(tài)的先驗(yàn)概率密度，再使用最近的觀測(cè)值進(jìn)行修正，最后得到后驗(yàn)概率密度。設(shè)x1,x2,….xn是獨(dú)立同分布的隨機(jī)變量，每一個(gè)變量相對(duì)于未知參數(shù)的條件概率密度為則未知參數(shù)的后驗(yàn)概率密度如式(2.1)所示（2.1）現(xiàn)在是20頁(yè)\一共有49頁(yè)\編輯于星期一2.1貝葉斯濾波原理式（2.1）中表示給定數(shù)據(jù)（x1,…xn）后參數(shù)的似然函數(shù)，是待估計(jì)參數(shù)的概率密度，稱之為先驗(yàn)分布。是參數(shù)的后驗(yàn)密度，稱之為后驗(yàn)概率密度。由貝葉斯定理可以看出，貝葉斯方法把待估計(jì)參數(shù)當(dāng)作一個(gè)隨機(jī)變量，在沒(méi)有新的觀測(cè)數(shù)據(jù)時(shí)，根據(jù)先驗(yàn)分布對(duì)參數(shù)作出判斷，在得到新的觀測(cè)數(shù)據(jù)后，根據(jù)貝葉斯定理將先驗(yàn)分布與實(shí)際觀測(cè)數(shù)據(jù)相結(jié)合得到后驗(yàn)分布。貝葉斯定理是一種通過(guò)更新參數(shù)值的先驗(yàn)分布從而得出其后驗(yàn)分布的數(shù)學(xué)方法，是將經(jīng)驗(yàn)知識(shí)與觀測(cè)數(shù)據(jù)加以綜合的過(guò)程。現(xiàn)在是21頁(yè)\一共有49頁(yè)\編輯于星期一2.2狀態(tài)轉(zhuǎn)移模型狀態(tài)轉(zhuǎn)移模型是一種離散時(shí)刻的狀態(tài)—空間運(yùn)動(dòng)模型，如圖2.1所示。其目的是根據(jù)當(dāng)前時(shí)刻t的觀測(cè)來(lái)估計(jì)隱含目標(biāo)狀態(tài)的概率分布?，F(xiàn)在是22頁(yè)\一共有49頁(yè)\編輯于星期一2.2狀態(tài)轉(zhuǎn)移模型根據(jù)圖2.1所描述的狀態(tài)轉(zhuǎn)移模型，其中的系統(tǒng)隱含狀態(tài){xt},t=1,2,…會(huì)由式(2.2)所示的系統(tǒng)方程隨時(shí)間更新:而觀測(cè){yt},t=1,2,…則由式（2.3）所示的觀測(cè)方程描述：2.22.3現(xiàn)在是23頁(yè)\一共有49頁(yè)\編輯于星期一2.2狀態(tài)轉(zhuǎn)移模型其中wt和vt是相互獨(dú)立切概率分布已知的噪聲向量，并假定初始狀態(tài)的概率密度函數(shù)p(x0)已知。{xt}稱為目標(biāo)狀態(tài)、真實(shí)狀態(tài)等。{yt}也稱測(cè)量信息、觀測(cè)等。為了使用方便，定義Xt={x0,x1,...xt},Yt={y0,y1,..yt}。在狀態(tài)空間模型中，系統(tǒng)狀態(tài)滿足式（2.4）所示的馬爾可夫?qū)傩?。在給定狀態(tài)向量Xt時(shí)，觀測(cè)Yt相互獨(dú)立，如式（2.5）2.42.5現(xiàn)在是24頁(yè)\一共有49頁(yè)\編輯于星期一2.3遞歸貝葉斯推理由圖2.1所示的狀態(tài)轉(zhuǎn)移運(yùn)動(dòng)模型中可以看出，如果在每次獲得觀測(cè)時(shí)都從頭開(kāi)始對(duì)時(shí)刻t的隱含目標(biāo)狀態(tài)tx進(jìn)行估計(jì)的話，會(huì)導(dǎo)致計(jì)算量的不斷增加而影響計(jì)算的速度。為了能夠?qū)崟r(shí)估計(jì)目標(biāo)狀態(tài)，需要一種遞歸的方法，即僅通過(guò)時(shí)刻t-1的狀態(tài)和新的觀測(cè)信息只對(duì)時(shí)刻t的狀態(tài)進(jìn)行估計(jì)。遞歸貝葉斯估計(jì)方法為此類(lèi)問(wèn)題提供了一種可靠的解決方法，在給定P(xt-1|Yt-1)以及最近的觀測(cè)yt時(shí)，通過(guò)如式(2.6)所示的貝葉斯定理計(jì)算后驗(yàn)概率密度。2.6現(xiàn)在是25頁(yè)\一共有49頁(yè)\編輯于星期一由(2.6)式可得到遞歸貝葉斯推理的兩個(gè)步驟，即如式(2.7)所示的預(yù)測(cè)步驟(時(shí)間更新)和式(2.8)所示的修正步驟(觀測(cè)更新)：其推導(dǎo)過(guò)程如式（2.9）2.72.8現(xiàn)在是26頁(yè)\一共有49頁(yè)\編輯于星期一2.9現(xiàn)在是27頁(yè)\一共有49頁(yè)\編輯于星期一在遞歸貝葉斯推理中，根據(jù)不同的假設(shè)條件，對(duì)p(xt|yt)的計(jì)算也存在多種解決方法，當(dāng)動(dòng)態(tài)系統(tǒng)滿足線性高斯假設(shè)時(shí)，可通過(guò)卡爾曼濾波器求得最優(yōu)解，通常所說(shuō)的“最佳”與“最優(yōu)”估計(jì)是以最小均方誤差為準(zhǔn)則的。當(dāng)動(dòng)態(tài)系統(tǒng)是非線性時(shí)，遞歸貝葉斯推理中的高維積分運(yùn)算通常是難解問(wèn)題，為了緩解非線性動(dòng)態(tài)貝葉斯分析的計(jì)算壓力，出現(xiàn)了許多近似方法，其中包括蒙特卡羅方法現(xiàn)在是28頁(yè)\一共有49頁(yè)\編輯于星期一蒙特卡羅采樣方法蒙特卡羅方法是一種非常簡(jiǎn)單的隨機(jī)模擬方法，可用隨機(jī)樣本近似積分來(lái)計(jì)算難解的積分問(wèn)題，其基本思想是從目標(biāo)概率分布p(xt|yt)中抽取N個(gè)獨(dú)立同分布的粒子則后驗(yàn)密度可以通過(guò)式(3.16)近似表達(dá)：其中表示從后驗(yàn)分布采樣得到的粒子，表示Diracdelta函數(shù)。基于這種近似表達(dá)，如果對(duì)的期望進(jìn)行估計(jì)，得式(3.1)：3.03.1現(xiàn)在是29頁(yè)\一共有49頁(yè)\編輯于星期一經(jīng)過(guò)隨機(jī)抽樣后，可通過(guò)式（3.2）計(jì)算經(jīng)驗(yàn)估計(jì)。根據(jù)大數(shù)定理，當(dāng)粒子數(shù)N趨于無(wú)窮時(shí)，近似期望收斂于真實(shí)期望，即：3.23.3現(xiàn)在是30頁(yè)\一共有49頁(yè)\編輯于星期一重要性采樣重要性取樣是蒙特卡羅方法中一種常用的取樣技術(shù)。后驗(yàn)概率密度可以由來(lái)自該密度的獨(dú)立同分布粒子近似，粒子數(shù)越多，近似的后驗(yàn)概率密度就越逼近真實(shí)后驗(yàn)概率密度。但往往不可能直接從后驗(yàn)密度采樣粒子，在實(shí)際計(jì)算中從一個(gè)已知、易于采樣而且同目標(biāo)概率分布相近的概率密度采樣粒子，這個(gè)概率密度稱為建議分布，即是如圖2.2所示的重要性取樣的基本思想。如果估計(jì)函數(shù)期望為E[f(xi)]如果無(wú)法直接從p(xt|Yt)取樣，就選擇從與p(xt|Yt)近似的概率分布中取樣?，F(xiàn)在是31頁(yè)\一共有49頁(yè)\編輯于星期一重要性采樣在重要性取樣過(guò)程中，式（3.1）可按式（3.4）進(jìn)行推理。式（3.4）可以看出，可通過(guò)從取得的樣本對(duì)于f(xt)有關(guān)的各種量進(jìn)行估計(jì)，概率密度稱為重要性函數(shù)，其中稱為重要性權(quán)值，重要性權(quán)值的表達(dá)如3.53.43.5現(xiàn)在是32頁(yè)\一共有49頁(yè)\編輯于星期一利用貝葉斯規(guī)則對(duì)式(3.5)繼續(xù)推理，消去p(Yt)，得式(3.6)3.6現(xiàn)在是33頁(yè)\一共有49頁(yè)\編輯于星期一由式（3.6）可以看出，通過(guò)從重要性函數(shù)取樣，E[f(xt)]可以通過(guò)（3.7）近似為其中正則權(quán)值可按（3.8）計(jì)算：3.73.8現(xiàn)在是34頁(yè)\一共有49頁(yè)\編輯于星期一貫序重要性取樣當(dāng)獲得時(shí)刻t的觀測(cè)時(shí)，為了能夠在不修改以前狀態(tài)x(0:t-1)情況下，對(duì)狀態(tài)xt的概率密度進(jìn)行序貫式估計(jì)，將建議分布分解為如式(3.9)所示的重要性函數(shù)：由于狀態(tài)空間模型滿足馬爾可夫過(guò)程，在給定狀態(tài)時(shí)觀測(cè)之間條件獨(dú)立，可得到式(4.0)3.94.0現(xiàn)在是35頁(yè)\一共有49頁(yè)\編輯于星期一把式(4.0)帶入式(3.5)中，可以得到如式4.1所示的重要性加權(quán)的遞歸估計(jì)表達(dá)式式(4.1)表明，只要選擇合適的建議分布獲得采樣粒子，就可以迭代計(jì)算粒子的重要性權(quán)值4.1現(xiàn)在是36頁(yè)\一共有49頁(yè)\編輯于星期一重要性函數(shù)的選擇如何選擇重要性函數(shù)是一個(gè)很重要的問(wèn)題，理想的重要性函數(shù)應(yīng)該能最小化重要性權(quán)值的方差。最簡(jiǎn)單的重要性函數(shù)形式是狀態(tài)的先驗(yàn)分布，即：則重要性權(quán)值計(jì)算簡(jiǎn)化為：式(3.29)表明，采用狀態(tài)轉(zhuǎn)移先驗(yàn)分布作為重要性函數(shù)，重要性權(quán)值和似然概率密度成正比。盡管采用狀態(tài)轉(zhuǎn)移先驗(yàn)作為重要性函數(shù)實(shí)現(xiàn)較為容易，但在采樣粒子的過(guò)程中沒(méi)有考慮最近的觀測(cè)信息，這會(huì)導(dǎo)致僅有少量的粒子有較大的權(quán)值。當(dāng)似然在先驗(yàn)分布的尾端或相對(duì)先驗(yàn)較窄時(shí)，都會(huì)發(fā)生這種情況，因此選擇合適的重要性函數(shù)很重要，最優(yōu)的重要性函數(shù)應(yīng)充分考慮最新的觀測(cè)信息，將粒子移動(dòng)到高似然區(qū)4.34.2現(xiàn)在是37頁(yè)\一共有49頁(yè)\編輯于星期一重采樣序貫重要性取樣方法中存在的致命缺陷是權(quán)值退化，即粒子經(jīng)過(guò)若干次迭代之后，會(huì)出現(xiàn)其余粒子的權(quán)值可忽略不計(jì)，而其中的一個(gè)粒子的規(guī)范化權(quán)值趨于1的現(xiàn)象，導(dǎo)致大量計(jì)算資源浪費(fèi)在幾乎