一种基于多分辨率拓扑网络的高质量初始图斑对象生成方法

左志权，张祖勋，张剑清

1.中国测绘科学研究院，北京100830；2.武汉大学遥感信息工程学院，湖北武汉430079

一种基于多分辨率拓扑网络的高质量初始图斑对象生成方法

左志权1，张祖勋2，张剑清2

1.中国测绘科学研究院，北京100830；2.武汉大学遥感信息工程学院，湖北武汉430079

设计出一种基于多分辨率拓扑网络的拓扑启发式影像分割算法，并对其涉及关键性技术进行探讨。通过细致分割试验，验证采用该分割算法生成高质量图斑对象的可行性。

影像分割；特征选择；异质度；启发式搜索；多分辨率拓扑网络

1 引 言

初始图斑对象是面向对象影像信息提取基础，经过影像信息相关学科学者多年不懈努力，高分辨率影像分割的新理论、新算法不断涌现：①以光谱亮度值在空间上的相似性与不连续性为理论基础的分割算法，如区域生长、阈值分割以及形态学分水岭变换等［1］，都有较高的分割效率，但由于噪声、纹理重复等因素影响，容易产生过分割现象，尽管一些学者［2－3］通过引入滤波算子避免过分割现象，但滤波器尺度因子难以控制，过度滤波可能造成边界模糊导致影像分割精度降低；② 以纹理特征提取为分析基础的分割算法，如灰度共生矩阵法［4］、Gabor小波法［5］以及马尔可夫随机场模型法［6］等，其分割效果过分依赖所选择纹理特征类型，在处理高分辨率遥感影像时效率较低；③ 顾及边界检测的分割算法，如多尺度分割［7］、相位一致分割［8－9］等，在分割过程中可较好地顾及边缘信息，但如何在分割过程中对离散线段进行取舍并构建拓扑关系较为困难。

本文在多分辨率影像分割算法［10］基础上设计出一种拓扑启发式分割算法。该算法不仅具有较强的抗过分割能力，而且能通过多分辨率拓扑网络结构管理矢量对象之间的复杂拓扑关系与继承关系，具有良好稳定性与实用性。

2 算法思想及流程

拓扑启发式影像分割是一个自下而上、逐步合并的过程：分割由单个像元开始，通过启发式搜索方式寻找局部最优分割区域对，合并区域并维护多分辨率拓扑网络的动态更新，迭代执行上述合并过程直到分割结束。算法采用层次索引树结构描述多分辨率拓扑网络，其实现流程如图1所示。

3 算法关键技术

3.1 异质度判据

特征向量由统计特征与几何特征两部分组成，异质度判据如图2所示。

为了消除不同特征值量纲差别，实践中多采用数据标准化方法［11］，进行特征值归一化处理。判据详细数学表达式参见文献［12］。

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

图2 异质度判据示意图Fig.2 Schematic diagram of heterogeneity criteria

3.2 启发式搜索策略

启发式搜索目的是寻找一对最优对象组合，是整个分割过程中的最基本操作单元。搜索过程中采用双向最小异质度条件，保证每一次搜索合并结果都是局部最优。启发式搜索的流程如图3所示。

图3 拓扑启发式搜索流程Fig.3 Process of topology heuristic searching strategy

图3为最优同质对象搜索过程示意图，其中图3（e）处满足双向最小异质度条件，结束本次搜索。黑色矩形表示当前对象，实方向线表示下一步最优搜索方向线，虚方向线表示搜索算法所经过路径。

3.3 多分辨率拓扑网络

拓扑启发式分割算法中包含两种基本关系：同一尺度下的对象邻接拓扑关系、不同尺度下父子对象继承关系。本文采用层次树索引结构管理不同尺度下对象间的空间关系，其关键技术包括3个方面：

（1）层次树节点数据结构。包含4部分内容：对象ID、特征属性数据、邻接拓扑信息以及继承信息，如图4所示。

图4 层次索引树节点结构示意图Fig.4 Structure of index tree node

（2）查询邻接拓扑关系。文献［13］从弧节点匹配、弧连接、闭合边界弧段连接等方面入手，提出了多种构建地理实体多边形拓扑关系方法，而文献［14］则提出一种基于图的多边形拓扑关系生成算法。上述算法可精确建立每一多边形对象的拓扑关系，但在分割过程中，仅需要快速查询多边形的拓扑邻接对象。本文采用一种局部包围盒求交方法获取对象间邻接拓扑关系，其基本思想是：可将父对象拆分成若干子对象进行包围盒求交运算，可快速求解对象拓扑关系。包围盒求交示意图如图5所示，红色矩形框为对象A的包围盒；4个蓝色矩形框分别为B、C、D、E包围盒；绿色矩形框为局部求交区域。

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

（3）尺度步距与拓扑网络。构建层次树索引是一个动态过程：算法从单像元开始，随着分割过程进行以层次间尺度步距逐级创建父对象，直到分割结束，所有父对象之并集即为原始影像。一个完整的层次树索引如图6所示。

图6 层次索引树结构示意图Fig.6 Structure of hierarchy index tree

其中，灰色框为原始影像，level0为单像元；红色节点为已合并子区域，蓝色节点为未合并区域；level2、level1、level0表示不同分割尺度下的影像对象之全体。

4 试验与分析

本文所有涉及算法均在Windows环境下使用C语言实现。为验证算法可行性，选用两幅数码影像进行多组分割试验，其中一幅为积木图像，另一幅为房屋图像，大小均为256×256像素。

4.1 不同尺度下的分割结果

尺度步距控制索引树深度，在实践中设置合适尺度步距（一般设为5），可在提高分割效率的同时避免过大树深度。将两幅影像以尺度步距5进行20层分割，并将3个层级分割结果进行抽样显示，如图7所示。

图7 不同尺度分割结果Fig.7 Segmentation results with different scales

从图7可看出：① 随着尺度增加图斑对象数目明显减少，分割精细程度降低；② 多分辨率拓扑网络中，大尺度父对象均由小尺度若干子对象组合而成，这说明多拓扑网络构建是严密的。

如果以对象平均异质度（所有区域平均标准差）描述分割精细程度，那么统计房屋图像每一层对象的平均异质度，并绘制尺度与平均异质度曲线变化示意图。随着分割尺度增加，平均异质度呈单调增变化趋势，如图8所示。

图8 平均异质度与尺度变化曲线Fig.8 Curve of medial heterogeneity with scale

4.2 特征权重对分割结果影响

由于几何特征因子从整体上控制着图斑对象几何形态（主要指边界的光滑程度与规则程度），同时也避免过分割现象发生。而光谱特征因子是影像主体特征，主要影响着图斑对象的内容。权重选择规律如下：① 光谱特征为主体，统计特征0.7，几何特征0.3；②在统计子特征中，均值0.4，标准差0.3，信息熵0.3；③在几何特征中不对称性为主体，不对称性0.7，密度0.3。在同一分割尺度下，通过改变各类权重，分割结果如图9所示。其中，图（a）～（d）为非常规参数设置下的分割结果，图（e）～（h）为常规参数设置下的分割结果。

从图9可以看出：① 没有或较少光谱特征参与的分割是无意义分割；图9（a）与图9（b）的光谱权重仅为0.1，其拓扑多边形的边界多不与物体边界重合，而图9（e）与图9（f）在相同分割尺度下，分割质量则相对较好；② 没有或较少几何特征参与的分割会导致产生过分割现象，以及影响对象边界光滑程度等。图9（c）与图9（d）的光谱权重为0.9，尽管图斑内部一致性较好，但是对象形状无规律、边界不光滑，在一定程度上增加对象特征分析难度，而图9（g）与图9（h）在相同分割尺度下，对象形态一致，避免了过分割现象等。

5 结 论

本文较详细地描述了一种面向对象影像分割算法的实现方法，并通过两组试验验证了算法的可行性，为后续面向对象的信息提取打下了基础。

图9 不同特征权重分割结果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，FENG 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.（左志权.DSM辅助下城区大比例尺正射影像镶嵌线智能检测［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.（齐华.自动建立多边形拓扑关系算法步骤的优化与改进［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.（周立新，严静，潘云鹤.一个基于图的多边形拓扑关系生成算法［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.（左志权，张祖勋，张剑清.一种基于多分辨率拓扑网络的高质量初始图斑对象生成方法［J］.测绘学报，2012，41（1）：65－68.）

P237

A

1001－1595（2012）01－0065－04

国家973计划重点项目（2006CB701303）；国家863计划（2008AA121506）

丛树平）

2010－11－08

2011－07－06

左志权（1983—），男，博士，研究方向为摄影测量与遥感。

E－mail：zqzuo＠casm.ac.cn