基于八叉树编码的点云邻域搜索算法

丁彩红，张 耀

(东华大学 机械工程学院，上海 201620)

0 引 言

近年来，激光扫描技术发展迅速，但激光点测量系统采集到的点通常呈散乱状态。在实际应用中，如果此时直接用点云数据对模型表面进行重建，会大量占用计算机内存，给后续工作带来很大困难。一般情况下，要先对离散点云建立拓扑结构，使相邻K个点之间产生联系，这样，后续工作的效率将会大大提高。通常，要求得点云中某个点K个邻域点集的方法是，先求出该点与点云中其余各点的欧氏距离，然后对所得距离进行升序排列，得到K个与采样点距离最近的点。随着计算机运算速度的提高，该方法在点云数量较少时能取得较满意的效果，当点云数量巨大时，频繁的距离计算，耗时惊人。查阅2000年后与点云邻域搜索相关文献发现，算法主要有3类：Voronoi图法、树层次法和空间分块法。通过Voronoi图建立点云K邻域关系，首先要构建点集的Voronoi图，此时，需进行较多的浮点运算，运算量较大[1]。M Muja等对K-D Tree进行了改进，通过确定最优邻域算法参数和最佳搜索路径进行K邻域搜索，但对于不同的数据集，算法中要重新设定参数和路径，此方法通用性欠佳[2]。文献[3]基于“凡在同一区域的采样点，它们邻域的搜索范围有着一定的重叠”的思想，利用多个相邻的子空间逐步缩小搜索范围，方法较新颖，但算法的稳定性不太理想。另外，研究者们提出了对海量数据进行空间划分的方法，此类方法在求某点K近邻时，目的在于缩小搜索范围，仅在其所设定的网格中搜索，但如果该点不在网格的中心位置，可能导致搜索结果不完整[4-6]。……