基于局部模糊聚類的超像素分割算法

龍建武，陳鴻發，鄢澤然，朱江洲

(重慶理工大學 計算機科學與工程學院， 重慶 400054)

圖像是有效傳遞信息的主要方式之一，良好的分割算法能為圖像理解帶來巨大的幫助。Ren等[1]首次提出了超像素的概念，超像素分割是將圖像劃分成具有一定視覺感知意義的原子區域，每個區域內的像素具有高度的相似性，從而提供一種簡明的圖像表示形式。超像素顯著地降低了圖像后續處理的復雜度，提高了處理效率。超像素分割正逐步成為越來越受歡迎的圖像預處理技術，被廣泛用于圖像分割[2-3]、目標識別[4]、目標追蹤[5]、3D重建[6-7]等眾多計算機視覺任務中。直至目前，為生成良好的超像素以滿足各種視覺任務的需要，已有多種超像素分割算法相繼被提出，根據原理的不同主要分為兩類。第一類是基于圖論的能量優化方法，比如規則化圖割算法[8](normalized cuts,NCuts)、熵率算法[9](entropy rate superpixel,ERS)、懶惰隨機游走算法[10](lazy random walk,LRW)。最初Shi等[8]提出的NCuts方法能生成具有良好邊界粘合和規則形狀的超像素，然而歸一化割是計算密集型的，每一次迭代只能產生一個超像素，因此NCuts的計算復雜性非常高。Liu等[9]提出的基于熵率的超像素分割算法(ERS)將超像素分割問題表述為一個目標函數，該函數由一個圖和一個平衡項組成，即計算從圖上的削減成本到生成超像素的熵率。熵率可以幫助將緊湊和均勻的區域組合在一起，這也有利于超像素覆蓋一個關于感知邊界的單一對象，但是ERS超像素的形狀不夠規則。Shen等[10]提出的懶惰隨機游走算法(LRW)是從輸入圖像中獲取每個像素的概率，并使用概率和切換時間獲取初始超像素。LRW引入了新的能量函數，迭代優化初始超像素，但是該方法的分割效率不佳。第二類是基于聚類的特征優化方法，包括簡單線性迭代聚類算法[11](simple linear iterative clustering,SLIC)，線性譜聚類算法[12-13](linear spectral clustering,LSC)，實時DBSCAN聚類算法[14](real-time DBSCAN clustering,DBSCAN)。Achanta等[11]于2012年提出的簡單線性迭代聚類(SLIC)采用K均值聚類方法生成相對較低計算成本的超像素，但面對復雜圖像時不能很好地貼合目標對象邊界。Shen等[14]提出了基于密度的帶噪聲應用空間聚類DBSCAN算法用于超像素分割，DBSCAN算法分為2個階段：在第一個階段，使用DBSCAN將像素聚類成超像素；在第二階段，將小的超像素合并到大的超像素中。該算法具有O(N)的計算復雜度，表現出了非常好的實時性。Li等[12-13]采用的線性譜聚類提取超像素結合了歸一化切割和K均值的優點，能獲得良好質量的超像素。然而，由于計算特征比較復雜，LSC的計算復雜度高。近兩年，一些新的超像素分割算法相繼被提出,包括高斯混合模型超像素算法[15]( gaussian mixture model superpixel.GMMS)和動態隨機游走算法[16](dynamic random walk,DRW),它們擁有著良好的算法性能，但同時也存在著不足之處。

雖然上述方法各具優勢，但一直以來提出一種實時的、邊界貼合與規則性相適應的、超像素數目與迭代次數可控的、算法復雜度較低的超像素分割算法都是一個非常具有挑戰性的研究問題。通過上述分析，以往的超像素分割算法大部分都是通過設計不同的能量優化函數進行硬劃分，對于簡單圖像能夠得到很好的效果，但在處理復雜圖像時分割效果不盡如人意，或者是采用的能量優化函數包含的特征較多導致算法復雜度較高，因此如何保證算法復雜度與分割效果兩者之間的平衡是值得深入研究的問題。為滿足這些要求，本文提出一種基于局部模糊聚類的超像素分割算法，這是FCM算法首次應用于超像素分割。超像素用于代替像素進行更緊湊的視覺表示，并作為大量圖像處理應用的一個重要的預處理步驟，它的計算成本是最受關注的問題之一。在這些超像素算法中，SLIC算法、DBSCAN算法等已成為較為流行的算法，因為它可以在不耗費太多成本的情況下快速生成超像素，但其仍有許多空間可提高。一種理想的超像素方法不僅需要滿足良好邊界粘附的要求，而且還需要高效。由于在視覺應用中使用了超像素分割作為預處理步驟，所以優先選擇具有較少計算的高質量超像素分割算法。本文提出的局部FCM超像素分割算法繼承了現有算法比如SLIC、DBSCAN等的優點，并進一步提高了分割效果。本文中將FCM算法用于生成超像素，由于FCM算法是以隸屬度的形式對圖像進行軟化分，它能有效減小復雜圖像中的復雜紋理對分割帶來的影響，以及對圖像中不規則對象的細分也能達到更好的效果。為了更好地利用FCM算法生成性能優良的超像素，對算法的搜索區域進行了幾何限制，同時結合超像素的特點，縮小了隸屬度的計算區域，改進了FCM算法的初始化方法與聚類中心的更新方式。生成超像素的過程主要分為兩步，首先通過FCM聚類算法獲得初始超像素，在該步驟中，聚類中心的更新改為每個超像素的所有像素點向量平均值，這滿足了超像素的規則度的要求。隸屬度矩陣由像素的所屬3×3鄰域超像素的隸屬度組成，而隸屬度計算中包含了像素點與各個聚類中心的向量距離加權。然后，通過顏色和空間信息的測量，將初始的小超像素與其附近的超像素融合在一起。

1 相關方法

1.1 SLIC算法

(1)

(2)

D=dlab+(m/S)dxy

(3)

最后可能出現一些“孤立”超像素，這就需要將“孤立”超像素合并到與鄰近超像素距離度量最小的超像素中，以保證超像素塊的一致性。整個過程如算法1所示。

算法1 SLIC算法

輸入：包含N個像素點的圖像I

輸出：SLIC超像素分割結果

初始化：超像素個數K以及K個像素點作為聚類中心，并將中心移動到鄰域內梯度值最小的像素點處。設定迭代停止閾值E，初始化聚類中心ci，設置迭代計數器t=0。

算法開始：

1：對N個像素計算在搜索范圍內的到聚類中心點的距離，并將該像素點歸入距離最近的聚類。

2：對K個聚類中心點進行更新。

3：如果‖ct-ct+1‖

4：將“孤立”超像素進行合并。

算法結束

1.2 傳統模糊聚類算法

模糊C均值(FCM)算法是一種基于軟化分的聚類算法。FCM算法的目標價值函數為：

(4)

式中：uij∈[0,1]；m是控制聚類效果的參數；ci是模糊簇的聚類中心；dij表示第j個數據點與第i個聚類中心的歐式距離。然后構造帶有約束因子的拉格朗日函數：

(5)

式中：λj是n個約束式的拉格朗日乘子。對式子中uij求導，得到使目標價值函數最小的必要條件：

(6)

(7)

通過迭代更新隸屬度與聚類中心，當目標價值函數幾乎達到最小時，獲得聚類結果。整個過程如算法2所示。

算法2FCM算法

輸入：數據樣本

輸出：數據聚類結果

初始化：給定聚類類別數c，0

算法開始：

1：根據式(6)計算或更新隸屬度矩陣uij。

2：根據式(7)更新聚類中心ci。

3：如果‖ct-ct+1‖

算法結束

傳統FCM算法通過計算隸屬度的形式來確定每一個數據點屬于某個聚類的程度，它的優點是，對于滿足正態分布的數據聚類效果會很好。算法是收斂的，因此得到的模糊隸屬度矩陣具有一致性；它的缺點是，當數據中包含噪聲的時候，聚類效果不好。算法的性能很依賴于初始聚類中心，同時算法是基于全局數據，當數據量特別大時，整個算法就非常耗時，效率低。

針對以上問題，一些典型的改進模糊聚類方法被提出，比如，PCM算法[17]作為一種窮舉型搜索算法，通過改變隸屬度的約束條件來改善聚類效果，它能很好地處理噪音，從而彌補了FCM容易受噪聲影響的不足。但PCM 算法需要一個比較好的初始劃分，以確保準確的聚類，這是一個難解決的問題；AFCM算法[18]通過對度量方式進行非線性變化，從某種程度上改善了聚類結果，但算法變得更加復雜，這種改變度量方式得到的聚類算法在數據尺度發生改變的時候，會比較敏感，可能會導致很糟糕的聚類結果，所以其適用性并不廣泛；Wang等[19]提出了一種使聚類中心的搜索范圍限制在直方圖峰值附近的新的FCM算法，該算法加快了收斂速度，但是它僅僅適用于有明顯峰值的聚類樣本；反之，則不適用。從以上分析可以看出，這些改進的模糊聚類算法各具優點，但同時也存在著許多不足之處，因此，對模糊聚類算法提出更好的改進是非常有必要的。

2 本文算法

根據在分割過程中，優化圍繞種子點像素搜索相鄰像素的搜索策略，利用FCM對復雜圖像的像素以隸屬度的形式進行聚類，提出了一種基于局部模糊聚類的超像素分割算法。傳統意義上的FCM算法的搜索方式是基于全局的，其搜索區域如圖1所示，并且聚類中心的更新也是基于全局的，對于圖像這種包含大量像素點的數據來說，相應的計算復雜度非常高，效率也非常低。所以為了與對圖像進行超像素分割相適應，需要對傳統的模糊聚類算法進行改進。Lab顏色模型由3個要素組成，L表示亮度，a表示的顏色通道的范圍是從綠到紅，b表示的顏色通道的范圍是從藍到黃。Lab顏色模型優點在于色域寬闊，包含了RGB顏色模型的所有色域，同時彌補了RGB色彩分布不均的不足。由于在超像素分割過程中需要充分利用像素的顏色信息，所以需要盡量保留寬闊的色域來獲得更完整的顏色信息。而Lab顏色模型能夠很好地符合上述要求，這對在超像素分割過程中提升分割效果有顯著的作用，因此本文算法選擇CIELAB顏色模型。聚類過程從在步長為S的常規網格空間上采樣K個聚類中心Ci=[li,ai,bi,xi,yi]T的初始化步驟開始，生成大小相等的超像素，聚類中心處于與該區域像素向量的平均值相對應的位置。這樣做可以有效避免將超像素種子點設定在邊緣并且減少噪聲像素成為超像素種子點的機會。在圖像中，當每個像素周圍的鄰域像素離該像素越近時，他們之間的相似性就越高，這種分布特點與正態分布的特點比較相似，根據前文中提及的模糊聚類算法對滿足正態分布的像素點的聚類效果會很好的優點，并且考慮到每個像素周圍的鄰域超像素包含了相應數量的像素點，而3×3鄰域大小能夠較好地覆蓋一定鄰域內的像素，在保證覆蓋鄰域內像素的同時避免了像素間差異性過大。因為鄰域過小比如4鄰域就不能完全覆蓋鄰域內像素，鄰域過大比如5×5鄰域會產生鄰域內像素間差異性過大的影響，兩者都會使分割不夠準確，不利于算法的性能。為了最終獲得更好的超像素分割結果，本文算法分配每個像素與被劃分的3×3鄰域的超像素相關聯，改進后的搜索區域如圖2所示。這是加快算法速度的關鍵，因為限制搜索區域的大小會大大減少計算的次數，降低計算復雜度。限制搜索區域大小的先驗信息為超像素個數K值。當K值過大時，每個超像素區域就非常小，對應搜索區域就很小，不能很好的保證信息的完整性；當K值過小時，每個超像素區域就很大，對應搜索區域就很大，此時像素信息過于冗余，會導致劃分結果不夠準確，降低分割效果。所以整個過程需要合理地初始化K值來限制搜索區域的大小。

圖1 FCM算法的搜索區域示意圖 圖2 本文算法的搜索區域示意圖

此處引入FCM算法中隸屬度函數的概念來計算像素對周圍3×3鄰域的超像素的隸屬度u，然后構造與超像素分割相適應的帶有約束因子的拉格朗日函數：

(8)

式中：n代表搜索區域內的像素個數，同時：

dij=dc+ds

(9)

其中：

(10)

(11)

對u和c分別進行求導得到使目標函數J達到最小的必要條件：

(12)

(13)

在實現算法的過程中，首先利用初始化的超像素求像素平均值計算聚類中心，然后確定d，接下來利用式(12)(13)進行迭代更新，直到聚類中心幾乎不再改變，可利用式(14)來控制：

|Jt+1-Jt|

(14)

式中：t是算法迭代次數；E是迭代停止閾值。t與E是給定值以滿足算法達到分割效果的要求。像其他超像素算法一樣，FCM超像素沒有顯式強制連接，在聚類過程結束時，一些不屬于與其聚類中心的“孤立”超像素可能仍然存在。為了解決這一點，這些超像素被指定為最近的聚類中心的標簽。在合并過程中，利用距離函數D計算“孤立”超像素與鄰近超像素之間的距離，距離函數D中包含了顏色距離和空間距離。一個好的超像素不僅要通過將超像素的邊界貼合在物體邊緣的性能來衡量，而且也能保持超像素的均勻大小，本算法利用色差來確定2個初始超像素是否應該合并為一個，空間距離保證了最終超像素的規則性，那么合并距離D被定義為：

D(Ii,p)=α1dc(Ii,p)+(1-α1)ds(Ii,p)

(15)

其中：

(16)

(17)

算法3基于局部模糊聚類的超像素分割算法

輸入：圖像I

輸出：超像素分割結果

初始化：指定超像素個數K，初始化聚類中心c，設定迭代停止閾值E，搜索步長S，設置迭代計數器t=0。

算法開始：

1：在搜索區域內根據式(12)計算或更新隸屬度矩陣uij。

2：根據式(13)更新聚類中心ci。

3：如果‖Jt-J(t+1)‖

4：根據式(15)對“孤立”超像素合并到鄰近超像素區域內得到最終的劃分結果。

算法結束

由于在進行超像素合并時需要同時考慮到顏色信息和空間信息，相比于典型的距離度量方式如傳統歐式距離、馬氏距離以及曼哈頓距離等，本文算法在超像素合并步驟采用的距離度量方式的特點在于，綜合考慮了顏色信息和空間信息，以每個超像素的聚類中心的顏色信息和空間信息代表對應的超像素，將顏色距離和空間距離相結合，并各自賦予相應的權重，顏色距離權重用來控制顏色信息的相似性，空間距離權重用來控制空間信息的影響。而此時對顏色信息的依賴性比對空間信息的依賴性要大，因此賦予較大的顏色距離權重和較小的空間距離權重，這樣可以保證兩者之間的平衡，從而在比較準確地衡量“孤立”超像素和鄰近超像素相似性的同時還能夠保證合并后的最終超像素的規則性。綜上，該距離度量方式優點在于，能夠很好地衡量“孤立”超像素和鄰近超像素的相似性，確保是否應該合并成一個，同時保證了最終超像素的規則性，這符合生成良好超像素的目標。

3 實驗結果與分析

為驗證本文算法的有效性，與現有典型超像素分割算法如ERS算法、SLIC 算法、LRW算法、LSC算法和DBSCAN算法以及近兩年一些新提出的超像素分割算法如GMMS算法和aptDRW算法從視覺、分割精度[20]和實時性等方面進行量化對比。

3.1 數據集

為了定量評價本文超像素分割算法的性能，實驗中選擇 BSDS500和MSRC-V1 2個數據集。BSDSS500是用于邊界檢測和圖像分割的數據集，內容包括從戶外場景、景觀、建筑、動物到人類。它由500張圖片組成，包括200張訓練圖片、100張驗證圖片和200張測試圖片，該數據集中每張圖片的大小為321×481或481×321。MSRC-V1是用于目標識別和圖像分割的數據集，內容包括建筑、景觀和動物等9個類別，總共240張圖片。

3.2 評價標準

在對圖像進行超像素分割中，高分割精度是最關鍵和最基本的要求。本文采用常用的準確性定量比較指標，包括邊界召回率(BR，boundary recall)和欠分割誤差(UE，under-segmentation error)。

邊界召回率BR是衡量超像素算法中邊界粘附性能的重要指標。邊緣召回率BR定義為與超像素邊緣的距離小于2像素的真實邊緣在所有真實邊緣中所占的比例，邊緣召回率越高，意味著很少有真正的邊界被忽略。邊界召回率BR的計算公式如下：

(18)

式中：B(si)和B(gj)分別表示超像素邊界和GroundTruth(GT)邊界的像素集；1()是一個指示函數，用來檢查B(si)和B(gj)之間最近像素是否在像素的ε-距離內，并設置ε為2。

欠分割誤差UE是邊界粘附的另一個評估指標。它是基于每個超像素只屬于一個對象的要求。UE測量從GT泄露的超像素內部像素的百分比，如果超像素與多個GroundTruth段有效重疊，UE將相應增加。欠分割誤差UE的計算公式如下：

(19)

式中：指標函數1( )等于有效重疊的一個值，κ=0.05是閾值。

3.3 實驗環境

對比試驗所采用的實驗平臺為1臺具有Intel i7-7700HQ 2.80 GHz處理器和8 GB RAM內存的計算機。為了對比公平，實驗使用各個超像素分割算法論文給出的源代碼，并盡量在不改變算法默認參數的條件下進行。本文算法采用 C++編寫。源代碼以C++實現的算法還有NC、SLIC、LRW算法，而LSC、ERS、DBSCAN、GMMS、aptDRW算法是以C++與Matlab相結合進行實現的。

3.4 超像素分割結果比較

各個超像素分割算法在K=300左右時的一些分割結果視覺上的對比如圖3所示。取部分結果的一些細節作對比，如圖4所示。由圖3和圖4可知當超像素個數K=300左右時，本文算法得到的超像素形狀規則且大小比較均勻，而且邊緣附著性能與規則度相對平衡。SLIC算法、LRW算法與本文算法的相似之處在于得到的超像素形狀也較為規則。而ERS算法、LSC算法、DBSCAN算法得到的超像素形狀總體上沒有本文算法規則。比如ERS算法得到的超像素形狀不夠規則且大小不均勻；LSC算法在圖像簡單區域得到的超像素比較規則，但是在比較復雜區域得到的超像素形狀的規則性不足，DBSCAN算法在圖像簡單區域得到的超像素的形狀呈菱形，但在圖像復雜區域得到的超像素規則性欠佳。GMMS算法得到的超像素規則度不夠高，而aptDRW算法生成的超像素的大小差異性比較明顯。

圖3 各超像素分割結果(從上到下各行依次是ERS、SLIC、LRW、LSC、DBSCAN、GMMS、aptDRW、Ours)

圖4 超像素局部放大區域的實驗結果

由于2個數據集中的圖片分辨率相對較小，參考文獻[14]，實驗對比時超像素個數K的值給定范圍為100～600。本文算法與各個超像素分割算法的在2個不同數據集表現的性能如下：

各個超像素分割算法在BSD500上的性能曲線如圖5、6所示。

圖5 邊界召回率曲線

圖6 欠分割誤差曲線

當K=400左右時，各個算法的BR與UE都比較接近。為了能更清楚明了的進行分析對比，本文給出下列相應的實驗數據，如表1所示。

表1 BSD500分割結果的BR與UE實驗數據

對于各個超像素分割算法在MSRC-V1數據集上的分割性能，本文取超像素個數K=200、400和600時的實驗數據進行對比，如表2和表3所示。

表2 MSRC-V1分割結果的BR實驗數據

表3 MSRC-V1分割結果的UE實驗數據

由于SLIC、LSC、DBSCAN、GMMS和本文算法的算法復雜度均為O(N)，根據文獻[13-15]，超像素個數K=100到600范圍內的取值對實時性數據影響不大，而ERS、LRW、aptDRW算法復雜度均高于O(N)。因此取超像素個數K=400時各個算法在BSDS500和MSRC-V12個數據集上的實時性數據進行對比，如表4所示。

表4 K=400時各個算法的平均時間 s

由圖5、6和表1～3分析對比可以得出，在2個數據集上，無論是在邊界召回率BR還是欠分割誤差UE上，本文算法相對SLIC和LRW算法都有明顯的優勢。這是由于局部模糊聚類采用在3×3鄰域超像素搜索區域內計算像素隸屬度并比較隸屬度大小進行軟化分，比較準確地將像素劃分到鄰域超像素。相比于除SLIC，LRW外的其他超像素分割算法如ERS、LSC、DBSCAN、GMMS以及aptDRW等算法，當超像素的個數設置較少時，本文算法的BR和UE表現欠佳。當超像素個數較多，特別是K=400左右或者K>400時，對于BSDS500數據集，在BR上本文算法比其他算法都略高。在UE上，本文算法比ERS、LSC、DBSCAN和aptDRW算法略低，但略高于GMMS算法；對于MSRC-V1數據集，在BR上，本文算法比其他算法都略高。在UE上，本文算法與ERS、LSC、DBSCAN和aptDRW算法都比較接近，略高于GMMS算法，但在K=600左右時本文算法最低；因此可以得出，本文算法能夠較好地處理不同數據集圖片。從局部模糊聚類來看，這是因為當超像素個數較多時，超像素區域的像素數量適中，區域像素求平均得到的聚類中心能夠很好地代表該超像素，因此能比較準確地在3×3鄰域超像素搜索區域內計算像素隸屬度并進行劃分。同時，在本文算法的合并步驟中，采用距離度量方式能夠保證生成的最終超像素的精度。在實時性方面，本文超像素分割算法由于限制了搜索區域的大小，在3×3鄰域超像素搜索區域內計算像素隸屬度，這表示，在搜索區域內，只需要計算每個像素對于3×3鄰域超像素的隸屬度，然后通過比較隸屬度的大小來進行像素的劃分，相比于基于全局的方式，這極大地降低了運算復雜度。與其他超像素分割算法的實時性數據相比較，由表4分析對比可以得出，本文算法慢于實時性最優的DBSCAN及SLIC算法，但相差不大，與GMMS算法也比較接近。而本文算法的實時性相比于ERS、LRW、LSC、aptDRW算法有明顯的優勢。因此本文算法以良好的實時性獲得了較好的分割效果，保證了算法復雜度和分割效果之間的平衡。

本文局部模糊聚類算法對于超像素個數K值的選取比較敏感，因為它決定了聚類中心的初始化，以及之后像素隸屬度的計算并進行劃分的的準確性。相對于傳統FCM基于全局的搜索方式，本文算法大大縮小了搜索區域，有效地降低了運算復雜度，同時不容易受噪聲影響，穩定性較高，彌補了傳統FCM對噪聲比較敏感的不足。

4 結論

提出了一種基于局部模糊聚類的超像素分割算法。FCM超像素分割算法能夠生成形狀規則性與邊界貼合性保持平衡的超像素。首先通過縮小搜索區域，設計像素對于超像素隸屬度的鄰域大小，適當改變隸屬度的計算方式，得到一種新的基于局部模糊聚類算法，然后利用該算法迭代生成初始的超像素，在后處理步驟中將一些未被劃分的像素與鄰近超像素進行合并，得到最后的超像素分割結果。采用2種標準的超像素分割精度的評價指標與其他幾種經典算法進行比較。本文算法的優勢在于對包括復雜對象或復雜紋理區域的圖像生成的超像素也能保持良好的形狀規則性與邊界貼合性，不足在于超像素的分割效果比較依賴于超像素的個數，當超像素個數較少時，本文算法的分割精度不高，這也是本文算法需要解決的問題，需要進一步研究。