基于局部優先的彩色圖像分割算法

張　琦，陳金勇，帥　通

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

?

基于局部優先的彩色圖像分割算法

張琦，陳金勇，帥通

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

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

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

0　引言

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

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

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

1　通勤時間

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

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

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

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

Cij=Hij+ Hji。

(1)

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

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

(2)

2　MSICTE算法

2.1局部優先

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

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

(3)

(4)

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

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

(5)

式中，λ(d,l)表示細節信息的加權優先度；(1-λ(d,l))表示亮度信息的加權優先度；λ(d,l)表示為：

(6)

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

局部優先可以使簇內的數據對象更加緊密，也可以使簇與簇之間數據對象更加分散。從而為后續的圖像分割算法提供更為適合的數據結構，并獲得更高的圖像分割質量。

2.2通勤時間嵌入算法

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

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

(7)

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

A=UΣVT。

(8)

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

使用余弦函數計算相似度矩陣W：

W=AAT=UΣ2UT。

(9)

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

U=AVΣ?

(10)

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

(11)

(12)

根據式(10)可以得到：

(13)

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

(14)

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

(15)

2.3MSICTE算法主要步驟

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

MSICTE算法的詳細步驟如下：

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

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

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

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

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

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

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

輸出：最終的圖像分割結果。

3　實驗設計及結果分析

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

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

圖1　4種算法圖像分割結果對比

(單位：s)

從圖1中可以得到如下結論：

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

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

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

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

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

4　結束語

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

[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—)，博士。主要研究方向：航天地面應用、信息處理和圖像分割。

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

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

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

TP391A

1003-3106(2016)08-0027-04

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