優化加權核K-means聚類初始中心點的SLIC算法*

楊 艷，許道云

貴州大學 計算機科學與技術學院，貴陽 550025

1 引言

所謂超像素（superpixel）是指圖中局部的、具有一致性的、能夠保持一定圖像局部結構特征的子區域，這些小區域大多保留了進一步進行圖像分割的有效信息。近年來，超像素作為一種圖像預處理技術，被廣泛應用于計算機視覺領域，逐漸成為研究熱點之一。2003年，Ren等人[1]首次提出了超像素的概念并應用于圖像分割中，經過不斷的發展，超像素在圖像分割領域的應用日益成熟。除此之外，超像素分割算法還被應用于圖像處理的各個方面，如前景提取算法、目標識別算法等。至今，針對超像素分割算法的研究取得了豐碩的成果[2-5]，在各種各樣的應用場景[6-8]中，不同的超像素分割算法被提出。目前，已有的超像素分割算法可分為兩類：基于圖論的算法和基于梯度下降的算法。基于圖論的算法是將分割問題轉化為能量函數最小化問題，將圖像中的像素點看作圖節點，并賦予節點與節點間的邊適當的權值，然后采用各種分割標準對圖進行劃分來形成超像素。基于梯度下降的算法是從最初的像素聚類開始，采用梯度法迭代修正聚類結果直至滿足收斂條件，從而形成超像素。表1提供了這兩類方法中相關算法的性能對比結果。

所有超像素分割算法在Berkeley SegmentationDatabase公共數據集上進行實驗，通過邊緣貼合度，包括“欠分割錯誤率（under-segmentation error）”和“邊緣召回率（boundary recall）”，來評估算法的性能。在表1中，基于圖論的經典算法有Shi等人提出的NC05算法以及Moore等人[9]提出的SL08算法。NC05算法利用輪廓特征和紋理特征遞歸地進行圖像分割，該算法生成規則的超像素，但邊緣貼合度較差，計算速度較慢。SL08算法采用尋找最優路徑的方式不斷地在垂直和水平方向將圖像分割成較小的區域，從而得到超像素。Veksler等人[10]提出的Compact Superpixels和Constant-Intensity Superpixels兩種超像素分割算法（簡稱GCa和GCb）是基于同一全局能量模型下的兩種變形，其基本思想是將相互重疊的圖像塊拼接起來，使任意像素只屬于其中一個圖像塊。GCa和GCb算法各有優劣，前者生成緊密的超像素，而后者生成的超像素邊緣貼合度較好。基于梯度下降的經典算法有Comaniciu等人[11]提出的MS02算法、Levinshtein等人[12]提出的TP09算法以及Achanta等人[13]提出的簡單線性迭代聚類算法（simple linear iterative clustering，SLIC）。MS02算法通過定位密度函數的局部最大，對具有相同模點的像素進行聚類，實現超像素分割，該算法生成的超像素很不規則。TP09算法利用幾何流的水平集方法，對初始化種子點進行逐步碰撞，實現超像素分割，該算法生成的超像素形狀規則，但邊緣貼合度較差。SLIC算法通過引入顏色距離和空間距離的相似性度量，采用簡單的K-means聚類算法生成超像素。SLIC算法雖然能夠生成較規則的超像素，但容易出現欠分割現象。

Table 1 Comparison of existing superpixel segmentation algorithms表1 現有超像素分割算法對比

雖然簡單線性迭代聚類算法（SLIC）根據像素的顏色和距離特征進行聚類能實現良好的分割結果，但是存在如下幾個問題：（1）SLIC算法實質上是K-means算法在特定場合的一種次優快速方案，K-means聚類的缺點是，算法要求先給出K值，但實際上K值很難估計。其次，算法根據原始聚類中心確定初始分割然后進行優化，而原始集群中心的選擇影響聚類結果的穩定性，從而導致局部最優而非全局最優。（2）有限的超像素容易出現欠分割的情況。因此，本文提出一種新的算法WKK-SLIC，基于圖像像素之間的顏色相似性和空間相似性度量，采用超像素分割的歸一化割（normalized cuts）公式。不同于傳統的基于特征的算法，WKK-SLIC算法使用核函數來近似相似性度量，將像素值和坐標映射到高維特征空間中，通過對該特征空間中的每個點賦予適當的權重，使加權K均值和歸一化割的目標函數的優化在數學上等價。因此，可以通過在所提出的特征空間中迭代地應用簡單的K-means聚類來優化歸一化割的目標函數。同時，采用密度敏感的相似性度量計算空間像素點的密度，啟發式地生成K-means聚類的初始中心以達到穩定的聚類結果。實驗結果表明，WKK-SLIC算法在評估超像素分割的幾個標準上優于SLIC算法。

2 SLIC超像素分割算法

簡單線性迭代聚類算法的思想是在圖像上均勻初始化K個初始聚類中心，將所有點賦予與其距離最近的聚類中心標簽。SLIC算法默認只需要設定參數K，K是目標超像素數量。首先，根據K計算出超像素的平均長和寬，初始化超像素中心，讓超像素中心初始值完全均勻地分布在整張圖像上。若圖片大小N為width×height，超像素的初始中心位置應該是網格狀分布，長和寬方向上的步長分別為為了計算方便，算法設定超像素間的間隔長和寬方向都是這樣會導致最右邊和最下邊的超像素初始覆蓋半徑很小。為了避免初始超像素中心落在物體邊界，算法讓每個超像素中心在當前3×3像素范圍內找一個顏色梯度最小的種子位置，平移此超像素中心到其種子位置。初始的各個種子位置就是超像素的中心位置。同時，算法限定在超像素中心點2S×2S的區域搜索與中心點相似的像素而不是整個圖像區域來提高算法的計算速度。每個像素點用五維空間中的一個點來表示，則像素點與超像素中心的相似性測量如下：

其中，dlab是CIELAB顏色空間中像素點之間的顏色距離；dxy是像素點間的空間距離；m是權衡顏色距離和空間距離重要性的一個常數參數。算法使用L2范數來計算當前超像素中心位置和新的超像素中心位置之間的殘差誤差E，重復迭代地更新超像素中心，直至誤差E收斂，算法結束。

SLIC算法整體流程如下。

算法1SLIC超像素分割算法

Fig.1 Segmentation results of SLIC algorithm圖1 SLIC算法的分割結果

圖1是使用SLIC算法進行圖像分割的結果，其中（a）是原圖BSD-118035，（b）～（d）分別表示目標超像素為200、400、600時的分割結果。圖1顯示，SLIC算法雖然能夠產生較規則的超像素，但在有限的超像素數目內，SLIC算法容易出現欠分割的情況（圖中用紅色框標注的地方），且目標超像素數目越小欠分割現象越明顯。

3WKK-SLIC算法

針對SLIC算法存在的缺陷，本文提出了一種基于優化加權核K-means聚類初始中心點的SLIC分割算法WKK-SLIC，算法基于圖像像素之間的顏色相似性和空間相似性度量，采用超像素分割的歸一化割公式。不同于傳統的基于特征的算法，WKK-SLIC使用核函數來近似相似性度量，將像素值和坐標映射到高維特征空間中，通過對該特征空間中的每個點賦予適當的權重，加權K均值和歸一化割的目標函數的優化在數學上等價。因此，可以通過在所提出的特征空間中迭代地應用簡單的K-means聚類來優化歸一化割的目標函數。同時，采用密度敏感的相似性度量計算空間像素點的密度，啟發式地生成K-means聚類的初始中心以達到穩定的聚類結果。

3.1 引入核函數來近似相似性度量

WKK-SLIC算法以加權K-means聚類算法的目標函數和歸一化割的目標函數之間的關系為基礎。首先，回顧加權K-means聚類和歸一化割的定義。用小寫的p、q來表示輸入空間中聚類的像素點，w(p)表示對應像素點賦予的權重，K表示聚類的數量，πk表示第k個聚類，ck表示第k個聚類的中心，φ表示將像素點映射到高維空間的函數，則加權核K-means的目標函數定義如下：

加權K-means的目標函數Fk-m可以通過迭代最小化。在歸一化割中每個像素點用圖G=(V,E,W)中的節點來表示，其中V是所有節點的集合，E是所有邊的集合，是像素點間的相似性函數。歸一化割的目的是最大化目標函數FNcuts。FNcuts的定義如下：

為了進一步了解Fk-m和FNcuts之間的關系，引入推論1。其中，式（5）和式（6）可由文獻[14]的結果推導得到。

推論1如果式（5）和式（6）成立，則加權K-means和歸一化割的目標函數的優化在數學上是等價的。

式（5）表示，高維特征空間中兩個向量的加權內積等于輸入空間中兩個對應點之間的相似性。式（6）表示加權K-means聚類中的每個像素點的權重等于對應的歸一化割中該點與其他所有節點的邊的權重的總和。在推論1的兩個充分條件中，式（6）可以通過歸一化割中邊的權重的總和作為加權K-means中的點的權重來實現，然而對于式（5），需要仔細選擇相似性函數。將式（5）重寫為式（7）：

式（7）實際上定義了一個對稱的核函數，因此它必須滿足對應的核矩陣總是半正定的條件。本文用(l,a,b,x,y)五維向量來表示圖像中的每個像素點，為了方便，限定每個變量的范圍在[0,1]。在CIELAB顏色空間，定義兩個像素點之間的相似性度量，如式（8）所示，其中Cs和Cc是衡量空間距離和顏色距離重要性的常系數。式（8）可以寫成式（5）的內積形式，其中φ和w分別定義為式（9）和式（10）：

選擇CIELAB顏色空間是因為歐幾里得距離在該空間中幾乎是均勻的。另外，選用余弦函數作為相似性度量函數是因為使用余弦函數定義的相似性函數W(p,q)能夠滿足式（7）所要求的對應核函數矩陣半正定的要求，φ和w也是根據此進行定義。到此，本文定義了十維的特征空間，使得加權K-means聚類在該特征空間中近似等價于輸入空間中的歸一化割。通過在該十維特征空間中直接應用加權K-means，可以有效地優化歸一化割的目標函數，達到全局的穩定的聚類結果。

3.2 結合密度敏感的相似性度量啟發地生成K-means聚類中心

SLIC算法實質上是K-means算法在特定場合的一種次優快速方案。原始的K-means算法存在如下缺陷：

（1）算法要求事先給定K值，但實際上K值一般很難確定；

（2）對初始聚類中心敏感，不同的初始中心可能會導致不同的聚類結果。

以上缺陷導致SLIC算法生成的超像素不穩定，容易出現欠分割的情況。因此，本文結合密度敏感的相似性度量來計算圖像像素點的密度，啟發地生成初始聚類中心。下面給出相關的定義[15]。

定義1（聚類對象的密度）對于圖像上的像素點，定義pi的密度為：

其中，d(pk,pk+1)表示對象pk、pk+1的歐式距離；σ為密度參數；rij為鏈接像素點pi和pj之間的所有路徑；l代表鏈接像素點pi和pj路徑中像素點的個數。

定義2（聚類對象的鄰域）對于任意像素點p，以p為中心，R為半徑的圓形區域，稱該區域為像素點p的鄰域，記為：

定義3（聚類對象的鄰域半徑）

其中，aver(D)表示所有像素點間距離的平均值；n是圖像像素點的總數；coefR是鄰域半徑調節系數。

基于密度初始化中心點算法的基本思想是首先在圖像上所有像素點集N中選擇密度最大的像素點作為第一個初始中心，然后在像素點集中去除該像素點及其鄰域內的所有像素點，再按同樣的方法確定第二個初始中心點，循環直達初始中心點集M中有K個點。算法描述如下。

算法2基于密度的初始化中心點算法

1.根據定義1計算所有像素點的密度density(pi)，初始化中心點集M={}。

2.選擇密度最大的像素點Pmax={pi|pi∈N,i=1,2,…,n}作為第一個初始中心點，添加到中心點集M中，M=M?{Pmax}，并從像素點集中刪去該對象，即N=N-{Pmax}。根據定義2和定義3計算Pmax鄰域內的所有像素點，并從像素點集N中刪去。

3.重復執行步驟2，直到初始中心點集中有K個中心點，即|M|=K。

4.輸出初始中心點集M，算法結束。

3.3 基于優化加權核K-means聚類初始中心點的SLIC分割算法

在SLIC算法框架的基礎上，結合3.1節和3.2節的內容，基于優化加權核K-means聚類初始中心點的SLIC分割算法（WKK-SLIC）的描述如下。

算法3WKK-SLIC算法

4 實驗結果與分析

WKK-SLIC算法的分割結果如圖2所示，其中（a）是原圖BSD-118035，（b）～（d）分別表示目標超像素為200、400、600時的分割結果。可以看出，與SLIC算法相比，WKK-SLIC算法不僅能生成規則的超像素，且在有限的超像素數內沒有出現欠分割的現象。

為了進一步比較，在Berkeley Segmentation Database公共數據集上進行實驗。采用邊緣貼合度標準，包括邊緣召回率和欠分割錯誤率，來評估算法性能。WKK-SLIC算法和SLIC算法性能對比結果如圖3所示。

邊緣召回率指落在至少一個真值邊緣像素點距離ε（通常ε取兩個像素）范圍內的超像素邊緣像素點數量與真值邊緣像素點總數的比值，邊緣召回率越高，生成的超像素越規則。本文采用文獻[16]中的邊緣召回率計算方法。

欠分割錯誤率衡量了超像素區域“溢出”真值區域邊界的比例，欠分割錯誤率越低，生成的超像素越純潔。由于處理不同區域間邊緣像素的方法不同，目前該標準存在多種計算模型[17]，本文采用的是文獻[18]提出的CUE（corrected under-segmentation error）計算模型。

Fig.2 Segmentation results of WKK-SLIC algorithm圖2WKK-SLIC算法的分割結果

Fig.3 Performance comparison results of WKK-SLIC algorithm and SLIC algorithm圖3WKK-SLIC算法和SLIC算法的性能對比結果

圖3（a）顯示對于不同數目的目標超像素，WKKSLIC算法比原始的SLIC算法有更低的欠分割錯誤率。圖3（b）顯示對于不同數目的目標超像素，WKKSLIC算法比原始的SLIC算法有更高的邊緣召回率。

5 結束語

本文在原始SLIC算法框架的基礎上，將圖像像素點映射到高維空間，引入核函數來近似像素相似性度量，同時使用基于密度的初始化中心點算法來初始化聚類中心，提出一種基于優化加權核K-means聚類初始中心點的SLIC分割算法WKK-SLIC。該算法生成的超像素規則且分割結果能夠保持圖像的全局屬性。實驗結果表明，WKK-SLIC算法在超像素分割中幾個常用的評價標準方面優于SLIC算法。

[1]Ren Xiaofeng,Malik J.Learning a classification model for segmentation[C]//Proceedings of the 9th International Conference on Computer Vision,Nice,Oct 13-16,2003.Washington:IEEE Computer Society,2003,1:10-17.

[2]Achanta R,Shaji A,Smith K,et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(11):2274-2282.

[3]Wang Chunyao,Chen Junzhou,Li Wei.Review on superpixel segmentation algorithms[J].Application Research of Computers,2014,31(1):6-12.

[4]Xu Chenliang,Corso J J.Evaluation of super-voxel methods for early video processing[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition,Providence,Jun 16-21,2012.Washington:IEEE Computer Society,2012:1202-1209.

[5]Rao Qian,Wen Hong,Yu Wen,et al.Review about superpixels and its applications[J].Computer and Information Technology,2013,21(5):1-3.

[6]Zhu Fengqing,Bosch M,Khanna N,et al.Multiple hypotheses image segmentation and classification with application to dietary assessment[J].IEEE Journal of Biomedical and Health Informatics,2015,19(1):377-388.

[7]Felzenszwalb P F,Huttenlocher D P.Efficient graph-based image segmentation[J].International Journal of Computer Vision,2004,59(2):167-181.

[8]Harary S,Kropf N S,Marder M,et al.Image segmentation:US,Patent 9,300,828[P].2016-03-29.

[9]Moore A P,Prince S J D,Warrell J,et al.Superpixel lattices[C]//Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition,Anchorage,Jun 23-28,2008.Washington:IEEE Computer Society,2008:1-8.

[10]Veksler O,Boykov Y,Mehrani P.Superpixels and supervoxels in an energy optimization framework[C]//LNCS 6315:Proceedings of the 11th European Conference on Computer Vision,Heraklion,Sep 5-11,2010.Berlin,Heidelberg:Springer,2010:211-224.

[11]Comaniciu D,Meer P.Mean shift:a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.

[12]Levinshtein A,Stere A,Kutulakos K N,et al.TurboPixels:fast superpixels using geometric flows[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(12):2290-2297.

[13]Achanta R,Shaji A,Smith K,et al.SLIC superpixels,149300[R].2010.

[14]Dhillon I S,Guan Yuqiang,Kulis B.Weighted graph cuts without eigenvectors a multilevel approach[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(11):1944-1957.

[15]Wang Zhong,Liu Guiquan,Chen Enhong.AK-means algorithm based on optimized initial center points[J].Pattern Recognition andArtificial Intelligence,2009,22(2):299-304.[16]Van den Bergh M,Boix X,Roig G,et al.SEEDS:superpixels extracted via energy-driven sampling[C]//LNCS 7578:Proceedings of the 12th European Conference on Computer Vision,Florence,Oct 7-13,2012.Berlin,Heidelberg:Springer,2012:13-26.

[17]Neubert P,Protzel P.Superpixel benchmark and comparison[C]//Proceedings of Forum Bildverarbeitung,Karlsruhe,2012:1-12.

[18]Buyssens P,Gardin I,Ruan Su,et al.Eikonal-based region growing for efficient clustering[J].Image and Vision Computing,2014,32(12):1045-1054.

附中文參考文獻：

[3]王春瑤,陳俊周,李煒.超像素分割算法研究綜述[J].計算機應用研究,2014,31(1):6-12.

[5]饒倩,文紅,喻文,等.超像素及其應用綜述[J].電腦與信息技術,2013,21(5):1-3.

[15]汪中,劉貴全,陳恩紅.一種優化初始中心點K-means算法[J].模式識別與人工智能,2009,22(2):299-304.