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

1.中國測繪科學研究院，北京100830；2.武漢大學遙感信息工程學院，湖北武漢430079

一種基于多分辨率拓撲網(wǎng)絡的高質(zhì)量初始圖斑對象生成方法

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

1.中國測繪科學研究院，北京100830；2.武漢大學遙感信息工程學院，湖北武漢430079

設計出一種基于多分辨率拓撲網(wǎng)絡的拓撲啟發(fā)式影像分割算法，并對其涉及關(guān)鍵性技術(shù)進行探討。通過細致分割試驗，驗證采用該分割算法生成高質(zhì)量圖斑對象的可行性。

影像分割；特征選擇；異質(zhì)度；啟發(fā)式搜索；多分辨率拓撲網(wǎng)絡

1 引 言

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

本文在多分辨率影像分割算法［10］基礎上設計出一種拓撲啟發(fā)式分割算法。該算法不僅具有較強的抗過分割能力，而且能通過多分辨率拓撲網(wǎng)絡結(jié)構(gòu)管理矢量對象之間的復雜拓撲關(guān)系與繼承關(guān)系，具有良好穩(wěn)定性與實用性。

2 算法思想及流程

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

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

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

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

為了消除不同特征值量綱差別，實踐中多采用數(shù)據(jù)標準化方法［11］，進行特征值歸一化處理。判據(jù)詳細數(shù)學表達式參見文獻［12］。

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

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

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

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

圖3 拓撲啟發(fā)式搜索流程Fig.3 Process of topology heuristic searching strategy

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

3.3 多分辨率拓撲網(wǎng)絡

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

（1）層次樹節(jié)點數(shù)據(jù)結(jié)構(gòu)。包含4部分內(nèi)容：對象ID、特征屬性數(shù)據(jù)、鄰接拓撲信息以及繼承信息，如圖4所示。

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

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

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

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

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

其中，灰色框為原始影像，level0為單像元；紅色節(jié)點為已合并子區(qū)域，藍色節(jié)點為未合并區(qū)域；level2、level1、level0表示不同分割尺度下的影像對象之全體。

4 試驗與分析

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

圖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.（肖鵬峰，馮學智，趙書河，等.基于相位一致的高分辨率遙感圖像分割方法［J］.測繪學報，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ū)大比例尺正射影像鑲嵌線智能檢測［J］.測繪學報，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.（齊華.自動建立多邊形拓撲關(guān)系算法步驟的優(yōu)化與改進［J］.測繪學報，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.（周立新，嚴靜，潘云鶴.一個基于圖的多邊形拓撲關(guān)系生成算法［J］.計算機應用，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)，張祖勛，張劍清.一種基于多分辨率拓撲網(wǎng)絡的高質(zhì)量初始圖斑對象生成方法［J］.測繪學報，2012，41（1）：65－68.）

P237

A

1001－1595（2012）01－0065－04

國家973計劃重點項目（2006CB701303）；國家863計劃（2008AA121506）

叢樹平）

2010－11－08

2011－07－06

左志權(quán)（1983—），男，博士，研究方向為攝影測量與遙感。

E－mail：zqzuo＠casm.ac.cn