|
Mean Shift 概述
2009-03-12 17:39
from:an introduction to mean shift.doc
原文很大圖放不上來，Google題目應(yīng)可找到
Mean Shift 簡介
Mean Shift 這個概念最早是由Fukunaga等人[1]于1975年在一篇關(guān)于概率密度梯度函數(shù)的估計中提出來的,其最初含義正如其名,就是偏移的均值向量,在這里Mean Shift是一個名詞,它指代的是一個向量,但隨著Mean Shift理論的發(fā)展,Mean Shift的含義也發(fā)生了變化,如果我們說Mean Shift算法,一般是指一個迭代的步驟,即先算出當前點的偏移均值,移動該點到其偏移均值,然后以此為新的起始點,繼續(xù)移動,直到滿足一定的條件結(jié)束.
然而在以后的很長一段時間內(nèi)Mean Shift并沒有引起人們的注意,直到20年以后,也就是1995年,另外一篇關(guān)于Mean Shift的重要文獻[2]才發(fā)表.在這篇重要的文獻中,Yizong Cheng對基本的Mean Shift算法在以下兩個方面做了推廣,首先Yizong Cheng定義了一族核函數(shù),使得隨著樣本與被偏移點的距離不同,其偏移量對均值偏移向量的貢獻也不同,其次Yizong Cheng還設(shè)定了一個權(quán)重系數(shù),使得不同的樣本點重要性不一樣,這大大擴大了Mean Shift的適用范圍.另外Yizong Cheng指出了Mean Shift可能應(yīng)用的領(lǐng)域,并給出了具體的例子.
Comaniciu等人[3][4]把Mean Shift成功的運用的特征空間的分析,在圖像平滑和圖像分割中Mean Shift都得到了很好的應(yīng)用. Comaniciu等在文章中證明了,Mean Shift算法在滿足一定條件下,一定可以收斂到最近的一個概率密度函數(shù)的穩(wěn)態(tài)點,因此Mean Shift算法可以用來檢測概率密度函數(shù)中存在的模態(tài).
Comaniciu等人[5]還把非剛體的跟蹤問題近似為一個Mean Shift最優(yōu)化問題,使得跟蹤可以實時的進行.
在后面的幾節(jié),本文將詳細的說明Mean Shift的基本思想及其擴展,其背后的物理含義,以及算法步驟,并給出理論證明.最后本文還將給出Mean Shift在聚類,圖像平滑,圖像分割,物體實時跟蹤這幾個方面的具體應(yīng)用.
Mean Shift 的基本思想及其擴展
基本Mean Shift
給定d維空間 中的n個樣本點,i=1,…,n,在點的Mean Shift向量的基本形式定義為:
k表示在這n個樣本點 中,有k個點落入區(qū)域中.
我們可以看到是樣本點 相對于點的偏移向量,(1)式定義的Mean Shift向量就是對落入?yún)^(qū)域中的k個樣本點相對于點 的偏移向量求和然后再平均.從直觀上看,如果樣本點從一個概率密度函數(shù)中采樣得到,由于非零的概率密度梯度指向概率密度增加最大的方向,因此從平均上來說, 區(qū)域內(nèi)的樣本點更多的落在沿著概率密度梯度的方向.因此,對應(yīng)的, Mean Shift向量應(yīng)該指向概率密度梯度的方向
如上圖所示, 大圓圈所圈定的范圍就是 ,小圓圈代表落入 區(qū)域內(nèi)的樣本點,黑點就是Mean Shift的基準點 ,箭頭表示樣本點相對于基準點 的偏移向量,很明顯的,我們可以看出,平均的偏移向量會指向樣本分布最多的區(qū)域,也就是概率密度函數(shù)的梯度方向
從前面關(guān)于Mean 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可以找到峰值,自然可以作為最優(yōu)化的方法,Mean Shift算法進行最優(yōu)化的關(guān)鍵是要把最優(yōu)化的目標轉(zhuǎn)化成Mean Shift隱含估計的概率密度函數(shù).
[1]The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition (1975)
[2]Mean shift, mode seeking, and clustering (1995)
[3]Mean Shift: a robust approach toward feature space analysis (2002)
[4]Real-time tracking of non-rigid objects using mean shift (2000)
[5]Mean-shift Blob Tracking through Scale Space (2003)
[6]An algorithm for data-driven bandwidth selection(2003)
|
|
