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

覃正優(yōu)，林一帆，陳瑜萍，林富強

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

0 引言

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

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

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

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

1 理論基礎(chǔ)

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

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

算法：BASS算法

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

1.2 譜聚類算法

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

（1）預處理和構(gòu)建相似度矩陣

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

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

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

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

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

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

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

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

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

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

2.1 顏色空間

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

圖1 CIELab色彩空間模型

2.2 混合高斯模型

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

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

2.3 本文算法步驟

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

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

3 實驗結(jié)果分析

3.1 實驗數(shù)據(jù)

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

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

3.2 實驗環(huán)境及參數(shù)設(shè)置

（1）實驗環(huán)境

本算法的驗證性實驗環(huán)境為64位的Win10系統(tǒng)、CPU型號是Intel Core i5-7200U、4G內(nèi)存的計算機，使用面向?qū)ο蟮腜ython語言進行編程實現(xiàn)，該語言語法清晰，易于理解及實現(xiàn)。

（2）實驗設(shè)計

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

（3）實驗參數(shù)

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

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

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

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

3.3 實驗結(jié)果及分析

（1）視覺結(jié)果比較

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

圖4 原始圖像

圖5 標準數(shù)據(jù)集圖像分割結(jié)果

圖6 K-means傳統(tǒng)圖像分割算法結(jié)果

圖7 基于KNN傳統(tǒng)譜聚類圖像分割算法結(jié)果

圖8 傳統(tǒng)NJW圖像分割算法結(jié)果

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

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

圖9 BSISC圖像分割算法結(jié)果

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

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

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

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

（2）定量評價比較

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

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

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

（3）運算時間比較

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

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

4 結(jié)語

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

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