基于细化和最小生成树的多边形主骨架线提取

杨雨雪　王红艳　张玲玲　景莹　姚欣赟　马燕

摘  要： 现有的不规则多边形主骨架线提取方法存在设计复杂、执行效率低等缺点，对此提出一种基于细化和最小生成树的多边形主骨架线提取方法.首先，确定多边形的最小包围盒，并在其中生成均匀分布、数值分别为0或1的点，运用细化算法提取多边形骨架;再利用Prim算法生成最小生成树;最后，计算最小生成树上的两个叶子节点间的路径长度，将长度最长的路径定义为主骨架线.实验结果表明：本方法提取出的主骨架线效果较好，具有一定的实用性.

关键词： 主骨架线; 细化; 最小生成树; 最小包围盒; 路径

中图分类号： P 208    文献标志码： A    文章编号： 1000-5137（2022）02-0204-06

YANG Yuxue， WANG Hongyan， ZHANG Lingling， JING Ying， YAO Xinyun， MA Yan

（College of Information， Mechanical and Electrical Engineering， Shanghai Normal University， Shanghai 201418， China）

It existed that the current methods for extracting main skeleton lines of irregular polygons had disadvantages such as complex design and low execution efficiency. To solve these issues， a novel algorithm to extract main skeleton lines of polygons based on thinning and minimum spanning tree was proposed. Firstly， the minimum bounding box of the polygon was determined， in which the points with values of 0 or 1 are uniformly distributed. Secondly， the skeleton of the polygon was extracted by the thinning algorithm， after which the minimum spanning tree was generated by Prim algorithm. Finally， the length of the path between the two leaf nodes in the minimum spanning tree was calculated and the path with the maximum length was taken as the main skeleton line. The experimental results showed that the proposed algorithm was effective and practical.

main skeleton line; thinning; minimum spanning tree; minimum bounding box; path

0  引言

主骨架线是对多边形主体形状的抽象描述，反映了多边形的主延伸方向和主体形状特征，是面状要素特征描述的重要指标之一.主骨架线在模式识别和计算机视觉领域中具有重要的研究意义，在地理信息系统（GIS）中也有广泛的应用.对于地图而言，主骨架线是其抽象描述的形式，通过提取地图区域的主骨架线，将文字标注在骨架线上，在一定程度上可以避免格网法、编码算法的压盖，以及文字与区域脱离等情况.

现有的骨架线提取方法可分为基于栅格图像和基于矢量地图的提取方法.WANG等在Delaunay三角網的基础上，对骨架线节点进行分类，利用回溯法提取主骨架线.SONG等基于GIS空间分析，利用各种可视化工具进行模型构建，实现多边形骨架线的自动获取.LIU等利用双缓冲区变换、障碍距离变换和Voronoi图技术，对多边形骨架进行层次划分.YE将骨架细化为单像素，根据骨架的特点选择不同的阈值，去除连通分支.

在提取多边形的骨架时，大多采用生成图网的方法，得到均匀覆盖在多边形内邻接点.但地图包含的多边形形状各异，位于多边形边界上的点也较多，生成三角网的代码复杂，并且通常会对骨架线进行拉直处理，使其更加平滑，算法执行效率较低.针对该问题，本文作者提出了基于细化和最小生成树的多边形骨架提取算法，将确定主骨架线转化为寻找最小生成树上的最长路径问题，利用最小生成树表示多边形的骨架，可适用于各种形状的多边形，提高了骨架提取的效率与准确性.

1  算法描述

算法的主要流程

输入任意形状的多边形，根据该多边形边界点的横、纵坐标，确定其最小包围盒.在最小包围盒内部生成均匀分布的点，同时判断点是否在多边形内部，将位于多边形内部的点的数值设置为1，外部的点的数值设置为0.对于数值为1的点，利用细化算法，经过多次迭代，提取区域的骨架，并利用Prim算法对骨架上的所有点生成最小生成树，即骨架线树.计算最小生成树上的任意两个叶子节点间路径的长度，将长度最长的路径作为主骨架线.

确定最小包围盒

根据输入的多边形，计算所有点横坐标的最小值和最大值，以及纵坐标的最小值和最大值，根据，，和确定矩形边框的四个顶点，从而确定该区域的最小包围盒，如图1所示.

在包围盒中生成均匀点

提取区域骨架

利用算法生成骨架线树

提取主骨架线

2  实验与分析

3  结论

通过在多边形内部和外部生成不同数值的均匀点，采用细化算法提取区域骨架，再通过计算骨架线树上每一条路径的长度确定主骨架线，将主骨架线作为对多边形主延伸方向的描述.鉴于最小生成树所有边权重之和最小的特性，提取出的主骨架线不存在螺旋形状，适用于任意形状的多边形，因此本算法具有一定的普适性.

参考文献：

[1]  CAI X Q， YANG Z， CAI R B， et al. Image skeleton extraction based on flooding filling [J]. Journal of System Simulation，2020，32（8）：1455-1464.

[2]  CHEN T， AI T H. Automatic search algorithm for polygonal skeleton lines and centroids [J]. Geomatics and Information Science of Wuhan University，2004（5）：443-446，455.

[3]  WANG T， WU H H. Multi⁃factor multi⁃layer skeleton line extraction for planar objects [J]. Geomatics and Information Science of Wuhan University，2004（6）：533-536.

[4]  AI T H， GUO R Z， CHEN X D. The simplification and consolidation of polygons supported by Delaunay triangle network [J]. Journal of China Graphics，2001（7）：93-99.

[5] LU W， AI T H.Extracting simple polygon target center point by triangulation skeleton graph [J].Geomatics and Information Science of Wuhan University，2020，45（3）：337-343.

[6]  ZHAO J， LUO X G， ZHANG R Y. A new annotation algorithm for electronic map： grid method [J]. Computer Engineering，2008（7）：278-279，282.

[7]  XU W， YAN Y.An embedded map dynamic annotation method based on grid coding [J]. Electronic Quality，2020（11）：5-8.

[8]  WANG Z H， YAN H W.Design and implementation of polygon main skeleton extraction algorithm [J]. Geography and Geo-Information Science，2011，27（1）：42-44，48.

[9]  SONG R B， ZHU Y X， DING S S， et al. Automatic extraction method of arbitrary polygon skeleton line based on GIS spatial analysis [J]. Remote Sensing for Land and Resources，2020，32（1）：51-59.

[10] LIU X F， WU Y L， HU H. Multi⁃level skeleton line extraction of planar elements [J]. Journal of Surveying and Mapping，2013（4）：588-594.

[11] YE F L. An improved image skeleton extraction algorithm [J]. Journal of Xichang University （Natural Science Edition），2018，32（3）：91-93，123.

[12] LUO D H， QIAN H Z， HE H W， et al. Planar building multi-level skeleton line extraction method [J]. Journal of Surveying and Mapping Science and Technology，2019，36（3）：324-330.

（責任编辑：包震宇，冯珍珍）