边界为一个复杂的平面点集构造算法

文摘

很难提取复杂平面的边界点与非均匀分布的点密度,凹信封和漏洞。为了解决这个问题,本文提出了一种算法。德劳内三角测量的基础上,介绍了最大边界角阈值作为参数的提取的边界。然后,重点介绍了松动阈值,和边界提取等地方进行凹信封和漏洞。最后,完成整个点集的边界的结果。验证了该算法的有效性通过实验模拟的点集和实际测量的点集。实验结果表明,它有更广泛的适用性和有效性在工程应用中比最先进的基于德劳内三角测量边界构造算法。

1。介绍

基本空间数据点集,表示物体的形状。GNSS调查中,三维激光扫描、航空摄影、航空航天遥感技术生产大规模数据点集。这些数据的准确和高效的处理是一个挑战建筑信息模型(BIM),地理信息(GIS)、遥感(RS)、计算机信息技术(IT),计算机辅助设计/制造(CAD / CAM)和其他相关领域(1]。点集的边界信息由离散点代表原始轮廓测量对象的特性。的快速和高效的建筑边界离散点集的信息基本空间数据处理的关键,在GIS-related领域中扮演着很重要的角色,如地理边界的决心(2,3)、建筑轮廓提取(4,5),地图概括(6,7)、统计图形区,和道路土方体积的计算8,9]。真正的对象是不同的物理形状,可以是简单或复杂的。这表明边界点集用于数字代表对象的外形也多样和复杂。这个边界的复杂性体现了以下四个问题:(1)的有效组织空间关系(几何、拓扑)的点;(2)非均匀分布的点密度;(3)准确表达信息的边界形状(凹面和凸面);和(4)的内部多孔的问题。这些都是要面对的主要问题复杂的平面点集的边界建设。

目前,两种算法主要是利用构造平面点集的边界点集的算法基于凸包的算法基于德劳内三角的点集。前(10- - - - - -12]从点集的凸壳多边形构成和使用不同的收缩算法获得的边界特征点集,可以处理非均匀分布的点集和点集与凹信封地区在特定条件下。这种算法的最大缺点是它不能处理内部多孔的问题。后者必须首先构建德劳内三角测量。然后,提取相应的边界三角形,边界线段,或边界点基于三角测量的几何特征来表示真实对象的轮廓特征。雕塑的算法(13)和α形状算法(14)是这类算法的主要代表。雕塑的关键算法和改进算法等算法(15),算法(16)是逐步删除不需要的三角形从外到内的三角测量,直到一个边界点集,最后生成满足给定的条件。本质上,雕塑算法是一个三角剥离算法。该算法的主要缺点是它不够稳定,处理复杂的凹边界和边界与内部漏洞,特别是狭长孔。阿尔法形状算法被Edelsbrunner首次提出。其主要功能是给一个严格的数学定义的“点集的形状。“在此基础上,该算法构造一个二维点集边界的基础上,德劳内三角。原α形状算法适用于处理的边界点集的凸包与均匀分布,但它不适合复杂的平面点集与凹信封和漏洞。之后,一些改进的Alpha版本图形算法,如(17),(18提出了]。基于局部度量或全球度规,这些算法采用不同的规则来解决问题构建复杂的平面形状边界点集和非均匀密度等漏洞。然而,一些问题需要解决,如必需的参数太多,令人不满意的提取边界的狭长孔。

总之,德劳内三角可以很容易地记录一个不规则的平面点集的空间信息在一个特定的数据结构。同时,它具有强大的可扩展性,是成熟和稳定的三角代算法。因此,与其他类型的算法相比,德劳内三角测量是相对强劲的平面点集的构造边界。德劳内三角测量的基础上,提出了新的边界构造算法来解决现有问题的边界平面点集的建设。该算法首先处理凸包的边界三角测量作为一个整体,形成一个粗略的边界,然后改进处理结果通过相应的数学模型来实现一个完整的建筑的复杂平面点集的边界。模拟对比实验的结果和实际测量实验表明,该算法是有效和可行的。

2。相关定义

为方便算法描述,一些基本概念的定义和符号,将在本文中使用了。

让 平面点集和是基于生成的德劳内三角测量 。让 是三角形的顶点,边三角形,三角形 ,分别为:(1)边界:在三角形的 ,属于边缘只标记为一个三角形 ;算法的结果是一组边界边,也就是说, 。(2)边界点: ,顶点连接边界边表示为 。边界点的边界点集合,例如, 。(3)内点: ,nonboundary点是内陆点,表示 。内陆点形成了内点集,也就是说, 。(4)边界三角形:三角形的 ,包含至少一个边界边的三角形表示 。三角形形成的边界三角形的边界集,也就是说, 。(5)边界角度:边界三角形的内角对应边界边缘来标示 。(6)凹信封(19:给定一个多边形覆盖点集 ,Conv代表的凸包 。 代表之间的空地和 ,和每个开放的区域是由一个封闭的曲线 。这些封闭的曲线形成的区域被称为凹信封。在 ,凹信封的边缘被称为凹边缘,并且每个凹信封包含可见的边界边和几个凹边缘。(7)洞:一个凹信封只有凹边缘和边界边是一个特例。

3所示。算法概述

该算法包括两个步骤:提取的边界和提取边界。预处理,一个稳定的算法是利用生成德劳内三角测量 。在此基础上,点集的凸包发现,基本数据准备的顺利进展的算法。首先,根据边界角的参数选择原则 ,一个粗略的边界提取,过滤内心从最初的凸壳的边缘。然后,最大密度和边缘点作为参数,长度等地方凹信封和孔进一步细化,形成最终的完整的边界。

3.1。提取的边界

3.1.1。算法流程

德劳内三角的点集生成需要的输入数据。生成德劳内三角测量的算法是非常成熟,和增量插入算法是利用生成德劳内点集的三角剖分算法。三角形,三角形边和三角形三种几何实体构成德劳内三角测量。列在表1数据结构与拓扑关系,德劳内三角测量是为了节省设备的存储空间和提高算法的运行效率。

从表可以看出1,德劳内三角的几何实体的拓扑关系定义的三角形边缘。后的开始点和结束点三角形边缘定义,三角形边缘变成一个向量,可以方便地记录其相邻的三角形。

根据完形接近原则(20.),平面点集的边界是由连结点具有相似距离他们的边缘点。至于边界三角形,如果边界边缘很长,超过给定的阈值,它违反了邻近原则,需要删除。因此,最大边界边长度可以作为筛选条件来提取边界。然而,长度阈值是一个全球性的度量。一旦设置,它是固定的点集的整个过程处理,这不是有效的在处理点集的非均匀分布。在这种情况下,使用最大边界角作为边界被认为是过滤条件。因为三角形的角是由三方构成三角形的相对长度,这是一个当地的指标和适用于处理非均匀分布的点。因此,最大边界角阈值选为筛选条件的边界提取的边界点集。在提取过程中,为了保证结果的唯一性,边界边需要安排在根据边界角的大小降序排列。提取过程如图1。

考虑到删除规则边界边,两个特殊情况需要关注,如图所示2:(1)链和暂停,这不是的一部分三角形;(2)两个以上边界边的交点,即。当删除一个边界边,有必要进行拓扑检查新的边界。如果(1)和(2)出现,应该撤销删除操作。

3.1.2。选择最大边界角阈值

的过程中提取的边界,最大边界的阈值角度不能确定一个明确的计算公式。相反,它需要由实验决定。在该算法中,规范(15计算公式(1)是用来评估的准确性提取结果:

在公式(1),代表原始图的多边形,代表了多边形图的四周边界提取的算法。的标准代表了边界提取效果通过之间的比例关系的多边形区域图的原始图和多边形区域提取的边界所包围。越小 ,提取的边界之间的重合程度越高和原始图形边界,和更好的效果。

本文实验通过三组符号形状,包括等值线,F,和k .实验数据点的数量,分别于100年、150年,200年和250年,代表不同的点密度。与此同时,点均匀分布的形状,并确保每个形状内的点集可以覆盖形状边界。最大的范围边界角和一个区间[0,180]10度。图3说明了F边界形状的提取效果,和图4显示相应的变化曲线。实验结果表明,该阈值范围内的最大边界角下降[100],和算法可以达到满意的边界提取结果。

3.2。提取的边界

3.2.1之上。算法流程

粗糙的边界提取得到的边界可以代表的轮廓形状特征点集在某种程度上。然而,复杂凹信封的表达不够准确,和黑洞的边界不能完全处理。它可以看到从红三角图5(一个)可能有非常小的边界角凹信封地区当不规则三角形。因此,边界边缘可能被忽略的过程中删除,从而影响边界结果的质量。删除这样的边界边,最大的门槛边界角必须降低。然而,这将导致边界收缩过度,成为打破。在这种情况下,无法获得理想的边界。考虑到黑洞的边界图所示6,因为它的边界不是边界三角形的边缘 ,规则提取的边界边的最大边界角是无效的。因此,有必要为凹信封和孔设计特殊规则来提取边界。

自一个洞是一个特例的凹信封,下面描述的凹信封包含孔的特点,除非另有说明。从数据可以看出5和6点集包含凹信封,信封凹区域的点密度明显低于正常的地区。从正常地区凹信封区域,反之亦然,点密度变化很大,和一个参数的变化可以表示称为点松动。让德劳内任意点的三角测量由给定的点集 ,和的宽松点,可以通过以下公式计算: 在哪里和的平均长度和标准差是点之间的线段分别和连接的点。

的值越小 ,更细微的点的边缘长度之间的区别和连接的点,不太可能是一个边界点;否则,越有可能是一个边界点。如数据所示5 (b)和6 (b),正常的边界点和凹的松动信封边界点很大,而内陆点很小。因此,松散的阈值可以作为一个参数设置检测凹信封地区,和宽松的凹信封集地区提出了以下公式:

边界点的凹信封可以获得的 。具体地说,一个大松动的凹信封边界点表明边界点之间的线段的长度和连结点是大大不同的。过滤这些线段移除不必要的长边下面的处理至关重要。一条边长度约束参数通过以下公式: 在哪里的平均长度是点之间的线段点和连接所有点的平均值吗在给定的点集 。

对于任何一个点在点集处理粗糙的边界提取,如果连结点的边缘长度大于 ,根据边界边缘应该删除删除规则。否则,保留连结点和边缘处理后的边界提取方法来生成所需的边界的结果。优良的边界提取过程如图7。

值得注意的是,处理好边界提取序列不能逆转。凹信封(无孔)应该是孔加工之前进行处理。至于算法,需要过滤前的点松动边界边。这可以过滤掉最不规则三角形。此外,宽松点遍历和边缘点遍历连接长度在降序排列,以确保边界提取结果的唯一性。

3.2.2。松动的确定阈值

确定点松动阈值是一个边界提取过程中关键的一步好。据的定义点松动,松动的边界点明显大于内部点的。宽松点的确定阈值可以被视为一个二次曲线分割的问题。所示的目标函数公式(5)是利用检测点集之间的过渡区,找到点自动确定初始边界和最终边界 。为此,有必要构建一套 它包含所有点的松动安排在一个升序排序: 在哪里是集合的元素 ; 是一组的平均值 ; 的标准偏差是准备好了吗 ;和是调整参数。更大的是,相应的松动阈值越大会,更多的边界细节将被保留。

根据目标函数后,松动点集的划分为两个部分。圆锥分割实现最好的效果(最大最小值组合方差和组内的方差),PBM指数(21]介绍了自动求解参数 。这个指数是一个相对的评价指标,可以满足密实度和分离的聚类标准。这个指数的计算公式如下: 在哪里代表的数量分类;代表点的数量分类 ; 代表了质心分类 ; 代表的内部距离分类(分类中的所有点之间的距离的总和和质心分类);代表的内部距离聚类的点集分成类;和代表着分离程度的点集的分类。PBM指数越高,分类结果的可靠性就越高。

4所示。模拟对比实验

来验证该算法的有效性,本文设计了仿真实验对于三个场景,包括非均匀分布的点集,与凹信封一个均匀分布的点集,一个均匀分布的点集与漏洞。与此同时,验证该算法的适用性,德劳内triangulation-based算法和被作为参考。实验结果和分析如下。

4.1。非均匀分布的点集

150点是手工绘制一个圆形区域的半径35长度单位的CAD软件。如图8点的密度,减少从左到右。这些点的二维坐标数据文件从CAD软件导出,然后导入到算法验证程序的点集数据。结果如图所示8和表2。

实验结果表明,三种算法可以成功地提取的边界点集,提取的边界的粗糙度随算法的参数。自全球测量算法阈值的边缘长度作为参数,边界提取的效果不稳定。为一个小 ,这个算法可能产生更多的锯齿波点密度较小的区域。这两个算法和该算法获得更好的边界的结果。

4.2。均匀分布与凹点集信封

200点是手动与均匀分布在一个封闭的区域的宽度大约20个单位长度。封闭的区域由CAD软件绘制,这是字母C的外围轮廓包围Arial黑色字体,如图9。这些点的二维坐标数据文件从CAD软件导出,然后导入到算法验证程序的点集数据。结果如图所示9和表3。

实验结果表明,三种算法可以成功地提取的边界点集具有良好的效果。相比算法和算法,该算法提供了一个合理的数学定义和检测方法基于二次曲线分割指数有很强的理论基础。

4.3。均匀分布和孔点集

280点了手动与均匀分布在一个圆形区域的半径35长度单位的CAD软件。然后,40分被删除沿水平方向的直径,形成一条狭窄的洞,如图10。这些点的二维坐标数据文件从CAD软件导出和导入到算法验证程序的点集数据。结果如图所示10和表4。

实验结果表明,算法未能提取洞边界,边界只有当算法提取出洞是适当的,而该算法提取的洞边界与更好的效果比吗算法时是适当的。尽管该算法可以提取的边界孔,有时它也可能失败,提取结果会截然不同的实际情况,如果参数值不合理。在这种情况下,人工歧视在实际应用需要。

5。试验研究山区高速公路的带状地形点集

来验证算法的有效性,实际测量的点集,长17公里公路地带地形数据组成的8000多个GPS点被选为实验数据。实际测量的点集得到带状地形图调查任务由作者在2016年5月,和高速公路地带位于农村公路的一段Guquan城镇Shuiyang镇宣城城市,安徽省。这项任务的目的是为当地提供地形图道路规划。任务的技术要求如下:(1)地形图应该在数字格式和规模应该是1:1000。(2)地形图的宽度是沿着道路中心线的两侧50米。(3)映射内容包括植物、河流网络、道路、建筑和结构沿中心线。任务的概况网站如图11。

调查任务在2016年5月没有具体表现来验证该算法的有效性。对于山区高速公路,有很多带状地形弯曲,密集的收集点在高低起伏的地区,和稀疏的集合点在平坦区域。这个特点是均匀分布的点集,许多凹信封(红色圆圈所示图12(一个)和一些漏洞,如坑池在某些领域(如图12 (c)和12 (d))。因此,GPS地形点集获得的调查任务是适合用作数据源来验证该算法的有效性。

8156 GPS地形点被用于实验,和道路的长度约17公里。实验对笔记本电脑配备英特尔®™核心i7 - 10750 h CPU@2.60 GHz和16 GB的内存。操作系统是64位Windows 10,和实验程序的算法实现了基于微软的c#编程语言Visual Studio 2010 IDE。实验结果如图所示12和表5。图12 (b)图12 (d)放大的图像边界提取的边界角阈值在高速公路曲线描述图中红色圆圈12(一个)。

实验结果表明,凹信封在西北的边界可以提取。同时,提取的边界结果改变从粗到细的最大边界角阈值从大到小的变化。这个结果与模拟实验是一致的。孔的数量由该算法提取的变化从少到多的最大边界角阈值α从大到小的变化。然而,正确的按照实际位置的孔数不会增加。对于一个大 ,忽略一些漏洞与较小的区域,提取数量小的洞。对于一个小 ,保留小孔,孔的数量增加。应该注意的是,提取的洞并不完全正确。有些是“伪黑洞”引起的非均匀分布的实际测量分,需要人工歧视。

6。结论

根据德劳内三角和两个约束参数,即。,最大的阈值边界角宽松的阈值点 ,本文的算法构造复杂的平面点集的边界密度分布不均匀点,凹信封和漏洞。该算法由粗糙边界提取和边界提取。与现有算法相比,该算法有两个主要优点:(1)该算法具有广泛的适用性,它可以应用于构造复杂的平面边界非均匀密度分布的点,凹信封,孔等。(2)一个合理的数学定义和基于二次曲线的检测方法分割指数给出处理凹信封,该算法提供了强有力的理论依据。

本文没有给出定量分析该算法的执行效率,即时间复杂性和空间复杂性。目前,该算法的应用仅局限于二维平面点集。进一步的研究应该进行效率的定量分析和三维表面重建。

数据可用性

使用的数据来支持本研究从实验中产生的结果。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究是由安徽教育部自然科学研究项目(KJ2018JD04)科技项目安徽省住房和城乡建设(2020 - yf23),和安徽大学的自然科学研究项目(KJ2020JD01)。作者要感谢乔丹编辑器(http://www.mjeditor.com)的语言帮助在准备这个手稿。

引用

1. 杨,r·黄董z, y藏,j·李,“两步自适应提取方法为地面点和破裂线从激光雷达点云,“ISPRS《摄影测量与遥感卷,119年,第389 - 373页,2016年。视图:出版商的网站|谷歌学术搜索
2. y,美国高,k . Janowicz b . Yu w·李和s·普拉萨德,“提取和理解使用标记照片感兴趣的城市,”电脑、环境和城市系统54卷,第254 - 240页,2015年。视图:出版商的网站|谷歌学术搜索
3. z . y . Wang h·c·马许h . g . et al .,“小说算法快速提取边缘从大规模点云,“计算机工程与应用,46卷,不。36岁,213 - 215年,2010页。视图:谷歌学术搜索
4. w·沈j . Li黄懿慧Chen等人”算法的研究建筑边界提取和基于激光雷达数据的规范化,“《遥感,12卷,不。5,692 - 698年,2008页。视图:谷歌学术搜索
5. d . b . y . f . Li Tan高g . et al .,“从点云提取建筑物轮廓使用双阈值α形状算法,”《长江科学研究所,33卷,不。11日,1 - 4,2016页。视图:谷歌学术搜索
6. t·h·Ai和l .姚”的方法简化集群具有空间分布特性的保存点,”Geodaetica et Cartographica学报没有,卷。31日。2、175 - 181年,2002页。视图:谷歌学术搜索
7. j·t·李,美国康和f·l·罗“点群泛化方法基于层次泰森多边形法图,“Geodaetica et Cartographica学报,43卷,不。12日,第1306 - 1300页,2014年。视图:谷歌学术搜索
8. b . y z太阳,j . Li刘et al .,“农业nachinery操作区域的测量算法,基于改进α形状”《中国农业机械化,40卷,不。8,144 - 148年,2019页。视图:谷歌学术搜索
9. 廖z . x和d·l·王”研究DTM锡生成算法考虑边界限制,”合肥工业大学学报(自然科学版),34卷,不。9日,第1384 - 1381页,2011年。视图:谷歌学术搜索
10. 答:位于和j·山”,建筑从机载激光雷达点云边界追踪和正规化,”摄影测量工程和遥感,卷73,不。7,805 - 812年,2007页。视图:出版商的网站|谷歌学术搜索
11. 他x j . Cheng和g . z,“洞边界提取的方法和应用多值表面修复,”Geodaetica et Cartographica学报,46卷,不。6,831 - 837年,2012页。视图:谷歌学术搜索
12. w·j·李,李、邱j . et al .,“边界检测multi-density点集群使用凸包收回方法,”测绘科学,39卷,不。9日,第129 - 126页,2014年。视图:谷歌学术搜索
13. j。Boissonnat,“几何结构三维形状表示,“ACM交易图片,3卷,不。4、266 - 286年,1984页。视图:出版商的网站|谷歌学术搜索
14. h . Edelsbrunner d·柯克帕特里克,r·塞德尔”形状的平面点集,“IEEE信息理论卷,29号4、551 - 559年,1983页。视图:出版商的网站|谷歌学术搜索
15. m . Duckham l . Kulik m . Worboys和a·高尔顿,“有效的代简单多边形的形状特征点集在平面上,“模式识别第41卷。。10日,3224 - 3236年,2008页。视图:出版商的网站|谷歌学术搜索
16. j . Peethambaran和r . Muthuganapathy形状重建的非参数方法从平面点集通过德劳内过滤”计算机辅助设计卷,62年,第175 - 164页,2015年。视图:出版商的网站|谷歌学术搜索
17. A·r·乔杜里比比乔杜里,s . k . Parui”一个新颖的方法来计算一个点的形状模式和提取的知觉边界,”计算机视觉和图像理解,卷68,不。3、257 - 275年,1997页。视图:出版商的网站|谷歌学术搜索
18. m . Melkemi和m . Djebali”计算平面点集的形状”模式识别,33卷,不。9日,第1436 - 1423页,2000年。视图:出版商的网站|谷歌学术搜索
19. 美国Mistry、联合国Niranjan和m . Gopi”Puzzhull:腔和突出层次结构以适应正形多边形,”计算机辅助设计,46卷,第238 - 233页,2014年。视图:出版商的网站|谷歌学术搜索
20. t·h·郭Ai和z,”多边形集群模式挖掘基于格式塔原则。”Geodaetica et Cartographica学报,36卷,不。3、302 - 308年,2007页。视图:谷歌学术搜索
21. m . k . Pakhira s Bandyopadhyay, Maulik,“清晰和模糊集群、有效性指数”模式识别,37卷,不。3、487 - 501年,2004页。视图:出版商的网站|谷歌学术搜索

版权

版权©2021 Zhenxiu辽和成国栋史。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。