一种大规模点云k邻域快速搜索算法  

A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud

作　　者：杨军[1] 林岩龙[1] 张瑞峰[1] 王小鹏[1] 

机构地区：[1]兰州交通大学电子与信息工程学院,甘肃兰州730070

出　　处：《武汉大学学报（信息科学版）》2016年第5期656-664,共9页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金(61462059);中国博士后科学基金面上项目(2013M542396);人社部留学人员科技活动项目择优资助(2013277);甘肃省财政厅基本科研业务费(214142)~~

摘　　要：针对大规模点云数据k邻域搜索效率低和分块不均匀的问题,提出了一种新的k邻域快速搜索算法。首先,根据设定的子空间内点云数目上限对点云空间在坐标轴方向自适应分块;然后,以待搜索点到所对应子空间6个面的最小距离作为边长生成初始自身小立方体,根据小立方体内采样点数目的控制阈值动态控制小立方体大小,缩小k邻域的搜索范围;最后,以搜索不成功的点到子空间边界的最小距离所对应的面的外法向量方向作为此面的扩展方向,并以所有搜索不成功点到该面距离的最大值作为该方向的扩展步长对子空间定量扩充。实验结果表明,该算法不仅具有较强的稳定性,而且自动化程度较高,能更快地完成k邻域搜索。To solve the problem of low efficiency and non-uniform blocking when searching nearest neighbors in large-scale scattered point clouds, a fast algorithm for finding k-nearest neighbors is presented. Firstly, a point cloud is blocked adaptively in the coordinate directions according to the point number threshold of a sub-block. Secondly, the initial small cube is created using the minimum distance from the point to the sub-block boundary, and the size of the small cube is changed dynamically based on a threshold; that is, the amount of points in a small cube to narrow down the search extent of k-neighbors. Thirdly, the expansion direction is determined by the outer normal vector of the corresponding side, which is the side nearest to a unsuccessful searching point. The maximal distance from the unsuccessful searching point to the side is taken as a step to expand the sub-block quantita- tively. Experimental results show that the proposed method is not only stable, but also is more auto- matic with better performance.

关 键 词：动态网格 k最近邻域 曲面重建 点云 搜索步长 

分 类 号：P208[天文地球—地图制图学与地理信息工程] TP391.4[天文地球—测绘科学与技术]