基于超像素和K-means的圖像分割算法

蘇建菖 馬燕

摘? 要： 傳統(tǒng)的簡單線性迭代聚類（SLIC）超像素算法在圖像細節(jié)處容易產(chǎn)生欠分割問題，文章對超像素塊采用K-means算法進一步聚類，并按聚類中心定義了相似度，對于相似度大于預(yù)設(shè)閾值的超像素塊，視其為欠分割區(qū)域，對該超像素塊保留K-means聚類結(jié)果。實驗結(jié)果表明，本文算法在分割準確率等各項指標上均優(yōu)于SLIC算法。

關(guān)鍵詞： 超像素; SLIC; K-means; 圖像分割

中圖分類號：TP317.4? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2019）02-58-03

Image segmentation algorithm based on superpixel and K-means

Su Jianchang， Ma Yan

（The College of Information， Mechanical and Electrical Engineering， Shanghai Normal University， Shanghai 201418， China）

Abstract： The traditional simple linear iterative clustering （SLIC） superpixel algorithm will lead to the issue of under-segmentation in the detail of image. This paper proposes to cluster the superpixel with K-means algorithm， the similarity degree is defined according to the cluster centers. For the superpixel whose similarity degree is greater than the predefined threshold， it will be seen as under-segmentation region and the clustering result of K-means will retain. The experimental results show that the proposed algorithm is superior to the SLIC algorithm with respect to the accuracy of segmentation.

Key words： superpixel; SLIC; K-means; image segmentation

0 引言

近年來，超像素的研究在計算機視覺與圖像處理等領(lǐng)域備受關(guān)注。通過超像素算法，將顏色相近的像素聚類視為同一區(qū)域，從而可進一步降低后期運算的復(fù)雜度，該算法通常被用于圖像預(yù)處理[1]，因此超像素算法被廣泛應(yīng)用于圖像分割，目標識別，視頻分割等計算機視覺領(lǐng)域。

超像素算法能分割出具有一定尺寸的像素塊。利用超像素，可以將圖像分割成具有語義相同的子塊，并且保留對象的邊界信息。目前，常用的超像素分割算法主要有Ncut（Normalized Cuts）[2]，Mean-shift[3]，SLIC[4]等。ACHANTA提出的SLIC（simple linear iterative clustering）算法在召回率、分割準確率、計算存儲效率等方面均具有一定優(yōu)勢。但是該方法在圖像細節(jié)處的分割效果較差，超像素塊的分割不準確，不同區(qū)域被歸類為同一超像素塊中，從而會產(chǎn)生欠分割的超像素塊。

對于SLIC超像素塊欠分割的問題，本文提出一種基于SLIC和k-means的圖像分割算法。首先，利用SLIC算法對圖像進行初步分割，得到超像素塊;接著，對各超像素塊分別進行k-means聚類，根據(jù)聚類中心定義相似度，并進一步檢測屬于欠分割的超像素塊，對于欠分割超像素塊則保留k-means聚類結(jié)果。

1 相關(guān)算法

1.1 SLIC算法

在SLIC算法中，首先將圖像從RGB顏色空間轉(zhuǎn)換到CIE-Lab顏色空間，對應(yīng)的每個像素的（L，a，b）顏色值和（x，y）坐標位置組成特征空間[L，a，b，x，y]，在該特征空間內(nèi)對所有像素進行聚類，兩個像素的相似性可由它們顏色空間的相似度與位置空間的向量距離來度量，相似度越小，距離越大，則相似性越小。根據(jù)此項準則，算法具體步驟如下。

⑴ 初始化聚類中心點。SLIC算法首先根據(jù)輸入?yún)?shù)確定超像素的數(shù)目，并以此確定聚類中心數(shù)目。算法將依據(jù)步長將聚類中心特征向量，i=1，2，3，…，K。N表示圖像內(nèi)所有像素數(shù)目，K表示超像素的數(shù)目。

⑵ 優(yōu)化初始聚類中心分布。算法根據(jù)所有像素點的Lab顏色梯度，將聚類中心顏色梯度值與其鄰域內(nèi)各像素顏色梯度值進行比較，并將聚類中心移至梯度最小值處，這樣就確保初始聚類中心不會在邊緣處出現(xiàn)，進一步保證后續(xù)分割的準確性。

⑶ 計算像素點與聚類中心的距離D。這一步驟類似k-means算法，通過不斷迭代計算每個像素點到聚類中心的距離D，將每個像素點歸類為距離最近的聚類中心。

像素點到聚類中心的距離D公式定義如下：

⑴

⑵

⑶

其中，j表示第j個像素點，i表示第i個聚類中心，dc和ds分別表示顏色距離和坐標距離，Ns為類內(nèi)最大空間距離，可以將Ns設(shè)置為步長S，且Ns=S，Nc為最大顏色距離，隨圖像不同而不同。

與k-means不同的是，SLIC算法只在每個聚類中心的2s×2s鄰域內(nèi)計算像素點與聚類中心的距離，而k-means算法則不需要界定距離，即在全局內(nèi)搜索。圖1列出了SLIC與k-means在搜索范圍上的區(qū)別。

⑷ 像素點分類。根據(jù)最小距離準則，將像素分類至距離最小的聚類中心，并再次迭代上述過程更新聚類中心，直至達到最大迭代量或聚類中心不再變化。

⑸ 聚類優(yōu)化。利用連通性，將多連通、區(qū)域面積過小等區(qū)域與相鄰區(qū)域合并。至此圖像被分為多個超像素像素。

1.2 k-means算法

k-means聚類是無監(jiān)督學習的一種典型的聚類算法，其主要任務(wù)是將圖片分為多個類或簇，同一簇內(nèi)的像素相似度盡可能大，而不同簇間的像素相似度盡可能小。k-means聚類通常通過歐式距離計算相似度。該算法具體如下：

⑴ 隨機從圖片中選取K個點作為初始聚類中心;

⑵ 計算圖片上所有像素到聚類中心的距離，把像素歸到離它最近聚類中心所在的類;

⑶ 計算新形成的每一個聚類像素的平均值，更新得到新的聚類中心;

⑷ 更新迭代直至聚類中心不再變化，則聚類函數(shù)已收斂。

2 改進SLIC算法

在傳統(tǒng)的SLIC算法中，有的超像素塊分割不夠完全，如圖2綠色圈中區(qū)域所示。為解決SLIC算法的欠分割問題，本文對欠分割區(qū)域進行再聚類，以得到更精細的分割效果。

⑴ 在超像素內(nèi)選取k-means聚類中心。

k-means算法的缺點之一是需要預(yù)先給出簇總數(shù)k，并且難以估計。本文算法取K=2對每個超像素塊進行k-means聚類，顏色空間為RGB顏色空間。假設(shè)有個超像素，則總共需進行m次k-means聚類。進行k-means聚類后重新計算并獲取超像素塊的聚類中心Ci，Cj，其中Ci，Cj的值分別表示[Ri，Gi，Bi]，[Rj，Gj，Bj]。

⑵ 計算超像素內(nèi)的兩類相似度。對已進行k-means聚類的超像素區(qū)域在RGB顏色空間內(nèi)采用歐式距離計算兩類相似度dRGB，公式表示如下：

⑷

對于dRGB>ξ的超像素，則認為該超像素欠分割，可以進一步分割，則將k-means聚類結(jié)果作為分割結(jié)果。這里，ξ為預(yù)設(shè)閾值，經(jīng)大量實驗，本文設(shè)置閾值ξ=280。欠分割區(qū)域如圖3所示，天空與樹枝被分配到同一個超像素內(nèi)。

⑶ 對欠分割的超像素重新標定類別。在對超像素執(zhí)行k-means聚類時選擇k=2，聚類后得到0，1兩種標簽，分別用紅色與藍色表示兩種類別。若超像素塊內(nèi)有兩種顏色，則表明該超像素已進行聚類再分割。

3 欠分割超像素處理結(jié)果

使用本文算法對圖2所示圖像進行超像素分割，結(jié)果如圖4所示。圖中欠分割區(qū)域已全部進行區(qū)域聚類后再分割，分割精細度高，效果良好，且在分割良好區(qū)域保留了SLIC的原始分割結(jié)果。樹枝與天空融合的超像素已被再分割為兩類。

欠分割區(qū)域再分割效果如圖5所示，對于同一超像素內(nèi)的樹枝與天空背景進行了準確分割。

4 實驗結(jié)果和分析

將本文算法與SLIC算法進行了對比實驗，其中采用基于分割區(qū)域、基于分割邊界的評價指標的評價指標如下[5]。

CUE（Corrected Undersegmentation Error）：CUE是基于分割區(qū)域的評價指標，反應(yīng)人工分割結(jié)果與超像素分割結(jié)果重合度。其計算公式如下：

⑸

其中sk是第k塊超像素，gi是第塊人工分割區(qū)域，gmax（sk）為與人工分割區(qū)域的最大重疊面積，定義式如下：

⑹

基于分割邊界的評價指標主要是邊界召回率BR（Boundary Recall）：該指標用來體現(xiàn)超像素分割與人工分割邊界的吻合度，算法的邊界召回率越高，表示其生成的分割邊界與真實邊界越接近，其計算公式如下：

⑺

B（s）表示人工分割的輪廓集，B（g）表示超像素分割結(jié)果。p為人工分割輪廓線上的點，q為超像素分割輪廓線上的點，I[·]函數(shù)用于確定超像素輪廓中在距離內(nèi)是否存某點與當前人工分割輪廓的上的點p（ε=2）。

使用本文算法得到的分割結(jié)果與傳統(tǒng)SLIC算法進行對比，各項指標結(jié)果如圖6所示。從中可見，本文算法在各項指標上均優(yōu)于傳統(tǒng)SLIC算法。

為了驗證本文算法的運算效率，分別在超像素數(shù)量K取不同值的情況下與傳統(tǒng)SLIC進行對比。實驗結(jié)果見表1。從表1可見，本文提出的新算法與傳統(tǒng)SLIC算法相比運行時間較慢，但綜合分割準確率與運行時間考慮，本文提出算法在整體運行效果上要優(yōu)于傳統(tǒng)SLIC算法。

5 結(jié)束語

本文針對傳統(tǒng)SLIC算法存在的欠分割現(xiàn)象提出了區(qū)域聚類再分割算法。本文實現(xiàn)提出的新算法在不改變原始SLIC分割結(jié)果的情況下取得更準確的分割結(jié)果。該方法在運行時間上略高于傳統(tǒng)SLIC算法，今后將在研究工作中繼續(xù)優(yōu)化該算法。

參考文獻（References）：

[1] Hsu C Y， Ding J J. Efficient image segmentation algorithmusing SLIC superpixels and boundary-focused region merging[C]// Communications and Signal Processing.IEEE，2014：1-5

[2] Shi J， Malik J. Normalized Cuts and Image Segmentation[J].IEEE Trans.pattern Anal.mach.intell，2000.22（8）：888-905

[3] Comaniciu D， Meer P. Mean shift： a robust approachtoward feature space analysis[J]. IEEE Trans Pattern Analysis & Machine Intelligence，2002.24（5）：603-619

[4] Achanta R， Shaji A， Smith K， et al. SLIC superpixelscompared to state-of-the-art superpixel methods.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2012.34（11）：2274-2282

[5] 葉偉，王遠軍.基于Mumford-Shah理論的最小生成樹圖像分割方法[J].計算機輔助設(shè)計與圖形學學報，2009.21（8）：1127-1