层次化点云边界快速精确提取方法研究

吴俊河，林 松，施向丰

(1.惠州市规划勘测研究院，惠州 516000；2.河海大学 地球科学与工程学院，南京 211100；3.江西理工大学 土木与测绘工程学院， 赣州 341000)

引 言

近年来,3维激光扫描技术在快速高精度获取3维空间信息中发挥着重要作用[1-2]，基于点云的目标识别和3维重建一直都是研究热点，边界提取是目标识别[3]、3维重建[4-5]过程中的重要步骤。精确的边界不仅影响着曲面几何特征的表达，还对重建后曲面模型的质量和精度有着重要的作用[6]。

目前边界点云的提取算法较多，主要有栅格划分法、微切平面法、三角网法和凸包类算法等。KE等人[7]对点云进行空间栅格划分，建立空间拓扑关系，依据栅格内是否有点检索边界，这种算法速度快，但是受点云密度和栅格大小影响较大，且提取精度不高。基于微切平面的方法是将待判定点及其邻域点投影到微切平面上，再依据一定的准则判别该点是否属于边界点。SUN等人[8]提出计算微切平面内投影点所构成的最大夹角作为判定依据。CHEN等人[9]通过模拟点与点间的拉力的合力判断待定点是否是边界点。SU等人[10]先计算各点法向量，然后将法向量投影至高斯球中，通过高斯映射法线聚类，依据聚类结果提取边界点，基于微切平面的方法效率太低，对每个点都需要投影，然后根据判断条件精确判定，耗时较长。基于三角网的方法，CHEN等人[11]提出通过遍历所有三角形的边长，依据边长阈值确定边界边，这种方法需要事先构建三角网，耗时较多。LIN等人[12]也提出了一种过滤三角网的方法提取点云边界，该方法也在点云数据量较少的情况下能取得较好的效果，在海量数据中提取效率较低。基于凸包类算法较为典型的是alpha shapes[13-14]，这种方法在2维点集中能取得较好的结果，但是在3维点集中提取结果不佳。LI等人[15]提出了凸壳内缩法提取离散点边界，但是无法提取内部空洞边界。JIANG等人[16]为了提高边界提取的效率，先采用HAN[17]提出的模拟点间拉力的方法先粗提取边界点，再依据SUN提出的最大夹角准则精提取边界点，该方法能够一定程度提高边界点提取效率，但是粗提取的判断准则计算量依然较大。

针对上述算法中边界点提取耗时较长的问题，本文中提出一种层次化提取边界点的方法。通常边界点只占总点云数据的少部分，对每个点都进行精确判定效率不高，可以采取简单的判定方法:先对整体点云进行初步筛选，提取出边界点潜在点集，再对边界点潜在点集进行精提取，从而能够实现边界点的高效提取。

1 算法描述

本文中的算法是首先对输入的点云数据构建k维(k-dimensional，k-D)树用于空间索引[18]，再采用R邻域内重心差异准则粗提取边界点，对粗提取的边界点在局部投影面上精确提取边界点。本文中算法的具体流程如图1所示。

Fig.1 Algorithm flow chart

1.1 边界点粗提取

3维激光扫描获取的点云数据是离散且无序的，需建立空间索引结构提高数据检索效率。k-D树是点云常用的数据组织结构，可以快速检索采样点的邻域点。对于非边界点，其R邻域内点集分布较为均匀，邻域内点集的重心坐标与采样点的距离较小；对于边界点，其R邻域内点集集中分布在采样点的一侧，邻域内点集的重心坐标与采样点的距离较大，如图2所示。因此,本文中从采样点R邻域内点集重心坐标与采样点位置的距离D出发，利用边界点与非边界点中D的差异性粗提取边界点集。

Fig.2 Location map of barycenter points in the neighborhood of non-boundary points and boundary points R

粗提取的具体流程如下所述。

(1)构建k-D树。采用快速分类的分割方法建立k-D树，把指定维度的值放在根上，在这个维度上较小数值放在左子树、较大的放在右子树，然后分别在左右子树上重复该过程，直至最后一个树仅有一个点。

(2)计算R邻域内点集重心。通过k-D树检索采样点R邻域内点，利用下式计算该邻域内点集重心坐标：

(1)

(3)计算重心点与采样点距离值D。设定距离阈值δ，若D≥δ，则采样点被标记为边界点，同时保存该点的索引。

(4)遍历所有点。重复步骤(2)和步骤(3)，对所有点进行判定，完成边界点的粗提取，得到粗提取边界点集的索引。

图3为边界点粗提取结果图。图中的点云数据包括点云内部边界点和点云外部边界点，粗提取的边界点集中包含边界点、少量毛刺噪声点、边界边缘内部点。粗提取方法可以有效地剔除大部分非边界点，可以为后续精提取边界点提高效率。

Fig.3 Crude extraction of boundary points

1.2 边界点精提取

粗提取的边界点中包含了边界点、部分边界边缘内部点和少量毛刺噪声点，精提取的目的就是将边界点从粗提取的点集中分离处理来。目前精确提取边界点的方法有很多，参考文献中提出的基于邻近点最大夹角的方法能够有效的提取边界点。将采样点及其邻域内点集投影至最小二乘拟合的微切平面上，寻找采样点与邻域内点连线构成的最大夹角εmax，若εmax大于设定的角度阈值，则该点为边界点。

(2)

(3)

在微切平面内，通过(4)式得到邻域投影点q′与采样点p(x,y,z)的单位方向向量。这样就将点p邻域内点分布在以点p为圆心的单位圆上，如图4a所示。选择单位圆内任意方向向量pqi′为起始方向，计算pqi′与微切平面法向量n的叉积v，分别计算其它方向向量与pqi′和v的夹角αi，βi，如图4b所示。

Fig.4 The included angle on the projection plane of neighborhood point

若βi≥90°，则αi=360°-αi。将αi从小到大排序，通过(5)式计算相邻向量间的夹角，最大夹角阈值一般设置为90°：

(4)

(5)

图5为精提取结果图。可以看出，基于邻近点最大夹角的方法剔除了少量毛刺噪声点和边界边缘内部点，能够精确提取边界点。对粗提取过程中筛选出的点集进行精确提取，避免对每一个原始点进行微切平面拟合及精确判定，故能够极大地提高边界点的提取效率。

Fig.5 Essence extraction of boundary points

2 实验与分析

选取扫描的桌子点云数据验证本文中算法的可行性，再采用瑞格VZ-1000扫描的白塔数据对本文中算法的提取精度进行分析。实验在配置为i5-6200U CPU 2.30GHz、内存8GB、Windows 10 64位操作系统的PC机运行，在MATLAB R2016a软件中编写脚本实现本文中的算法、参考文献[8]中的算法和参考文献[16]中的算法。

2.1 可行性验证分析

原始点云平均间距为0.001m，共454943个点，首先对原始点云精简，采用网格法下采样[19-20]，网格间距为0.01m，精简后点云个数为20988个，如图6a所示。参考文献[8]中提取的边界结果如图6b所示。本文中算法粗提取中R取3倍网格间距，即R=0.3m，距离D取网格间距，即点云平均间距0.01m，粗提结果如图6c所示，粗提取过程中最大夹角阈值设置为90°，最终提取的边界点结果如图6d所示。参考文献[16]中同样采用先粗提取后精提取的思路，其粗提取的结果如图6e所示，精提取结果如图6f所示。由实验结果可以看出，本文中算法相较于参考文献[16]中的能更为完整地提取边界点云，验证了本文中算法的可行性。

Fig.6 Table boundary points extract results

表1中对3种不同边界提取方法的提取结果进行了比较。参考文献[8]中可视为不进行粗提取，直接对原始数据进行精提取，总耗时最长，但能得到精确的边界点集。参考文献[16]中粗提取的点云个数比本文中的方法多，但是精提取后点云个数比本文中方法少，说明本文中粗提取的点集包含更多的边界点，本文中粗提取的精度更高，因此后续精提取的时间能缩短35.54%。本文中提出的粗提取方法运行时间相较于参考文献[16]中的缩短了21.21%，总耗时相较于参考文献[8]中的缩短了28.21%，较参考文献[16]中的缩短了22.89%。

Table 1 Comparison of operation efficiency of different boundary extraction methods

2.2 精度分析

对白塔点云数据先进行网格法下采样，网格大小为0.01m，共55049个点，如图7a所示。同样粗提取中R取0.03m，距离D取0.01m，最大夹角阈值取90°，本文中边界点的提取结果如图7b所示，参考文献[8]中提取的白塔边界点结果如图7c所示，参考文献[16]中提取的边界点结果如图7d所示。

Fig.7 Extraction results of white tower boundary points

表2中对3种边界提取方法进行了比较分析。参考文献[8]中提出的方法能够有效精确地提取边界点，且本文中和参考文献[16]中精提取方法都与参考文献[8]中边界提取方法一致，故可以假设参考文献[8]中提取的边界点是精确且完整的，通过将本文中和参考文献[16]中的提取结果与参考文献[8]中的提取结果进行比较，分析本文中算法的提取精度。对于本文中和参考文献[16]中提取的结果，通过与参考文献[8]中的提取结果进行同名点检索，若本文中或参考文献[16]中提取的点能在参考文献[8]中提取的点集中能检索到同名点，则该点被标记为正确提取点，否则为错误提取点。分析表2中正确率和运行时间可知，本文中算法相对与参考文献[16]不仅耗时较少，而且精度更高，这是由于在粗提取过程中本文中采用了更简单、更有效的边界点判定规则。

Table 2 Comparison of extraction precision between different boundary extraction methods

3 结 论

本文中提出了一种快速精确提取边界点的方法，针对传统的基于邻近点最大夹角提取边界点方法进行改进，首先依据R邻域点集重心坐标与采样点的距离粗提取边界点，将大量的非边界点剔除，提高提取效率，再依据邻近点最大夹角精确提取边界点。实验表明本文中提出的方法能够快速精确的提取边界点，层次化快速边界提取方法中尽管缩短了提取时间，但是降低了提取精度，通过白塔数据实验表明，相对于传统的依据邻近点最大夹角提取边界点方法，本文中的方法在损失5.23%的精度下能缩短22.11%的运行时间，相较于其它层次化提取方法，本文中的提取精度在提高7.17%的同时能缩短10.99%的运行时间。但本文中的方法易受到点云密度的影响，相关阈值的选取都与点云密度有关，对密度分布不均匀的数据提取的效果不佳，下一步研究方向为提高算法的自适应程度。