一種改進(jìn)的基于最小生成樹的遙感影像多尺度分割方法

李 慧，唐韻瑋，劉慶杰，丁海峰，荊林海

中國(guó)科學(xué)院遙感與數(shù)字地球研究所數(shù)字地球重點(diǎn)實(shí)驗(yàn)室，北京 100094

1 引 言

自面向?qū)ο筮b感影像分析軟件eCognition［1］問(wèn)世以來(lái)，面向?qū)ο蟮挠跋穹治龇椒ㄖ饾u成為遙感影像分析領(lǐng)域的研究熱點(diǎn)之一。圖像分割是面向?qū)ο筮b感信息提取的前提，精確的圖像分割是后續(xù)的面向?qū)ο笥跋穹治龅幕A(chǔ)。文獻(xiàn)［2—3］對(duì)典型軟件和算法進(jìn)行了定量評(píng)價(jià)，結(jié)果表明eCognition軟件的分形網(wǎng)絡(luò)演化算法（fractal network evolution approach，F(xiàn)NEA）優(yōu)于其他方法。然而，eCognition軟件相對(duì)昂貴的價(jià)格限制了該方法的廣泛應(yīng)用。為探索高效的遙感影像分割算法，文獻(xiàn)［4］提出了基于分水嶺和最小異質(zhì)性合并準(zhǔn)則的多尺度分割算法，分割精度達(dá)到FNEA方法的分割精度。但在該算法中，同樣的尺度參數(shù)得到的分割基元數(shù)量跟FNEA方法相比差異很大。文獻(xiàn)［5］提出了一種綜合利用影像的結(jié)構(gòu)和光譜特征、采用區(qū)域生長(zhǎng)和合并的分割方法，與FNEA方法的比較驗(yàn)證了該方法的有效性，但該方法在合并過(guò)程中僅考慮了光譜相似性。文獻(xiàn)［6］提出了一種綜合利用光譜、紋理與形狀信息的分割方法。與FNEA方法相比，該方法對(duì)紋理信息較為豐富的區(qū)域能有效改善分割質(zhì)量。基于圖論的圖像分割算法［7］是圖像分割領(lǐng)域的研究熱點(diǎn)［8－14］。文獻(xiàn)［15］提出了基于最小生成樹的多尺度多層次分割方法，并成功用于高分辨率遙感影像的分割，但該方法在區(qū)域合并過(guò)程中未利用區(qū)域形狀特性。

本文基于eCognition軟件的多尺度分割思想，提出了基于最小生成樹分割和最小異質(zhì)性合并準(zhǔn)則（combining minimum spanning tree and minimum heterogeneity criteria，CMHC）的分割方法。通過(guò)與eCognition軟件中FNEA方法的對(duì)比試驗(yàn)表明，CMHC方法是一種有效的遙感影像多尺度分割方法。

2 方 法

為了高效地分割遙感影像，CMHC方法采用的技術(shù)流程見(jiàn)圖1：首先使用相干增強(qiáng)各向異性擴(kuò)散濾波進(jìn)行影像平滑處理，然后對(duì)平滑圖像進(jìn)行基于最小生成樹的影像分割，接著結(jié)合光譜特性和形狀特性參數(shù)采用最小異質(zhì)性準(zhǔn)則進(jìn)行區(qū)域合并，最后得到分割結(jié)果。

圖1 CMHC方法流程圖Fig.1 The procedure of the CMHC method

2.1 相干增強(qiáng)各向異性擴(kuò)散濾波

為削弱噪聲影響和提高效率，本文算法首先采用相干增強(qiáng)各向異性擴(kuò)散模型［16－17］對(duì)待分割影像進(jìn)行圖像平滑處理。對(duì)于圖像u，該模型的基本形式為

此外，濾波處理前先對(duì)試驗(yàn)數(shù)據(jù)的各個(gè)波段ui進(jìn)行拉伸處理

式中，ui和u′i分別為原始和拉伸后的波段i；wi為波段權(quán)重；σmax為各波段方差的最大值；N為波段數(shù)量。

2.2 基于最小生成樹的分割算法

本文采用基于Krusal算法實(shí)現(xiàn)的最小生成樹算法［11］。該算法在步長(zhǎng)為r的鄰域內(nèi)建立最近鄰圖G，其合并準(zhǔn)則為區(qū)域間的差異必須小于兩區(qū)域內(nèi)部的最小差異。該算法設(shè)置了一個(gè)觀察尺度參數(shù)k，以避免噪聲影響或形成過(guò)小區(qū)域和抑制較大連通區(qū)域的產(chǎn)生，并將像元數(shù)量小于指定閾值nT的基元與其鄰居基元合并。該算法涉及的主要參數(shù)有鄰域步長(zhǎng)r、觀察尺度參數(shù)k和最小像元數(shù)量nT。

2.3 基于最小異質(zhì)性的區(qū)域合并

CMHC方法在區(qū)域合并中采用FNEA算法所使用的最小異質(zhì)性合并準(zhǔn)則［1］?；漠愘|(zhì)性值f由式（3）計(jì)算

式中，Wcolor和Wshape分別是光譜和形狀信息權(quán)重，取值位于區(qū)間［0，1］，Wcolor＋Wshape＝1；hcolor和hshape分別為光譜異質(zhì)性和形狀異質(zhì)性指標(biāo)，其定義及公式見(jiàn)文獻(xiàn)［1］。當(dāng)異質(zhì)性值f小于閾值T時(shí)，則合并基元。閾值T與尺度參數(shù)s相關(guān)。經(jīng)分析，閾值T還與影像最大灰度值umax、波段數(shù)量N和最大方差值σmax相關(guān)，本文采用公式為

2.4 評(píng)價(jià)準(zhǔn)則

圖像分割算法評(píng)價(jià)分為監(jiān)督方法和非監(jiān)督方法［18］，本文采用基于評(píng)價(jià)準(zhǔn)則的非監(jiān)督評(píng)價(jià)方法，評(píng)價(jià)準(zhǔn)則采用基元內(nèi)部方差最小和基元之間空間相關(guān)性最小準(zhǔn)則［19］。全局內(nèi)部方差wVar定義為所有基元的加權(quán)方差［18］；基元間空間相關(guān)性準(zhǔn)則采用 Moran’s I指標(biāo)（MI）［18，20-21］。對(duì)不同參數(shù)或不同算法的分割結(jié)果計(jì)算其在各個(gè)波段的wVar和MI統(tǒng)計(jì)值，并分別對(duì)其進(jìn)行歸一化拉伸處理［18］，得到 wVarnorm和 MInorm。

對(duì)于每個(gè)影像波段的統(tǒng)計(jì)結(jié)果，按式（5）得到波段i的全局得分GSi（global score，GS），再對(duì)所有波段的GS求平均值，得到每個(gè)分割影像的全局得分GSavg

式中，N為波段數(shù)量。

wVar值越小，表明基元內(nèi)部同質(zhì)性越高；MI值越小，表明基元間的空間相關(guān)性越小。因此GSavg值越小，表明分割結(jié)果既不過(guò)分割也不欠分割，分割效果越好。隨著尺度參數(shù)增大，分割基元數(shù)量減少，各波段wVar值增大，各波段MI值減少。因此，對(duì)于同一分割方法在不同尺度參數(shù)下的分割結(jié)果，GSavg最小值對(duì)應(yīng)的尺度，即為最優(yōu)分割尺度。對(duì)于不同算法的分割結(jié)果，GSavg越小表明分割結(jié)果在過(guò)分割和欠分割間的平衡越好。

3 試驗(yàn)與分析

3.1 試驗(yàn)數(shù)據(jù)

本文分別選用了1幅ASTER和1幅IKONOS影像子區(qū)進(jìn)行試驗(yàn)（圖2）。ASTER影像獲取時(shí)間為2000年夏天，包含綠、紅及近紅外3個(gè)波段，空間分辨率為15m。該子區(qū)位于加拿大安大略省中部的森林 地 區(qū) （46°33′51.33″N—46°34′30.22″N，83°23′50.32″W—83°26′49.27″W），大小為131行×205列。IKONOS影像獲取時(shí)間為2000年5月，包含藍(lán)、綠、紅及近紅外4個(gè)波段，空間分辨率為4米。該子區(qū)位于北京城區(qū)（39°57′21.58″N—39°58′27.68″N，116°23′21.74″E—116°24′49.02″E），大小為512行×512列。兩個(gè)子區(qū)包含水體、樹木、草地、道路、建筑物等多種地物類型，由于空間分辨率差異，前者地物邊界不清晰，后者比較清晰。

圖2 試驗(yàn)影像Fig.2 The experimental images

本文算法的參數(shù)設(shè)置情況如下：①在相干增強(qiáng)擴(kuò)散濾波中，高斯參數(shù)σ和ρ分別設(shè)為0.8和1，α和β分別設(shè)為0.001和1.0e－10；②在最小生成樹分割中，為避免過(guò)分割，鄰域步長(zhǎng)r、觀察尺度k和像元數(shù)量閾值nT分別設(shè)為1、1和2；③在區(qū)域合并中，參考eCognition軟件的默認(rèn)參數(shù)，波段權(quán)重wi、Wshape和Wcmpct分別設(shè)為1、0.1和0.5。

作為對(duì)比，兩個(gè)圖像子區(qū)也用eCognition Developer 8.7［22］進(jìn)行了分割。其中，波段權(quán)重wi、參數(shù)Wshape和Wcmpct的取值均同本文算法。

3.2 CMHC方法和FNEA方法比較

由于尺度參數(shù)和分割基元數(shù)量均對(duì)wVar和MI有較大影響，為客觀評(píng)價(jià)CMHC方法和FNEA方法，應(yīng)選擇最優(yōu)分割尺度或接近最優(yōu)分割尺度，且基元數(shù)量接近的分割結(jié)果進(jìn)行比較。因此，本文首先利用GSavg值確定兩種方法分別對(duì)兩個(gè)影像子區(qū)的最優(yōu)分割尺度參數(shù)，進(jìn)而結(jié)合基元數(shù)量Nobj選擇比較對(duì)象。

對(duì)于ASTER和IKONOS子區(qū)，分別采用［5，20］區(qū)間（步長(zhǎng)為1）和［10，40］區(qū)間（步長(zhǎng)為2）的尺度參數(shù)進(jìn)行分割試驗(yàn)，GSavg和基元數(shù)量Nobj分布見(jiàn)圖3。對(duì)于ASTER子區(qū)，F(xiàn)NEA和CMHC方法分別在尺度為9（AST－FNEA－9）和8（AST－CMHC－8）時(shí) GSavg值最小，對(duì)應(yīng)的基元數(shù)量接近（分別為202和235），因此選擇這兩個(gè)分割結(jié)果進(jìn)行比較。由于兩個(gè)分割結(jié)果對(duì)應(yīng)的分割基元數(shù)量差異超過(guò)10%，為公平起見(jiàn)，將FNEA方法在尺度為8的分割結(jié)果（AST－FNEA－8）也加入比較；對(duì)于IKONOS子區(qū)，F(xiàn)NEA和CMHC方法分別在尺度為22（IK－FNEA－22）和24（IK－CMHC－24）時(shí)GSavg值最小，對(duì)應(yīng)的基元數(shù)量差異較小（分別為3610和3628），因此選擇這兩個(gè)分割結(jié)果進(jìn)行比較。這5個(gè)分割結(jié)果的統(tǒng)計(jì)見(jiàn)表1。

圖3 試驗(yàn)圖像在不同尺度S分割結(jié)果的GSavg和基元數(shù)量Nobj分布圖Fig.3 GSavgand Nobjvalues of resulting maps with different scale parameter values for test images

表1 試驗(yàn)圖像在最優(yōu)分割尺度的分割結(jié)果的統(tǒng)計(jì)值Tab.1 Statistical values of segment results using the optimal scale parameters

對(duì)于 ASTER子區(qū)，AST－CMHC－8的B1和B2的 wVar和 MI值均低于 AST－FNEA－9和AST－FNEA－8的相應(yīng)統(tǒng)計(jì)值，B3的 wVar和 MI值 則 略 高 于 或 等 于 AST－FNEA－9 和 ASTFNEA－8的相應(yīng)統(tǒng)計(jì)值。因此，定量評(píng)價(jià)表明，對(duì)于ASTER影像，CMHC方法的過(guò)分割和欠分割的平衡方面優(yōu)于FNEA方法。圖4顯示了兩種方法對(duì)ASTER子區(qū)分割結(jié)果的局部圖。由圖中灰色框區(qū)域可見(jiàn)，CMHC方法對(duì)光譜特性細(xì)微差異更為敏感，而FNEA方法的分割結(jié)果則在形狀上更規(guī)則。因此，目視比較表明，對(duì)于ASTER影像，與FNEA方法相比，CMHC方法對(duì)光譜細(xì)微差異區(qū)域分割更細(xì)致。

對(duì)于IKONOS子區(qū)，IK－CMHC－24的B1、B2和B3的wVar和 MI值低于IK－FNEA－22的相應(yīng)統(tǒng)計(jì)值，B4的wVar值及4個(gè)波段的MI值均略低于IK－FNEA－22的相應(yīng)統(tǒng)計(jì)值。因此，定量評(píng)價(jià)表明，對(duì)于IKONOS影像，CMHC方法在基元內(nèi)部同質(zhì)性指標(biāo)上優(yōu)于FNEA方法，在全局空間相關(guān)性指標(biāo)上略遜于后者。圖5顯示了兩種方法對(duì)IKONOS子區(qū)分割結(jié)果的局部圖。目視比較可見(jiàn)，CMHC對(duì)光譜細(xì)微差異區(qū)域分割更細(xì)致（灰色框），對(duì)光譜特性差異更為敏感，而FNEA方法的分割結(jié)果則在形狀上更規(guī)則。

圖4 ASTER影像分割結(jié)果Fig.4 Results of ASTER imagery segmentation.

圖5 IKONOS影像分割結(jié)果局部圖Fig.5 Subsets of IKONOS imagery segmentation results

此外，對(duì)于兩個(gè)試驗(yàn)圖像，CMHC與FNEA方法的最優(yōu)分割尺度很接近。

綜上所述，從目視比較和定量指標(biāo)評(píng)價(jià)均表明，與FNEA方法相比較，CMHC能更好地分割光譜細(xì)微差異區(qū)域，而FNEA分割結(jié)果更為規(guī)則。

4 結(jié) 論

為探索基于圖論最優(yōu)化理論的遙感影像多尺度分割方法，本文提出了基于最小生成樹和最小異質(zhì)性合并準(zhǔn)則的多尺度分割方法（CMHC），并選用兩幅不同空間分辨率影像的子區(qū)，對(duì)CMHC和eCognition軟件的FNEA方法進(jìn)行了定量指標(biāo)評(píng)價(jià)和目視比較。其中，定量評(píng)價(jià)采用全局基元同質(zhì)性指標(biāo)與全局基元空間相關(guān)性指標(biāo)。試驗(yàn)過(guò)程中，首先根據(jù)這兩個(gè)指標(biāo)確定最優(yōu)分割尺度；然后選擇最優(yōu)分割尺度或接近最優(yōu)分割尺度，并且基元數(shù)量接近的分割結(jié)果進(jìn)行目視比較和定量評(píng)價(jià)。試驗(yàn)表明，CMHC方法在光譜細(xì)微差異區(qū)域細(xì)分方面優(yōu)于FNEA方法，在基元形狀規(guī)整性方面則略遜于FNEA方法，且該方法的最優(yōu)分割尺度與FNEA方法很接近。由于CMHC方法在Matlab開發(fā)環(huán)境中實(shí)現(xiàn)，在執(zhí)行效率方面有待提升，下一步將在C／C＋＋開發(fā)環(huán)境下進(jìn)行算法優(yōu)化和效率提升。

［1］ BAATZ M，SCH?PE A.Multiresolution Segmentation：An Optimization Approach for High Quality Multi－scale Image Segmentation［J］.Journal of Photogrammetry and Remote Sensing，2000，58（3－4）：12－23.

［2］ NEUBERT M，HEROLD H，MEINEL G.Assessing Image Segmentation Quality——Concepts，Methods and Application［M］∥BLASCHKE T，LANG S，HAY G J.Objectbased Image Analysis.Berlin：Springer，2008：769－784.

［3］ MARPU P R，NEUBERT M，HEROLD H，et al.Enhanced Evaluation of Image Segmentation Results［J］.Journal of Spatial Science，2010，55（1）：55－68.

［4］ WANG M.A Multiresolution Remotely Sensed Image Segmentation Method Combining Rainfalling Watershed Algorithm and Fast Region Merging［C］∥Proceedings of the International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.Beijing：［s.n.］，2008：1213－1218.

［5］ LIU Jing，LI Peijun.A High Resolution Image Segmentation Method by Combined Structural and Spectral Characteristics［J］.Acta Geodaetica et Cartographica Sinica，2014，43（5）：466－473.（劉婧，李培軍.結(jié)合結(jié)構(gòu)和光譜特征的高分辨率影像分割方法［J］.測(cè)繪學(xué)報(bào)，2014，43（5）：466－473.）

［6］ WU Zhaocong，HU Zhongwen，ZHANG Qian，et al.On Combining Spectral，Textural and Shape Features for Remote Sensing Image Segmentation［J］.Acta Geodaetica et Cartographica Sinica，2014，42（1）：44－50.（巫兆聰，胡忠文，張謙，等.結(jié)合光譜紋理與形狀結(jié)構(gòu)信息的遙感影像分割方法［J］.測(cè)繪學(xué)報(bào)，2014，42（1）：44－50.）

［7］ MORTENSEN E N，BARRETT W A.Intelligent Scissors for Image Composition［C］∥Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques.New York：［s.n.］，1995：191－198.

［8］ ZAHN C T.Graph－theoretical Methods for Detecting and Describing Gestalt Clusters［J］.IEEE Transactions on Computers，1971，C－20（1）：68－86.

［9］ XU Y，UBERBAEHER E C.2DImage Segmentation Using Minimum Spanning Trees［J］.Image and Vision Computing，1997，15（1）：47－57.

［10］ LERSCH J R，IVERSON A E，WEBB B N，et al.Segmentation of Multiband Imagery Using Minimum Spanning Trees［C］∥Aerospace／Defense Sensing and Controls，International Society for Optics and Photonics.Orlando，F(xiàn)L：SPIE，1996：10－18.

［11］ FELZENSZWALB P F，HUTTENLOEHER D P.Efficient Graph－based Image Segmentation［J］.International Journal of Computer Vision，2004，59（2）：167－181.

［12］ WU Z，LEAHY R.An Optimal Graph Theoretic Approach to Data Clustering：Theory and Its Application to Image Segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15（11）：1101－1113.

［13］ BOYKOV Y Y，JOLLY M P.Interactive Graph Cuts for Optimal Boundary ＆Region Segmentation of Objects in ND Images［C］∥Proceedings of the 8th IEEE International Conference on Computer Vision.Vancouver，B C：IEEE，2001：105－112.

［14］ PENG B，ZHANG L，ZHANG D.A Survey of Graph Theoretical Approaches to Image Segmentation［J］.Pattern Recognition，2013，46（3）：1020－1038.

［15］ CUI W H，ZHANG Y.An Effective Graph－based Hierarchy Image Segmentation ［J］.Intelligent Automation ＆ Soft Computing，2011，17（7）：969－981.

［16］ WEICKERT J.Anisotropic Diffusion in Image Processing［M］.Stuttgart：Teubner，1998.

［17］ WEICKERT J，SCHARR H.A Scheme for Coherenceenhancing Diffusion Filtering with Optimized Rotation Invariance［J］.Journal of Visual Communication and Image Representation，2002，13（1－2）：103－118.

［18］ ZHANG H，F(xiàn)RITTS E J，GOLDMAN S A.Image Segmentation Evaluation：A Survey of Unsupervised Methods［J］.Computer Vision and Image Understanding，2008，110（2）：260－280.

［19］ HARALICK R M，SHAPIRO L G.Image Segmentation Techniques［J］.Computer Vision，Graphics，and Image Processing，1985，29（1）：100－132.

［20］ ESPINDOLA G M，CAMARA G，REIS I A，et al.Parameter Selection for Region－growing Image Segmentation Algorithms Using Spatial Autocorrelation［J］.International Journal of Remote Sensing，2006，27（14）：3035－3040.

［21］ KIM M，MADDEN M，WARNER T.Estimation of Optimal Image Object Size for the Segmentation of Forest Stands with Multispectral IKONOS Imagery［M］∥BLASCHKE T，LANG S，HAY G J.Object－based Image Analysis.Berlin：Springer，2008：291－307.

［22］ TRIMBLE GERMANY GMBH.eCognition Developer 8.7，2009［EB／OL］.［2011－09－26］.http：∥www.ecognition.com.