基于細(xì)化和最小生成樹的多邊形主骨架線提取

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

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

關(guān)鍵詞： 主骨架線; 細(xì)化; 最小生成樹; 最小包圍盒; 路徑

中圖分類號(hào)： P 208??? 文獻(xiàn)標(biāo)志碼： A??? 文章編號(hào)： 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? 引言

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

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

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

1? 算法描述

算法的主要流程

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

確定最小包圍盒

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

在包圍盒中生成均勻點(diǎn)

提取區(qū)域骨架

利用算法生成骨架線樹

提取主骨架線

2? 實(shí)驗(yàn)與分析

3? 結(jié)論

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

參考文獻(xiàn)：

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

（責(zé)任編輯：包震宇，馮珍珍）