楊雨雪　王紅艷　張玲玲　景瑩　姚欣赟　馬燕

摘? 要： 現有的不規(guī)則多邊形主骨架線提取方法存在設計復雜、執(zhí)行效率低等缺點，對此提出一種基于細化和最小生成樹的多邊形主骨架線提取方法.首先，確定多邊形的最小包圍盒，并在其中生成均勻分布、數值分別為0或1的點，運用細化算法提取多邊形骨架;再利用Prim算法生成最小生成樹;最后，計算最小生成樹上的兩個葉子節(jié)點間的路徑長度，將長度最長的路徑定義為主骨架線.實驗結果表明：本方法提取出的主骨架線效果較好，具有一定的實用性.

關鍵詞： 主骨架線; 細化; 最小生成樹; 最小包圍盒; 路徑

中圖分類號： 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? 引言

主骨架線是對多邊形主體形狀的抽象描述，反映了多邊形的主延伸方向和主體形狀特征，是面狀要素特征描述的重要指標之一.主骨架線在模式識別和計算機視覺領域中具有重要的研究意義，在地理信息系統(tǒng)（GIS）中也有廣泛的應用.對于地圖而言，主骨架線是其抽象描述的形式，通過提取地圖區(qū)域的主骨架線，將文字標注在骨架線上，在一定程度上可以避免格網法、編碼算法的壓蓋，以及文字與區(qū)域脫離等情況.

現有的骨架線提取方法可分為基于柵格圖像和基于矢量地圖的提取方法.WANG等在Delaunay三角網的基礎上，對骨架線節(jié)點進行分類，利用回溯法提取主骨架線.SONG等基于GIS空間分析，利用各種可視化工具進行模型構建，實現多邊形骨架線的自動獲取.LIU等利用雙緩沖區(qū)變換、障礙距離變換和Voronoi圖技術，對多邊形骨架進行層次劃分.YE將骨架細化為單像素，根據骨架的特點選擇不同的閾值，去除連通分支.

在提取多邊形的骨架時，大多采用生成圖網的方法，得到均勻覆蓋在多邊形內鄰接點.但地圖包含的多邊形形狀各異，位于多邊形邊界上的點也較多，生成三角網的代碼復雜，并且通常會對骨架線進行拉直處理，使其更加平滑，算法執(zhí)行效率較低.針對該問題，本文作者提出了基于細化和最小生成樹的多邊形骨架提取算法，將確定主骨架線轉化為尋找最小生成樹上的最長路徑問題，利用最小生成樹表示多邊形的骨架，可適用于各種形狀的多邊形，提高了骨架提取的效率與準確性.

1? 算法描述

算法的主要流程

輸入任意形狀的多邊形，根據該多邊形邊界點的橫、縱坐標，確定其最小包圍盒.在最小包圍盒內部生成均勻分布的點，同時判斷點是否在多邊形內部，將位于多邊形內部的點的數值設置為1，外部的點的數值設置為0.對于數值為1的點，利用細化算法，經過多次迭代，提取區(qū)域的骨架，并利用Prim算法對骨架上的所有點生成最小生成樹，即骨架線樹.計算最小生成樹上的任意兩個葉子節(jié)點間路徑的長度，將長度最長的路徑作為主骨架線.

確定最小包圍盒

根據輸入的多邊形，計算所有點橫坐標的最小值和最大值，以及縱坐標的最小值和最大值，根據，，和確定矩形邊框的四個頂點，從而確定該區(qū)域的最小包圍盒，如圖1所示.

在包圍盒中生成均勻點

提取區(qū)域骨架

利用算法生成骨架線樹

提取主骨架線

2? 實驗與分析

3? 結論

通過在多邊形內部和外部生成不同數值的均勻點，采用細化算法提取區(qū)域骨架，再通過計算骨架線樹上每一條路徑的長度確定主骨架線，將主骨架線作為對多邊形主延伸方向的描述.鑒于最小生成樹所有邊權重之和最小的特性，提取出的主骨架線不存在螺旋形狀，適用于任意形狀的多邊形，因此本算法具有一定的普適性.

參考文獻：

[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.

（責任編輯：包震宇，馮珍珍）