Mean

Shift算法,一般是指一個迭代的步驟,即先算出當前點的偏移均值,移動該點到其偏移均值,然后以此為新的起始點,繼續移動,直到滿足一定的條件結束.

1.

Meanshift推導

給定d維空間Rd的n個樣本點 ,i=1,…,n,在空間中任選一點x，那么Mean

Shift向量的基本形式定義為:

Sk是一個半徑為h的高維球區域,滿足以下關系的y點的集合,

k表示在這n個樣本點xi中,有k個點落入Sk區域中.

以上是官方的說法，即書上的定義，我的理解就是，在d維空間中，任選一個點，然后以這個點為圓心，h為半徑做一個高維球，因為有d維，d可能大于2，所以是高維球。落在這個球內的所有點和圓心都會產生一個向量，向量是以圓心為起點落在球內的點位終點。然后把這些向量都相加。相加的結果就是Meanshift向量。

如圖所以。其中黃色箭頭就是Mh(meanshift向量)。

再以meanshift向量的終點為圓心，再做一個高維的球。如下圖所以，重復以上步驟，就可得到一個meanshift向量。如此重復下去，meanshift算法可以收斂到概率密度最大得地方。也就是最稠密的地方。

最終的結果如下：

Meanshift推導：

那么，meanshift算法變形為

(1)

解釋一下K()核函數，h為半徑，Ck,d/nhd

為單位密度，要使得上式f得到最大，最容易想到的就是對上式進行求導，的確meanshift就是對上式進行求導.

(2)

令：

K(x)叫做g(x)的影子核，名字聽上去聽深奧的，也就是求導的負方向，那么上式可以表示

對于上式，如果才用高斯核，那么，第一項就等于fh,k

第二項就相當于一個meanshift向量的式子：

那么(2)就可以表示為

下圖分析

的構成，如圖所以，可以很清晰的表達其構成。

要使得

=0，當且僅當

=0，可以得出新的圓心坐標：

(3)

上面介紹了meanshift的流程，但是比較散，下面具體給出它的算法流程。

選擇空間中x為圓心，以h為半徑為半徑，做一個高維球，落在所有球內的所有點xi

計算

，如果

>ε, 則利用(3)計算x，返回1.

2.meanshift在圖像上的聚類：

真正大牛的人就能創造算法，例如像meanshift，em這個樣的算法，這樣的創新才能推動整個學科的發展。還有的人就是把算法運用的實際的運用中，推動整個工業進步，也就是技術的進步。下面介紹meashift算法怎樣運用到圖像上的聚類核跟蹤。

一般一個圖像就是個矩陣，像素點均勻的分布在圖像上，就沒有點的稠密性。所以怎樣來定義點的概率密度，這才是最關鍵的。

如果我們就算點x的概率密度，采用的方法如下：以x為圓心，以h為半徑。落在球內的點位xi

定義二個模式規則。

(1)x像素點的顏色與xi像素點顏色越相近，我們定義概率密度越高。

(2)離x的位置越近的像素點xi，定義概率密度越高。

所以定義總的概率密度，是二個規則概率密度乘積的結果，可以(4)表示

(4)

其中：

代表空間位置的信息，離遠點越近，其值就越大，

表示顏色信息，顏色越相似，其值越大。如圖左上角圖片，按照(4)計算的概率密度如圖右上。利用meanshift對其聚類，可得到左下角的圖。

Matlab中meanshift算法

mean-shift

的特點是把支撐空間和特征空間在數據密度的框架下綜合了起來。對圖像來講，支撐空間就是像素點的坐標，特征空間就是對應像素點的灰度或者RGB三分量。將這兩個空間綜合后，一個數據點就是一個5維的向量：[x,y,r,g,b]。

這在觀念上看似簡單，實質是一個飛躍，它是mean-shift方法的基點。

mean-shift方法很寶貴的一個特點就是在這樣迭代計算的框架下，求得的mean-shift向量必收斂于數據密度的局部最大點。可以細看[ComaniciuMeer2002]的文章。

寫了點程序，可以對圖像做簡單的mean-shift filtering，供參考：

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [DRGB, DSD, MSSD] = MScut(sMode, RGB_raw, hs, hf, m

);

% designed for segmenting a colour image using mean-shift

[ComaniciuMeer 2002]

% image must be color

% procedure in mean-shift

% 1. combine support space and feature space to make a mean-shift

space

%?based data description

% 2. for every mean-shift space data

% 3.?do mean-shift

filtering

%?until convergence

% 4. end

% 5. find the converged mean-shift space data that you are

interested in

%?and label it

% 6. repeat the above steps

%

% a?-- data in

support space

% b?-- data in

feature space

% x?-- data in

mean-shift space

% f(.)?-- data density

function

% k(.)?-- profile function

(implicit)

% g(.)?-- profile function

(explicit)

% m?-- mean shift

vector

% hs?-- bandwidth in support

space

% hf?-- bandwidth in feature

space

% M?-- threshold

to make a distinct cluster

%% enter $hs$, $hf$, $m$ if necessary

if ~exist('hs')

hs = input('please enter

spatial bandwidth (hs):n');

end

if ~exist('hf')

hf = input('please enter

feature bandwidth (hf):n');

end

if ~exist('m')

m = input('please enter

minimum cluster size (m):n');

end

switch upper(sMode)

case 'RGB'

RGB = double(

RGB_raw );

case 'gray'

error('FCMcut

must use colored image to do segmentation!')

end

sz = size(RGB);

mTCUT = Tcut( RGB(:,:,1) ); % trivial segmentation

%% project data into mean-shift space to make $MSSD$ (mean-shift

space data)

mT = repmat([1:sz(1)]', 1, sz(2));

vX = mT(1:end)';?% row

mT = repmat([1:sz(2)], sz(1), 1);

vY = mT(1:end)';?% column

mT = RGB(:,:,1);

vR = mT(1:end)'; % red

mT = RGB(:,:,2);

vG = mT(1:end)'; % green

mT = RGB(:,:,3);

vB = mT(1:end)'; % blue

MSSD = [vX, vY, vR, vG, vB];

%% make $g$ - explicit profile function

disp('Using flat kernel: Epanechnikov kernel...')

g_s = ones(2*hs+1, 2); % 's' for support space

g_f = ones(2*hf+1, 3); % 'f' for feature space

%% main part $$

nIteration = 4;

nData?= length(MSSD); % total

number of data

DSD?= MSSD*0; %

'DSD' for destination space data

for k = 1:nData

%

tMSSD = MSSD(k,:); % 't' for

temp

for l = 1:nIteration

%

mT = abs(

MSSD - repmat(tMSSD, nData, 1));

vT = logical(

(mT(:,1)<=hs).*(mT(:,2)<=hs).*(mT(:,3)<=hf).*(mT(:,4)<=hf).*(mT(:,5)<=hf)

);

v?=

MSSD(vT,:);

% update

$tMSSD$

tMSSD = mean(

v, 1 );

if nIteration

== l

DSD(k,:) =

tMSSD;

end

end

end

% show result

DRGB = RGB * 0;

DRGB(:,:,1) = reshape(DSD(:,3), sz(1), sz(2)); % red

DRGB(:,:,2) = reshape(DSD(:,4), sz(1), sz(2)); % red

DRGB(:,:,3) = reshape(DSD(:,5), sz(1), sz(2)); % red

figure, imshow(uint8(DRGB), [])

總結

以上是生活随笔為你收集整理的matlab中partdata,[转载]meanshift算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。