GPU加速的3D配准最近邻搜索

### GPU加速的3D配准最近邻搜索 #### 1. 引言 最近邻搜索（NNS）算法旨在优化在两个数据集中根据距离度量寻找最近点的过程，它是计算机视觉中常用的几何算法，在3D视觉领域，NNS常用于3D点云配准。然而，现代3D传感器获取的大型数据集配准计算量巨大。 近年来，图形处理单元（GPU）因其紧凑设计下的强大计算能力备受关注。其可编程性的提高使通用计算成为可能，为传统多计算机或多处理器系统提供了强大的大规模并行处理替代方案，且商用显卡每浮点运算成本更低。 传统NNS具有递归性质，难以在GPU上实现。我们利用Arya的优先搜索算法，使NNS适应单指令多数据（SIMD）模型，从而可通过GPU加速。提出的GPU - NNS算法基于NVIDIA的CUDA并行计算架构实现，还采用了单元素优先队列和基于数组的k - d树等方法加速NNS过程，并将其应用于3D配准算法GPU - ICP。分析表明，标准顺序CPU的ICP算法中，NNS是最耗时的部分，而在GPU - ICP实现中，不仅NNS阶段，其他阶段也由GPU加速，实验显示其比基于k - d树的顺序CPU ICP算法快88倍。 #### 2. 相关工作 在GPU上，NNS通常采用暴力方法实现，这些方法本质上高度并行，易于在GPU上实现，已有多种实现方式： - Purcell等人用单元格表示光子位置，通过计算与搜索半径相交的单元格中光子与查询点的距离来定位k个最近邻以估计辐射度，他们强调k - d树和优先队列方法高效但难在GPU上实现。 - Bustos等人将索引和距离信息作为四元数存储在纹理缓冲区的RGBA通道中，使用三个片段程序计算曼哈顿距离并通过归约最小化。 - Rozen等人采用桶排序原语搜索最近邻。 - Van Kooten等人引入基于投影的最近邻搜索方法解决粒子排斥问题，利用GPU的硬件加速功能，如投影和纹理缓冲区的2D布局进行网格计算。 - Garcia等人使用CUDA实现暴力NNS方法，在高维情况下比CPU的k - d树方法快数倍。 除暴力实现外，全局光照领域也有基于GPU的具有高级搜索结构的NNS算法，但这些算法大多不能作为通用的基于点的NNS算法。在最近的GPU加速NNS实现中，多数NNS内核基于暴力方法，实现简单但效率低，且大多需要归约内核来寻找最小距离，归约内核因非并行性质速度慢。基于树的NNS算法在全局光照中表现出色，但因设计目的难以用于非图形用途。 #### 3. 大规模并行最近邻搜索 NNS问题可表述为：在度量空间M中，给定一个点集S和一个查询点q，优化寻找点集S中与q欧氏距离最小的点p的过程。我们的大规模并行最近邻搜索算法GPU - NNS基于CUDA架构实现，采用空间划分结构k - d树改进搜索过程，其中“主机”指CPU，“设备”指GPU。 ##### 3.1 GPU - NNS GPU - NNS过程包含三个步骤： - **基于数组的k - d树**：搜索前，在主机端分配一块页锁定内存。通过始终在最长轴的中位数上分割空间，为点集S构建左平衡k - d树。左平衡的k - d树可序列化为扁平数组并存储在页锁定内存中。由于设备内存不能动态分配，在NNS阶段前将基于数组的k - d树下载到设备。为满足CUDA全局内存的合并要求，使用数组结构（SoA）。 - **优先搜索方法**：由于CUDA不支持递归，传统k - d树搜索方法无法使用，优先搜索方法为在GPU上实现NNS提供了途径。GPU中的寄存器维护优先队列，优先搜索算法迭代执行以下三步： 1. 从队列中提取与查询点距离最小的元素。 2. 扩展提取的节点，将较高节点插入队列，然后扩展较低节点，重复此步骤直到叶节点。 3. 更新当前最近邻。 完整的GPU - NNS算法如下： ```plaintext Algorithm 1. GPU - NNS Algorithm Require: download the k - d tree, model point cloud and scene point cloud to GPU global memory. 1: assign n threads, where n = number of query points. ```