張　琦，陳金勇，帥　通

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

?

基于局部優(yōu)先的彩色圖像分割算法

張琦，陳金勇，帥通

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

針對彩色圖像分割聚類算法效果不理想以及計算復(fù)雜度較高的問題，提出了一種有效的彩色圖像分割算法。該算法只對小區(qū)域進行處理操作，大大降低了計算復(fù)雜度，而且大大提高了圖像分割的質(zhì)量。與此同時，定義了名為局部優(yōu)先級的變量，同時考慮了小區(qū)域的亮度和其他詳細信息，減少由于只考慮像素點的亮度信息導(dǎo)致不恰當劃分的可能性。實驗結(jié)果表明，在真實彩色圖像的分割結(jié)果中，該算法具有較好的圖像分割效果。

彩色圖像分割；均值漂移；通勤時間嵌入；局部優(yōu)先

0　引言

圖像分割是計算機視覺領(lǐng)域的一個重要話題，它是一個把圖像劃分為幾個非相交區(qū)域的過程，使得每個區(qū)域均勻且相關(guān)[1-2]。彩色圖像比灰度圖像包含更多的信息，因此彩色圖像分割逐漸成為研究的重點，并且涌現(xiàn)出一系列的圖像分割算法。例如，K-Means算法[3]和層次算法[4]可以在圖像像素是凸形簇時獲得較好的結(jié)果。譜聚類算法[5-6]不對簇的結(jié)構(gòu)做強的假設(shè)，圖像分割效果優(yōu)于K-Means算法和層次算法。然而，譜聚類算法在執(zhí)行中需要對圖的拉普拉斯矩陣進行特征值分解，使得算法的時間復(fù)雜度、空間復(fù)雜度高達O(n3) 和O(n2)[7-8]。

近來來，研究學(xué)者采用采樣技術(shù)降低譜聚類算法特征值分解的計算復(fù)雜度。例如，文獻[9]利用Nystrom方法獲取隨機采樣樣本的特征值，然后逼近原始數(shù)據(jù)的特征值。文獻[10]使用譜聚類算法分析處理利用K-Means算法得到的小規(guī)模的原始數(shù)據(jù)中心點集合。文獻[11]利用稀疏編碼的思想，近似表達原始數(shù)據(jù)的相似度矩陣，從而可以高效地計算出特征值。然而，無論對原始數(shù)據(jù)進行任何的采樣或者代表點選取，都不能準確捕獲原始數(shù)據(jù)的結(jié)構(gòu)。并且，一旦采樣點或者代表點數(shù)據(jù)足夠多時，特征值分解所消耗的時間也不可忽視。

為了解決這些問題，本文提出一種結(jié)合MeanShift算法與改進的通勤時間嵌入算法(以下簡稱為MSICTE算法)。MSICTE算法具有較低的計算復(fù)雜度，并且能夠獲得較好的圖像分割結(jié)果。MSICTE算法首先使用MeanShift算法對彩色圖像進行預(yù)分割，并用預(yù)分割得到的區(qū)域亮度和細節(jié)信息的均值代表該區(qū)域，并以此為基礎(chǔ)構(gòu)建一個圖，然后利用基于局部優(yōu)先的通勤時間嵌入算法對預(yù)分割形成的區(qū)域進行劃分，得到最終的圖像分割結(jié)果。在MSICTE算法中，MeanShift算法[12]不僅可以顯著減少彩色圖像的數(shù)據(jù)量，而且能保留原始圖像的不連續(xù)性特性。并且，通勤時間基于Laplacian圖、熱核和圖上隨機游走等譜圖理論，能夠捕獲數(shù)據(jù)的復(fù)雜空間結(jié)構(gòu)[13]。實驗結(jié)果表明，MSICTE算法能獲得高質(zhì)量的圖像分割結(jié)果。

1　通勤時間

給定一個權(quán)圖G=(V，E，W )，V表示圖的頂點的集合，E?V×V是圖的邊的集合，W表示圖的相似度矩陣。

定義1：首中時間H(i,j)。圖上隨機游走的首中時間H(i,j)為由i點出發(fā)首次到達j點的期望步長：

式中，wij是相似度；dii是圖的度。

定義2：通勤時間Cij[14]可定義為由i點出發(fā)首次到達j點后第一次返回i點的期望步長。通勤時間與首中時間之間的關(guān)系可通過式(1)來描述：

Cij=Hij+ Hji。

(1)

通勤時間Cij可用拉普拉斯矩陣L和它的偽逆計算得到，如式(2)所示：

Cij=vol(ei-ej)TL?(ei-ej)。

(2)

2　MSICTE算法

2.1局部優(yōu)先

彩色圖像的視覺信息包括亮度和細節(jié)信息。亮度主要包含像素值，而細節(jié)信息是指像素值的變化程度。本文中，預(yù)分割區(qū)域的合并策略描述為：綜合亮度信息、細節(jié)信息，并利用下文定義的局部優(yōu)先概念合并這些區(qū)域。

對于給定的第l個局部區(qū)域記為Re(l)∈Rn×m×d，像素(i,j,d)的值記為re(i,j,d)，則該區(qū)域的亮度和細節(jié)信息分別記為lig(d，l)、det(d，l)，如式(3)和式(4)所示。

(3)

(4)

Re(l)的局部優(yōu)先度f(d,l)表示為：

f(d,l)=λ(d,l)det(d,l)+(1-λ(d,l))lig(d,l)。

(5)

式中，λ(d,l)表示細節(jié)信息的加權(quán)優(yōu)先度；(1-λ(d,l))表示亮度信息的加權(quán)優(yōu)先度；λ(d,l)表示為：

(6)

λ(d,l)和(1-λ(d,l))稱為局部優(yōu)先的敏感因子，可反映f(d,l)的局部信息敏感度。局部亮度的敏感因子的值越大，亮度信息的局部優(yōu)先敏感度越大。

局部優(yōu)先可以使簇內(nèi)的數(shù)據(jù)對象更加緊密，也可以使簇與簇之間數(shù)據(jù)對象更加分散。從而為后續(xù)的圖像分割算法提供更為適合的數(shù)據(jù)結(jié)構(gòu)，并獲得更高的圖像分割質(zhì)量。

2.2通勤時間嵌入算法

對于一個給定的數(shù)據(jù)集A，它包含n個數(shù)據(jù)點，每個數(shù)據(jù)點由p個屬性進行描述，即A∈Rn×p，A=[a1,a2,…,an]T，可使用歸一化拉普拉斯矩陣Ln推導(dǎo)通勤時間Cij。

根據(jù)式(2)，Cij也可以表示為：

(7)

A的奇異值分解可以表示為：

A=UΣVT。

(8)

式中，U與V正交；Σ=diag(σ1，…，σp)；UUT=I∈Rn×n；VVT=E∈Rp×p；Σ是奇異值方陣。

使用余弦函數(shù)計算相似度矩陣W：

W=AAT=UΣ2UT。

(9)

對于式(8)，兩邊同時右乘(ΣVT)RP，并應(yīng)用右偽逆公式(X)RP=XT(XXT)-1，可以推導(dǎo)出

U=AVΣ?

(10)

因此，矩陣ATD-1A的特征值分解可以表示為：

(11)

(12)

根據(jù)式(10)可以得到：

(13)

結(jié)合式(7)和式(12)，Cij可以變換為：

(14)

式(14)說明i和j兩點間的通勤時間Cij等于矩陣S的第i列與第j列間的歐氏距離的平方，并且下式成立：

(15)

2.3MSICTE算法主要步驟

MSICTE算法步驟主要包括：首先使用Mean Shift算法把原始圖像預(yù)分割為若干個小圖像區(qū)域；然后利用本文定義的局部優(yōu)先策略對預(yù)分割結(jié)果構(gòu)建無向圖；最后利用通勤時間嵌入算法處理，得到最終的圖像分割結(jié)果。

MSICTE算法的詳細步驟如下：

輸入：待分割原始圖像及分割的類別數(shù)目k；

步驟1：使用Mean Shift算法對原始圖像進行預(yù)分割，得到若干個小區(qū)域；

步驟2：利用本文定義的局部優(yōu)先策略對預(yù)分割后小區(qū)域計算，得到其代表點集合A。

步驟3：使用式(9)計算W。

步驟4：使用式(11)計算ATD-1A。

步驟6：使用式(15)計算矩陣S，然后調(diào)用k-means算法將S聚類為k個簇。

步驟7：使用邊緣檢測算法獲取物體的輪廓。

輸出：最終的圖像分割結(jié)果。

3　實驗設(shè)計及結(jié)果分析

本節(jié)對本文提出的MCISTE算法進行實驗對比，測試圖像3幅、圖像大小421×381或381×421。實驗硬件環(huán)境為：聯(lián)想 Ideapad Y460，Intel(R) Core(TM) i3M 350 @ 2.27 GHz CPU、2 G 內(nèi)存；軟件環(huán)境為：Windows 7操作系統(tǒng)、Matlab2010a。

為驗證本文算法的有效性，MSICTE算法與3種算法進行對比實驗，對比算法分別為：Nystr?m方法的譜聚類算法(SCUNM算法)、結(jié)合Mean shift與模糊C均值的MSFCM算法、結(jié)合Mean Shift與Ncut算法的MSNcut算法。4種算法的分割結(jié)果如圖1所示，運行時間如表1所示。圖1(a)中為原始圖像，且從上至下類別數(shù)分別為3、8、4；第2列SCUNM算法的圖像分割結(jié)果；第3列為MSFCM算法的圖像分割結(jié)果；第4列為MSNcut算法的圖像分割結(jié)果；第5列為本文提出的MSICTE算法圖像分割結(jié)果。

圖1　4種算法圖像分割結(jié)果對比

(單位：s)

從圖1中可以得到如下結(jié)論：

① 使用均值漂移算法進行預(yù)分割的MSFCM、MSNcut和MSICTE算法能夠獲得比SCUNM算法更好的圖像分割結(jié)果。SCUNM算法為了降低譜聚類算法的計算復(fù)雜度，采用了基于采樣技術(shù)的Nystr?m方法，然而采樣點不一定能精確的捕捉整個數(shù)據(jù)集的結(jié)構(gòu)，會丟失一部分信息，導(dǎo)致無法從圖1(b)圖像分割結(jié)果中得到物體的輪廓，而其他3種算法不使用采樣技術(shù)，因此保持了圖像的顯著特征。因此，可以從MSFCM、MSNcut和MSICTE算法的圖像分割結(jié)果清晰的得到物體的輪廓；

② MSNcut的圖像分割結(jié)果好于MSFCM。MSFCM算法容易陷入局部最優(yōu)。如，針對圖1(a)中的圖像2和圖像3從上至下，MSFCM算法把圖像2中的“大?！迸c圖像3中的“石頭”分割為小塊，沒有保留圖像的全局信息。反觀MSNcut算法始終可以獲得圖像的全局信息，能夠得到全局最優(yōu)結(jié)果；

③MSICTE算法的圖像分割質(zhì)量最好。MSICTE算法首先使用MS算法保留原始圖像的顯著特征，隨后利用通勤時間算法得到全局最優(yōu)的圖像分割結(jié)果。從圖1中可以明顯看出，MSICTE的圖像分割結(jié)果清晰，可輕松識別圖像中的物體，并且物體的輪廓清晰、完整、準確。

在表1中可以看出，在所有的4種彩色圖像分割算法中，TMSNcut

總之，MSICTE算法能夠得到較好的圖像分割質(zhì)量，且運行效率較高。

4　結(jié)束語

本文提出了一種結(jié)合均值漂移算法與改進的通勤時間嵌入的彩色圖像分割算法，實驗表明本文提出的算法較其他常用的方法具有更高的有效性和魯棒性。本文算法的長處在于綜合利用了均值漂移和通勤時間嵌入算法的優(yōu)點。預(yù)分割階段的均值漂移算法能夠較好的保持原始圖像不連續(xù)特征，而基于局部優(yōu)先策略構(gòu)建的區(qū)域鄰接圖與通勤時間算法對預(yù)分割后的小區(qū)域進行處理，大大增強了圖像分割算法的性能。除此之外，MSICTE算法具有較低的時間復(fù)雜度。

[1]BAI X D，CAO Z G，YU Z H，et al.Color Image Segmentation Using Watershed and Nystr?mMethod Based Spectral Clustering[C]∥Proceedings of SPIE—The International Society for Optical Engineering，2011:1-8.

[2]邢旭東，周旭，米健.基于改進的人工蟻群的圖像分割算法[J].無線電工程，2013，39(6):71-73，81.

[3]GUI Y，BAI X，LI Z，et al.Color Image Segmentation UsingMean Shift and Improved Spectral Clustering，Control Automation Robotics &Vision[C]∥Proceedings of 2012 12th International Conference,2012:1 386-1 391.

[4]GUPTA P，SAXENA S，SINGH S，et al.Color Image Segmentation:A State of the Art Survey[J].International Journal of Computational Intelligence Research，2012，8(1):17-25.

[5]VON L U.A Tutorial on Spectral Clustering[J].Statistics and Computing,2007，17(4):395-416.

[6]NG A Y，JORDANM I，WEISS Y.On Spectral Clustering:Analysis and an Algorithm[C]∥Proceedings of Advances in Neural Information Processing Systems.Cambri-dge，MA:MIT Press，2001(14):849-856.

[7]SHI J，MALIK J.Normalized Cuts and Image Segmentation[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2000，22(8):888-905.

[8]CHEN W Y，SONG Y Q，BAI H J.Parallel Spectral Clustering in Distributed Systems[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2011，33(3):568-586.

[9]FOWLKES C，BELONGIE S，CHUNG F.Spectral Grouping Using the Nystr?mMethod[J].Pattern Analysis andMachine Intelligence，IEEE Transactions on，2004，26(2):214-225.

[10]YAN D H，HUANG L，JORDANM I.Fast Approximate Spectral Clustering[C]∥Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM，2009:907-916.

[11]CHEN X L，CAI D.Large Scale Spectral Clustering with Landmark-Based Representation[C]∥Proceeding of 2011 AAAI.

[12]COMANICIU D，MEER P.Mean Shift:A Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2002，24(5):603-619.

[13]FOUSS F，PIROTTE A，RENDERS JM，et al.Random-Walk Computation of Similarities Between Nodes of a Graph with Application to Collaborative Recommendation[J].IEEE Transactions on Knowledge and Data Engineering，2007，19(3):355-369.

[14]QIU H J，HANCOCK E R，Clustering and Embedding Using Commute Times[J].IEEE Transactions on Pattern Analysis andMachine Intelligence，2007，29(11):1 873-1 890.

張琦男，(1987—)，博士。主要研究方向：航天地面應(yīng)用、信息處理和圖像分割。

陳金勇男，(1970—)，研究員。主要研究方向：系統(tǒng)工程、航天地面應(yīng)用。

AColorImageSegmentationAlgorithmBasedonLocalPriority

ZHANGQi，CHENJin-yong，SHUAITong

(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

Inviewofunfavorableclusteringeffectandhighcomputationalcomplexityforcolorimagesegmentation，anovelalgorithmwhichcansupplyeffectivecolorimagesegmentationisproposedinthispaper.Thealgorithmisonlyusedforprocessingandoperationofsmallregions，thussignificantlyimprovingthecomputationalcomplexityandthequalityofimagesegmentation.Meanwhile，thelocalpriorityisdefined，consideringthelightnessandotherdetailedinformationofsmallregionsinordertoreducetheprobabilityofgeneratingsomeinappropriatepartitioningwhenconstructingthegraphbyusingonlythelightnessinformationofpixels.Theexperimentalresultsshowthatthisalgorithmhasbetterimagesegmentationeffect.

colorimagesegmentation；meanshift；commutetimeembedding；localpriority

10.3969/j.issn.1003-3106.2016.08.07

2016-05-05

中國博士后科學(xué)基金資助項目(2015M580217)；河北省博士后科學(xué)基金資助項目(B2015005003)。

TP391A

1003-3106(2016)08-0027-04

引用格式：張琦，陳金勇，帥通.基于局部優(yōu)先的彩色圖像分割算法[J].無線電工程,2016,46(8):27-30.