面状要素骨架线提取算法的研究

郭邦梅,王 涛,赵 荣,梁 勇

(1.山东农业大学信息科学与工程学院,山东泰安 271018;2.中国测绘科学研究院,北京 100830)

面状要素骨架线提取算法的研究

郭邦梅1,2,王 涛2,赵 荣2,梁 勇1

(1.山东农业大学信息科学与工程学院,山东泰安 271018;2.中国测绘科学研究院,北京 100830)

基于栅格数据的经典细化算法获得的骨架线会丢失一些重要特征点或特征线,且无法按照需求保持该要素细化后与周边重要要素间的关联性。在经典细化算法的基础上提出改进算法,克服已有算法的一些不足,使获得的骨架线更能适应具体应用。试验结果表明此改进算法能够按照实际需求,更准确地保留原图形的重要特征,且很好地保持了该要素与周边重要要素间的关联性。

经典细化算法;骨架线;细化

一、引 言

所谓骨架(skeleton),是指用与原形状连通性和拓扑结构相一致的细曲线作为理想表达的一种对象表示[1]。骨架线是描述物体几何及拓扑性质的重要特征,在 GIS中有着广泛的应用。制图综合中,在研究河系结构时,各有关内部结构如局部宽度变化、分叉等可忽略时,可以用河道骨架线来代表河流[2];地物注记的自动配置中,如对于大面积面状要素,需先提取骨架线,将该骨架线作为注记的定位参考线[3];面状地理现象的分析等很多空间操作中都需要提取骨架线。

本文以提取面状要素骨架线及河流骨架线为例,分析不同的提取骨架线算法的优劣,如杜世宏[4]等提出的基于栅格数据提取骨架线的新算法,该算法是利用栅格算法研究最长骨架线的提取,具有较快的处理速度且主要用来提取面状要素的主骨架线。文献[5]中,王涛提出顾及多因素的面状目标多层次骨架线提取。类似对提取骨架线算法的研究较多,但都无法保证骨架线与其周边重要线的连通性。其中经典细化算法具有快速实用的特点,同时能保证细化后曲线的连通性且较简单快捷,故本文以经典细化算法为基础来提取骨架线。经典细化算法提取的骨架线基本保持了面状要素的连通性,但是有些主要特征点或线并没有保留下来。同时,在水系要素处理中,提取的面状河流骨架线同样也没有保留与周边重要支流间的连通性,这样就破坏了该河流与周边主要支流间的关联性。

针对以上提出的经典细化算法所存在的不足,本文提出了相应的改进算法。并对利用改进后的细化算法得到的骨架线,与改进前的经典算法及ArcGIS 9.2提供的细化工具提取的骨架线进行了对比分析。

二、现有细化算法及评析

1.提取骨架线算法

骨架线的提取方法通常有基于矢量数据和栅格数据两种方法。其中基于矢量数据的代表性算法有平行线切割中点连线法及 Delaunay三角网法。平行线切割中点连线法是最简单、最直观的求取骨架线的方法,但是它只能处理一些简单的多边形,对于复杂的多边形(如有岛多边形),处理起来比较困难。Delaunay三角网法具有很好的几何特性,能够方便地建立起各地理目标的空间邻近关系,探测目标的结构特征,有着较大的灵活性和可操作性。但由于自动综合中建立的 Delaunay数据结构要比一般Delaunay数据结构复杂,因此工作量和计算量都比较大,对内存操作频繁,占用更多的计算机资源[6]。

基于栅格数据的方法大多使用数学形态学方法,主要经过数学形态学的“序贯减薄”运算,选择紧致的凸结构元用逐次侵蚀与断开运算形成一种骨架线算法。目前可归纳为两大类：①基于距离变换,首先得到骨架像元,然后跟踪距离变换图中的“山脊线”(即在局部范围内灰度值最大的像元系列),并将其作为中轴线;②基于在不破坏栅格拓扑连通性的前提下,按对称的原则删除影像边缘的栅格点[7]。此类算法主要有：用距离变换法搜寻中轴线法、最大数值计算法、经典细化算法、边缘跟踪剥皮法。本文主要讨论后一类中的经典细化算法。

2.经典细化算法

经典细化算法的基本原理是：通过逐个考察某一像素 P的八个领域灰度值的分布格局,在不破坏原栅格影像拓扑连通性的情况下删除该点,反之保留。这样逐点扫描,消去所有不破坏连通性的点,直到点阵图中不再有可删除的点为止。

设已知目标点标记为 1,背景点标记为 0。算法对标记为 1的像元点进行了如下操作：考虑以某一像元点为中心的八个领域,记中心点为 P,其领域的八个点顺时针绕中心点分别记为 P1、P2、P3、P4、P5、P6、P7、P8,其中 P1在 P的上方 (如图 1所示)。将标记满足下列任意一个条件的中心像元点保留。

图1 像元P八领域示意图

1)P1+P3+P5+P7=4且 P2+P4+P6+P8= 0(或 4);

2)P3+P7=0且 P1+P2+P8＞0且 P4+P5+ P6＞0;

3)P1+P5=0且 P2+P3+P4＞0且 P6+P7+ P8＞0;

4)P1+P3=0且 P2=1且 P4+P5+P6+P7+ P8＞0;

5)P3+P5=0且 P4=1且 P1+P2+P6+P7+ P8＞0;

6)P5+P7=0且 P6=1且 P1+P2+P3+P4+ P8＞0;

7)P7+P1=0且 P8=1且 P2+P3+P4+P5+ P6＞0。

需要注意的是,以上条件实际上是给出的连通性条件,如果简单地将它们依次用于一幅图像,那么一个连通区域的像元灰度值都将变为 0。因此对于某一方向的细化来说,中心像元的取舍决定,不能立即表现为物理上去除或保留,而应先将中心像元 P置为 2(表示此点为中轴线上的像元)或 3(表示此为可删除的像元),以免破坏原始影像的结构。

依次迭代以上操作,直至没有点可被删除,这时剩下的点组成面的骨架线。

三、算法的改进

利用经典细化算法提取面状要素的骨架线,会出现很多重要特征点及线都没有提取出来的情况,如图 2中黑色圆圈标出的地方。下面对经典算法作相应的改进,以解决该问题。

图 2 改进前得到的骨架线与原图的叠加图

1.保证骨架线完整性的改进

第二部分第 2节中已经提到过,经典算法中的七个条件实际上是给出的连通性条件,通过多次试验发现,这七个条件中的 2)和 3)是用来保证上下方向的连通性。由此可想到将经典算法中的条件2)放宽,改为 P3+P7=0且 P1+P2+P8＞0或P4+ P5+P6＞0。图 3为原栅格面状要素,图 4为对第二个条件作修改后所得到的骨架线与原图的叠加图,与图 2改进前所得到的骨架线与原图的叠加图相比,可以发现保留了更多的重要支线与点,图中黑色圆圈已标出。

图3 原栅格面状图

图 4 改进条件 2)后所得骨架线与原图的叠加图

同理,将条件 3)改为 P1+P5=0且 P2+P3+ P4＞0或 P6+P7+P8＞0,所得到的骨架线见图 5,很明显比图 2保留了更多的特征线或点,但保留要素有些不同。

图 5 改进条件 3)后所得骨架线与原图的叠加图

将条件 2)和 3)同时改进可得到图 6,保留了更多的骨架支线和特征点。由此可以看出通过这样的改进后,提取的骨架线更能比较详细地反映面状要素的基本特征。

图 6 同时改变条件 2)和 3)所得骨架线

图 7是利用ArcGIS软件中的 Thin细化工具所得到的面状要素骨架图与原图的叠加图,可以明显看出,骨架线不是很平滑,会产生一些抖动现象且很多支线或重要点被删除。相比而言,通过对经典细化算法改进后所得到的骨架线,更能比较详细地反映面状要素的形状特征,且无抖动现象。

图 7 通过ArcGIS 9.2提取的骨架线

2.保证线、面连通性的优化

在制图综合中,时常会通过提取河流骨架线来作双线河到单线河的转变。图 8为某条河流及它周边的一条支流,图 9是对图 8中黑色方格处的放大图,从图 9可以看出,提取该河流的骨架线时,在保证河流与周边支流间的独立性的同时,必须保持该河流的骨架线与其周边支流间的关联性。而利用经典细化算法提取该河流的骨架线时,无法实现与特定支流间的连通性,从图 10中可以看出提取的骨架线与支流没有任何连接,破坏了该河流与支流间的关联性。对于这个问题,可以通过对原始数据进行预处理来解决。

图8 河流栅格图

图 9 对图 8中黑色方格处的放大图

图 10 未改进时所得骨架线与原图的叠加图

首先对原始数据进行扫描,找出该河流与支流的相交点并将该交点的像素值改为其他值,此试验中原像素值为 1,将其改为 2。图 11即为运用此改进后的经典算法提取河流的骨架线与原图的叠加图,该图方框中标出的线即为强制保留的骨架线,与图 10改进前提取的骨架线与原图的叠加图比较,可以发现经过改进后的经典算法能够很好地保持骨架线与其周边重要要素间的关联性。

图 11 改进后所得骨架线与原图的叠加图

四、结束语

不同的应用目标,对细化结果的要求不同。从试验结果可以看出,利用改进后的算法所得到的结果比较符合实际需要,在提取骨架线的同时保留了必要特征点,既实现了骨架线的连通性,同时也保持了与其他要素之间的关联性。经总结改进后的经典细化算法有以下优点：①通过修改经典算法的基本规则,使得骨架线可以延伸至面状目标边界,保证了骨架线的完整性;②通过改变线状要素与周边其他要素间的交点像素值,保留了它们之间的连通性;③最大限度地消除冗余数据的同时,根据需要提取线状要素的骨架线,具有较强的灵活性和实用性。

[1] 车武军,杨勋年,汪国昭.动态骨架算法 [J].软件学报,2003,14(4)：818-823.

[2] 毋河海.地图综合基础理论与技术方法研究[M].北京：测绘出版社,2004.

[3] 樊红.地图注记自动配置的研究[M].北京：测绘出版社,2004.

[4] 杜世宏,杜道生,樊红,等.基于栅格数据提取主骨架线的新算法 [J].武汉测绘科技大学学报,2000,25 (5)：432-436.

[5] 王涛,毋河海.顾及多因素的面状目标多层次骨架线提取[J].武汉大学学报：信息科学版,2004,29(6)：533-536.

[6] 艾廷华,郭仁忠.支持地图综合的面状目标约束Delaunay三角网剖分[J].武汉测绘科技大学学报,2000,25 (1)：35-41.

[7] 张宏,温永宁,刘爱利,等.地理信息系统算法基础[M].北京：科学出版社,2006：80-82.

[8] 乔庆华,吴凡.河流中轴线提取方法研究[J].测绘通报,2004(5)：14-17.

[9] ZHANG T Y,SUEN C Y.A Fast Parallel Algorithm for Thinning Digital Patterns[J]. Image Processing and ComputerVision,1984,27(3)：236-239.

[10] 杜瑞颖,刘镜年.面状地物名称注记的自动配置研究

[J].测绘学报,1999,28(4)：365-368.

Research on Algorithm of Polygon Skeleton L ine Extracting

GUO Bangmei,WANG Tao,ZHAO Rong,L IANG Yong

0494-0911(2010)12-0017-03

P208

B

2010-01-26

国家863计划项目

郭邦梅(1986—),女,青海互助人,硕士生,主要研究方向为地图制图学与地理信息工程。