黃煌，肖鵬峰，王結(jié)臣

(1.江蘇省地理信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 210023；2.南京大學(xué) 地理信息科學(xué)系，南京 210023)

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

黃煌1，2，肖鵬峰1，2，王結(jié)臣1，2

(1.江蘇省地理信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 210023；2.南京大學(xué) 地理信息科學(xué)系，南京 210023)

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

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

0 引 言

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

歸一化割是一種基于圖論的圖像分割方法。圖論是離散數(shù)學(xué)的一個(gè)分支，它是以圖為研究單位，研究頂點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法。圖論在數(shù)據(jù)聚類和圖像分割中的應(yīng)用可以追溯到1971年Zahn的工作[2]，他提出的基于最小生成樹的圖像分割方法，使用固定閾值進(jìn)行圖像分割和點(diǎn)聚類?；趫D論的圖像分割方法具有廣泛的數(shù)學(xué)基礎(chǔ)，并具有能捕獲全局特征的優(yōu)點(diǎn)，從而在圖像分割領(lǐng)域廣泛應(yīng)用。Wu和Leahy在1993年將最小割原理應(yīng)用于圖像分割[3]，該方法容易劃分出孤立小區(qū)域。Shi和Malik克服了最小割準(zhǔn)則中容易劃分出孤立小區(qū)域的缺點(diǎn)，于1997提出的歸一化割方法[4]，并很快得到廣泛應(yīng)用。

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

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

1 歸一化割原理

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

(1)

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

(2)

2 多尺度歸一化割

2.1 權(quán)值定義

首先確定圖像上任意兩點(diǎn)之間的相關(guān)性計(jì)算方法，考慮亮度、距離、圖的邊緣等信息，將權(quán)值計(jì)算方法定義如下：

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

(3)

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

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

(4)

結(jié)合上述兩種權(quán)值定義得到如下的相似度計(jì)算方法：

(5)

2.2 關(guān)聯(lián)半徑

當(dāng)兩點(diǎn)之間的距離大于一定的關(guān)聯(lián)半徑r時(shí)，設(shè)定兩點(diǎn)之間的權(quán)值為0，這樣可以很大程度上提高計(jì)算效率。關(guān)聯(lián)半徑的設(shè)定對于分割結(jié)果和分割時(shí)間產(chǎn)生很大的影響。對于Ikonos的0.86m分辨率遙感圖像(大小為100像素×80像元)設(shè)定不同關(guān)聯(lián)半徑進(jìn)行歸一化割分割實(shí)驗(yàn)，結(jié)果如下：

圖1 不同關(guān)聯(lián)半徑的歸一化割分割結(jié)果

對不同關(guān)聯(lián)半徑圖像進(jìn)行分割所用時(shí)間如表1所示。

表1 不同關(guān)聯(lián)半徑對應(yīng)歸一化割時(shí)間

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

同時(shí)可以看出，不同關(guān)聯(lián)半徑的分割效果和效率具有很大影響，因此，將圖劃分為不同的尺度，對不同尺度采用不同的關(guān)聯(lián)半徑進(jìn)行分割，最后綜合不同尺度的分割結(jié)果，就可以很大程度上提高分割效率。

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

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

W=W1+W2+…+WS

(6)

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

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

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

(7)

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

(8)

采樣鄰域Pi表示圖層Is+1中點(diǎn)i在較精細(xì)尺度圖Is上的投影，其絕對值簡單定義為采樣鄰域中的結(jié)點(diǎn)數(shù)目。

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

(9)

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

(10)

使用約束多尺度歸一化分割標(biāo)準(zhǔn)：

(11)

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

3 實(shí)驗(yàn)和分析

3.1 Ikonos圖像分割實(shí)驗(yàn)

利用2010年南京市棲霞區(qū)某地0.86m Ikonos

多光譜遙感圖像進(jìn)行多尺度歸一化割實(shí)驗(yàn)，得到如下結(jié)果：

圖3 建筑及農(nóng)田區(qū)域遙感圖像及多尺度歸一化割結(jié)果

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

3.2 精度評價(jià)

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

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

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

(12)

其中，x，y分別表示訓(xùn)練對象區(qū)域和分割結(jié)果區(qū)域，x通過對實(shí)驗(yàn)遙感數(shù)據(jù)進(jìn)行人工分割得到。過分割和欠分割定義如下[15]：

(13)

(14)

3個(gè)參數(shù)的值域都是[0，1]，越接近0表示分割結(jié)果越好。用該方法對上文中eCognition與多尺度歸一化割實(shí)驗(yàn)進(jìn)行分割精度評價(jià)，結(jié)果如表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

在兩種方法參數(shù)的設(shè)定上，使實(shí)驗(yàn)結(jié)果最優(yōu)，這從上表結(jié)果的過分割率和欠分割率中可以看出，得到的過分割率和欠分割率都在近似相等的區(qū)間?？梢钥吹剑趨?shù)設(shè)定合適的情況下，多尺度歸一化割方法能夠得到較高的分割精度，qr值保持在0.2左右，欠分割率和過分割率都在0.1左右。和eCognition對比可以看出，參數(shù)設(shè)定合理的情況下，多尺度歸一化割的總體分割精度略高于eCognition中的多尺度分割模塊。

4 結(jié)束語

針對高空間分辨率遙感圖像數(shù)據(jù)量大、地物信息豐富、紋理結(jié)構(gòu)復(fù)雜、含多尺度信息的特點(diǎn)，本文利用多尺度歸一化割的方法進(jìn)行高空間分辨率遙感圖像的分割，分析了該方法在遙感圖像分割中的適用性，并定量評價(jià)了分割結(jié)果。

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

[1] 肖鵬峰，馮學(xué)智.高分辨率遙感圖像分割與信息提取[M].北京：科學(xué)出版社，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，F(xiàn)AN 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)，F(xiàn)irst 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)，F(xiàn)ourth 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

全球變化研究國家重大科學(xué)研究計(jì)劃課題(2011CB952001)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程項(xiàng)目(PAPD)。

黃煌(1992—)，男，本科，研究方向?yàn)檫b感圖像處理。

E-mail：huangyymail@163.com

10.3969/j.issn.1000-3177.2015.05.003

TP751

A

1000-3177(2015)141-0020-06