面状要素骨架线提取算法的设计与实现

连超 刘雪

(河南省金地遥感测绘技术有限公司，河南 郑州 450003)

1 引言

面状要素的骨架线是对面状地物主体形状的抽象描述，反映了面状地物的主延伸方向和主体形状特征，在GIS中有着非常重要的应用[1]。其提取方法通常有基于矢量方式和栅格方式两种，基于矢量方式的主要算法有平行线切割中点连线法和Delaunay三角网法[2-4]。平行线切割中点连线法是最简单、最直观求取骨架线的方法，但只能处理简单的多边形，对于复杂多边形（含岛多边形）处理起来比较困难[5]。Delaunay三角网法具有很好的几何特性、较大的灵活性和可操作性，但工作量较大，内存操作频繁，占用计算机资源较多，且被应用于平行轮廓时，得到的中轴线会存在很多“锯齿”[6]。基于栅格方式的方法大多使用数学形态学方法，内存需求少，适应性强，但提取效率低。为此，本文在研究上述算法基础上，提出了一种新的面状要素骨架线提取算法，以实现面状要素骨架线的快速提取。

2 基本定义

图1中黑线表示基本骨架线，依据文献[7]对其建立结点 -弧段拓扑关系。结合图1进行了以下定义：

度——与结点相关联弧段的个数称为结点的度。度为1的结点称为悬挂结点，与悬挂结点相关联的弧段称为悬挂弧段；度为3的结点称为岔口结点。

假岔口结点——对于岔口结点，若多边形在其附近呈十字路口或丁字路口状，则称其为真岔口结点；反之，则称其为假岔口结点。

节点——组成线段的点称为节点。对于任意一节点，与其相邻节点为该节点的邻节点，与其邻节点相邻节点为该节点的跨节点。

角点——三点组成的夹角中，夹角对应的点为角点（如图1中，∠ABC的角点为B）。

图1 假岔口结点、节点和角点

3 面状要素骨架线的提取

3.1 基本思想

首先，依据文献[8]提取多边形基本骨架线，结合文献[7]对基本骨架线建立结点 - 弧段拓扑关系。其次，标记Delaunay三角网中三角形。再次，根据已建立的拓扑关系和三角形标记，对基本骨架线上的结点和弧段集合进行悬挂结点、岔口结点、假岔口结点和悬挂弧段的判断和标记，并将它们分别存放至各自对应的集合中。然后，根据上述集合对基本骨架线末梢进行分类，根据多边形节点集合对多边形进行分类。最后，根据骨架线末梢类型、多边形类型和最小比例阈值对基本骨架线末梢进行优化。

3.2 Delaunay三角网中三角形的标记

根据基本骨架线和Delaunay三角网中三角形间的空间关系，对Delaunay三角网中三角形进行标记：基本骨架线穿过的三角形标记为true；反之，标记为false。

3.3 悬挂结点、岔口结点、假岔口结点和悬挂弧段的判断

对于悬挂结点、岔口结点和悬挂弧段，根据其定义进行判断，并把岔口结点存放至岔口结点集合中，用于假岔口结点的判断；假岔口结点的判断是在岔口结点的基础上，根据其定义进行的。

假设基本骨架线上岔口结点M关联的三条弧段为L1、L2、L3，L1、L2、L3上的非M结点在其对应弧段上的邻节点分别为A、B、C，A、B、C三点间两两组成线段的中点依次为P1、P2、P3，则判断M是否为假岔口结点的步骤为：（1）计算出点P1、P2、P3。（2）依据“点是否在多边形内部判断方法”判断出P1、P2、P3是否在多边形内部。（3）根据步骤2判断结果和假岔口结点定义，对M进行判断：若P1、P2、P3都在多边形内部，则多边形在M附近没有呈现十字路口或丁字路口状，M为假岔口结点；否则，多边形在M附近呈现十字路口或丁字路口状，M为真岔口结点。按照上述步骤对图2中岔口结点O进行判断可得：O为假岔口结点。

点是否在多边形内部的判断方法：首先，找出以点为重心、一定阈值为对角线长度的最小矩形。其次，在Delaunay三角网中找出与最小矩形属于包含关系的三角形，并将其存入三角形集合中。再次，根据上述结果对该点进行判断：若集合中没有三角形或存在标记为false的三角形，则该点在多边形外部；反之，该点在多边形内部。

图2 假岔口结点的判断

3.4 基本骨架线末梢和多边形的分类

基本骨架线末梢，是指基本骨架线的末端。根据基本骨架线和悬挂弧段的定义可知；在基本骨架线末梢在悬挂弧段上。因此，本文根据悬挂弧段集合和假岔口结点集合对基本骨架线末梢进行了分类：若悬挂弧段上非末梢处的悬挂结点是假岔口结点，且与该结点相关联的另两条弧段中至少有一条为悬挂弧段，则将该结点附近末梢称为T形末梢；反之，称为拐角末梢。

对于多边形，根据其节点个数N进行了分类：若N≠4，称其为一般多边形；否则，称其为四点多边形。对于四点多边形，根据其内角进行分类：若时，称其为似矩形四点多边形；否则，称为一般四点多边形。

3.5 基本骨架线末梢的优化

多边形分为四点多边形和一般多边形。下面分别对这两种多边形基本骨架线末梢的优化进行讨论。

通过分析四点多边形基本骨架线末梢类型可知，其都为拐角末梢。因此，四点多边形基本骨架线末梢的优化实际上是指四点多边形基本骨架线拐角末梢的优化。四点多边形基本骨架线末梢的优化步骤为：（1）对四点多边形进行分类：若其为一般四点多边形，则保持不变；否则，进入下一步。（2）找出步骤1中四点多边形每条边上的中点，并将属于相对关系两条边的中点归为一组。（3）计算出每组两点连线间的距离，并进行比较。（4）依据步骤3的比较结果和骨架线最长原则，保留长度值较大两点间的连线为优化后的骨架线。如图3（a）中BD表示已构建Delaunay三角网的似矩形四点多边形的基本骨架线，按照上述步骤对其优化，可得到优化后的骨架线，即图3（b）中的P2P4。

图3 似矩形四点多边形基本骨架线末梢的优化

分析一般多边形基本骨架线末梢类型可知，其既可属于拐角末梢，又可属于T形末梢。下面对一般多边形两种类型末梢的优化分别进行讨论。

（1）拐角末梢的优化。假设一般多边形基本骨架线拐角末梢处端点为O，则拐角末梢的优化过程为：首先，找出以O为顶点、标记为true的三角形。其次，在找到的三角形中找出以O为端点的两条边，并确定这两条边的中点M、N。再次，在基本骨架线上找出O的邻节点和跨节点。最后，依次计算出O、M、N和邻节点、跨节点组成的以邻节点为角点的夹角，找出最大角，并将O移至最大角所对应的点（邻节点、跨节点除外）。如图4（a）中AI为基本骨架线，其末梢都为拐角末梢，按照上述过程对其优化，可得到优化后的骨架线，即图4（b）中的P2P4。

图4 拐角末梢的优化

（2）T形末梢的优化。它是在已优化拐角末梢的基础上进行的。假设一般多边形基本骨架线T形末梢处对应的假岔口结点为O，则T形末梢的优化过程为：

①找出与O相关联的三条弧段，计算出它们的长度，并进行排序。②分别计算出最长弧段与另两条弧段的比值以及另两条弧段间的比值。若前两个比值都大于最小比例阈值，且最后一个比值接近1，则进入下一步；否则，T形末梢保持不变。③分别判断较短两条弧段是否为悬挂弧段。才若都为悬挂弧段，则进入下一步；否则，T形末梢保持不变。④在步骤1中找到的三条弧段上分别找出O的邻节点和跨节点。⑤找出O所在三角形，计算出三边的中点，并从中点中找出与O邻节点（在最长弧段上）坐标相同的点。⑥依据文献[9]判断步骤5中找到三角形的类型，若为Ⅰ类或Ⅲ类三角形，则删除较短的两条弧段，并将O移至与步骤5中找到点所在三角形的边属于相对关系的三角形的顶点即可；否则，进入下一步。⑦依次计算出O在两条较短弧段上的邻节点和O在最长弧段上的邻节点、跨节点组成的以最长弧段上O的邻节点为角点的夹角，找出较大角所对应的点（最长弧段上结点O的邻节点和跨节点除外），并判断不包含该点的弧段（最长弧段除外）是否为悬挂弧段，若为悬挂弧段，则删除，并将O移至该步骤中已找到的点处即可。如图5（a）中黑线表示拐角末梢优化后的骨架线，假岔口结点O、M附近的末梢都为T形末梢，按照上述过程对其优化，优化后的结果如图5（b）中的黑线。

3.6 骨架线提取的步骤

步骤一：提取多边形基本骨架线，并对其建立结点形 -弧段拓扑关系。

步骤二：标记Delaunay三角网中三角形。

步骤三：标识悬挂结点、岔口结点、假岔口结点和悬挂弧段，并将它们分别存入各自对应的集合中。

步骤四：对基本骨架线末梢和多边形进行分类。步骤五：对四点多边形的基本骨架线进行优化。步骤六：对一般多边形的基本骨架线进行优化。

图5 T形末梢的优化

4 试验分析

笔者运用这一算法，以某地区地面支渠数据为例，进行了面状要素骨架线提取。如图6（a）表示地面支渠原始数据，图6（b）表示运用本文算法提取的骨架线。分析结果可知，该算法不仅有效解决了提取平行轮廓或似平行轮廓中轴线时出现的“锯齿”，而且较好反映了面状地物的主延伸方向和主体的形状特征，准确性较高。

图6 地面支渠骨架线的提取

5 结束语

本文所用方法实现了面状要素骨架线的提取，利用Visual Studio 2010编写了程序，对某地区地面支渠进行了骨架线的提取。实验结果表明该方法是可行的，且准确性较高，适合大多数地面支渠数据，但还不太成熟，特别是在地面支渠数据比较复杂的情况下，优化后的骨架线并不理想。这些问题需要在以后的研究过程中进一步改善，使其更加实用化。