基于FPGA的kNN搜索加速器用于点云配准
摘要
点云配准在多种领域中起着关键作用，包括3D重建和姿态估计。点云配准的主流技术是迭代最近点（ICP）。然而，ICP过程中的一个重要组成部分——k最近邻(kNN)搜索，往往因为其耗时巨大而无法满足实时性要求。因此，已付出大量努力来加速ICP框架内的kNN搜索。本文提出一种基于FPGA的kNN搜索加速器，利用改进的LSH方法加速点云访问和搜索。实验结果表明，与CPU和GPU实现的kNN过程分别相比，其速度提升了120倍和15倍。值得注意的是，kNN搜索仅耗时0.64毫秒，优于以往工作。
作者
Chengliang Wang 重庆大学
Zhetong Huang 重庆大学
Ao Ren 重庆大学
Xun Zhang 重庆大学
发表信息
期刊: 2024 IEEE International Symposium on Circuits and Systems (ISCAS) 年份: 2024 页码: 1-5 DOI: 10.1109/ISCAS58744.2024.10558303 文章编号: 10558303 ISSN: Electronic ISSN: 2158-1525, Print on Demand(PoD) ISSN: 0271-4302
指标
论文引用: 1 总下载量: 267
关键词
IEEE关键词: 点云压缩, 三维显示, 数字信号处理器, 姿态估计, 随机存取存储器, 图形处理单元, 实时系统
索引词条: 点云, 点云配准, K最近邻, 三维重建, 姿态估计, 邻域搜索, 迭代最近点, 局部敏感哈希, 功耗, 资源消耗, 变换矩阵, 密度数据, 哈希函数, 子树, 宽度增加, 数字信号处理, 随机存取存储器, 点云数据, 硬件资源, KITTI数据集, 位宽, 分区过程, 查询点
作者关键词: FPGA, 加速器, kNN搜索, 点云
未定义
第一节. 介绍
点云数据是一种表示，包含了在三维空间中对象表面采样点的集合，封装了对象的空间信息。激光雷达技术的最新进展提升了精度、性能并降低了成本，促进了激光雷达在移动设备中的集成。然而，这一发展也带来了新的挑战，主要是对海量点云数据实时处理的需求。
点云配准是点云处理的关键方面，在三维重建 1 2 3、三维定位、姿态估计 4 5 6 和其他相关领域中发挥着核心作用。该过程涉及确定两个点云之间的变换矩阵以实现更好的对齐，需要多次迭代以获得最佳变换矩阵。迭代最近点（ICP）7 是点云配准中最广泛使用的方法，k-最近邻（kNN）搜索是关键组成部分。基于 ICP 的先前研究 8 已证明 kNN 搜索占 ICP 过程耗时的 75% 以上。我们使用 C++ 和 Python 对我们的方案进行了编程和测试，并通过多次测试验证了这一发现。
第二节：相关工作
基于 k-d 树的常用 kNN 搜索方法已被证明是有效的。在该方法中，首先需要近似 k-d 树 9 来构建 k-d 树 10。为实现这一点，首先对点的一个子集进行排序，并将其均等地划分到左子树和右子树之间。排序和划分过程会重复进行，直到划分后对应叶节点的桶中剩余的点数小于给定大小为止。每个点的 kNN 搜索所消耗的时间与桶的大小成正比，从而实现了显著加速。然而，在 FPGA 11 上实现 k-d 树的构建需要大量时间和硬件资源。这是因为 k-d 树构建过程需要对点进行排序，以确保它们能均匀地划分到二叉树的左右子树中。相反，基于层次图的法 12 13 是另一种点云划分技术。通过使用层次图，搜索可以在线性时间内完成。然而，该方法需要在芯片上存储大量层次图。事实上，对于 32k 规模的点云，需要约 23 Mb 的存储空间，这导致在 FPGA 上实现时资源消耗很高。 /par 本文的重要贡献如下：
高效 kNN 搜索方法：本文提出了一种改进的 kNN 搜索方法，使用增强的局部敏感哈希 (LSH) 技术对点云数据进行划分。划分过程旨在最小化资源消耗，同时提高搜索数组内的并行性和可扩展性。该方法实现了更高效、更有效的 kNN 搜索操作。
高速且资源高效的 kNN 搜索加速器：我们提出了一种专为 3D 点云数据设计的基于 FPGA 的 kNN 搜索加速器。加速器的架构经过优化，以实现高速性能，同时降低硬件资源需求和功耗。该加速器为以资源高效的方式加速 kNN 搜索提供了有前景的解决方案。
高效 RAM 分配方法：为提高访问速度，点云数据被存储在片上 BRAM 中。我们还提出了一种将分配的 RAM 分成多个桶块的方法，并根据每个哈希桶中存储的点云数量动态分配这些块。这种方法优化了每个哈希桶的存储空间分配，从而提升 RAM 的利用率并减少资源浪费。
图 1. 12 位值映射函数：将来自 x、y、z 轴的 12 个典型位连接为键值
为了评估我们搜索方法的准确性，我们使用 KITTI 数据集 14 对其性能进行评估。我们的加速器在 Xilinx ZCU102 平台上实现，kNN 搜索的延迟测得为 0.64 毫秒，适用于 30k 规模的点云。与 CPU（120×）和 GPU（15×）执行的 kNN 过程相比，这代表了显著的加速。此外，我们对加速器消耗的硬件资源进行了全面评估，并将其与现有加速器进行比较。我们的加速器在速度和效率方面表现优异，消耗的硬件资源比其他加速器更少。
第 III 节. 优化分区方法
局部敏感哈希（LSH）是一种广泛采用的技术，它涉及使用映射函数将多维数据映射为一维值，正如先前的研究所描述 15 16。通过使用改进的哈希函数，在划分点云时每个周期可以处理一个点，整个划分时间被限制为 30K 周期。在本研究中，我们提出了一种改进的映射函数，专门设计用于提升 FPGA 位操作的性能，如图 1 所示。哈希函数所选的位宽对 k-最近邻（kNN）搜索的准确性以及点云哈希桶的大小都有影响。在我们的实验中，我们评估了不同位宽的哈希值，即 6 位、9 位、12 位和 15 位，如图 2 所示。图 2(a) 展示了使用不同 k 值（1NN、5NN、6NN、8NN 和 10NN）的速度测量准确性。可以明显看到，随着位宽的增加，准确性逐渐下降。进一步，图 2(b) 显示了哈希桶的平均大小，随着位宽的增加而减小。基于我们的发现，我们为哈希函数选择了 12 位值。其对应的平均哈希桶大小为 127，同时保持 80% 的满意准确率，用于前 10 kNN 搜索。本研究中使用的哈希函数的具体结构是将各个哈希组件连接形成 12 位哈希值，如图 2 所示。
图 2. 基于 KITTI 的不同哈希值的平均准确率和平均桶大小
第 IV 节. 架构
硬件架构由四个不同模块组成：Partition Unit、Search Bucket、Reference Bucket 和 NN Search。要查看整个设计的可视化表示，请参阅图 3。
A. 点云存储
参考点云和搜索点云都经过相同的分区过程。有趣的是，我们观察到这两个点云的分区在时间上不重叠，从而可以使用共享的分区单元。这一优化显著降低了分区单元的硬件资源消耗。此外，我们使用片上 BRAM（块RAM）来存储分区后的点云，在搜索过程中实现高速访问。为进一步优化点云存储的硬件资源利用，我们提出如下方案。
为了解决分区过程中哈希桶内点分布不均的问题，我们实现了一种基于块的 RAM 分区方法。这一方法类似于操作系统中的虚拟内存概念。将可存储 65,536 个点的 RAM（如图 4 所示）划分为每块可容纳 64 个点的块，即可构造所谓的“桶块”——哈希桶的基本单元。随后将 RAM 分区为 1,024 个桶，并为每个桶块分配唯一的 10 位块编号。
为跟踪不同键值的块编号分配，我们使用哈希信息表。如果某个桶所需空间超过已分配块数，则必须分配新块。为方便此过程，我们实现了桶块表，如图 4 的 Block Table 所示。该表包含两条信息：已分配的桶块和对应桶的逻辑下一个桶块。
图 3. 基于 FPGA 的 3D 点云 kNN 搜索加速器架构
图 4. 左侧架构展示了按块划分的 RAM，包含 65536 个单元的 RAM 均分为 1024 块。Block Table 存储逻辑连续块的链接。
通过采用此方法，我们确保仅为地址较小的桶分配块。因此，数据存储密度得到优化，实验中超过 65%。该策略最大限度减少资源浪费，并为点数较多的哈希桶分配更多空间。
B. 分区单元
在本文提出的流水线架构中，Partition 单元负责将点云的相关关键值传输到存储模块。该流水线过程包含多个阶段，操作如下。我们首先将存储点云的随机存取存储器（RAM）划分为若干块。划分过程采用流水线方法执行，使每个阶段能够在单个周期内完成。该方法有效地将点数据拆分，从而实现其在对应哈希桶中的高效存储。
图 5. 如图所示，SE（搜索元素）架构，它是查询数组的基本单元。
C. NN 搜索
NN搜索过程依赖于搜索元素（SE），它是基本组成部分，如图5所示。SE架构包含三个减法器、三个乘法器和两个加法器，用于计算点之间的欧几里得距离。随后将此距离与存储在邻居缓冲区中的点进行比较，从而选择距离最小的点。随后将该点存储到邻居缓冲区中。对于NN搜索模块，我们采用了32个SE的阵列，能够并行搜索32个点的kNN。最初，NN搜索模块从搜索数据RAM模块加载32个查询点，这些点全部属于同一哈希桶。与此同时，从参考数据RAM模块加载点。随后计算已加载点与查询点之间的距离，并选择k个最小欧几里得距离的点。该过程重复进行，直至搜索完桶内所有点。得到的数据通过AXI总线写入DDR。一旦此搜索完成，模块将加载下一个搜索的查询点。
SECTION V. 实验结果与分析评估
A. 评估设置
我们实现所选的硬件平台是 Xilinx Zynq UltraScale+ MPSoC ZCU102 平台。我们进行全面评估，以评估各个方面，包括搜索速度、资源利用率和功耗。为了评估我们设计的延迟，我们使用 KITTI 数据集作为基准。具体来说，在从数据集中去除地面点后，每帧大约包含30k个点。我们在架构上针对 kNN 搜索执行延迟测试，k 值设为8。此外，我们还与现有加速器进行了比较分析，以确定我们提出的解决方案的有效性。
B. 与 CPU 和 GPU 的延迟和功耗比较
我们的评估结果使用 Xilinx ZCU102 平台获得，工作时钟频率为 300 MHz。完成一次单个 k‑最近邻（kNN）搜索所需的执行时间记录为 0.64 ms，如表 I ，展示了相较于文献中引用的 FLANN_CPU 和 FLANN_GPU 17 18 方法的显著性能提升。FLANN CPU 在搭载 32 GB DRAM 的 Intel i7 8700 CPU 上基准测试。FLANN GPU 在 NVIDIA GTX 1080 GPU 上测试。具体而言，我们的方法相比 FLANN_CPU 提升了 120 倍、相比 FLANN_GPU 提升了 15 倍。此外，我们的方案在能效比上实现了显著提升，表明资源利用更为优化。
表 I
C. 与其他加速器的延迟与资源比较
如表 II 所示，与以往研究相比，我们提出的加速器在延迟和资源利用方面表现出更优的性能。具体而言，我们的加速器实现了 0.64 ms 的稳定执行时间，超过了其他方法。此外，它在资源消耗方面更为高效，例如数字信号处理器（DSP）和块随机存取存储器（BRAM），相较于现有解决方案。
表 II
表 III
D. 在 FPGA 上测量延迟和 DSP 数量
为分析不同数量的搜索引擎（SE）对 k‑最近邻（kNN）搜索延迟的影响，我们使用包含 10k、20k 和 30k 个点的数据集进行了实验，结果如表 III 所示。我们的结果表明，搜索时间与点数以及 SE 数量之间存在明显关系。这一特性使得能够高效处理大规模点云数据集，同时最小化搜索延迟。与此同时，我们观察到 DSP 的使用随 SE 数量线性增长。
SECTION VI. 结论
本文提出了一种新型基于 FPGA 的加速器，用于点云配准领域的 kNN 搜索。我们提出的加速器利用改进的局部敏感哈希（LSH）技术，实现了对点云的高效划分，将其分配到不同的哈希桶中。此外，我们提出了一种基于芯片上随机存取存储器（RAM）块的分配方法，能有效降低资源消耗。更进一步的是，通过仅使用 96 个数字信号处理器（DSP）资源的并行搜索方式，我们显著减少了搜索时间。与 CPU 和 GPU 的比较分析表明，我们的方法实现了 120 倍和 15 倍的加速。值得一提的是，本研究中改进的 LSH 方法可以推广到其他 kNN 过程，而资源优化技术也可以方便地适配多种移动计算平台。
参考文献
额外参考文献
F. Chen, R. Ying, J. Xue, F. Wen 和 P. Liu, “ParallelNN: A Parallel Octree-based Nearest Neighbor Search Accelerator for 3D Point Clouds”， 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)，蒙特利尔，QC，加拿大，2023，pp. 403 - 414.
H. Sun, X. Liu, Q. Deng, W. Jiang, S. Luo 和 Y. Ha, “Efficient fpga implementation of k-nearest-neighbor search algorithm for 3d lidar localization and mapping in smart vehicles”， IEEE Transactions on Circuits and Systems II: Express Briefs，vol. 67，no. 9，pp. 1644–1648，2020.
Kramer, O.（2013）。K-Nearest Neighbors。在：Dimensionality Reduction with Unsupervised Nearest Neighbors. Intelligent Systems Reference Library，vol 51。Springer，柏林，海德堡。
Jakob, J. 和 Guthe, M.（2021），Optimizing LBVH-Construction and Hierarchy-Traversal to accelerate kNN Queries on Point Clouds using the GPU。Computer Graphics Forum，40：124 - 137。