[分享] 《智能驾驶之激光雷达算法详解》6、基于 3D 激光点云的聚类分割

        本章深入探索3D激光点云的聚类算法，作为机器学习中的核心任务之一，聚类旨在依据特定规则将数据划分为不同集合，促使相似数据聚合，非相似数据分离。在机器人与无人车领域，3D激光点云的聚类分割技术尤为关键，特别是在深度学习驱动的目标检测与点云分析新方法日益普及的背景下，其精确度直接关乎后续目标检测、跟踪等模块的性能。聚类分割不仅独立承担重要角色，还与3D目标检测模块相辅相成，显著降低目标遗漏的风险。聚类作为无监督学习算法的优势——无需预设类别，仅凭数据间的相似性进行划分，辅助系统判断环境状态，如障碍物识别与路径规划。鉴于多线束激光雷达生成的海量点云数据（每帧可达数万至数十万点），传统聚类算法（如DBSCAN、Mean Shift）直接处理时面临计算量大、难以满足实时性需求的挑战。因此，研究者们普遍采用降维或体素化等技术手段，以优化点云表示与存储方式，减少算法的计算负担与空间占用。本章基于现有技术分析，将相关算法归纳为三大类别：

        1、 基于网格/体素的点云聚类分割：在第五章中，我们已探讨过将3D激光点云投影至2D网格以实现地面与非地面点云的分离。此类方法因技术开销小、实时性强，在机器人与无人车领域早期研究中广受欢迎。例如，DARPA城市挑战赛中的多数团队便采用了网格地图技术。Douillard等通过均值高程地图分离非地面点云后，进一步利用体素网格表示并聚类，而Himmelsbach等则结合2D栅格地图与3D体素网格的高度差信息实现聚类，均展示了良好的应用效果。

        2、基于围模型的点云聚类：在图论框架下实现数据聚类划分，已成为聚类分析领域的璀璨明珠，诸多经典算法如谱聚类与受限拉普拉斯秩聚类等，均彰显了其深远影响。在此背景下，探索者们正积极将此类算法应用于3D激光点云的聚类分割难题中，力求突破。Klasing团队便是其中的佼佼者，他们巧妙地借助有向图与RBNN（Radially Bounded Nearest Neighbors）图的概念，创新性地提出了针对3D激光点云的聚类算法。该算法将点云数据映射为图G(U,E)，其中U代表节点（即激光点），E则连接着满足特定距离阈值r的点对，形成边集。通过精细调控点间距离d与阈值r的关系，实现了点云中聚类结构的精准划分。而Moosmann等学者，则另辟蹊径，针对机械旋转激光雷达的扫描特性，采用无向图模型来描绘3D激光点云。在他们的无向图G(U,E)中，每个激光点均巧妙地与四个特定方向的邻域节点相连，这些节点分别来自同一线束的左右两侧，以及不同线束但偏航角相同的前后位置。这一设计不仅深刻捕捉了点云数据的空间结构特征，还为后续的聚类分析奠定了坚实基础。

        3、基于深度图的点云聚类：第5章详尽阐述了深度图的精髓及其构建机制。深度图以其独特的方式，将繁复的3D激光点云凝练为直观的图像形式，其构建与索引过程既简便又高效，尤为可贵的是，它能精准保留激光点的距离精髓。正因此，基于深度图的点云聚类分割技术，在该领域内占据了举足轻重的地位。以德国波恩大学的Bogoslavskyi与Stachniss为例，他们巧妙地将3D激光点云转化为深度图后，借助高效的BFS算法，进一步推动了该领域的研究进展。

        德国波恩大学的Bogoslavskyi与Stachniss在2016年创新性地提出一种高效算法，该算法巧妙地将3D激光点云转化为深度图，并引入角度阈值作为约束条件，结合BFS算法在深度图领域内进行搜索，实现了点云的精准聚类分割。此算法设计精妙，无需构建复杂的三维点云树或索引，确保了高实时性处理能力。在I5 5200U 2.2GHz CPU平台上，针对32线激光点云数据，该算法展现出卓越性能，平均运行频率高达74至250Hz。作为深度图应用于点云聚类领域的先驱探索，该算法为后续研究奠定了坚实基础，并产生了深远影响。其开源代码现已发布于GitHub，供全球开发者学习与应用。Bogoslavskyi算法的核心策略精妙地融合了地面点云的精准分割与非地面点云的高效聚类。

        2017年，美国明尼苏达大学的Zermas与德尔福汽车公司的Izzat等人在ICRA会议上推出了创新的3D激光点云聚类算法——SLR（Scan Line Run）。该算法巧妙融合了机械旋转式激光雷达的扫描特性，专注于每条扫描线的点云数据，借鉴图像处理中的连通区域标记技术，在深度图层面逐行实施点云聚类的精细分割与智能合并。SLR算法的核心原理在于，它视深度图的每一行为激光雷达的一条独立扫描线，而每一列则映射了扫描的不同角度。Zermas等人创新性地定义了“run”概念，即将扫描线中连续且邻近的激光点视为同一集合，并赋予它们共同的类别标识。通过这一方法，算法能够沿扫描线将点云分割成多个run，并依据设定的距离阈值，跨扫描线进行run的合并，最终实现对整个激光点云的高效聚类。SLR算法作为逐线束点云聚类分割的典范，其精髓在于先通过相邻位置关系精准划分各激光线束内的聚类子集，随后借助距离条件巧妙融合不同线束间的聚类子集。然而，面对高线束激光雷达的广泛应用场景，SLR算法因需详尽计算三维空间内激光点间距离，导致计算耗时较长，实时性能受限。

        韩国东国大学的M. Wen等学者在2018年创新性地提出了将深度图与DBSCAN算法相结合的方法，巧妙地将3D激光点云数据转化为2D表示形式，并借助DBSCAN算法在转换后的深度图中实施基于密度连通的聚类分析。这一策略经实验验证，相较于直接在3D空间应用DBSCAN，其计算效率实现了惊人的飞跃，速度提升高达572.4倍；即便是与基于k-d树的DBSCAN算法相比，平均计算速度也实现了约16.89倍的提升。DBSCAN（Density-Based Spatial Clustering of Applications with Noise），这一由德国慕尼黑工业大学Ester等人于1996年开创的算法，是密度聚类领域的璀璨明珠。它无需预设聚类数量，通过遍历数据集，自动识别并划分出高密度区域作为独立聚类，能够灵活捕捉任意形状的聚类结构，包括图6-11所示的复杂形态，展现了其卓越的数据处理能力。

        鉴于近年来高线束激光雷达（如速腾MI、禾赛AT128等）在量产车型中的广泛应用，其点云数据量激增，每点云包含数十万至数百万激光点，这对实时聚类算法的计算效率与复杂度构成了严峻挑战。同时，传统聚类方法受限于固定距离或角度阈值，难以精确区分远近目标，未能充分发挥高分辨率激光雷达的潜力。保守的阈值设定易导致近处障碍物欠分割与远处目标过分割。进一步地，3D激光点云转换为深度图后，目标尺度随距离变化，加剧了远处物体的分割难度。鉴于此，创新性地提出了MVC（Multi-View Clustering）算法，专为高线束激光雷达的3D点云聚类设计。MVC算法巧妙融合了BEV与FV视角的优势，实现了对高密度激光点云的高效聚类与分割。该算法遵循从粗到细的双重策略，首先在BEV视角下构建极坐标栅格，并据此对点云进行初步聚类，随后针对潜在的欠分割区域，利用深度图进行精细化的再处理。实验验证，MVC算法兼具卓越的精度与实时性，足以应对智能驾驶领域的广泛需求。可根据实际需求，进一步拓展MVC算法，如在FV阶段引入动态阈值调整，或依据激光雷达的分辨率在水平与垂直方向上设定差异化阈值，以持续提升聚类精度，优化算法性能。