基于改進譜聚類算法在圖像分割中的應用

王貝貝 楊明 燕慧超

摘要：為解決譜聚類算法應用于圖像分割時，相似矩陣內存占用較大甚至滿溢以及后續計算量大的問題，利用Nystrom方法隨機獲取一部分樣本點，根據樣本點和樣本點、樣本點和非樣本點2種相似關系近似表征所有像素點的相似性，得到原圖像的近似相似矩陣。在構建上述所需2種相似關系的相似矩陣時，距離度量采用余弦函數。結果表明，采用近鄰傳播聚類算法代替kmeans算法對得到的低維向量子空間聚類，克服了聚類過程對初始值的敏感性，得到的分割結果較穩定，4幅真實圖片也驗證了研究算法的優越性。改進的譜聚類算法為圖像分割的穩定性研究提供了依據。

關鍵詞：圖像處理；圖像分割；譜聚類；Nystrom方法；余弦距離；AP算法

中圖分類號：TP391文獻標志碼：Adoi： 10.7535/hbgykj.2018yx01010

Application of improved spectral clustering algorithm in image segmentation

WANG Beibei， YANG Ming， YAN Huichao

（School of Science， North University of China， Taiyuan， Shanxi 030051， China）

Abstract：To solve the problem of large usage of the similar matrix memory， even overflowing，and the large amount of calculation when spectral clustering algorithm is applied in image segmentation， a part of sample points are obtained by using the Nystrom method， according to the two similarity relations between sample points and sample points， sample points and nonsample points to get the similarity relation of all pixel points， then the approximate similarity matrix of the original image is got. In building the two block similar matrixs required in Nystrom， cosine function is used to overcome the absoluteness of Euclidean distance in the distance measurement . In this paper， the nearest neighbor propagation clustering algorithm is used to replace the kmeans algorithm to overcome the sensitivity to the initial value in the clustering process， thus obtaining a more stable effect. The experimental results of the 4 real images show that the method is far superior， and the improved spectral clustering algorithm provides reference for the stable study of image segmentation.

Keywords：image processing； image segmentation； spectral clustering； Nystrom method； cosine distance； AP algorithm

圖像分割是模式識別中的一個重要研究領域，它的目標是根據對圖像的像素屬性（如灰度、顏色和紋理等）進行劃分從而實現對圖像的分割。在實際應用中，對同一幅圖像，不同的研究人員可能需要提取不同的信息，人們需要也即感興趣的區域稱為前景，其余區域稱為背景。圖像分割就是把圖像分成各具特性的區域并提取出感興趣目標的技術和過程[12]。

聚類算法在圖像分割中應用得較為廣泛，其中譜聚類算法是依托譜圖劃分理論演化而來的，優于kmeans算法[3]、FCM算法[4]等傳統算法，這是因為其不受樣本空間形狀的限制，能收斂于全局最優解的特性。在進行圖像分割時[5]，譜聚類算法將圖像的每個像素點視為對應無向圖的一個節點，用像素矩陣來表達圖像，這樣就把圖像的分割問題轉換為對數據的聚類問題，此時，再根據某種距離準則構造新數據集的相似矩陣，新矩陣中的元素表示任意兩像素點間的相似度，若需要分割的圖像像素點個數為m×n，則它對應的相似矩陣的維數為（m×n） ×（m×n），計算量大，占用內存也較大。為解決該問題，文獻＼[6＼]基于Nystrom方法提出了一種近似方法估計相似矩陣，首先解決一個小的隨機像素子集的分組問題，然后將該解外推到圖像或圖像序列中的全部像素組中，這樣能簡單、高效地估計出相似矩陣的主特征向量，分割的結果也較穩定。JIAO等[7]將譜聚類算法與網格結合，通過將原始網格模型嵌入到光譜空間中，來解決分割問題。首先根據最小規則確定網格凹區，然后通過考慮網格顯著性和曲率信息定義拉普拉斯矩陣，最后用特征分解法計算拉普拉斯矩陣的前k個特征向量，將原始網格嵌入到一個k維的光譜空間中，利用混合高斯方法實現最終的分割。李楊等[8]研究了在不同的顏色空間中，不同的距離測度構造的相似矩陣對分割結果的影響，通過分析比較6種不同相似度構造方法的分割效果，得出無論在RGB還是HSV顏色空間下，采用余弦距離公式得到的分割效果都是最優的。李小斌等[9]設計了一個遞歸的多尺度分層分割算法，解決了譜聚類應用于圖像分割時權值矩陣的特征值和特征向量難以計算的問題，首先定義像素點與類之間的距離，在研究對圖像的像素進行抽樣的基礎上得到一個抽樣數定理，對少量的采樣點采用SCAWM聚類，然后再按距離最近原則對大量的非采樣點聚類，引入尺度因子使圖像從“粗”到“細”完成分割。

1經典譜聚類算法研究

在數據聚類和圖像分割中，結合譜圖理論的譜聚類算法一直表現很好，并已成功用于解決數據聚類和圖像分割問題，而對圖像的分割實質也是對數據的聚類，因為對圖像的分割是對代表圖像信息的像素點集X=（x1，x2，…，xn）的聚類。譜聚類算法在數據聚類中的高性能和較易實現，近年來吸引了越來越多人的關注。其本質是將聚類問題轉化為圖的最優劃分問題，將圖像映射為帶權無向圖，圖的每個節點對應一個像素，每對像素之間的相似性作為無向圖的邊，通過邊上的權值構造相似性矩陣。大致過程可歸納為3步。

1）根據某種相似性度量構建待聚類數據集的相似矩陣W=[wij]；

2）計算規范化拉普拉斯矩陣L=D-12WD-12的前k個特征值及其對應的特征向量，其中D=diag（d1，d2，…，di，…，dn），di=∑nj=1wij，構建特征空間的向量矩陣V=[v1，v2，…，vk]∈Rn×k；

3）對上述得到的向量矩陣用經典聚類算法進行聚類。

然而，在傳統的譜聚類算法中依然存在如下問題：

1）常用的基于相似性度量的高斯核函數：

W（xi，xj）=exp（-‖xi-xj‖2/2σ2）（1）

不能充分反映數據集的復雜空間分布，當集群是復雜的流形結構時不適用[10]；

2）當數據集的規模N比較大時，總的時間復雜度和空間復雜度分別達到了O（N3）和O（N2），儲存和分解一個大的相似矩陣就比較困難，尤其是對一個圖像。

2改進譜聚類算法

2.1基于Nystrom方法的譜聚類

譜聚類算法的瓶頸之一是相似矩陣的構建及其計算，首先解決計算量大的問題。

因為相似矩陣中元素的個數是樣本數的平方，例如：一幅由512×512個像素組成的圖像，需要計算262 144×262 144維的相似矩陣，計算量較大，計算時間長，很可能會引起內存滿溢的情況。有研究表明，基于Nystrom方法的譜聚類能在很大程度上提升譜聚類算法的性能。

Nystrom方法是一種基于積分方程，計算矩陣特征值和特征向量的近似方法，適用于對稱正定矩陣。其基本思想是采用隨機采樣的方式獲得一定的樣本點，用樣本點與非樣本點之間的相似性來近似估計非樣本點之間的相似性[11]。若原圖像的像素總數為N，從中隨機采集m個樣本像素點（mN），則非樣本點的個數為n=N-m，相似性矩陣W可以表示為

式（2）中A∈Rm×m，B∈Rn×m，C∈Rn×n。矩陣A表示隨機采集的m個樣本像素點之間的相似矩陣，矩陣B表示隨機采集的m個樣本像素點與n個非樣本像素點之間的相似矩陣，矩陣C表示n個非樣本像素點之間的相似矩陣。因為mN，所以矩陣C計算量如同未采樣前的矩陣的計算量一樣巨大，故通過Nystrom采樣方法用A和B估計C[12]。

先將矩陣A對角化為A=UΛUT，其中Λ是一個對角矩陣，非零元素對應矩陣A的特征值，再將特征向量U擴展為相似矩陣W的近似特征向量：

由式（3）可知Nystrom采樣方法是用BTA-1B估計C，即C=BTA-1B。由此，便可以用較少的樣本像素點逼近全部點的相似矩陣W。

筆者得到了相似矩陣和其主特征向量的近似估計和。但是應用到譜聚類中，需要的是特征系統D-1/2WD-1/2的主特征向量。所以接下來，計算的行和，將其對應為對角矩陣D中對角線上的元素，估計矩陣的行和為

若矩陣A正定，接下來便解決估計特征向量的正交化問題。令A1/2表示A的對稱正定平方根，并定義Q=A+A-1/2BBTA-1/2，將Q對角化為Q=UQΛQUTQ，則W可正交化為=VΛVT，其中：

經過上述變換，則可取矩陣V的前k個向量構成矩陣E，再對矩陣E的行向量聚類，由此便可減少在譜聚類算法中的計算量。

2.2基于余弦函數的相似矩陣

在上述過程中，筆者已經用Nystrom方法解決了相似矩陣計算量大的問題，該節解決的則是相似矩陣的構建問題，也即采取合適的高斯度量來表示相似矩陣。圖像的相似度矩陣由該圖像中各像素之間的相似度構成，而高斯核函數中的歐氏距離度量只考慮絕對距離，在考慮相對距離時，余弦距離比其他距離表現出更好的實際意義。

假設待分割的圖像包含N個像素點，每個像素有p個特征數，則該圖像可表示為A∈RN×p，這里A=[a1，a2，…，aN]T，其中ai∈Rp，1≤i≤N，用余弦函數得到的圖的相似度矩陣可表示為W=[wij]N×N，其中：

如果對數據集A進行歸一化，即有‖ai‖=‖aj‖=1，則像素點xi到像素點xj的余弦相似度可簡化為wij=aiaj，相應地相似矩陣W簡化為W=[wij]N×N=AAT。由此，圖像的相似度矩陣可由圖像矩陣A和其轉置相乘得到。

2.3近鄰傳播聚類算法

在2.1節最后所得的矩陣E的每一行都對應一個像素點，這節需要做的則是將新得到的矩陣相應的數據點進行聚類處理，傳統譜聚類算法的最后一步在采用kmeans聚類算法時，對初始值較敏感，需要人為初始化類的個數，分割結果不穩定，即取不同的初始值得到的分割效果也不同。為解決該問題，本研究引入近鄰傳播算法（AP算法）[13]，該算法是2007年刊登在《科學》期刊上的的一篇文章提出的一種新型的聚類算法，事先不需要知道類的數目，通過對矩陣進行迭代收斂，最終更新到穩定的類中心，然后計算每一個數據點與所有類中心的相似度的大小，將其劃分到相似度最大的類中心，每個類中心及其劃分到該類中心的其他數據點即組成一個類別。

近鄰傳播算法需要首先構建新的數據集中點與點之間的相似度矩陣，相似度用歐氏距離度量即可。Sij=-‖yi-yj‖2，i≠j，然后把相似度矩陣S（i，j）=-‖yi-yj‖作為輸入，交換數據點間的信息，交換方式主要依靠2種度量：吸引度和歸屬度。吸引度r（i，k）是數據點yi發送到候選類中心yk的信息，表示點yi對候選類中心點yk的支持程度，該值越大，則表明點yk作為點yi的類中心的可能性越大；歸屬度a（i，k）是候選類中心yk發送給數據點yi的信息，表示候選類中心yk作為點yi的類中心的合適程度，該值越大，則表明點yi選擇點yk作為其類中心的可能性越大。在算法迭代過程中，每個數據點都會進行2種信息的交替更新，更新公式為

當每個數據點都進行了上述2次的信息更新后，算法也迭代了1次。在運算過程中，引入阻尼系數λ∈[0，1），來避免AP算法的大幅度震蕩，迭代次數和每次迭代的結果都會隨著阻尼系數的改變而改變：λ取值較小時，迭代的次數會較少，但是運算過程中的數值波動性卻較大，此時得到的較大圖像的收斂結果不理想；λ取值較大時，迭代的次數雖會較多，但圖像的收斂效果較理想。本文取λ=0.9，對應的吸引度矩陣和歸屬度矩陣更新公式如下：

其中t表示迭代次數。數據點yi的聚類中心即是令r（i，k）+a（i，k）取最大值的點yk。

2.4改進譜聚類算法

譜聚類算法在進行圖像分割，初始化相似矩陣時會出現內存滿溢的情況，無法進行后續工作。為了解決該問題，本研究提出一種改進的譜聚類算法——INJW算法，對預處理的圖像，研究利用Nystrom方法隨機獲取一定的樣本點。先構建樣本點與樣本點間的相似矩陣、樣本點與非樣本點間的相似矩陣，再根據式（4），用這2個分塊矩陣來近似表征所有像素點間的相似矩陣。在構造上述所需的分塊矩陣時，距離度量采用余弦函數，克服歐氏距離的絕對性，由此便完整的得到了譜聚類算法第1步所需的相似矩陣；第2步所需規范化拉普拉斯矩陣的主特征向量為式（8）的前k個向量；最后對這個低維向量子空間聚類時采用近鄰傳播聚類算法代替kmeans算法，克服了聚類過程對初始值的敏感性。

1）預處理輸入圖像G，隨機抽取1%的樣本像素點，根據式（9）的余弦函數構造像素點的分塊相似性矩陣A和B，得到待處理圖像的相似矩陣為

2）計算拉普拉斯矩陣L=D-1/2D-1/2的前k個特征向量，即根據式（8）計算出矩陣V，并取V的前k個最大特征值對應的特征向量，得到新的特征矩陣為E。

3）將矩陣E的行向量規范化為單位矩陣Zij，

4）矩陣Zij的每一行對應原圖像的一個像素點，用AP算法對其進行聚類。

5）根據步驟4）得到的聚類結果確定所有像素點的類別：當矩陣Zij的第i行對應第j類時，像素點Ei對應第j類。

3結果與分析

為了驗證本研究算法的性能，在操作平臺為64位Windows 7系統、CPU為Intel（R） Core（TM）i52450M（2.50 GHz）、4 GB內存的計算機和Matlab R2014a中進行實驗。實驗圖片來自美國南加州大學的USISIPI圖像數據庫和美國加州大學伯克利分校的BSDB標準測試圖像數據庫中的4幅圖像，對比算法為k均值聚類算法（kmeans）、基于規范化拉普拉斯矩陣的譜聚類算法（NJW），實驗對比圖見圖1—圖4。

圖1是數據庫中4幅圖的原始圖像：圖1 a）和圖1 b）分別是人物圖lena和cameraman，圖1 c）是動物圖ducks，圖1 d）是實物圖airplane。圖2是kmeans算法的分割結果，由于該算法對初始值較敏感，且取不同的分割數時結果也不相同，故在編程時設置k分別取2，3，4，5，6，且在程序運行20次后選擇最優直觀分割圖，其中lena圖的最優分割為k=3，cameraman圖的最優分割為k=4，ducks圖的最優分割為k=6，airplane圖的最優分割為k=4。 圖3是基于規范化拉普拉斯矩陣的譜聚類算法（NJW）的分割結果圖。圖4是本文算法INJW——改進的譜聚類算法的分割結果圖。

從總體上來看，kmeans算法分割出來的圖較模糊，前景和背景區域都含有很多噪聲點，NJW算法的分割結果圖較純凈，本文算法的分割效果圖最清晰，不管是人物還是動物，前景和背景區分都較明顯，區域對比度、區域內部均勻性都較前2種算法明顯提高。

1）人物lena圖kmeans算法的分割圖中人物的帽子、頭發和五官都已模糊化，且前景、背景混為一體；NJW算法的分割圖雖然前背景明顯，但人物的五官不是很清楚，鼻梁和臉頰并沒有分割開；本研究算法運行出來的分割圖中帽子和頭發都更加細膩，五官清晰。

2）人物cameraman圖kmeans算法的分割圖中右側有少量噪聲點，前景人物和背景海水混為一體；NJW算法的分割圖則把前景人物分割出來，但是人臉五官不明顯，背景的輪廓沒有分割出來；本研究算法較好地分割開前景和背景，海上的建筑物高樓雖然并沒有完全分割出來，但總體上還是達到較理想的效果。

3）動物ducks圖3種算法都分割出前背景，樹干上的涂白劑都和未噴涂部分分割開來，鴨子和海水也分割開。但是很明顯，kmeans算法分割出來的鴨子輪廓不明顯，且遠處的3只已經模糊化；NJW算法則把靠岸的3只鴨子和岸邊混為一體；本研究算法細節分割的更加明顯，鴨子的嘴巴也能顯露出來。

4）實物airplane圖該幅圖不僅要把前景的飛機和背景的天空、雪山分割開，還要準確地分割出飛機上的圖案和字母。kmeans和NJW算法都沒能達到理想的效果，本研究算法能分割出機尾的字母和數字F16，以及飛機上的五角星標志。

4結論

每一幅圖像都能用對應的像素矩陣表示，所以對圖像的分割本質上是對代表其像素點的數據的分割。譜聚類算法用于分割圖像時，最大的困難是相似矩陣的構造，經常會出現內存不足甚至滿溢的情況，即使能計算出，時間成本也較高。本研究結合Nystrom采樣方法，很大程度上減少了計算的復雜度，且對相似矩陣中距離度量做了改進，用余弦距離代替傳統歐氏距離。最后階段，以近鄰傳播算法取代kmeans算法對k個特征主向量進行聚類。實驗結果驗證了本文算法的穩定性和有效性，分割出來的圖像質量有了很大提升，接下來的工作重點將放在對前背景較復雜圖像的分割。

參考文獻/References：

[1]周莉莉， 姜楓. 圖像分割方法綜述研究[J]. 計算機應用研究， 2017， 34（7）：19211928.

ZHOU Lili， JIANG Feng. Survey on image segmentation methods [J]. Application Research of Computers， 2017， 34（7）：19211928.

[2]章國紅，辛斌杰.圖像處理技術在紗線毛羽檢測方面的應用[J].河北科技大學學報，2016，37（1）：7682.

ZHANG Guohong， XIN Binjie. Application of image processing technology in yarn hairiness detection[J]. Journal of Hebei University of Science and Technology， 2016，37（1）：7682.

[3]SHI B， PANG Z F， XU J. Image segmentation based on the hybrid total variation model and the kmeans clustering strategy[J]. Inverse Problems & Imaging， 2016， 10（3）：807828.

[4]DUBEY Y K， MUSHRIF M M. FCM clustering algorithms for segmentation of brain MR images[J]. Advances in Fuzzy Systems， 2016（3）：114.

[5]BAILLARD C， HELLIER P， BARILLOT C. Segmentation of brain 3D MR images using level sets and dense registration[J]. Medical Image Analysis， 2001， 5（3）：185194.

[6]FOWLKES C， BELONGIE S， CHUNG F， et al. Spectral grouping using the Nystrm method [J]. Pattern Analysis and Machine Intelligence IEEE Transactions， 2004， 26（2）：214225.

[7]JIAO X， WU T， QIN X. Mesh segmentation by combining mesh saliency with spectral clustering[J]. Journal of Computational & Applied Mathematics， 2018，329：134146.

[8]李揚， 陸璐， 崔紅霞. 譜聚類圖像分割中相似度矩陣構造研究[J]. 計算機技術與發展， 2016， 26（7）：5558.

LI Yang， LU Lu， CUI Hongxia. Research on similarity matrix structure in spectral clustering image segmentation [J]. Computer Technology and Development， 2016， 26（7）：5558.

[9]李小斌， 田錚. 基于譜聚類的圖像多尺度隨機樹分割[J]. 中國科學， 2007， 37（8）：10731085.

[10]YANG Y， WANG Y， XUE X. A novel spectral clustering method with superpixels for image segmentation[J]. Optik International Journal for Light and Electron Optics， 2016， 127（1）：161167.

[11]管濤， 李玉玲. 大規模矩陣降維的隨機逼近方法[J]. 數學的實踐與認識， 2016，46（24）：184193.

GUAN Tao， LI Yuling. Stochastic approximation method for largescale matrix reduction[J]. Mathematics in Practice and Theory， 2016，46（24）：184193.

[12]BERGH F V D， ENGELBRECHT A P. Training product unit networks using cooperative particle swarm optimisers[J]. International Joint Conference on Neural Networks， 2001，1：126131.

[13]FREY B J， DUECK D. Clustering by passing messages between data points[J]. Science， 2007，315（5814）：972976.