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

蘇建菖 馬燕

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

關鍵詞： 超像素; 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 引言

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

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

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

1 相關算法

1.1 SLIC算法

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

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

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

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

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

⑴

⑵

⑶

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

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

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

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

1.2 k-means算法

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

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

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

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

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

2 改進SLIC算法

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

⑴ 在超像素內選取k-means聚類中心。

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

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

⑷

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

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

3 欠分割超像素處理結果

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

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

4 實驗結果和分析

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

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

⑸

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

⑹

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

⑺

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

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

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

5 結束語

本文針對傳統SLIC算法存在的欠分割現象提出了區域聚類再分割算法。本文實現提出的新算法在不改變原始SLIC分割結果的情況下取得更準確的分割結果。該方法在運行時間上略高于傳統SLIC算法，今后將在研究工作中繼續優化該算法。

參考文獻（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].計算機輔助設計與圖形學學報，2009.21（8）：1127-1