袁小翠 陈华伟

1(南昌工程学院江西精密驱动与控制重点实验室 江西 南昌 330099)2(贵州师范大学机械与电气工程学院 贵州 贵阳 550025)

0 引 言

三维扫描仪可以快速获取物体表面的三维信息，对三维点云数据处理可以实现曲面重建和产品再制造等应用。然而，三维扫描仪获取的数据一般只有三维坐标信息，无任何拓扑结构，点云数据处理时需要以点云的邻域为基础。点云邻域的准确性直接影响点云处理结果，如法向量估计、去噪和曲面重建等。

点云数据处理一般基于点云的k邻域。对任意点pi求其k邻域最直接的方法是计算该点与其他数据点的欧氏距离，取距离最近的k个点。然而，这种方法计算量大、效率低。为了提高计算效率，提出了许多快速邻域搜索算法。这些方法可以大致分为四类：多步递归法，并行法，栅格法(空间划分法)和数据重组算法[1]，栅格法和数据重组法是比较常用的点云邻域搜索方法。

栅格法[2-5]计算邻域的思路是：对点云模型构建最大包围盒，对包围盒进行空间划分得到八个子立方体，再对这八个立方体进行递归划分直到子立方体不包含点云或者立方体的边长小于给定阈值。对任意点在其周围26个子立方体中搜索得到k邻域。文献[2-3]利用栅格法搜索邻域对曲面进行重建和提取点云模型空洞。文献[6]利用子块扩张方法避免搜索相邻子空间，但是该方法只适合规则点云。文献[4]解决了栅格法对大规模点云数据k邻域搜索效率低和分块不均匀的问题。……