Cheesemap：一种高性能的点索引数据结构，用于LiDAR数据中的邻域搜索

《Future Generation Computer Systems》：Cheesemap: A high-performance point-indexing data structure for neighbor search in LiDAR data

本文提出一种名为cheesemap的新数据结构，基于体素网格的三种变体（密集、稀疏、混合）优化三维LiDAR点云的邻域搜索，实验表明其性能和内存效率优于现有方法，尤其在ALS点云中表现突出。

　　

Ruben Laso | Miguel Yermo

维也纳大学计算机科学学院科学计算研究组，W?hringer Stra?e 29，维也纳，1090，奥地利

摘要

点云数据作为三维空间信息的表示，在许多领域中都是基础性的。在这些领域中，高效地索引和查询点云对于对象识别、自主导航和环境建模等任务至关重要。在本文中，我们提出了一种新的数据结构cheesemap，专为3D激光雷达（LiDAR）点云中的快速邻居搜索而设计。点通过体素（voxels）网格进行索引，这种网格可以以三种不同的方式组织，从而形成了三种类型的cheesemap：密集型、稀疏型和混合型。理论上，体素的查找可以在常数时间或摊销常数时间内完成，从而加快了邻居点的搜索速度。实验结果表明，在性能和内存占用方面，cheesemap优于其他最先进的数据结构，无论是对于基于区域的查询还是对于$k$-NN查询，尤其是在机载激光扫描（ALS）点云中。

引言

点云数据通过离散点表示三维信息，在计算机视觉、机器人技术、考古学、地理空间映射和自主导航等多个领域中发挥了重要作用。从点云中高效提取有意义的信息对于对象识别、场景理解和环境建模等任务至关重要。点云处理中的一个基本操作是围绕特定点搜索其邻居点，因为这一操作是分割、特征提取、数据挖掘、卷积和聚类等任务的基础。

由于数据采集方法的多样性（主要使用光检测与测距（LiDAR）技术，如机载激光扫描（ALS）、地面激光扫描（TLS）、移动激光扫描（MLS）或无人激光扫描（ULS）），因此产生了各种不同密度和分布的点云类型。根据这些特性，并非所有用于搜索给定点邻居点的方法以及所有用于存储点云的数据结构都同样适用。

本文对不同类型点云中各种数据结构与邻居搜索方法的组合进行了全面的比较分析。我们的目标是揭示这些方法在各种场景下的优势、劣势和适用性。通过了解不同条件下的邻居搜索技术性能，研究人员和从业者可以做出明智的选择，以选择适合他们特定点云处理任务的方法。我们进行这项研究的动机在于观察到，最先进的数据结构和邻居搜索方法的效率可能会因点云数据的性质而有所不同。例如，点密度变化、分布不规则和高维度等因素会显著影响这些方法的性能。此外，我们提出了一种新的数据结构，旨在优化邻居搜索操作的效率，尤其是（但不限于）针对ALS点云。

本文的其余部分安排如下：第2节回顾了点云处理中数据结构和邻居搜索方法的相关工作。第3节介绍了一种旨在提高ALS点云搜索性能的新数据结构。第4节介绍了实验中使用的数据集和实验设置。第5节展示了我们的比较分析结果，突出了每种数据结构在不同条件下的性能。最后，第6节总结了关键观察结果和未来研究的方向。

相关研究

在点云中计算邻居点是一项非平凡的任务，因为数据本身具有不规则性。给定数据点的邻居点由满足某些条件的所有周围点组成，这提供了关于点云局部结构的信息，这对于其处理至关重要[1]。在最先进的文献中遇到的最常见的邻居搜索方法有两种：固定半径邻居[2]和$k$-最近邻（$k$

Cheesemap

作为上述方法的替代方案，我们提出了一种称为cheesemap的数据结构及其三种形式：密集型、稀疏型和混合型。

这种结构，特别是其稀疏型和混合型形式，旨在利用激光雷达点云的特点，其中点密度通常不均匀。在ALS点云中，垂直$z$轴上的范围往往比$x$轴和$y$轴上的范围要小得多。因此，在索引时...

实验设置

在本节中，我们将描述使用的数据集、进行实验的机器以及用于评估数据结构性能的指标。

结果与讨论

实验结果分为两部分：一部分分析cheesemap及其参数的性能，另一部分将cheesemap与其他最先进的数据结构进行比较。

结论

在本文中，我们对几种用于点云索引的数据结构进行了全面分析，并从性能和内存占用方面进行了比较。我们还介绍了cheesemap，这是一种专为激光雷达点云设计的快速且内存高效的新数据结构。cheesemap基于网格结构，将空间划分为体素，每个体素列出了其中的点。这种结构允许快速查询一定范围内的点。

CRediT作者贡献声明

Ruben Laso：撰写 – 审稿与编辑，撰写 – 原稿，可视化，软件，方法论，调查，形式分析，数据管理，概念化。Miguel Yermo：撰写 – 审稿与编辑，撰写 – 原稿，可视化，软件，方法论，调查，形式分析，数据管理，概念化。

写作过程中生成式AI和AI辅助技术的声明

在准备这项工作时，作者使用了ChatGPT来改进文本的语言和可读性。使用该工具/服务后，作者根据需要对内容进行了审查和编辑，并对出版物的内容负全责。

利益冲突声明

作者声明他们没有已知的财务利益冲突或个人关系可能会影响本文报告的工作。

致谢

本项工作得到了文化、教育与大学管理部（认证编号ED431C-2022/16, ED431G-2019/04）和欧洲区域发展基金（ERDF）的财政支持，后者将CiTIUS-智能技术研究中心认定为加利西亚大学系统的研究中心。西班牙经济与竞争力部（资助编号PID2019-104834GB-I00, 和 PID2022-141623NB-I00）也提供了支持。

感谢...

Ruben Laso目前担任维也纳大学科学计算研究组的博士后研究员。我于2023年在圣地亚哥-德孔波斯特拉大学获得了高性能与并行计算博士学位。在此之前，我分别于2019年获得了工业数学硕士学位，2017年获得了计算机科学学士学位，均在圣地亚哥-德孔波斯特拉大学完成。我的研究兴趣包括并行计算，特别关注...