一種基于自適應超像素的改進譜聚類圖像分割方法

覃正優，林一帆，陳瑜萍，林富強

（南寧師范大學計算機與信息工程學院，南寧530100）

0 引言

圖像數據的處理和分析是數據分析處理領域的重要課題，圖像分割則是圖像處理中的基礎領域之一。它是一種基于圖像中各像素點的相似性，把圖像分成子區域達到提取所需目標的技術。圖像分割的結果直接關系著后續的圖像分析、理解和識別是否能夠順利開展，因此在計算機視覺領域一直廣受關注。

傳統譜聚類算法在圖像分割的應用中面臨的最大問題是：算法運行時需要構建相似度矩陣，而圖像數據的像素信息量往往大且復雜，導致傳統譜聚類難以應用于大圖像或多張圖像的圖像分割。針對此問題，很多研究者通常采用對像素點進行抽樣的方式來降低圖像分割時的計算量，以達到加快算法運算速度的目的，例如Fowlkes等人提出的nystr?m方法[1]。但這些抽樣的方式本質是隨機取出了部分圖像像素信息進行聚類劃分，取樣導致了部分圖像信息未進入分割階段，這種抽樣的隨機性使得算法不具有魯棒性，同時由于取樣數量越多效果越好，時間卻相對越長，導致算法難以達到分割效果好的同時兼顧分割速度快問題。

超像素是一種將圖像從像素級變成區域級的表示方法，超像素塊通常是由位置相鄰且像素特征相似的像素構成，它們大多保留了進一步進行圖像分割的有效信息，捕獲了圖像的冗余，最大程度保留全局圖像信息。這些優點使得它在最近幾年的圖像分割領域受到國內外研究者的密切關注，除了研究出性能優異的超像素分割算法，還有一部分學者們研究將超像素分割算法作為其他圖像算法的預處理步驟，降低后續圖像分析、識別處理任務的復雜度。

由于超像素一般情況下并不會破壞圖像中物體的顏色、紋理和邊緣信息，可以作為其他算法的預處理步驟，因此本文提出了一種新的譜聚類算法，通過使用一種超像素分割方法作為傳統NJW（Ng-Jordan-Weiss）譜聚類算法[2]的預處理步驟，對原始圖像進行降維，解決NJW譜聚類算法在矩陣在特征向量計算上開銷過大的問題。較傳統NJW算法，本文所提出的改進算法在保證分割質量的同時，又降低了整體的運算成本和運算時間。

1 理論基礎

1.1 貝葉斯自適應超像素分割算法

許多研究學者提出了超像素分割算法用于圖像分割，它是一種圖像過度切割方法。通過分割，可將圖像從像素級變成區域級，所得的區域像素塊稱為超像素塊，這些超像素一般情況下并不會破壞圖像中物體的顏色、紋理和邊緣信息，因此，超像素分割算法可以作為其他算法的預處理步驟，達到降低后續圖像分析與識別任務的算法復雜度。近年來，學者們提出了很多種性能優異的超像素分割算法，例如，2019年，Uziel等人基于貝葉斯方法的概念提出的貝葉斯自適應超像素算法（Bayesian Adaptive Superpixel Segmentation，BASS）[3]，它是一種基于狄利克雷過程（Dirichlet Process）高斯混合模型（DPGMM），而DPGMM是一種非參數混合的貝葉斯模型的一個重要例子，不需要指定類別數量，就可以從數據中推斷分類，因此BASS算法可以不需要用于預先設置超像素的數目來自適應根據圖像的像素特征來生成超像素，BASS算法的具體步驟如下：

算法：BASS算法

鑒于BASS算法優異性能，本文將該算法作為后續譜聚類算法的預處理，以降低算法的復雜度。

1.2 譜聚類算法

譜聚類是一種基于譜圖理論的靈活有效的聚類方法，多用于具有復雜結構的數據集聚類。它通過將數據點映射到由特征向量構成的低維空間中，從而優化數據結構，獲得滿意的聚類結果。譜聚類本身實際隱含了數據降維，即通過特征向量的求解來簡化運算，因此適用于圖像這種高維數據的處理。基于譜聚類的圖像分割算法核心原理就是將圖像分割問題轉為圖的最優劃分問題，即利用加權無向圖來表示圖像，圖中的點為像素點，邊表示各點間特征的相似度。譜聚類算法可以大致分為四個階段[4]：

（1）預處理和構建相似度矩陣

相似度矩陣是各點之間的相似度構成的矩陣。矩陣元素為Wij，可表示第i個樣本和第j個樣本間的相似度，有距離d(xi,xj) ，σ作為為尺度參數，公式為：

（2）對相似度矩陣進行歸一化

指根據相似度矩陣獲得圖的拉普拉斯矩陣的過程，設有度矩陣D，它每行的值是相似矩陣W對應行或列的對角矩陣，元素公式可表示為di=∑jWij。

結合相似度矩陣W(i,j)，可構建拉普拉斯矩陣，公式表示為：

（3）譜映射，根據拉普拉斯矩陣計算特征向量

將k個特征向量組合在一起得到n×k維的矩陣，并將每一行作為k維空間中的一個向量。

（4）結合其他的聚類算法進行分類，獲得最終結果

算法的結果區域的共同特征作為元素以進行譜聚類，可在最大程度保留全局圖像信息的同時，達到降低算法的整體復雜度和算法的運算時間的目的，相較于抽樣預處理方式也更加穩定。

2 基于自適應超像素的改進譜聚類圖像分割算法

傳統正則譜聚類（Ng-Jordan-Weiss，NJW）算法是一種被廣泛使用的傳統譜聚類算法，但該算法構建相似矩陣時采用了全連接方式，導致應用于圖像分割領域時，計算量過大且運算時間過長，難以應用于實際情況。針對此問題，本文提出一種基于自適應超像素的改進譜聚類圖像分割算法（An Improved Spectral Clus?tering Image Segmentation Method Based on Adaptive Superpixel）。

2.1 顏色空間

CIELab色彩空間是由國際照明委員會于1976年公布的一種色彩空間，由表示明度的分量L、表示像素顏色在紅色至綠色的區間內取值的分量a，表示像素顏色在黃色至藍色的區間內取值的分量b組成[5]。相比傳統的RGB色彩空間，CIELab具有更接近人類視覺感受的優勢，故本文改進算法采用LAB作為預處理和后續聚類部分的色彩空間。

圖1 CIELab色彩空間模型

2.2 混合高斯模型

混合高斯模型（Gaussian Mixture Model，GMM）[6]是一種基于高斯變量分布模型構成的模型，算法原理是假設數據分布符合多個高斯分布，通過極大似然估計（Maximum Likelihood Estimation，MLE）獲得符合該數據分布情況的多個高斯分布的參數，以得到用于描述當前數據聚類情況的最佳混合高斯分布函數。

傳統的NJW算法使用了K-means作為聚類步驟，但K-means的隨機初始點選擇對結果影響較大，故算法存在穩定性的問題。針對該情況，本文將傳統NJW譜聚類的算法中的聚類步驟所使用的K-means替換為GMM，使算法獲得更為穩定的效果。

2.3 本文算法步驟

為降低算法的整體復雜度和算法的運算時間，本文所提出的改進圖像分割算法，利用了BASS超像素分割算法能自適應生成緊湊而貼合的超像素作為NJW算法的輸入，大大降低了NJW算法構建相似度矩陣的規模，從而一定程度上降低整體算法的計算成本和運行時間。針對預處理階段所獲得的超像素，將像素的顏色空間從RGB顏色空間轉換到更接近人類視覺感受的Lab顏色空間，并且在NJW算法的聚類階段，使用了GMM模型，增強了算法的穩定性。本文改進的圖像分割算法的具體步驟如下：

算法：本文改進的圖像分割算法

3 實驗結果分析

3.1 實驗數據

實驗使用的數據集為美國加州大學伯克利分校的BSDS500標準圖像數據庫[7]中的圖像，該圖像數據集共有500張圖像，并有對應圖像的標準分割結果數據，可用于驗證算法的分割結果。

該數據集圖像數量較多，為更好地進行結果分析，根據圖像內容的復雜度和圖像特點，將圖像分為A、B、C三類。其中，A類圖像特征為需分割的圖像前景和后景都較簡單的圖像類型；B類圖像特征為前景較清晰但背景復雜，且整體顏色較接近的圖像；C類圖像特征為前景背景都較復雜，但像素間顏色區分較明顯的圖像。

3.2 實驗環境及參數設置

（1）實驗環境

本算法的驗證性實驗環境為64位的Win10系統、CPU型號是Intel Core i5-7200U、4G內存的計算機，使用面向對象的Python語言進行編程實現，該語言語法清晰，易于理解及實現。

（2）實驗設計

為了驗證本文改進算法的有效性，本文首先將本文改進算法與傳統K-means算法、基于KNN的傳統譜聚類算法和傳統NJW算法在Lab色彩空間下，對三種類型圖像進行分組重復實驗，記錄實驗結果和實驗所用時間，保留實驗圖像。其次從三組對照組中取出具有代表性的三張圖像展示分割結果圖像，與該圖像的原圖像、標準圖像分割結果圖像進行視覺結果比較。再通過引入量化指標回歸率（Recall）和精確率（Precision），對三組運算結果求定量指標的平均值，進行定量評價比較。最后通過對時間記錄求運行時間平均值，進行四種算法的運行時間比較。

（3）實驗參數

實驗使用參數如下：K-means算法實驗組聚類個數為2，迭代次數參數為10。基于KNN的傳統譜聚類實驗組聚類個數為2，鄰居數為280。本文改進圖像分割算法實驗組聚類個數為2，預處理部分初始超像素個數參數為400。本文改進算法所使用的參數選擇，對算法影響較大的主要是初始超像素個數參數。

初始超像素個數參數是指本文改進算法預處理部分的限定初始生成的超像素數量的參數，主要影響運算時間和最終算法的效果。在不同參數下，超像素數量參數對本文改進算法運算時間影響結果如圖2，可知在400之后運算時間增加比例大幅提升；超像素數量參數對運算結果F1的影響如圖3，可知在400后運算效果對多種類圖像的綜合效果最佳。綜合運算時間和分割效果考慮，認為超像素個數參數應取400左右為佳。

圖2 超像素個數參數對算法時間影響對比

圖3 超像素個數參數對算法效果影響對比

3.3 實驗結果及分析

（1）視覺結果比較

為了對分割結果量進行公平的比較，我們實現運行了傳統K-means算法、基于KNN的傳統譜聚類算法和傳統NJW算法，使用它們的建議參數來生成最佳的分割結果。圖6至圖9給出了傳統K-means算法、基于KNN的傳統譜聚類算法和傳統NJW算法和我們算法分割得到的具有代表性的視覺分割結果。

圖4 原始圖像

圖5 標準數據集圖像分割結果

圖6 K-means傳統圖像分割算法結果

圖7 基于KNN傳統譜聚類圖像分割算法結果

圖8 傳統NJW圖像分割算法結果

總體可看出，四種圖像分割算法都能夠獲取目標圖像，但分割效果各有不同。

對于A類圖像，以圖像135069為例。對于B類圖像，以圖像100007為例。對于C類圖像，以圖像3063為例。視覺結果比較情況見圖6至圖9。針對不同算法對該標準數據集進行圖像分割的結果，分析如下：

圖9 BSISC圖像分割算法結果

由圖6可見，傳統K-means算法分割的效果僅對A類圖像效果較好，對B類圖像效果一般，對C類圖像效果極差，即該算法隨著圖像復雜度提高效果漸差。這是由于傳統K-means算法的聚類初始點隨機選擇，且初始點選擇對結果影響很大，所以面對具有復雜背景的圖像時效果不佳，算法不穩定。

由圖7可見，基于KNN的傳統譜聚類算法的效果對A類、B類和C類差別不大，很穩定但效果一般，錯認漏認的情況較多。由于K近鄰法中選取鄰居不考慮像素位置特征，導致分割結果邊緣不連貫，有大量離散點。

由圖8可見，傳統NJW算法的效果對A類圖像效果較好，對B類圖像效果極差，對C類圖像效果一般，總體來說不夠穩定。這是由于傳統NJW算法應用于圖像分割時計算量極大，實驗使用的計算機內存不足，故根據實驗設備情況將圖像等比例縮放至0.25倍，聚類分割后再通過插值放大4倍以獲得實驗結果。該方法雖然降低了運算成本，但插值放大并二值化后的圖像也存在分割結果邊緣貼合度不佳的情況，且導致對前景與后景區分度不高、后景復雜的圖像分割效果極差。

由圖9可見，本文改進算法通過改進提高了算法整體穩定性，使其面對A類、B類和C類這三種不同復雜度的圖像都能保持相對良好的分割結果。由于預處理部分的貝葉斯自適應超像素算法所獲得的超像素具有良好的邊緣貼合度，使得本文改進算法最終的分割結果邊緣貼合效果比三種對比算法好。同時本身具有良好的魯棒性，效果穩定，不易受噪音影響。

（2）定量評價比較

回歸率（R）表示算法避免遺漏的能力，精確率（P）表示抗干擾及噪聲的能力[6]，理論上兩種指標都越高則最終效果越好，但通常兩者不能同時兼顧，因此文獻[6]中提出平衡兩者的評價指標，即精確率和回歸率的調和均值F1。

根據量化指標對幾種算法的分割結果進行定量比較。從表1可以看出本文改進算法效果比較穩定，對各種復雜度下的圖像都有較好的圖像分割效果。

表1 三種算法定量分析比較

（3）運算時間比較

在實驗過程中可知，由于通過超像素預處理降低了譜聚類的聚類元素數量，本文改進算法在運算時間上遠優于傳統基于KNN譜聚類圖像分割算法。實驗中，傳統基于KNN譜聚類圖像分割算法的平均運算時間在900秒至1200秒之間，傳統NJW圖像分割算法的速度由于經過等量縮放與插值放大處理，平均運算時間按倍數運算后在3600秒至6000秒之間，本文改進算法的平均運算時間在400秒至580秒之間。

因此綜合來看，本文改進算法的效果較好，準確率較高，受噪聲影響較小，分割時較少出現離散點，面對不同類型的圖像都能保持較高穩定性，運算速度較基于KNN的傳統譜聚類算法而言有明顯的提升，運算時間、運算成本相對較低，可以應用于大尺寸圖像的圖像分割。

4 結語

本文分析了傳統譜聚類算法的問題，提出了一種本文改進圖像分割算法。通過引入貝葉斯自適應超像素算法作為預處理過程，降低傳統NJW譜聚類算法的整體算法的復雜度，以達到減少算法運算時間和所需運算資源的目的。

目前，譜聚類算法仍在發展中，在進行研究的過程中，也發現了一些問題有待研究，例如超像素的代表值僅獲取了顏色特征和空間位置特征進行處理，而紋理等更多特征未能得到很好的體現和應用。在未來的工作中，將考慮使用顏色和紋理特征相結合的方式對圖像進行特征提取，以提高算法的廣泛適用性和魯棒性。