多尺度單特征譜分割算法*

張敬茂，沈艷霞

江南大學 物聯網技術與應用教育部工程研究中心，江蘇 無錫 214122

1 引言

圖像分割是圖像理解的關鍵步驟之一[1-2]，將輸入圖像分割為不相交的連貫區域，從中提取整個區域的特征信息，減小分析的計算消耗。針對圖像分割，已經提出了很多優秀的圖像分割算法，主要分為兩類：不基于圖的算法，如均值漂移算法[3]、EM（expectation-maximization）[4]和基于圖的算法[5-9]。與不基于圖的算法相比，基于圖的算法能夠自適應地權衡局部相似關系[10]。

規范割（normalized cut，Ncut）算法是一種廣泛應用的基于譜圖理論的譜分割算法。在圖像分割中，Ncut能夠同時權衡類內相似性和類間不相似性，并且可以近似為廣義特征向量問題。使用Ncut進行圖像分割時，關于圖的相似矩陣對圖像分割結果有很大的影響。目前，為了提高譜分割效果，已有很多研究對該相似矩陣的構建進行改進。一種方法是結合圖像中像素點（或者超點）的不同特征信息構建相似矩陣[11-13]。例如文獻[12]結合4種特征信息即超點的均值和方差、像素點的顏色和邊緣信息構建相似矩陣；文獻[13]考慮結合多種局部輪廓信息，如亮度、顏色和紋理差異、結構森林輪廓等。另一種方法是對輸入圖像進行多層分解，或者結合不同的分解方法對圖像進行分解[14-17]，然后利用分解后的圖構建相似矩陣。文獻[15]對圖像進行多層分解，并以此構建多尺度相似矩陣；文獻[16]和文獻[17]利用不同的方法對圖像進行分解，然后利用分解圖構建相似矩陣。無論利用不同圖像不同特征信息，還是對圖像進行不同的分解，都有多種組合特征信息和分解圖的方式。然而在實際應用中，確定使用哪種方式是個復雜的過程，尤其是在核磁共振影像（MRI），合成孔徑雷達影像（synthetic aperture radar，SAR）等應用領域，無法提供顏色信息，此時根據顏色特征信息改進的算法就不適用，因此有必要考慮從相似矩陣中提取多尺度特征，構建新的相似矩陣，提高使用單一特征信息時譜分割的效果。

目前，擴散映射（diffusion map）在三維形狀分析[18]、圖像表示[19]、語言識別[20]等許多領域得到廣泛應用。擴散映射能夠提取出輸入圖像的本質幾何描述，對像素點來說，即以該點為中心的所有幾何結構的局部信息?；跀U散映射[21]，本文定義了一種多尺度特征描述器（diffusion map based multiscale feature descriptor，DMFD）。然后，建立擴散映射與譜圖小波[22]的關系，利用譜圖小波中切比雪夫多項式算法進行快速計算，避免計算輸入圖像DMFD全部特征值和特征向量的問題。最后，構建基于DMFD的譜分割算法，提出一種能夠自適應選擇最優尺度計算相似矩陣的方法，避免執行算法時選擇尺度的過程。

2 基于擴散映射的多尺度特征描述器

Coifman等人[21]根據馬爾科夫隨機游走定義了擴散映射。對于輸入圖像G，包含N個像素點，根據其特征信息構建的相似矩陣為A，對角矩陣轉移矩陣P=D-1A，矩陣P的特征值和特征向量分別為 (λl)l=0,1,…,N-1和 (χl)l=0,1,…,N-1，則擴散映射定義為：

其中，c表示尺度參數；g(?)表示關于特征值的函數。

給定像素點a，根據以上定義，定義基于擴散映射的多尺度特征描述器為：

在給定尺度c下，像素點之間的距離采用歐氏距離度量，即：

式（3）也被稱為擴散距離[21]。

如上所述，計算DMFD及擴散距離的步驟如算法1。

算法1計算DMFD與擴散距離

輸入：圖，尺度。

（1）對輸入圖像提取每個像素點的特征信息，利用這些特征構建相似矩陣；

（2）根據相似矩陣，計算轉移矩陣P；

（3）計算轉移矩陣P的特征值 (λl)l=0,1,…,N-1和特征向量 (χl)l=0,1,…,N-1；

（4）根據式（1）和式（2）計算所有點的DMFD；

（5）根據式（3）計算擴散距離。

3 快速計算算法

由式（1）和式（2）可知，對于尺寸為m×n的輸入圖像，需要計算DMFD的mn個特征值和特征向量。例如Berkeley數據庫中圖像尺寸為321×481，則需要對維度為N2(N=154 401)的矩陣進行特征分解，計算N個特征向量和特征值，這在實際應用中是不現實的?？紤]到譜圖小波的定義與特征值和特征向量有密切關系，并且存在快速計算譜圖小波的切比雪夫多項式算法，建立譜圖小波與擴散映射之間的關系，利用切比雪夫多項式算法來快速計算DMFD，避免對所有特征值和特征向量的計算。

由式（1）和式（3）可得：

譜圖小波中，在尺度c下，以a點為中心的基函數定義為：

由式（5）計算歐氏距離為：

根據文獻[21]，在平方可積測量空間(X,μ)中，式（6）可根據式（5）寫為如下形式。

4 多尺度單特征譜分割算法

下文首先定義算法的流程，然后分析其在實際應用時的不足，并提出一種自適應尺度選擇方法解決該問題。

4.1 基于DMFD的多尺度單特征譜分割

Ncut作為被廣泛應用的譜分割算法，其相似矩陣尺寸為N2，然而對于一般電腦來說，無法計算和存儲該矩陣。為此，將圖像分割為超點，提取超點的特征信息計算相似矩陣A。本文使用兩種特征信息，即顏色和紋理。對于顏色特征，采用RGB和HSV顏色空間，計算兩個超點間的26種顏色距離[1,23]dcolor；對于紋理特征，采用超點間的64種紋理差異[1,24]dtexture。提取超點的特征信息后，首先構建相似矩陣A和轉移矩陣P。其中Aij=exp(-dcolor/σd)或Aij=exp(-dtexture/σd)。計算擴散映射、DMFD以及dc(a,b)后，利用提出的特征描述器計算超點之間的相似性度量：

進而構成相似矩陣S。

基于DMFD的多尺度單特征譜分割算法（DMFDNcut）可描述如算法2。

算法2DMFD-Ncut

輸入：圖，k，尺度c。

輸出：分割圖像。

（1）對輸入圖像進行超點分割，并對超點提取單一特征信息，如顏色、紋理等；

（2）利用提取的特征信息構建相似矩陣A和轉移矩陣P；

（3）由式（2）計算DMFD，并由式（6）計算式（3），得到距離度量；

（4）根據式（8）計算相似矩陣S及拉式矩陣

（5）計算L的前k個特征向量，構成新的特征空間；

（6）由k-means算法對k個特征向量構成的特征空間進行聚類，得到圖像分割結果。

4.2 自適應尺度選擇

在執行DMFD-Ncut時，需要指定尺度，然后對輸入圖像在指定尺度下進行分割。DMFD-Ncut雖然可以讓用戶指定分割尺度，但是得到分割結果后才能判斷哪個尺度更為合適。這無疑為算法執行增加了困難。因此，本文提出一種逐點自適應確定最優尺度（pointwise self-adaptive optimal scale，PSOS）的方法，在分割之前確定最優尺度。

圖方差[15]可用來判斷相似向量攜帶的信息量，圖方差越大，攜帶的信息量越大。因此，本文使用圖方差作為判斷最優尺度的方法。假設輸入圖像的相似矩陣為S，a為圖像的第i個點，則Sa=Si?表示以a為中心的所有相似度量值。圖方差定義如下：

考慮上述自適應最優尺度選擇方法，DMFDNcut算法可更新為算法3。

算法3自適應DMFD-Ncut（PSOS）

輸入：圖，k，尺度集C。

輸出：分割圖像。

（1）對輸入圖像進行超點分割，并對超點提取單一特征信息，如顏色、紋理等；

（2）利用提取的特征信息構建相似矩陣A和轉移矩陣P；

（3）由式（2）計算DMFD，并由式（6）計算式（3），得到距離度量；

（4）根據式（8）計算相似矩陣S；

（5）使用式（9）計算圖方差，選取最優尺度；

（6）使用式（10）對相似矩陣進行更新，并計算相應拉式矩陣

（7）計算L的前k個特征向量，構成新的特征空間；

（8）由k-means算法對k個特征向量構成的特征空間進行聚類，得到圖像分割結果。

5 實驗分析

為了驗證本文提出的算法，在真實數據集上進行實驗，并對DMFD-Ncut和 DMFD-Ncut（PSOS）進行分析，對比這兩種算法的差別。具體數據選擇、參數設置及結果對比如下文所述。

5.1 參數設置

本文算法與使用單一特征信息構建相似矩陣的Ncut算法（Ncut_color，Ncut_texture）進行對比。實驗采用Berkeley圖像分割數據庫（BSD300），該數據庫包含測試集（100幅圖）和訓練集（200幅圖）。根據實驗及經驗，對于灰度特征取σd=1；對于顏色特征取σd=1；對于紋理特征取σd=15。對于灰度信息，選取尺度c={10,15,20,25,30,35}；對于顏色和紋理信息，選取尺度c={20,25,30}。Ncut_color與Ncut_texture的相似矩陣使用Aij=exp(-dcolor/σd)和Aij=exp(-dtexture/σd)分別計算。取4個參數對圖像分割結果進行量化評估，分別為 F-measure（F）、Segmentation Covering（Covering）、Probabilistic Rand Index（PRI）、Variation of Information（VOI）[14]。其中，F-measure度量邊緣分割效果。對每個量化評估參數，使用兩種度量方式：ODS（optimal dataset scale），對所有圖像使用固定參數進行分割；OIS（optimal image scale），對每個圖像選取最優分割參數。為了計算這兩種度量方式，本文將ODS和OIS中使用的參數設置為圖像的分割數目，k={2,3,…,40}。

5.2 實驗結果

表1為使用顏色和紋理特征的量化評估結果，最優結果用粗體標注。其中Ours_color和Ours_texture為DMFD-Ncut在所有3個尺度下的最優結果；PSOS_color和PSOS_texture為使用自適應最優尺度選擇方法的評估結果。從表1中可以看出，在使用單一特征信息進行圖像分割時，本文提出的算法相對于原Ncut算法，幾乎在所有的評估結果中，都顯示了對分割結果明顯的優勢。在只使用灰度信息時，DMFD-Ncut的ODS評估與Ncut大部分相同，OIS評估則優于Ncut。而在實際應用時，往往只會對單獨的一幅圖片進行分割，從這方面考慮，OIS評估更能反映出算法的應用價值。盡管在使用PSOS方法時，因為式（10）對兩點取平均導致圖像分割結果與直接使用DMFD-Ncut時相同或略有降低，但PSOS方法的大部分結果依然優于原Ncut算法。因此，使用PSOS方法可避免尺度選擇的過程，但直接使用DMFD-Ncut可取得更為優秀或相同的分割結果。

圖1和圖2對顏色和紋理分別提供了視覺結果對比。

（1）顏色

圖1選取人、動物、植物3類圖進行對比。在所有的3幅圖中，DMFD-Ncut能夠在k=10時將顯著目標分割出來，而Ncut_color則無法識別。在細節方面，如圖（1）中，DMFD-Ncut在k=20時就可以將人、帆船、海分割出來，而Ncut_color則一直無法將三者完全分割；圖（2）、（3）中，DMFD-Ncut始終能較完整地將鳥與蘑菇識別出來，而Ncut_color在分割數增加時，將背景和目標物都進行不適當的分割。以上說明，DMFD能夠提供更加本質的特征描述，從而提升圖像分割效果。

（2）紋理

圖2選取人、動物、建筑進行對比。在圖像背景復雜（圖（1）、（3））或背景簡單（圖（2））時，DMFDNcut都能夠盡量將符合視覺直覺的區域分割到一類，得到較滿意的分割結果。如圖（1），DMFD-Ncut完美地將路面分為一類，且將人識別出來，而Ncut_texture將路面過分割。而圖（3）中，隨著分割數k增加，DMFD-Ncut仍能將船以及建筑物識別出來，而Ncut_texture傾向于將目標過分割。這說明，在使用紋理特征時，DMFD仍能對圖像提供更為本質的特征描述。

圖3為使用顏色特征時，利用PSOS方法的圖像分割結果與不同尺度下DMFD-Ncut分割結果對比。如圖所示，PSOS方法可以將最優的尺度選取出來。如小丑魚部分，使用PSOS方法可以將小丑魚較完整地分割出來。但是在背景的珊瑚部分，使用PSOS的分割效果比尺度為25時差，但是優于尺度為30時的結果。這是因為計算PSOS相似矩陣的公式（10）對逐點的最優結果取平均導致的。因此，使用PSOS方法可避免尺度選擇的過程，但直接使用DMFD-Ncut可取得更為優秀或相同的分割結果。

Table 1 Quantitative evaluation on BSD300表1 BSD300量化評估結果

Fig.1 Comparison of segmentation results on color圖1 使用顏色特征的分割結果對比

5.3 運行時間

圖4為在給定尺度c下，隨著相似矩陣尺寸N的變化，對一個像素點計算擴散映射的時間對比。其中N=100,150,200,…,5 000 ，“diffusion map”表示未使用快速計算方法時的時間曲線，“DMFD”表示使用快速計算方法時的時間曲線。當相似矩陣尺寸不大時，如N＜1 000時，兩者相差不大；但是隨著N變大，本文方法計算時間明顯低于直接計算擴散映射所用時間。

圖5為本文算法運行時間與Ncut算法運行時間的對比，隨機選取20幅圖片，設置分割數目k=30。其中“+”表示Ncut運行時間，“◆”表示 DMFD-Ncut運行時間，“o”表示PSOS DMFD-Ncut運行時間。DMFD-Ncut在單尺度下運行，PSOS DMFD-Ncut則選取3個尺度進行自適應選擇。如圖所示，在大部分數據上，DMFD-Ncut和PSOS DMFD-Ncut運行時間小于Ncut，而在小部分情況下PSOS DMFD-Ncut運行時間遠高于其余兩種算法，這是因為需要在不同尺度中自適應地選擇合適的尺度，并根據待選擇尺度的多少，運行時間也會有所變化。

Fig.2 Comparison of segmentation results on texture圖2 使用紋理特征的分割結果對比

6 結束語

使用譜分割算法進行圖像分割時，無論使用多特征融合還是圖分解方法，都是十分復雜的，尤其是在某些應用領域如MRI影像、SAR影像等，無法提供某些特征如顏色，因此本文提出一種基于擴散映射的多尺度特征描述器（DMFD），提高使用單一特征信息下，譜分割在圖像分割上的效果。DMFD可以描述輸入圖像更為本質的結構，為后續譜分割過程提供更為本質的特征描述。為了使DMFD在實際應用中可行，本文建立了擴散映射與譜圖小波的關系，利用譜圖小波中的切比雪夫多項式算法快速計算DMFD，避免了擴散映射必須計算全部特征值和特征向量的問題?；贒MFD，構建了相應譜分割算法DMFD-Ncut，提出了一種能夠自適應選擇最優尺度計算相似矩陣的方法，避免了執行算法時選擇尺度的過程。實驗顯示，DMFD-Ncut和使用自適應尺度選擇方法的DMFD-Ncut都能夠顯著提升使用單一特征的Ncut在圖像分割中的效果。然而使用超點分割解決Ncut計算量大的問題，使得圖像分割結果過分依賴于超點分割的效果，下一步工作將集中研究適用于DMFD-Ncut的快速計算方法。

Fig.3 Comparison of segmentation results with PSOS and DMFD-Ncut圖3 使用PSOS的圖像分割結果與不同尺度DMFD-Ncut結果對比

Fig.5 Comparison of running time with different algorithms圖5 不同算法運行時間對比

[1]Kim S,Nowozin S,Kohli P,et al.Higher-order correlation clustering for image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,36:1761-1774.

[2]Mobahi H,Rao S R,Yang A Y,et al.Segmentation of natural images by texture and boundary compression[J].International Journal of Computer Vision,2011,95(1):86-98.

[3]Comaniciu D,Meer P.Mean shift:a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.

[4]Carson C,Belongie S,Greenspan H,et al.Blobworld:image segmentation using expectation-maximization and its application to image querying[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,24(8):1026-1038.

[5]Yuan Yonghua,Li Yu,Zhao Xuemei.High-resolution panchromatic remote sensing image segmentation based on spectral clustering[J].Chinese Journal of Scientific Instrument,2016,37(7):1656-1664.

[6]Yang Nongying,Li Feng,Gui Yan.Repeated texture elements extraction from texture images[J].Journal of Frontiers of Computer Science and Technology,2016,10(8):1154-1165.

[7]Shi Jianbo,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[8]Benson A R,Gleich D F,Leskovec J.Tensor spectral clustering for partitioning higher-order network structures[C]//Proceedings of the 2015 International Conference on Data Mining,Vancouver,Apr 30-May 2,2015.Philadelphia:SIAM,2015:118-126.

[9]Aytekin ?,Ozan E C,Kiranyaz S,et al.Extended quantum cuts for unsupervised salient object extraction[J].Multimedia Tools andApplications,2017,76(8):10443-10463.

[10]Estrada F J,Jepson A D.Benchmarking image segmentation algorithms[J].International Journal of Computer Vision,2009,85(2):167-181.

[11]Rohkohl C,Engel K.Efficient image segmentation using pairwise pixel similarities[C]//LNCS 4713:Proceedings of the 29th Annual Symposium of the German Association for Pattern Recognition,Heidelberg,Sep 12-14,2007.Berlin,Heidelberg:Springer,2007:254-263.

[12]Li Xiang,Jin Lianghai,Song Enmin,et al.An integrated similarity metric for graph-based color image segmentation[J].Multimedia Tools and Applications,2016,75(6):2969-2987.

[13]Pont-Tuset J,Arbeláez P,Barron J T,et al.Multiscale combinatorial grouping for image segmentation and object proposal generation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,39(1):128-140.

[14]Arbelaez P,Maire M,Fowlkes C C,et al.Contour detection and hierarchical image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(5):898-916.

[15]Cour T,Bénézit F,Shi Jianbo.Spectral segmentation with multiscale graph decomposition[C]//Proceedings of the 2005 Conference on Computer Vision and Pattern Recognition,San Diego,Jun 20-26,2005.Washington:IEEE Computer Society,2005,2:1124-1131.

[16]Kim T H,Lee K M,Lee S U.Learning full pairwise affinities for spectral segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(7):1690-1703.

[17]Wang Xiaofang,Tang Yuxing,Masnou S,et al.A global/local affinity graph for image segmentation[J].IEEE Transactions on Image Processing,2015,24(4):1399-1411.

[18]Sidi O,van Kaick O,Kleiman Y,et al.Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering[J].ACM Transactions on Graphics,2011,30(6):126.

[19]Seo D,Ho J,Vemuri B C.Covariant image representation with applications to classification problems in medical imaging[J].International Journal of Computer Vision,2016,116(2):190-209.

[20]Keller Y,Coifman R R,Lafon S,et al.Audio-visual group recognition using diffusion maps[J].IEEE Transactions on Signal Processing,2010,58(1):403-413.

[21]Coifman R R,Lafon S.Diffusion maps[J].Applied and Computational HarmonicAnalysis,2006,21(1):5-30.

[22]Hammond D K,Vandergheynst P,Gribonval R.Wavelets on graphs via spectral graph theory[J].Applied and Computational HarmonicAnalysis,2011,30(2):129-150.

[23]Pele O,Werman M.Fast and robust earth mover's distances[C]//Proceedings of the 12th International Conference on Computer Vision,Kyoto,Sep 27-Oct 4,2009.Washington:IEEE Computer Society,2009:460-467.

[24]Leung T,Malik J.Representing and recognizing the visual appearance of materials using three-dimensional textons[J].International Journal of Computer Vision,2001,43(1):29-44.

附中文參考文獻：

[5]袁永華,李玉,趙雪梅.基于譜聚類的高分辨率全色遙感影像分割[J].儀器儀表學報,2016,37(7):1656-1664.

[6]楊弄影,李峰,桂彥.紋理圖像中重復紋理元素提取方法[J].計算機科學與探索,2016,10(8):1154-1165.