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

韓俊，王保云

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

0 引言

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

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

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

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

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

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

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

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

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

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

3 MeanShift圖像分割

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 灰度圖和彩色圖分割對(duì)比

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

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

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

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

表1 幾種常見(jiàn)的圖像分割方法分割效果對(duì)比

4 結(jié)語(yǔ)

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

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