MeanShift算法在圖像分割中的應(yīng)用

韓俊，王保云

（1.云南師范大學(xué)信息學(xué)院，昆明 650500；2.云南師范大學(xué)數(shù)學(xué)學(xué)院，昆明 650500）

0 引言

近年來，大數(shù)據(jù)時代的到來促使計算機視覺技術(shù)飛速發(fā)展，圖像分割是計算機視覺中的重要技術(shù)。圖像分割就是把圖像分成若干個特定的、具有獨特性質(zhì)的區(qū)域，提出感興趣目標的技術(shù)和過程。圖像分割被廣泛應(yīng)用于地理、軍事、醫(yī)學(xué)和人工智能中。

圖像分割的方法眾多，不同學(xué)者對分割方法的概括不同［1-2］?？偟恼f來，圖像分割可分為5類：基于閾值的分割、基于區(qū)域的分割、基于邊緣的分割、基于特定理論的分割和基于神經(jīng)網(wǎng)絡(luò)的分割。MeanShift是密度類聚類算法的一種，用作圖像分割時屬于特定理論的分割方法。Mean-Shift于1975年由Fukunaga等［3］提出，他們使用了密度梯度對樣本進行估計的方法，并用核函數(shù)對MeanShift中樣本進行加權(quán)。Silverman B［4］提出的無參數(shù)核密度估計方法為MeanShift對樣本的估計提供了系統(tǒng)的證明。Cheng Y等［5］介紹常用核函數(shù)原理并提出更多適用的核函數(shù)，為每個帶寬內(nèi)的樣本分配權(quán)重，使得隨著樣本與被偏移點的距離不同，其偏移量對均值偏移向量的貢獻也不同。文中對MeanShift算法應(yīng)用于圖像分割進行了實驗，驗證了算法良好的分割效果。

1 MeanShift算法理論基礎(chǔ)

給定d維空間Rd中的n個樣本點xi，i=1,…n，在x點的MeanShift向量為:

其中,Mh(x)稱為MeanShift向量，圖1中的寬箭頭所示。Sh是一個半徑為h的高維球區(qū)域，圖1中實線大圈所示。xi表示在高維球區(qū)域內(nèi)的樣本點，圖1中黑點所示。x表示初始聚類中心點，圖1中的實線小圈中心位置。k表示在這n個樣本點xi中,有k個點落入Sh區(qū)域中。

圖1Sh區(qū)域內(nèi)MeanShift示意圖

式（1）是對高維球中的樣本權(quán)重做均值計算，距離x點近的xi應(yīng)該有更高的權(quán)重。引入核函數(shù)［3］和w(xi)［5］對MeanShift中樣本進行加權(quán)的方法，將MeanShift算法擴展為如下形式：

其中，w(xi)≥0是一個賦給樣本點xi的權(quán)重，G(x)是一個單位核函數(shù)，G(x)=g(‖x2‖)，h是核函數(shù)的帶寬。在模式識別中，處理圖像時經(jīng)常用到的核函數(shù)如：Epanechnikov核、Uniform核和高斯核函數(shù)。

若不考慮權(quán)重w(xi)，通過式（2），計算某一次聚類中心與帶寬內(nèi)樣本間的MeanShift向量為：

式（4）中mh(x)為x加上Mh(x)后新聚類中心的位置，圖1中虛線小圈中心位置。

3 MeanShift圖像分割

圖像有分辨率和色彩等屬性，用一種核函數(shù)或者固定的核帶寬h并不能達到理想的處理結(jié)果。Comaniciu，Dorin等人［6］提出了空間域（分辨率）帶寬hs和色域（色彩）帶寬hr，并將空間域和色域統(tǒng)稱為聯(lián)合域?？梢杂煤撕瘮?shù)Khs,hr來估計圖像中樣本點x=(xs,xr)在聯(lián)合域上的分布：

其中，p是色彩通道，C為一個歸一化常數(shù)。當(dāng)p=1表示一個灰度圖像，p=3表示三通道的彩色圖像，p＞3表示高維圖像，比如衛(wèi)星圖像。

圖像分割時，對聚為同一類的點取模態(tài)點（MeanShift迭代收斂的點）的色值，并選擇性的對小于M個像素值的區(qū)域進行合并。下面是使用MeanShift在聯(lián)合域上對彩色圖像進行分割的步驟。

定義xi和zi，i=1,…,n,分別為濾波前的圖像和濾波后的圖像，Li為第i個像素對應(yīng)的標簽。給定收斂界限ε，將mh(x)替換成yj+1，并且?guī)雋s和hr，則mh(x)變?yōu)槿缦碌腗eanShift形式：

（1）初始化j=1,yi,1=xi。

（2）根據(jù)式（5）計算yi,j+1，使得yi,j+1-yi,j收斂到ε，令zi=yi,c，yi,c為收斂后的位置。

（3）在聯(lián)合域中，將距(hs,hr)窗口最近的模態(tài)點組成一類，用{Cp}p=1,…,m來表示。

（4）對于每一個i=1,…,n，賦值Li={p|zi∈Cp}，即：對于第i個像素，將符合p的包含在Cp中的zi賦值給標簽Li。

（5）可選項：消除分割中總像素小于M的空間區(qū)域（M根據(jù)實際情況而定）。

將同屬于標簽Li區(qū)域中的像素色值更新為最后的模態(tài)點色值。迭代所有像素點，最終達到分割目的。下面是使用Uniform核對圖像分割的效果。

圖2 不同hs、hr和M對圖像分割的影響

圖2 不同hs、hr和M對圖像分割的影響（續(xù)）

可以看出，色域帶寬和最小合并像素控制著分割的區(qū)域數(shù)，分辨率帶寬對分割結(jié)果的影響較小。

圖3中，由于狗與草地在灰度圖中灰度值相近，在hr大于2后，狗的輪廓已經(jīng)不能保留，此時分割失敗。彩色圖中卻能很好的分割。

圖3 灰度圖和彩色圖分割對比

對圖4中白框區(qū)域做灰度值分析如下。從圖4中可以看出，分割后，聚為同一類的像素具有相同的色值，轉(zhuǎn)化為灰度值圖后更加平滑。

圖4 白框內(nèi)灰度值對比

對圖像的分割方法眾多，為了驗證MeanShift算法在圖像分割中的效果，表1是幾個常用的機器學(xué)習(xí)分割方法和兩個基于深度學(xué)習(xí)的分割方法deeplabv3、MaskRCNN的分割對比。選取了3類圖像進行實驗：第一類為背景、紋理和目標區(qū)域有較大差異，如表1中圖①；第二類為單實例圖像，背景和紋理與目標區(qū)域有較大差異，少噪點如表1中圖②，多噪點如表1中圖③；第三類為多實例圖像，背景、紋理與目標區(qū)域難區(qū)分，難區(qū)分如圖如表1中④，較難區(qū)分如表1中圖⑤。除了邊界分割和層次聚類分割，其他都是在RGB圖像上實現(xiàn)分割。

從表1可以看出，第一類圖像中，深度學(xué)習(xí)的兩種方法未對實例進行訓(xùn)練，分割失敗，其他分割效果良好；第二類圖像中，每種方法都成功分割。閾值、SVM、MeanShift、深度學(xué)習(xí)對表1中圖②分割效果優(yōu)于其他幾種。閾值、Mean-Shift、深度學(xué)習(xí)對表1中圖③分割效果優(yōu)于其他幾種；第三類圖像中，MeanShift、深度學(xué)習(xí)對表1中圖④分割效果良好、其他分割效果較差。深度學(xué)習(xí)對表1中圖⑤分割效果良好、其它分割效果較差。

表1 幾種常見的圖像分割方法分割效果對比

4 結(jié)語

在圖像分割中，隨著圖像復(fù)雜程度的提升，MeanShift的聚類分割方法比其他傳統(tǒng)的分割方法有更好的分割效果?；谏疃葘W(xué)習(xí)的方法能帶來更好的分割效果，但深度學(xué)習(xí)的方法仍然存在問題，如訓(xùn)練成本高、計算量大等。必須是預(yù)先訓(xùn)練過的實例，否則無法分割。MeanShift則具有不需要預(yù)訓(xùn)練、計算量小和易部署的特點。Mean-Shift是無參數(shù)的聚類方法，有著諸多優(yōu)點，但算法中核函數(shù)的選擇和核帶寬的設(shè)定，對算法的收斂速度和計算量有著重要影響。核帶寬h的選取關(guān)系著迭代速度和迭代后的效果，h過大存在過分割情況，h過小存在欠分割情況。

仍然有大批學(xué)者對MeanShift進行研究、探討和改進，進一步提高算法的運算速度和結(jié)果準確性。趙勝男［7］提出了一種快速均值漂移的方法，李宏益等［8］提出并行運行算法的方法，他們提高了算法運行的速度。熊平等［9］使用區(qū)域相似性準則對分割不明顯的區(qū)域進行合并。王晏等［10］在HSV色域中，定義了以高維球內(nèi)樣本點到基準點的顏色差值為核心的w(xi)計算函數(shù)，對圖像分割取得了不錯的效果。在大數(shù)據(jù)領(lǐng)域，MeanShift無參數(shù)的核密度聚類方法是一個很好的數(shù)據(jù)挖掘工具［11-13］。對MeanShift算法的改進和應(yīng)用絕對不止文中所闡述的方向。如何降低算法復(fù)雜度，更有效的提升算法處理效果，需要廣大學(xué)者做更進一步的研究。