多核CPU的海量点云并行kNN算法

被引：9

作者：

王宗跃 ^{[1
,2
]}

马洪超 ^{[2
]}

徐宏根 ^{[3
]}

张建伟 ^{[4
]}

彭检贵 ^{[2
]}

机构：

[1] 集美大学计算机工程学院

[2] 武汉大学遥感信息工程学院

[3] 中国国土资源航空物探遥感中心

[4] 武汉大学软件工程国家重点实验室

来源：

测绘科学技术学报 | 2010年 / 27卷 / 01期

关键词：

机载激光雷达; 海量点云; k最近邻; 多核CPU; 并行算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

提出基于多核CPU的海量点云k最近邻(kNN)快速搜索算法。该算法先将点云数据按格网方式进行组织存储于外存;在搜索kNN点时,从搜索点所在的块向外扩张搜索;在多核CPU环境下采用多线程模式进行数据的内外存调度和kNN点搜索。当内存达到设定上限时,采用距离搜索点最远策略释放内存,降低内外存数据交换的频率。将该方法应用于基于kNN的滤波和格网化方法中,处理速度显著提高。

引用

页码：46 / 49

页数：4

共 5 条

[1] 复杂城市环境的机载Lidar点云滤波
蒋晶珏
张祖勋
明英
[J]. 武汉大学学报(信息科学版), 2007, (05) : 402 - 405
[2] 基于图形处理器(GPU)的通用计算
吴恩华
柳有权
[J]. 计算机辅助设计与图形学学报, 2004, (05) : 601 - 612
[3] Processing and interactive editing of huge point clouds from 3D scanners
Wand, Michael
Berner, Alexander
Bokeloh, Martin
Jenke, Philipp
Fleck, Arno
Hoffmann, Mark
Maier, Benjamin
Staneker, Dirk
Schilling, Andreas
Seidel, Hans-Peter
[J]. COMPUTERS & GRAPHICS-UK, 2008, 32 (02): : 204 - 220
[4] An optimal algorithm for approximate nearest neighbor searching fixed dimensions[J] . Sunil Arya,David M. Mount,Nathan S. Netanyahu,Ruth Silverman,Angela Y. Wu.Journal of the ACM （JACM） . 1998 (6)
[5] AnO（n logn） algorithm for the all-nearest-neighbors Problem[J] . Pravin M. Vaidya.Discrete ＆ Computational Geometry . 1989 (1)

← 1 →