多尺度歸一化割用于遙感圖像分割

黃煌，肖鵬峰，王結臣

(1.江蘇省地理信息技術重點實驗室，南京 210023；2.南京大學 地理信息科學系，南京 210023)

多尺度歸一化割用于遙感圖像分割

黃煌1，2，肖鵬峰1，2，王結臣1，2

(1.江蘇省地理信息技術重點實驗室，南京 210023；2.南京大學 地理信息科學系，南京 210023)

針對高分辨率遙感圖像數據量大、地物類型豐富、紋理結構復雜等特點，該文利用多尺度歸一化割方法進行高分辨率遙感圖像的分割。該方法是一種從全局出發的基于圖論的分割方法，能夠兼顧粗糙層和精細層的信息，適合復雜地物的分割。利用南京某區域Ikonos數據進行了實驗，并與主流遙感圖像分割軟件eCognition中多尺度分割模塊進行了效果對比和定量評價。結果表明，該方法在高分辨率遙感圖像分割中可以取得較好的效果，具有較好的研究前景。

圖像分割；遙感圖像；多尺度；歸一化割；精度評價

0 引 言

隨著衛星及傳感器技術的不斷發展，衛星遙感呈現出高空間分辨率、高光譜分辨率和高時間分辨率的趨勢，其中高空間分辨率是目前遙感應用領域普遍關注的指標。高空間分辨率遙感為經濟建設、國防安全和社會公眾信息服務等領域提供了重要的數據源。遙感圖像分割是高空間分辨率遙感圖像理解和地物識別的關鍵問題，也是有效利用地物信息的基礎[1]，它可以將遙感圖像的同質區域分離開，使后續的分析和應用可以針對同質區域進行，有效提高地物識別的精度和效率。高空間分辨率遙感圖像空間分辨率高，不同地物分異明顯，紋理信息豐富，有利于提高圖像分割的精度，但圖像數據量大、含多尺度信息等使得高空間分辨率遙感圖像分割成為一個難題。

歸一化割是一種基于圖論的圖像分割方法。圖論是離散數學的一個分支，它是以圖為研究單位，研究頂點和邊組成的圖形的數學理論和方法。圖論在數據聚類和圖像分割中的應用可以追溯到1971年Zahn的工作[2]，他提出的基于最小生成樹的圖像分割方法，使用固定閾值進行圖像分割和點聚類。基于圖論的圖像分割方法具有廣泛的數學基礎，并具有能捕獲全局特征的優點，從而在圖像分割領域廣泛應用。Wu和Leahy在1993年將最小割原理應用于圖像分割[3]，該方法容易劃分出孤立小區域。Shi和Malik克服了最小割準則中容易劃分出孤立小區域的缺點，于1997提出的歸一化割方法[4]，并很快得到廣泛應用。

但是，歸一化割方法存在明顯的缺點：運算量巨大，是一個NP-hard問題。Shi和Malik在實數范圍內將該問題轉化為一個Rayleigh問題，得到了有效的近似解。后續出現了一些改進算法效率的方法，如Fowlkes首先提出采用Nystrom近似方法[5]，該方法通過采樣估計相似度矩陣和特征向量，一定程度上提高了計算效率；Belongie等提出了改進后的Nystrom-Ncut方法[6]；Yu等提出了多類的思想重新定義了分割標準[7]，多類的概念是指把圖分成多個不相交的集合，多類譜圖求解的特點在于能夠在一次循環中求出包含多個分割信息的特征向量。在此方法上，Tolliver等提出了更有效的計算圖的Laplace矩陣特征向量的方法[8]；Cour等用多尺度方法改進了多類譜圖方法[9]，使求解復雜度呈線性增長，從而使歸一化割能處理大規模的數據。此后，研究重點主要在提高分割效果，如Cai等提出基于形狀的歸一化割方法[10]；Sun等結合紋理信息進行歸一化割[11]；Zhang等提出彩色圖像中最小化信息丟失的方法[12]；Mei等將K-means方法和歸一化割結合[13]等。

針對高分辨率遙感圖像數據量大，含多尺度信息等特點，本文采用多尺度歸一化割的方法分割遙感圖像。該方法可以實現大尺寸遙感圖像的快速分割，同時兼顧精細層與粗糙層的信息，適用于高空間分辨率遙感圖像的分割。

1 歸一化割原理

圖G=(V，E)可以分割成兩個不相交的集合A和B，A∪B=V，A∩B=?，只需移除連接兩個集合的邊。這兩個部分的相似度可以通過移除的邊的權重計算。在圖像理論語言中，它被稱為切割：

(1)

對于一個圖像的最優分割是將切割值降到最低。但是這一最小切割準則有利于切割圖形中的孤立結點。為了避免切割產生孤立結點，Shi和Malik提出了歸一化方法解決這一問題，稱為歸一化割(normalized cut)：

(2)

2 多尺度歸一化割

2.1 權值定義

首先確定圖像上任意兩點之間的相關性計算方法，考慮亮度、距離、圖的邊緣等信息，將權值計算方法定義如下：

WI(ij)=e-‖Xi-Xj‖2/σx-‖Ii-Ij‖2/σI

(3)

其中，Xi和Ii分別表示像元位置和亮度。在此基礎上定義基于邊緣的權值：

WC(ij)=e-maxx∈line(i,j)‖Edge(x)‖2/σC

(4)

結合上述兩種權值定義得到如下的相似度計算方法：

(5)

2.2 關聯半徑

當兩點之間的距離大于一定的關聯半徑r時，設定兩點之間的權值為0，這樣可以很大程度上提高計算效率。關聯半徑的設定對于分割結果和分割時間產生很大的影響。對于Ikonos的0.86m分辨率遙感圖像(大小為100像素×80像元)設定不同關聯半徑進行歸一化割分割實驗，結果如下：

圖1 不同關聯半徑的歸一化割分割結果

對不同關聯半徑圖像進行分割所用時間如表1所示。

表1 不同關聯半徑對應歸一化割時間

可以看出隨著關聯半徑的增加，分割時間也逐步增加，而對于圖像分割效果，實驗圖像為單一建筑屋頂遙感圖像，可以看出，該建筑屋頂較長。在關聯半徑為4的分割圖像中，我們可以看出，建筑屋頂未被完整分割。在關聯半徑為8及16的分割圖像圖1(c)、圖1(d)中，可以看到屋頂被完整分割出來。

同時可以看出，不同關聯半徑的分割效果和效率具有很大影響，因此，將圖劃分為不同的尺度，對不同尺度采用不同的關聯半徑進行分割，最后綜合不同尺度的分割結果，就可以很大程度上提高分割效率。

2.3 多尺度歸一化割算法流程

設有圖像I，N為圖像I中的總像元數，用I中的像素作為頂點構造賦權圖G=(V，E)，構造相似度矩陣W=(wi,j)N×N，并將賦權圖G=(V，E)表示為G=(V，E，W)。利用等間距采樣的方法將圖G分解成不同的尺度。圖G的相似度矩陣可表示為：

W=W1+W2+…+WS

(6)

其中，WS表示距離固定空間距離的像元對的相似度：僅當Gr,s-1

圖2 多尺度圖分解在r=1時一維示意圖

通過多尺度分割并行處理多個尺度圖的方法，使信息可以在不同尺度圖中傳播。令Xs∈{0,1}Ns×K為尺度圖s中的劃分矩陣，如果結點i∈Is屬于劃分k，則Xs(i,k)=1。 構造多尺度劃分矩陣和多尺度對角相似度矩陣如下：

(7)

對于多尺度分割，需要使分割代價在不同尺度間傳遞。在最精細尺度圖上需要考慮所有較粗尺度圖中的連接，以達到所有尺度圖的一致性分割。為解決所有尺度圖的一致性，將較粗尺度圖結點的劃分矩陣取為其在較細尺度圖上投影所包含結點劃分矩陣的均值，通過約束多尺度圖劃分矢量X來實現。對于圖層Is+1中的所有結點i：

(8)

采樣鄰域Pi表示圖層Is+1中點i在較精細尺度圖Is上的投影，其絕對值簡單定義為采樣鄰域中的結點數目。

定義矩陣Cs,s+1(尺寸為Ns+1×Ns)作為尺度圖Is和Is+1之間的跨尺度插值矩陣：

(9)

定義跨尺度約束矩陣C以及跨尺度約束方程：

(10)

使用約束多尺度歸一化分割標準：

(11)

并且滿足CX=0，X∈{0,1}N*×K，X1K=1N*，其中N*=∑SNS。 上述問題的最優解即為分割結果。

3 實驗和分析

3.1 Ikonos圖像分割實驗

利用2010年南京市棲霞區某地0.86m Ikonos

多光譜遙感圖像進行多尺度歸一化割實驗，得到如下結果：

圖3 建筑及農田區域遙感圖像及多尺度歸一化割結果

可以看出，該算法在建筑區域和農田區域的分割中都取得較好的效果。在建筑區域遙感圖像中，所有建筑都被獨立分割出來，且大部分建筑邊界較好地貼合了實際邊界。右側存在少量房屋分割結果不貼合實際建筑邊界的現象，而道路區域由于關聯半徑大小的原因，難以完整地分割出來，道路分割結果表現為多個斷裂的部分，植被區域存在類似問題。對于農田遙感圖像，由于一塊農田的范圍較大，受分割關聯半徑影響，分割結果存在一定破碎，但是不同塊農田的邊界都實現了較好的分割，農田周邊的綠地區域也都和農田分割開，且分割結果貼合實際邊界。中部和左下方的小湖也都較完整地分割出來了。從目視結果分析，可以看出該方法在遙感圖像分割中的表現較好，保證了分割結果不同區域內的同質性和不同區域間的異質性，可以滿足一般的分割精度要求。

3.2 精度評價

為了進一步評價分割結果，利用主流遙感圖像分割軟件eCognition中的多尺度分割工具與多尺度歸一化割方法進行分割效果比對，原遙感圖像采用圖3(a)。在eCognition中不斷調整參數，得到分割結果較優的幾組參數；在多尺度歸一化割中分別設定K值為250，300，350，得到如下結果：

從圖4中可以看到對于建筑區域，兩者都能夠較好的區分。多尺度歸一化割中，分割塊數K值的設定過大或者過小會使分割結果呈現過分割或者欠分割，合理K值下，分割結果較為理想，建筑屋頂分割完整且貼合實際邊界，分割結果各區域內同質性較高。eCognition分割結果中，從3幅圖中的下方區域，都可以看出分割結果較細碎，部分建筑物邊緣扭曲，不能很好體現建筑屋頂的形狀，這是由于該方法主要基于局部像元灰度差異進行分割，而多尺度歸一化割作為全局的分割方法，結果中建筑輪廓都較完整。此外，兩者在單一對象長度較大的道路與植被的分割都存在破碎的現象，在多尺度歸一化割中，這是由于關聯半徑不夠大造成的。

為了定量評價分割精度，本文采用Weidner等提出的評價方法來衡量分割精度[14]：

(12)

其中，x，y分別表示訓練對象區域和分割結果區域，x通過對實驗遙感數據進行人工分割得到。過分割和欠分割定義如下[15]：

(13)

(14)

3個參數的值域都是[0，1]，越接近0表示分割結果越好。用該方法對上文中eCognition與多尺度歸一化割實驗進行分割精度評價，結果如表2所示。

圖4 eCognition基于對象多尺度分割與多尺度歸一化割對比

parameterOverSegmentationUnderSegmentationqrMulti-scaleNormalized-cutK=3500.15060.06710.1992K=3000.09340.11940.1936K=2500.07580.12570.2007eCognitionscale:350.15020.10320.2423scale:370.13460.12940.2306scale:390.11670.19860.2754

在兩種方法參數的設定上，使實驗結果最優，這從上表結果的過分割率和欠分割率中可以看出，得到的過分割率和欠分割率都在近似相等的區間。可以看到，在參數設定合適的情況下，多尺度歸一化割方法能夠得到較高的分割精度，qr值保持在0.2左右，欠分割率和過分割率都在0.1左右。和eCognition對比可以看出，參數設定合理的情況下，多尺度歸一化割的總體分割精度略高于eCognition中的多尺度分割模塊。

4 結束語

針對高空間分辨率遙感圖像數據量大、地物信息豐富、紋理結構復雜、含多尺度信息的特點，本文利用多尺度歸一化割的方法進行高空間分辨率遙感圖像的分割，分析了該方法在遙感圖像分割中的適用性，并定量評價了分割結果。

通過與eCognition的結果對比和定量評價，可以看出多尺度歸一化割方法在遙感圖像分割中取得了不錯的效果，具有很大的應用前景。但是該方法也存在一些不足：算法的效率較慢，盡管該方法在歸一化割的基礎上，時間效率有顯著提高，但是在分割大尺寸遙感圖像仍然較慢；需要預先設定分割塊數，要通過幾次實驗來確定合適的分割塊數使分割結果最優。后續將著力研究解決上述問題。

[1] 肖鵬峰，馮學智.高分辨率遙感圖像分割與信息提取[M].北京：科學出版社，2012.

[2] ZAHN C T.Graph theoretical methods for detecting and describing Gestalt clusters[J].IEEE Trans.On Computation，1971，20(1)：68-86.

[3] WU Z，LEAHY R.An optimal graph theoretic approach to data clustering：Theory and its application to image segmentation[J].IEEE Trans on PAM I，1993，15(11)：1101-1113.

[4] SHI J，MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(11)：1768-1783.

[5] FOWLKES C，BELONGIE S，MALIK J.Efficient spatiotemporal grouping using the Nystrom method[J].Computer Vision and Pattern Recognition，2001，1：231-238.

[6] FOWLKES C，BELONGIE S，FAN C，et al.Spectral grouping using the nystrom method[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2004，26(2)：214-225.

[7] YU S X，SHI J.Multiclass spectral clustering[J].Computer Vision，Ninth IEEE International Conference on，2003，1：313-319.

[8] TOLLIVER D，COLLINS R T，BAKER S.Multilevel spectral partitioning for efficient image segmentation and tracking[J].Application of Computer Vision，2005，1：414-420.

[9] COUR T，BENEZIT F，SHI J.Spectral segmentation with multiscale graph decomposition[J].IEEE International Conference on Computer Vision and Pattern Recognition (CVPR)，2005，2：1124-1131.

[10] CAI W，WU J，CHUNG A C S.Shape-based image segmentation using normalized cuts，image processing[J].IEEE International Conference on，2006：1101-1104.

[11] SUN F，HE J.The remote-sensing image segmentation using textons in the normalized cuts framework[J].Mechatronics and Automation International Conference on，2009，1877-1881.

[12] ZHANG J，SONG Y，ZHANG Y，et al.A new approach of color image quantization based on Normalized Cut algorithm[J].Pattern Recognition (ACPR)，First Asian Conference on，2011，451-455.

[13] MEI Y C，WEI L K，WEI Y K，et al.Graph-based image segmentation using k-means clustering and normalized cuts，computational intelligence[J].Communication Systems and Networks (CICS&N)，Fourth International Conference on，2012，307-312.

[14] WEIDER U.Contribution to the assessment of segmentation quality for remote sensing applications[J].Proceedings of the 21stCongress for the International Society for Photogrammetry and Remote Sensing，2008.

[15] CLINTON N，HOLT A，SCARBOROUGH J，et al.Accuracy assessment measures for object-based image segmentation goodness[J].Photogrammetric Engineer & Remote Sensing，2010，76(3)：289-299.

Remote Sensing Image Segmentation Based on Multi-scale Normalized Cut

HUANG Huang1，2，XIAO Peng-feng1，2，WANG Jie-chen1，2

(1.JiangSuProvinceKeyLaboratoryofGeographicInformationScienceandTechnology，
NanjingUniversity，Nanjing210023；
2.GeographicInformationScienceDepartment，NanjingUniversity，Nanjing210023)

Due to high-resolution remote sensing images have characteristics of large size，rich feature types，and complex texture，we use multi-scale normalized cut method for high resolution remote sensing image segmentation.The method is a global segmentation method based on graph theory.The method is able to take into account information of coarse and fine layers，thus it is suitable for complex feature segmentation.We use Ikonos image of a region of Nanjing to conduct experiments，and to compare it with multi-scale segmentation module in mainstream segmentation software eCognition.The evaluation results show that the method can achieve sound results for high-resolution remote sensing image segmentation，which has good research prospects.

image segmentation；remote sensing image；multi-scale；normalized cut；accuracy assessment

2014-08-22

2014-10-06

全球變化研究國家重大科學研究計劃課題(2011CB952001)；江蘇高校優勢學科建設工程項目(PAPD)。

黃煌(1992—)，男，本科，研究方向為遙感圖像處理。

E-mail：huangyymail@163.com

10.3969/j.issn.1000-3177.2015.05.003

TP751

A

1000-3177(2015)141-0020-06