摘要
提出基于多核CPU的海量点云k最近邻(kNN)快速搜索算法。该算法先将点云数据按格网方式进行组织存储于外存;在搜索kNN点时,从搜索点所在的块向外扩张搜索;在多核CPU环境下采用多线程模式进行数据的内外存调度和kNN点搜索。当内存达到设定上限时,采用距离搜索点最远策略释放内存,降低内外存数据交换的频率。将该方法应用于基于kNN的滤波和格网化方法中,处理速度显著提高。
A fast k-nearest neighbors （kNN） algorithm has been proposed for large scale point clouds data with multi-core CPU. The point clouds data is arranged by grid and stored in external memory in the first; the searching starts form its own inner block area to the outer block when finding for the k nearest points for one point; internal-external memory scheduling and k-nearest neighbors searching are performed by multi-core CPU with multi thread. The memory of the farthest blocks from current point will be released when reaching the limitation of the memory. In this way, the exchange ratio can be reduced. The processing speed is improved significantly when applying this algorithm in kNN based filtering and gridding methods.
出处
《测绘科学技术学报》
北大核心
2010年第1期46-49,共4页
Journal of Geomatics Science and Technology
基金
国家863计划资助项目(2006AA12Z101)
关键词
机载激光雷达
海量点云
k最近邻
多核CPU
并行算法
LiDAR
large scale point clouds
k-nearest neighbors
multi-core CPU
parallel algorithm
