三维激光扫描点云边界提取研究
杜秋;郭广礼
【摘 要】In the process of digital mine construction,3D laser scanning is used to obtain point cloud data of surface or buildings quickly. The point cloud boundary is not only an important geometric feature to represent surface,but also serves as a model to solve the domain of the surface,which plays an important role in reconstructing the quality and precision of the surface model. It is necessary to extract the boundary points from the mass data in order to model the laser point cloud data. In this pa-per,a method is proposed to automatically extract the boundary features of the point cloud by discussing the geometric distribu-tion of the local point set projection onto the micro-tangent plane fitted by them. This algorithm could be applied to various point cloud data in complicated surface with its rapid processing speed and accurate extraction result.%在数字矿山建设过程中,三维激光扫描仪可快速获得地表或建筑物的点云数据.点云边界不仅作为曲面表达的重要几何特征,而且作为模型求解曲面的定义域,对重建曲面模型的品质和精度起着重要作用.利用激光点云数据
进行建模首先需从海量数据当中提取边界区域的采样点.本文提出了一种通过局部型面参考点集拟合微切平面,讨论参考点在对应微切平面上投影点的几何分布来自动提取边界特征的算法.该算法运行速度快,提取结果准确,可适用于各种复杂型面的点云数据. 【期刊名称】《金属矿山》
【年(卷),期】2017(000)010
【总页数】5页(P67-71)
【关键词】数字矿山;三维激光扫描;点云边界;特征提取;K近邻
【作 者】杜秋;郭广礼
【作者单位】中国矿业大学环境与测绘学院,江苏 徐州221116;中国矿业大学环境与测绘学院,江苏 徐州221116
【正文语种】中 文
【中图分类】TD676
与传统测量方式如全站仪和GPS相比，三维激光扫描技术能够获取目标地物表面的高密度点云数据，具有测量效率快、自动化程度高等优点，被誉为“继GPS技术以来测绘领域的又一次革命”，是文物保护[1]、数字城市[2-3]、变形监测[4]等领域的研究热点。但目前大多数扫描仪获取的数据通常只包含采样点的几何信息(三维坐标值)与物理信息(彩信息和激光强度值)，无法直接得到采样点的拓扑关系。在利用散乱点云进行三维建模的过程中，基于特征点拟合的特征线是进行网格构造和数据分块的主要依据[5-6]。
到目前为止已有很多研究人员提出了不同的边界点提取算法。第一类是基于空间栅格划分的边界点提取算法。
李江雄[7]首先提出了一种简单易实现的“网孔法”进行散乱点云边界提取。其算法的主要思想是将空间单值曲面的散乱点投影至二维平面，将投影后的散乱点经栅格划分为网孔，考察某网孔临近网孔的状态以判断是否为边界网孔。
慈瑞梅等[8]在李江雄研究的基础上提出了经纬线扫描式判断方法。其算法的主要思想是先令扫描经线x=Xmin，在给定的微小变动范围(Xmin,Xmin+dx)中，寻y的最大和最小值对应的点，并把它们存储起来，然后增加dx，在(Xmin+dx,Xmin+2dx)中查边界点并记录，
依此类推，直至搜寻完整个区间。再令扫描纬线y=Ymin，取步长为dy，继续如x轴方向的操作。
柯映林等[9]则直接进行空间网格划分，直接考察三维网孔临近网孔的状态，首先得到种子边界网格，然后利用种子边界网孔的拓扑关系，使种子边界网孔沿特定拓扑方向进行带约束的生长来获得所有边界网孔。
总体说来，这一类算法最为简单，易于编程实现，但是由于网孔包含的是1个区域的点集，仅仅判断网孔会将不在边界上的点误判为边界点，导致获得的边界粗糙，给后期建模造成较大误差；另外，空间三维栅格划分法只适用于能到合适投影面且分布较为均匀的点云,算法适用性较低。
另一类是基于建立三角网格曲面的边界点提取算法。张献颖等[10]首先建立空间三角网格曲面，然后判断1个点的邻接点能否通过三角网格的边组成闭合曲线来获取边界点，具体思想如图1所示：由于A、B、C、J、G、H能够围成封闭多边形，所以I是内部点；点A、B、C、D、E、F、G、H的邻接点不能围成封闭多边形，所以是边界点。
这类算法的数据适应性较强，提取结果在理论上更接近于边界点的定义，但由于需提前建立三角网格模型，程序运行时需占据大量的系统资源，导致提取效率较低。
针对这2种方法存在的问题，本研究提出了基于考察局部型面参考点集分布状态的边界点提取算法。相比于前2种方法，一方面提取处理的对象是点，得到的结果更为清晰，精度更高；另一方面，避免了各种网型的建立，提升了数据处理的效率，并易于编程实现。
1.1 采样点k近邻点查询
空间三维散乱点云中，计算某采样点pi的k近邻点是从点集p={pi|i=1,2,…,n}中到与采样点欧氏距离最近的k个点。由于边界点判断算法当中需要查各点的k近邻点，并且运算次数庞大，因此，k近邻搜索算法的执行速度直接代表了整个点云边界提取的速度。
如表1所示，Neighbourhood函数即为k近邻点查询算法的具体实现，其运行占据了总程序的大部分时间。(注意：JudgePoint函数包含了Neighbourhood函数，所以其运行时常在表格中显示得比Neighbourhood函数长)
已经有许多学者对快速提取k近邻点提出了一些实际的方法。熊邦书等[11]利用空间分块策
略进行三维空间k近邻搜索，提出了包含点的总数及最近临点数k来考虑确定子立体包围盒尺寸的方法，但是这种算法一旦在目前子立方体包围盒中不能顺利到当前点的k近邻点时，就要求将搜索范围扩大一圈甚至几圈。
针对上述问题，张涛等[12]提出了一种改进的k近邻算法。这种算法通过控制搜索方向，优先向当前点k近邻点最可能出现的子立方体包围盒中进行扩展，进一步缩小了搜索的范围，从根本上提高了搜索速度。
马娟等[13]在此基础上继续提出一种以建立离散数据空间索引为空间划分目标的k近邻搜索新算法，在点云分配和遍历时间效率、随机点搜索时间稳定性及对不同k值的适应性等方面得到了提高。
1.2 特征值法拟合微切平面
从散乱点云中拟合平面的方法有很多种，其中最常见的有最小二乘法[14]和特征值法，另外还有稳健整体最小二乘法[15]。最小二乘法一般将平面方程
改写为
此方法将z视为观测值，平差时只考虑z方向的误差，但是这样与实际测量中3个坐标方向都存在误差的情况是不符合的，具有奇异点。而与最小二乘法不同，特征值法在满足a2+b2+c2=1的条件下，根据平面方程ax+by+cz=d经过一系列计算得出所拟合平面的参数。它综合考虑了3个方向的误差，而且没有奇异点，是一种十分实用的平面拟合方法。
1.3 点至微切平面的投影
通过上一节的分析，已得到采样点与其k近邻点构成的微切平面的相关参数。接下来需要将采样点与其k近邻点投影到它们形成的微切平面上。
根据空间几何的知识，过某一点(xi,yi,zi)且垂直于投影面的直线L与投影面P相交所得的交点即为点(xi,yi,zi)至投影面P的投影点。
为了符合平面表达式的规范性和唯一性，定义三维空间当中平面的标准表达式为
其中，n(a,b,c)为平面的单位法向量，且满足a2+b2+c2=1；d的大小为坐标系原点到平面的距离。确定平面的关键就是确定a、b、c、d这4个参数，而唯一确定a、b、c、d还需要规定法向量的正方向，法向量的正方向可以任意选取。 对于经过目标点的直线，其方向向量即为投影面的法线向量。为了方便运算，本研究选择点法式方程作为求投影点直线L的表达式，即：
式中，m是为了方便运算而取的符号。
由式(2)可得
将式(3)代入平面方程解得
所以各点至投影面的投影点的坐标即为
1.4 解算向量夹角
本研究边界点提取算法中判断某采样点是否为边界点的核心思想为设置1个角度阈值ε，如果采样点的投影与其k邻域点分别的连线所形成的k个向量之间的夹角的最大值δmax大于角度阈值ε，就判定这个采样点为边界点。
因此，问题就涉及到求出上述当中的k个向量之间的夹角。经过分析可用以下步骤进行求解：
(1)设点集p={(xi,yi,zi)|i=0,1,…,k}为某采样点与其k近邻点，与此对应的投影点集注：点集p和点集p′中i=0时对应的点均为采样点)。
(2)以当前点的投影点为起始点为终点，定义向量在这些向量当中任意选取1个向量作为基准向量，求其与点集p形成的微切平面的法线向量n的叉积v，也即是下面叙述当中的判断向量。
(3)分别计算基准向量和判断向量v与采样点的投影与其余k-1个点的投影所连接形成的向量之间的夹角αi、βi，如果βi≥90°，那么我们令αi=360°-αi。
(4)将第(3)步所得的αi从小到大进行排序，则这k个向量之间的夹角可以表示为
获得各相邻向量之间的夹角，并按角值大小进行，当相邻向量之间的夹角的最大值δmax大于角度阈值ε时，就可以判断采样点为边界点。
2.1 实验数据获取
本研究使用Trimble GX200全站式地面三维激光扫描仪(图2)获取边界提取研究所需要的点
云数据，此仪器的相关指标如表2所示。为了能够进行点云边界提取研究，首先须对采集的数据进行数据预处理工作。预处理结果的质量优劣将直接影响到边界提取的准确性以及最终生成模型的质量。
和传统测量作业相同，三维激光扫描仪进行测量也遵照“先控制后碎步”的原则。首先用全站仪进行了平面控制测量，用水准仪进行了水准控制测量。经过这2个步骤获得控制点。将三维激光扫描仪直接安置到控制点上便可以进行扫描作业。
为了便于后期各站扫描数据的拼接工作，可采用靶标，或者后视棱镜直接定向2种方式进行处理。本研究选择的是后视棱镜，该方法直接有效，扫完数据即可得到拼接后的结果。
