二进制编码八叉树的海量点云邻域快速搜索算法

Fast Neighborhood Search of Large-Scale Scattered Point Cloud Based on the Binary-Encoding Octree

海量点云的邻域搜索是点云数据处理的关键技术,是对点云进行进一步处理的基础.针对海量点云数据邻域搜索效率较低的问题,提出了一种基于二进制编码八叉树的快速搜索算法.首先构建八叉树,利用一种二进制编码方式对八叉树的各个节点进行编码,即对空间3个维度分别进行编码;其次对邻域点进行查找过程,根据搜索半径直接确定需要搜索的高度;最后在确定的节点高度下,根据编码的特点直接计算所需要查询的邻域节点.实验结果表明,该算法准确性高、速度快,能够实现海量点云数据的快速邻域搜索.

The neighborhood search is a key technique of large-scale scattered point clouds data processing.It is a basic algorithm for further processing of point clouds.To solve the problem of low efficiency of the neighborhood search for large-scale scattered point clouds,this paper introduces and realizes a fast neighbourhood searching algorithm based on the binary-encoding octree.First,when constructing the octree,each node of the octree is binary encoded with certain rules.In the process,the three dimensions of the space are encoded respectively.Second,when searching the neighbourhood points,the searching level can be decided by the search radius.Last,when implementing neighborhood search,the required node and its neighbour nodes can be located quickly under the given level.The experiments show that our method is high accuracy and speed,and can realize fast neighborhood search of large-scale scattered point clouds.