基于誤差采樣的Nystr?m譜聚類圖像分割算法研究

劉仲民，李博皓，李戰明，胡文瑾

(1.蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州730050；2.西北民族大學 數學與計算機學院，甘肅 蘭州730000)

基于誤差采樣的Nystr?m譜聚類圖像分割算法研究

劉仲民1，李博皓1，李戰明1，胡文瑾2

(1.蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州730050；2.西北民族大學 數學與計算機學院，甘肅 蘭州730000)

譜聚類算法在聚類過程中要計算樣本相似度矩陣，構造數據量大，并且要對拉普拉斯矩陣進行特征分解，計算比較耗時。Nystr?m擴展方法通過部分采樣數據來逼近原始特征空間，可以有效降低譜聚類算法的計算復雜度。采樣點的選擇是決定Nystr?m擴展方法精度的重要因素，通過對Nystr?m擴展方法的誤差進行分析，結合圖像特征信息，設計了一種新的采樣方案。利用均勻采樣方法對圖像進行初步采樣，并通過迭代的方法最小化采樣點與像素點之間的誤差，得到最終采樣點特征值。通過在Berkeley圖庫上的圖像分割實驗表明了算法的可行性和有效性。

Nystr?m；譜聚類；圖像分割；K均值

0 引言

圖像分割就是指把圖像分成各具特性的區域并提取出感興趣目標區域的技術和過程[1]。它是計算機視覺處理中極為重要的環節之一，是由圖像處理進入到圖像分析的關鍵步驟[2]。譜聚類是一種新型聚類分析方法，具有能夠處理任意形狀的數據集、易于執行等優點[3]。近些年來譜聚類算法得到了迅速發展，并被應用于圖像分割及其相關領域。

在圖像分割中，譜聚類計算像素點之間的相似度矩陣并求解該矩陣的特征值與特征向量，通過對特征向量進行聚類完成對圖像的劃分。譜聚類算法將圖像劃分為多個區域，使得同一區域內部像素點相似度高，不同區域之間相似度低，獲得了較好的分割效果[4]。然而，譜聚類算法計算過程中產生的相似度矩陣規模過大，特征值與特征向量的存儲、計算使得譜聚類算法計算復雜度過高[5]。例如：一幅像素數目為n、特征維度為d的圖像，計算其相似度矩陣的時間復雜度高達O(d2n2)，空間復雜度高達O(n2)，拉普拉斯矩陣特征分解的時間復雜度更是高達O(n3)。

譜聚類的計算復雜度過高嚴重制約了其在圖像分割方面的應用。對此，國內外學者對其進行了一系列的研究和改進，其中Nystr?m擴展方法[6]是應用和研究較多的一種改進方法。Nystr?m擴展方法可以使用小部分數據近似逼近整個數據集的相似度矩陣和其特征空間，從而降低了譜聚類對時空的要求。文獻[7]最初將Nystr?m擴展方法應用在譜聚類中，并以此成功地進行了圖像分割。文獻[8-9]在文獻[7]的基礎上對Nystr?m擴展的逼近誤差進行了詳細的理論分析，提出了基于K均值采樣的Nystr?m算法。但在圖像分割中K均值采樣算法存在兩點不足:① 無法準確預估像素各特征值之間的權重;② 采樣點較多時，K均值聚類運算速度較慢。

針對以上問題，本文提出了一種基于最小誤差采樣的Nystr?m譜聚類算法。經實驗驗證，該算法在分割有效性上相對于傳統Nystr?m譜聚類算法有顯著提高。

1 譜聚類及其改進算法

1.1 譜聚類算法

譜聚類是一種基于圖論的聚類方法。圖由若干點及連接兩點的線構成，用點代表事物，線表示對應2個事物間具有的某種關系，又稱為權重。將圖劃分為若干個子圖，各子圖無交集，劃分時子圖之間被“截斷”的邊的權重和稱為損失函數[10]。譜聚類通過最小化損失函數來實現圖的劃分[11]。

(1)

損失函數：

(2)

(3)

式中，W為權重矩陣；D為對角矩陣。

(4)

定義拉普拉斯矩陣L=D-W，將最小化損失函數的問題轉化為最小化qTLq的問題[12]。

1.2 基于Nystr?m的譜聚類算法

譜聚類通過最小化qTLq實現聚類劃分，qTLq的最小值在q為L的次小特征值對應的特征向量時實現。對L進行特征分解運算量巨大，文獻[13]利用Nystr?m擴展方法求得特征向量的近似值。

(5)

式中，P(y)為核密度函數；k(x,y)為正定的核函數；λi為特征值；Φi為特征向量。

(6)

(7)

(8)

對于非連續核密度函數，設數據集X={x1,x2,…,xn}，相似度矩陣K，采樣點集Z={z1,z2,…,zm}，采樣相似度矩陣W，則K的特征值和特征向量分別為：

(9)

(10)

2 最小誤差采樣的Nystr?m方法

Nystr?m擴展方法提高了譜聚類算法的運算效率，但是如果得到的相似度矩陣與原相似度矩陣誤差過大會影響圖像的分割效果[14]。本文通過對相似度矩陣誤差進行分析，并選擇最小化誤差的采樣方法完成譜聚類圖像分割。

2.1 最小誤差分析

本文所取相似度矩陣函數為高斯核函數[15]，由中值定理可知存在C使其滿足：

(11)

相似度矩陣誤差為：

ε=‖K-EW-1ET‖F。

(12)

對于單獨數據點來說,

εIi,Ij=‖KIi,Ij-EIi,ZW-1EIj,ZT‖F。

(13)

AIi,Ij=KIi,Ij-Wpq，

BIi,Z=EIi,Z-WpZ，

CIj,Z=EIj,Z-WqZ。

(14)

(15)

(16)

從以上推導可以看出Nystr?m方法最終誤差大小由采樣數目、采樣相似度矩陣以及數據點與最近的采樣點誤差決定。

2.2 最小誤差采樣算法

對Nystr?m擴展方法進行誤差分析，發現在圖像分割中，采樣數目與相似度函數不變的情況下，可以通過最小化像素點與采樣點誤差對最終誤差進行優化。

本文選取圖像為灰度圖像，3個特征值分別為坐標x坐標、y坐標和灰度值I(x,y)。對灰度圖像進行采樣必須保證式(17)最小化。

(17)

式中，εx,y為坐標誤差；εI(x,y)為灰度值誤差。具體采樣步驟如下：

輸入：給定圖像I，像素個數n，特征中心個數m，終止迭代參數σ。

輸出：特征中心Q。

步驟 1：按照設定的采樣點個數m，在圖像I上進行均勻采樣，并將像素分配到與之最近的采樣點；

步驟2：計算采樣點3×3鄰域內像素點的灰度梯度值，選取梯度值最小的點作為新的采樣點；

步驟3：設置步長S=(nm)1/2，在2S×2S鄰域內按照距離：

d=dx,y+dI(x,y)，

(18)

為每一個采樣點分配像素。其中dx,y為坐標的歐氏距離，dI(x,y)為灰度差的絕對值。

步驟4：求取采樣點所屬像素的平均值作為新的采樣點Q，計算新舊采樣點誤差：

(19)

如果ε<σ轉步驟5；否則轉步驟3；

步驟5：輸出Q作為區域特征中心。

從算法流程可以看出，算法的關鍵在于對數據點的選取時充分利用像素點與采樣中心之間的距離關系，使得誤差最小化。根據K均值聚類算法可得知，通過步驟1在空間上進行均勻采樣可得到最小化的εx,y。利用步驟2可以防止采樣點落在噪音或者邊界上。在此基礎上，步驟3和步驟4計算每個采樣中心擁有像素的灰度值，并在一定范圍內變化像素點所屬采樣中心，并更新采樣中心坐標，利用迭代的方式最小化灰度值誤差εI(x,y)。

基于以上表述，改進的譜聚類算法步驟如下[16]:

步驟1：將圖像按照本文算法進行采樣，利用高斯函數構建采樣相似度矩陣W，采樣點與像素點的相似度矩陣E；

步驟2：通過Nystr?m方法估算出特征值與特征向量，將特征值由大到小排序后，選擇前k最小的特征值所對應的特征向量，用矩陣V表示；

步驟3：將矩陣V進行歸一化，并記歸一化的矩陣為Y：

(20)

步驟4：矩陣Y的每行視為樣本，運用K均值聚類算法將它們聚為k類；

步驟5：確定原像素點歸屬類別，完成圖像分割。

3 實驗結果與有效性分析

為了檢驗該算法的性能，對文中所述算法進行了實驗分析。實驗環境為Windows10系統、Inteli3處理器、4GB內存，實驗平臺MATLAB7.0。實驗圖像來源于Berkeley圖庫。實驗中對每幅圖像抽取m=100的像素點。

圖1為圖像數據庫中3幅原始圖像。圖2為隨機采樣Nystr?m譜聚類分割結果。圖3為本文算法分割結果。圖4為人工分割結果。

圖1 原始圖像

圖2 隨機采樣Nystr?m譜聚類分割結果

圖3 本文算法分割結果

圖4 人工分割結果

通過對比發現，在對圖1(a)～圖4(a)的松樹圖像的分割中，隨機采樣Nystr?m譜聚類分割將背景中與松塔灰度值接近的區域與目標劃分在一起，而本文提出的改進算法能準確地將目標區域分割出來。對圖1(b)～圖4(b)的水牛以及圖1(c)～圖4(c)的海豚圖像的分割中，由于圖像背景復雜，傳統分割方法效果很不理想。不僅存在大量噪點，而且存在誤分割區域。而本文算法可以更清楚地觀察到分割輪廓和圖像細節的對應情況，明顯將水牛與海豚同背景區分開來，其分割效果與人工分割結果基本一致。

4 結束語

本文基于采樣誤差分析，通過最小化像素與最鄰近采樣點之間誤差對Nystr?m譜聚類圖像分割方法進行了優化。首先在全局范圍內均勻采樣，最小化坐標之間的誤差；其次在局部范圍內利用迭代算法最小化灰度值誤差，最終找到最優的采樣中心，使得本文算法運算過程中所得相似度矩陣能更真實的反映圖像信息。通過對Berkeley圖庫標準測試圖片進行分割驗證了本算法的有效性。

[1] 章毓晉.圖像分割中基于過渡區技術的統計調查[J].計算機輔助設計與圖形學學報， 2015,27(3):379-381.

[2]ZHUZ,WANGL.InitializationApproachforFuzzyCmeansAlgorithmforColorImageSegmentation[J].ApplicationResearchofComputers,2015,32(4):1 257-1 260.

[3] 蘇木亞,郭崇慧.基于主成分分析的單變量時間序列聚類方法[J].運籌與管理,2011(6):66-72.

[4] 田 玲,鄧旌波.基于多空間多層次譜聚類的非監督SAR圖像分割算法[J].計算機應用研究,2013,30(7):2 213-2 215.

[5] 蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機科學,2008,35(7):14-18.

[6] 陽 春,張向榮,焦李成.結合Nystr?m逼近的圖半監督紋理圖像分割[J].系統工程與電子技術,2009,31(12):2 820-2 825.

[7]FOWLKESC,BELONGIES,CHUNGF,etal.SpectralGroupingUsingNystr?mExtension[J].IEEETransactionsonPatternAnalysisandMachineIntel1igencc,2004,26(2):214-225.

[8]ZHANGK,TSANGIW,KWOKJT.ImprovedNystr?mLow-rankApproximationandErrorAnalysis[C]∥InProceedingsofthe25thInternationalConferenceonMachineLearning,Helsinki,2008:1 232-1 239.

[9]ZHANGK,KWOKJT.ClusteredNystr?mMethodforLargeScaleManifoldLearningandDimensionReduction[J].JEEETransactionsonNeuralNetworks,2010,21(10):1 576-1 587.

[10] 吳 健,崔志明,時玉杰,等.基于局部密度構造相似矩陣的譜聚類算法[J].通信學報,2013(3):14-22.

[11]WANGS,GUJ,CHENF.ClusteringHigh-DimensionalDataviaSpectralClusteringUsingCollaborativeRepresentationCoefficients[M].IntelligentComputingTheoriesandMethodologies.SpringerInternationalPublishing,2015:248-258.

[12] 侯 葉,郭寶龍.基于圖論的運動對象分割[J].吉林大學學報(工學版),2008,38(4):902-906.

[13]CHENZ,QIUZ,LIJ,etal.Two-derivativeRunge-Kutta-Nystr?mMethodsforSecond-orderOrdinaryDifferentialEquations[C]∥NumericalAlgorithms,2015:1-31.

[14] 唐文俊,左亞堯,張 波,等.一種基于密度聚類Nystr?m抽樣算法[J].計算機工程與科學,2012,34(11):148-152.

[15]LUZ.ConstrainedSpectralClusteringthroughAffinityPropagation[C]∥IEEEConferenceonComputerVisionandPatternRecognition,2008:1-8.

[16] 印世樂,曾志勇.一種改進的Nystr?m譜聚類圖像分割算法[J].計算機與現代化,2014(4):20-23.

劉仲民 男，(1978—)，副教授，博士研究生。主要研究方向：機器視覺、智能信息處理與模式識別。

李博皓 男，(1990—)，碩士研究生。主要研究方向：智能信息處理與模式識別。

Error Sampling Based Nystr?m Spectral Clustering Image Segmentation

LIU Zhong-min1,LI Bo-hao1,LI Zhan-ming1,HU Wen-jin2

(1.CollegeofElectricalandInformationEngineering,LanzhouUniversityofTechnology,LanzhouGansu730050,China; 2.CollegeofMathematicandInformationTechnology,NorthwestUniversityforNationalities,LanzhouGansu730000,China)

Spectral clustering is based on the similarity of data,but the similarity matrix is complex,and the calculation process of Laplacian characteristic decomposition is very time-consuming.The Nystr?m extension method approximates the original feature space by sampling,which reduces the computational complexity of spectral clustering effectively.A new sampling method is presented in this paper,which is based on the features of image and Nystr?m error analysis.First,uniform sampling is used to generate a set of cluster centers；then,the error between data and centers is minimized by iteration.Finally,experiments verify the feasibility and effectiveness of the method.

Nystr?m；spectral clustering；image segmentation；k-means

10.3969/j.issn.1003-3106.2017.04.05

劉仲民，李博皓，李戰明，等.基于誤差采樣的Nystr?m譜聚類圖像分割算法研究[J].無線電工程,2017,47(4):20-23.

2017-01-06

國家自然科學基金資助項目 (64561042)。

TP391

A

1003-3106(2017)04-0020-04