左志權(quán)，張祖勛，張劍清

1.中國(guó)測(cè)繪科學(xué)研究院，北京100830；2.武漢大學(xué)遙感信息工程學(xué)院，湖北武漢430079

一種基于多分辨率拓?fù)渚W(wǎng)絡(luò)的高質(zhì)量初始圖斑對(duì)象生成方法

左志權(quán)1，張祖勛2，張劍清2

1.中國(guó)測(cè)繪科學(xué)研究院，北京100830；2.武漢大學(xué)遙感信息工程學(xué)院，湖北武漢430079

設(shè)計(jì)出一種基于多分辨率拓?fù)渚W(wǎng)絡(luò)的拓?fù)鋯l(fā)式影像分割算法，并對(duì)其涉及關(guān)鍵性技術(shù)進(jìn)行探討。通過細(xì)致分割試驗(yàn)，驗(yàn)證采用該分割算法生成高質(zhì)量圖斑對(duì)象的可行性。

影像分割；特征選擇；異質(zhì)度；啟發(fā)式搜索；多分辨率拓?fù)渚W(wǎng)絡(luò)

1 引 言

初始圖斑對(duì)象是面向?qū)ο笥跋裥畔⑻崛』A(chǔ)，經(jīng)過影像信息相關(guān)學(xué)科學(xué)者多年不懈努力，高分辨率影像分割的新理論、新算法不斷涌現(xiàn)：①以光譜亮度值在空間上的相似性與不連續(xù)性為理論基礎(chǔ)的分割算法，如區(qū)域生長(zhǎng)、閾值分割以及形態(tài)學(xué)分水嶺變換等［1］，都有較高的分割效率，但由于噪聲、紋理重復(fù)等因素影響，容易產(chǎn)生過分割現(xiàn)象，盡管一些學(xué)者［2－3］通過引入濾波算子避免過分割現(xiàn)象，但濾波器尺度因子難以控制，過度濾波可能造成邊界模糊導(dǎo)致影像分割精度降低；② 以紋理特征提取為分析基礎(chǔ)的分割算法，如灰度共生矩陣法［4］、Gabor小波法［5］以及馬爾可夫隨機(jī)場(chǎng)模型法［6］等，其分割效果過分依賴所選擇紋理特征類型，在處理高分辨率遙感影像時(shí)效率較低；③ 顧及邊界檢測(cè)的分割算法，如多尺度分割［7］、相位一致分割［8－9］等，在分割過程中可較好地顧及邊緣信息，但如何在分割過程中對(duì)離散線段進(jìn)行取舍并構(gòu)建拓?fù)潢P(guān)系較為困難。

本文在多分辨率影像分割算法［10］基礎(chǔ)上設(shè)計(jì)出一種拓?fù)鋯l(fā)式分割算法。該算法不僅具有較強(qiáng)的抗過分割能力，而且能通過多分辨率拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)管理矢量對(duì)象之間的復(fù)雜拓?fù)潢P(guān)系與繼承關(guān)系，具有良好穩(wěn)定性與實(shí)用性。

2 算法思想及流程

拓?fù)鋯l(fā)式影像分割是一個(gè)自下而上、逐步合并的過程：分割由單個(gè)像元開始，通過啟發(fā)式搜索方式尋找局部最優(yōu)分割區(qū)域?qū)?，合并區(qū)域并維護(hù)多分辨率拓?fù)渚W(wǎng)絡(luò)的動(dòng)態(tài)更新，迭代執(zhí)行上述合并過程直到分割結(jié)束。算法采用層次索引樹結(jié)構(gòu)描述多分辨率拓?fù)渚W(wǎng)絡(luò)，其實(shí)現(xiàn)流程如圖1所示。

3 算法關(guān)鍵技術(shù)

3.1 異質(zhì)度判據(jù)

特征向量由統(tǒng)計(jì)特征與幾何特征兩部分組成，異質(zhì)度判據(jù)如圖2所示。

為了消除不同特征值量綱差別，實(shí)踐中多采用數(shù)據(jù)標(biāo)準(zhǔn)化方法［11］，進(jìn)行特征值歸一化處理。判據(jù)詳細(xì)數(shù)學(xué)表達(dá)式參見文獻(xiàn)［12］。

圖1 影像分割基本流程Fig.1 Process of segmentation algorithm

圖2 異質(zhì)度判據(jù)示意圖Fig.2 Schematic diagram of heterogeneity criteria

3.2 啟發(fā)式搜索策略

啟發(fā)式搜索目的是尋找一對(duì)最優(yōu)對(duì)象組合，是整個(gè)分割過程中的最基本操作單元。搜索過程中采用雙向最小異質(zhì)度條件，保證每一次搜索合并結(jié)果都是局部最優(yōu)。啟發(fā)式搜索的流程如圖3所示。

圖3 拓?fù)鋯l(fā)式搜索流程Fig.3 Process of topology heuristic searching strategy

圖3為最優(yōu)同質(zhì)對(duì)象搜索過程示意圖，其中圖3（e）處滿足雙向最小異質(zhì)度條件，結(jié)束本次搜索。黑色矩形表示當(dāng)前對(duì)象，實(shí)方向線表示下一步最優(yōu)搜索方向線，虛方向線表示搜索算法所經(jīng)過路徑。

3.3 多分辨率拓?fù)渚W(wǎng)絡(luò)

拓?fù)鋯l(fā)式分割算法中包含兩種基本關(guān)系：同一尺度下的對(duì)象鄰接拓?fù)潢P(guān)系、不同尺度下父子對(duì)象繼承關(guān)系。本文采用層次樹索引結(jié)構(gòu)管理不同尺度下對(duì)象間的空間關(guān)系，其關(guān)鍵技術(shù)包括3個(gè)方面：

（1）層次樹節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)。包含4部分內(nèi)容：對(duì)象ID、特征屬性數(shù)據(jù)、鄰接拓?fù)湫畔⒁约袄^承信息，如圖4所示。

圖4 層次索引樹節(jié)點(diǎn)結(jié)構(gòu)示意圖Fig.4 Structure of index tree node

（2）查詢鄰接拓?fù)潢P(guān)系。文獻(xiàn)［13］從弧節(jié)點(diǎn)匹配、弧連接、閉合邊界弧段連接等方面入手，提出了多種構(gòu)建地理實(shí)體多邊形拓?fù)潢P(guān)系方法，而文獻(xiàn)［14］則提出一種基于圖的多邊形拓?fù)潢P(guān)系生成算法。上述算法可精確建立每一多邊形對(duì)象的拓?fù)潢P(guān)系，但在分割過程中，僅需要快速查詢多邊形的拓?fù)溧徑訉?duì)象。本文采用一種局部包圍盒求交方法獲取對(duì)象間鄰接拓?fù)潢P(guān)系，其基本思想是：可將父對(duì)象拆分成若干子對(duì)象進(jìn)行包圍盒求交運(yùn)算，可快速求解對(duì)象拓?fù)潢P(guān)系。包圍盒求交示意圖如圖5所示，紅色矩形框?yàn)閷?duì)象A的包圍盒；4個(gè)藍(lán)色矩形框分別為B、C、D、E包圍盒；綠色矩形框?yàn)榫植壳蠼粎^(qū)域。

圖5 局部包圍盒求交算法示意圖Fig.5 Algorithm of local bounding box intersection

（3）尺度步距與拓?fù)渚W(wǎng)絡(luò)。構(gòu)建層次樹索引是一個(gè)動(dòng)態(tài)過程：算法從單像元開始，隨著分割過程進(jìn)行以層次間尺度步距逐級(jí)創(chuàng)建父對(duì)象，直到分割結(jié)束，所有父對(duì)象之并集即為原始影像。一個(gè)完整的層次樹索引如圖6所示。

圖6 層次索引樹結(jié)構(gòu)示意圖Fig.6 Structure of hierarchy index tree

其中，灰色框?yàn)樵加跋瘢琹evel0為單像元；紅色節(jié)點(diǎn)為已合并子區(qū)域，藍(lán)色節(jié)點(diǎn)為未合并區(qū)域；level2、level1、level0表示不同分割尺度下的影像對(duì)象之全體。

4 試驗(yàn)與分析

本文所有涉及算法均在Windows環(huán)境下使用C語言實(shí)現(xiàn)。為驗(yàn)證算法可行性，選用兩幅數(shù)碼影像進(jìn)行多組分割試驗(yàn)，其中一幅為積木圖像，另一幅為房屋圖像，大小均為256×256像素。

4.1 不同尺度下的分割結(jié)果

尺度步距控制索引樹深度，在實(shí)踐中設(shè)置合適尺度步距（一般設(shè)為5），可在提高分割效率的同時(shí)避免過大樹深度。將兩幅影像以尺度步距5進(jìn)行20層分割，并將3個(gè)層級(jí)分割結(jié)果進(jìn)行抽樣顯示，如圖7所示。

圖7 不同尺度分割結(jié)果Fig.7 Segmentation results with different scales

從圖7可看出：① 隨著尺度增加圖斑對(duì)象數(shù)目明顯減少，分割精細(xì)程度降低；② 多分辨率拓?fù)渚W(wǎng)絡(luò)中，大尺度父對(duì)象均由小尺度若干子對(duì)象組合而成，這說明多拓?fù)渚W(wǎng)絡(luò)構(gòu)建是嚴(yán)密的。

如果以對(duì)象平均異質(zhì)度（所有區(qū)域平均標(biāo)準(zhǔn)差）描述分割精細(xì)程度，那么統(tǒng)計(jì)房屋圖像每一層對(duì)象的平均異質(zhì)度，并繪制尺度與平均異質(zhì)度曲線變化示意圖。隨著分割尺度增加，平均異質(zhì)度呈單調(diào)增變化趨勢(shì)，如圖8所示。

圖8 平均異質(zhì)度與尺度變化曲線Fig.8 Curve of medial heterogeneity with scale

4.2 特征權(quán)重對(duì)分割結(jié)果影響

由于幾何特征因子從整體上控制著圖斑對(duì)象幾何形態(tài)（主要指邊界的光滑程度與規(guī)則程度），同時(shí)也避免過分割現(xiàn)象發(fā)生。而光譜特征因子是影像主體特征，主要影響著圖斑對(duì)象的內(nèi)容。權(quán)重選擇規(guī)律如下：① 光譜特征為主體，統(tǒng)計(jì)特征0.7，幾何特征0.3；②在統(tǒng)計(jì)子特征中，均值0.4，標(biāo)準(zhǔn)差0.3，信息熵0.3；③在幾何特征中不對(duì)稱性為主體，不對(duì)稱性0.7，密度0.3。在同一分割尺度下，通過改變各類權(quán)重，分割結(jié)果如圖9所示。其中，圖（a）～（d）為非常規(guī)參數(shù)設(shè)置下的分割結(jié)果，圖（e）～（h）為常規(guī)參數(shù)設(shè)置下的分割結(jié)果。

從圖9可以看出：① 沒有或較少光譜特征參與的分割是無意義分割；圖9（a）與圖9（b）的光譜權(quán)重僅為0.1，其拓?fù)涠噙呅蔚倪吔缍嗖慌c物體邊界重合，而圖9（e）與圖9（f）在相同分割尺度下，分割質(zhì)量則相對(duì)較好；② 沒有或較少幾何特征參與的分割會(huì)導(dǎo)致產(chǎn)生過分割現(xiàn)象，以及影響對(duì)象邊界光滑程度等。圖9（c）與圖9（d）的光譜權(quán)重為0.9，盡管圖斑內(nèi)部一致性較好，但是對(duì)象形狀無規(guī)律、邊界不光滑，在一定程度上增加對(duì)象特征分析難度，而圖9（g）與圖9（h）在相同分割尺度下，對(duì)象形態(tài)一致，避免了過分割現(xiàn)象等。

5 結(jié) 論

本文較詳細(xì)地描述了一種面向?qū)ο笥跋穹指钏惴ǖ膶?shí)現(xiàn)方法，并通過兩組試驗(yàn)驗(yàn)證了算法的可行性，為后續(xù)面向?qū)ο蟮男畔⑻崛〈蛳铝嘶A(chǔ)。

圖9 不同特征權(quán)重分割結(jié)果Fig.9 Segmentation results with different features weight

［1］ GONZALEZ R C，WOODS R E.Digital Image Processing［M］.2nd ed.Beijing：Publishing House of Electronic Industry，2003.

［2］ MARR D，HDLDRETH E C.Theory of Edge Detection［C］∥Proceedings of the Royal Society of London：Series B.London：The Royal Society，1980，207：187－217.

［3］ CANNY J F.A Computational Approach to Edge Detection［J］.PAMI.1986，8（6）：679－698.

［4］ HARALICK R M.Statistical and Structural Approaches to Texture［J］.Proceedings of the IEEE.1979，67（5）：786－804.

［5］ DUNN D，HIGGINS W E.Optimal Gabor Filters for Texture Segmentation［J］.IEEE Transactions on Image Processing.1995，4（7）：947－964.

［6］ MODESTINO J W，ZHANG J.A Markov Random Field Model Based Approach to Image Interpretation［J］.PAMI， 1992，14（6）：606－615.

［7］ TABB M，AHUJA N.Multiscale Image Segmentation by Integrated Edge and Region Detection［J］.IEEE Transaction on Image Processing，1997，6（5）：642－655.

［8］ KOVESI P.Image Features from Phase Congruency［J］.Journal of Computer Vision Research，1999，1（3）：1－26.

［9］ XIAO Pengfeng，F(xiàn)ENG Xiuzhi，ZHAO Shuhe，et al.Segmentation of High－resolution Remotely Sensed Imagery Based on Phase Congruency［J］.Acta Geodaetica et Cartographica Sinica，2007，36（2）：146－151.（肖鵬峰，馮學(xué)智，趙書河，等.基于相位一致的高分辨率遙感圖像分割方法［J］.測(cè)繪學(xué)報(bào)，2007，36（2）：146－151.）

［10］ BAATZ M，SCHAPE 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.

［11］ TIMOTHY J R.Fuzzy Logic with Engineering Applications［M］.Beijing：Publishing House of Electronic Industry，2001.

［12］ ZUO Zhiquan.Seamlines Intelligent Detection in Largescale Urban Orthoimage Mosaicking［J］.Acta Geodaetica et Cartographica Sinica，2011，40（1）：84－89.（左志權(quán).DSM輔助下城區(qū)大比例尺正射影像鑲嵌線智能檢測(cè)［J］.測(cè)繪學(xué)報(bào)，2011，40（1）：84－89.）

［13］ QI Hua.The Optimization and Improvement for the Algorithm Steps on the Automatic Creation of Topological Relation of Polygons［J］.Acta Geodaetica et Cartographica Sinica，1997，26（3）：254－260.（齊華.自動(dòng)建立多邊形拓?fù)潢P(guān)系算法步驟的優(yōu)化與改進(jìn)［J］.測(cè)繪學(xué)報(bào)，1997，26（3）：254－260.）

［14］ ZHOU Lixin，YAN Jing，PAN Yunhe.A Graph－based Algorithm for Generating Polygons Topological Relationships［J］.Computer Applications，1999，19（10）：37－39.（周立新，嚴(yán)靜，潘云鶴.一個(gè)基于圖的多邊形拓?fù)潢P(guān)系生成算法［J］.計(jì)算機(jī)應(yīng)用，1999，19（10）：37－39.）

A High－quality Image Objects Generating Method Based on Multi－resolution Topology Network

ZUO Zhiquan1，ZHANG Zuxun2，ZHANG Jianqing2
1.Chinese Academy of Surveying and Mapping，Beijing100830，China；2.School of Remote Sensing and Information Engineering of Wuhan University，Wuhan 430079，China

A topology heuristic segmentation algorithm is proposed based on multi－resolution topology network and some key technologies are discussed in detail.The results of segmentation experiments show that it is feasible to generate high－quality image objects with this proposed algorithm.

image segmentation；feature selecting；heterogeneity；heuristic searching；multi－resolution topology network

ZUO Zhiquan（1983—），male，PhD，majors in photogrammetry and remote sensing.

ZUO Zhiquan，ZHANG Zuxun，ZHANG Jianqing.A High－quality Image Objects Generating Method Based on Multi－resolution Topology Network［J］.Acta Geodaetica et Cartographica Sinica，2012，41（1）：65－68.（左志權(quán)，張祖勛，張劍清.一種基于多分辨率拓?fù)渚W(wǎng)絡(luò)的高質(zhì)量初始圖斑對(duì)象生成方法［J］.測(cè)繪學(xué)報(bào)，2012，41（1）：65－68.）

P237

A

1001－1595（2012）01－0065－04

國(guó)家973計(jì)劃重點(diǎn)項(xiàng)目（2006CB701303）；國(guó)家863計(jì)劃（2008AA121506）

叢樹平）

2010－11－08

2011－07－06

左志權(quán)（1983—），男，博士，研究方向?yàn)閿z影測(cè)量與遙感。

E－mail：zqzuo＠casm.ac.cn