摘要
海量点云的邻域搜索是点云数据处理的关键技术,是对点云进行进一步处理的基础.针对海量点云数据邻域搜索效率较低的问题,提出了一种基于二进制编码八叉树的快速搜索算法.首先构建八叉树,利用一种二进制编码方式对八叉树的各个节点进行编码,即对空间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.
作者
姜晓通
戴宁
程筱胜
张长东
郭保苏
Jiang Xiaotong;Dai Ning;Cheng Xiaosheng;Zhang Changdong;Guo Baosu(College of Mechanical Engineering,Changshu Institute of Technology,Changshu 215500;College of Mechanical and Electrical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016;School of Mechanical Engineering,Nanjing University of Science and Technology,Nanjing 210094;College of Mechanical Engineering,Yanshan University,Qinhuangdao 066044)
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2018年第5期824-832,共9页
Journal of Computer-Aided Design & Computer Graphics
基金
江苏省自然科学基金(KB20161487)
国家青年自然科学基金(51605422)
新引进教师科研启动基金项目(KYZ2017093Z)
关键词
海量点云
二进制编码
八叉树
邻域查询
large-scale scattered point clouds
binary-encoding
octree
neighborhood search