基于kd_tree算法和法向量估计的点云数据精简方法

2019-02-13王丽

宿州学院学报 2019年12期

王丽

宿州学院环境与测绘工程学院，安徽宿州，234000

地面三维激光扫描技术是近年发展起来的一种新的获取空间三维信息的技术方法，其通过非接触式扫描快速获取物体表面信息，扫描的数据以离散点云形式存储。数据具有高精度的特点，但同时包含物体信息的海量点云数据为后续数据处理带来困难，几十万甚至上百万的点云数据不仅影响数据处理的进程，而且还影响结果的精度。为此，近几年国内外学者都在保证点云特征和精度的前提下，致力于研究点云数据精简的算法。如HAMANN等提出对于不同平面实体曲线重建点云简化方法[1]；WEIR等提出包围盒算法，实现点云简化[2]；邢正全等提出正方体栅格划分实现K近邻搜索，利用法向量特征实现点云简化[3]；马振国提出利用kd_tree索引实现点云数据结构划分，并且结合点云曲率特征实现点云简化[4]，该方法需手动介入，自动化程度不够。本文考虑三维数据结构特点，提出一种基于kd_tree索引算法的法向量估计点云数据精简方法。该方法利用kd_tree算法构建空间数据树结构，搜索每个点K邻域点，搜索速度快，可提高数据简化速度，结合最小二乘原理拟合每个邻域点构成的平面，估计每个点的法向量，并进行法向量方向调整，计算每个点及其邻域点法向量的夹角，设定夹角阈值，如果大于阈值，则删除，从而实现点云数据精简。