mean-shift算法概述

1、MeanShift概述概述MeanShift簡(jiǎn)介簡(jiǎn)介MeanShift這個(gè)概念最早是由Fukunaga等人[1]于1975年在一篇關(guān)于概率密度梯度函數(shù)的估計(jì)中提出來(lái)的其最初含義正如其名就是偏移的均值向量在這里MeanShift是一個(gè)名詞它指代的是一個(gè)向量但隨著MeanShift理論的發(fā)展MeanShift的含義也發(fā)生了變化如果我們說(shuō)MeanShift算法一般是指一個(gè)迭代的步驟即先算出當(dāng)前點(diǎn)的偏移均值移動(dòng)該點(diǎn)到其偏移均值然后以此為新的起始

2、點(diǎn)繼續(xù)移動(dòng)直到滿足一定的條件結(jié)束.然而在以后的很長(zhǎng)一段時(shí)間內(nèi)MeanShift并沒(méi)有引起人們的注意直到20年以后也就是1995年另外一篇關(guān)于MeanShift的重要文獻(xiàn)[2]才發(fā)表.在這篇重要的文獻(xiàn)中YizongCheng對(duì)基本的MeanShift算法在以下兩個(gè)方面做了推廣首先YizongCheng定義了一族核函數(shù)使得隨著樣本與被偏移點(diǎn)的距離不同其偏移量對(duì)均值偏移向量的貢獻(xiàn)也不同其次YizongCheng還設(shè)定了一個(gè)權(quán)重系數(shù)使得不同的樣

3、本點(diǎn)重要性不一樣這大大擴(kuò)大了MeanShift的適用范圍.另外YizongCheng指出了MeanShift可能應(yīng)用的領(lǐng)域并給出了具體的例子.Comaniciu等人[3][4]把MeanShift成功的運(yùn)用的特征空間的分析在圖像平滑和圖像分割中MeanShift都得到了很好的應(yīng)用.Comaniciu等在文章中證明了MeanShift算法在滿足一定條件下一定可以收斂到最近的一個(gè)概率密度函數(shù)的穩(wěn)態(tài)點(diǎn)因此MeanShift算法可以用來(lái)檢測(cè)概率

4、密度函數(shù)中存在的模態(tài).Comaniciu等人[5]還把非剛體的跟蹤問(wèn)題近似為一個(gè)MeanShift最優(yōu)化問(wèn)題使得跟蹤可以實(shí)時(shí)的進(jìn)行.在后面的幾節(jié)本文將詳細(xì)的說(shuō)明MeanShift的基本思想及其擴(kuò)展其背后的物理含義以及算法步驟并給出理論證明.最后本文還將給出MeanShift在聚類圖像平滑圖像分割物體實(shí)時(shí)跟蹤這幾個(gè)方面的具體應(yīng)用.MeanShift的基本思想及其擴(kuò)展的基本思想及其擴(kuò)展基本基本MeanShift給定d維空間中的n個(gè)樣本點(diǎn)ix

5、i=1…n在點(diǎn)的MeanShift向量的基本形式定義dRx為:????1ihhixSMxxxk????(1).表示實(shí)數(shù)域.如果一個(gè)函數(shù)存在一個(gè)剖面函數(shù)即2Txxx?R:KXR???:0kR??(3)??2()Kxkx?并且滿足:(1)是非負(fù)的.k(2)是非增的即如果那么.kab?()()kakb?(3)是分段連續(xù)的并且k0()krdr????那么函數(shù)就被稱為核函數(shù).()Kx舉例舉例:在MeanShift中有兩類核函數(shù)經(jīng)常用到他們分別是單