一种基于改进的Alpha Shapes算法的地面激光点云建筑物轮廓线提取方法

摘要

本发明公开了一种基于改进的Alpha Shapes算法的地面激光点云建筑物轮廓线提取方法，其特征在于，包括如下步骤：(1)首先基于RANSAC算法进行建筑物的立面分割，得到多个相对独立的建筑物立面点云；(2)根据每个平面的点集建立Delaunay三角网；(3)设置Alpha shapes算法中检测圆的半径R，设置为1～2倍的平均点间距；(4)若三角形中某条边的长度大于2R，则删除该三角形；(5)对三角形的每条边进行判断：若过某条边的两点且半径为R的圆包含其他点，则删除该三角形；(6)在所得到的三角网上求出三角网的边缘；(7)进行点云面片的合并从而得到完整的建筑物轮廓线。本发明具有效率高、稳定性好等优点。

说明书

技术领域

本发明涉及地理信息技术领域，尤其涉及一种基于改进的Alpha Shapes算法的激光点云建筑物轮廓线提取方法。

背景技术

地面三维激光扫描系统作为一种全新的空间数据获取方式，兼顾了距离和空间分辨率的高精度需求，其能快速、精准、连续、自动的获取关于建筑物立面的高精度三维点云。建筑物的轮廓信息是建筑物提取与三维模型重建的重要基础,已广泛应用于城市基础信息库更新、目标识别、灾害预估、变化检测、房地产等领域。目前,基于激光点云数据追踪建筑物平面轮廓的一般方法是采用插值算法,将三维点云的高程值赋给图像灰度值,进一步处理得到规则化的nDSM,最后图像分割,边缘检测或结合高分辨率影像进行建筑物轮廓线的提取。这些方法存在的问题是所追踪到的边缘是离散点集的粗略边界,精度较低。

也有一些学者研究了直接从离散点集提取其轮廓的方法,如黄先锋等提出一种基于平面离散点的边缘追踪算法,该算法将边长比作为约束条件,降低了算法参数对点密度的依赖性,从而提高算法对细长特征或分布不均匀的点集边缘提取的适应性,但是约束条件的阈值设置不当易造成边缘过渡收缩的现象。

Alpha Shapes算法最早由Edelsbrunner等提出,后来许多学者对其进行改进并应用于激光点云数据处理领域,该算法理论完善、效率高,还能够处理较复杂的建筑物轮廓提取问题,主要缺点是不适用于分布不均匀的数据,同时算法参数的选择也较困难。当检测圆的半径α较大时,检测圆在点集S的外部滚动,外部滚动的痕迹就是点集的边界轮廓线。当半径α值较小时,检测圆就滚动到点集S内部去,当α值足够小时,点集中的每个点都是边界点。圆半径α的取值与检测出来的建筑物轮廓线精细程度密切相关。半径相对较小时,检测出来的轮廓线较精细,半径相对较大时,检测出来的轮廓线略微粗糙。因此现有方法还需要进一步完善。

发明内容

本发明所要解决的技术问题是提供一种基于改进的Alpha Shapes算法的激光点云建筑物轮廓线提取方法，用于解决现有建筑物的轮廓线提取效率低等问题。

为解决上述的技术问题，本发现采用以下技术方案：

基于改进的Alpha Shapes算法的地面激光点云建筑物轮廓线提取方法，包括以下步骤：

步骤1：首先基于RANSAC算法进行建筑物的立面分割，得到多个相对独立的建筑物立面点云；

步骤2：根据每个平面的点集建立Delaunay三角网；

步骤3：设置Alpha shapes算法中检测圆的半径R，一般设置为1～2倍的平均点间距；

步骤4：若三角形中某条边的长度大于2R，则删除该三角形；

步骤5：对三角形的每条边进行判断：若过某条边的两点且半径为R的圆包含其他点，则删除该三角形；

步骤6：在所得到的三角网上求出三角网的边缘；

步骤7：进行点云面片的合并从而得到完整的建筑物轮廓线。

作为优选，所述步骤1中采用的基于RANSAC算法进行建筑物的立面分割的具体方法是：

步骤1.1：设点集Q为空，最优点集Q_best为空，迭代次数为1；

步骤1.2：随机选取三个点，计算出平面参数，记为模型M；

步骤1.3：计算点集中的所有点与该模型的偏差，将偏差小于0.5的点加入点集Q中；

步骤1.4：如果当前点集Q元素个数大于最优点集Q_best，则更新Q_best＝Q，同时更新迭代次数；如果迭代次数大于10000,则退出,此时最优点集Q_best即为该建筑物分割出的一个点云平面；否则迭代次数加1，并将Q设为空集，并重复上述步骤1.2至1.4。

步骤1.5：并重复上述步骤1.2至1.4。

作为优选，所述步骤2中建立Delaunay三角网具体方法是：

步骤2.1：构建平面点集p的超三角形或超多边形，并以此作为该点集的凸闭包；

步骤2.2：将点集p中的一点插入三角网中，在插入的过程中要注意满足Delaunary三角网的空圆法则，如果三角网中存在三角形Ti的外接圆包含插入点即将其删除；

步骤2.3：以插入点和三角形Ti的非公共边为基础构建新的三角网，以此循环迭代直至点集p为空时则算法停止。

本发明的技术构思是：提出一种基于改进的Alpha Shapes算法的激光点云建筑物轮廓线提取方法。首先通过调整参数实现建筑物各立面的分割；接着对各个面片进行轮廓线的提取；最后进行立面面片的合并，得到整体建筑物的轮廓线。本发明能够完成建筑物轮廓线的提取，不依赖先验信息。

本发明的优点在于：无需借助任何其他先验信息，能够完成建筑物轮廓线的提取。本发明具有效率高、稳定性好等优点，为建筑物的三维建模提供了很好的技术支持。

附图说明

图1为本发明的总的流程图。

图2为建筑物立面分割整体效果图。

图3a～3c为建筑物三个不同立面面片。

图4a～4c为图3a～3c中建筑物各立面面片对应的轮廓线提取图。

图5为建筑物的整体轮廓线提取图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明做进一步地详细说明。此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

基于改进的Alpha Shapes算法的地面激光点云建筑物轮廓线提取方法，包括以下步骤：

步骤1：首先基于RANSAC算法进行建筑物的立面分割，得到多个相对独立的建筑物立面点云；

步骤1.1：设点集Q为空，最优点集Q_best为空，迭代次数为1；

步骤1.2：随机选取三个点，计算出平面参数，记为模型M；

步骤1.3：计算点集中的所有点与该模型的偏差，将偏差小于0.5的点加入点集Q中；

步骤1.4：如果当前点集Q元素个数大于最优点集Q_best，则更新Q_best＝Q，同时更新迭代次数；如果迭代次数大于10000,则退出,此时最优点集Q_best即为该建筑物分割出的一个点云平面；否则迭代次数加1，并将Q设为空集，并重复上述步骤1.2至1.4。

本实施例为LiBackpack D50背包激光雷达扫描系统扫描得到的单栋建筑物，在用RANSAC算法进行立面提取的时候事先进行平面偏差阈值的设定，即可完成对本实施例的立面分割，建筑物立面分割整体效果图如图2所示，单个的立面面片如图3a～3c所示。

步骤2：根据每个平面的点集建立Delaunay三角网；

步骤2.1：构建平面点集p的超三角形或其他超多边形，并以此作为该点集的凸闭包；

步骤2.2：将点集p中的一点插入三角网中，在插入的过程中要注意满足Delaunary三角网的空圆法则，如果三角网中存在三角形Ti的外接圆包含插入点即将其删除；

步骤2.3：以插入点和三角形Ti的非公共边为基础构建新的三角网，以此循环迭代直至点集p为空时则算法停止。

步骤3：设置Alpha shapes算法中检测圆的半径R，一般设置为1～2倍的平均点间距；

步骤4：若三角形中某条边的长度大于2R，则删除该三角形；

步骤5：对三角形的每条边进行判断：若过某条边的两点且半径为R的圆包含其他点，则删除该三角形；

步骤6：在所得到的三角网上的所有点进行逐点连接，得到建筑物立面的轮廓线，本实施例中建筑物各立面面片对应的轮廓线提取图如图4a～4c所示。

步骤7：进行点云面片的合并从而得到完整的建筑物轮廓线，点云合并即为同一视窗中多个点云的可视化加载，本实施例中建筑物的整体轮廓线提取图如图5所示。

本发明充分利用了建筑物自身的特点，能够实现复杂的、带噪声的三维点云建筑物的轮廓线提取，本发明不需要先验信息，在精确性和鲁棒性两个方面有明显的优势。

最后说明的是以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明技术方案进行修改或者同等替换，而不脱离本发明的原理和范围。