自动驾驶算法——提取点云障碍物轮廓—DBSCAN聚类算法

前言

最近在做项目过程中，我们注意到当考虑车体轮廓去进行全局路径规划（如混合A*算法），如果仅仅将障碍物点云数据中得每一个点只当成点，会造成较大的计算时间，如若将点云聚类成圆形 线型 多边形障碍物 会提高计算效率，这是其中一个原因，另一个原因是，我们需要知道障碍物的大小，障碍物大小程度决定了我们的动态避障的方法和策略。因此我根据costmap_conventer 进行了脱ROS处理，删除了一些暂时不用的逻辑，方便项目中使用。

带噪声的基于密度的空间聚类（DBSCAN）是一种数据聚类算法，由Martin Ester、Hans-Peter Kriegel、Jörg Sander和Xiaowei Xu于 1996 年提出。它是一种基于密度的聚类非参数算法：给定某个空间中的一组点，它将紧密堆积的点（具有许多附近邻居的点）组合在一起，并将单独位于低密度区域（其最近邻居太远的点）的点标记为异常值。DBSCAN 是最常见、最常被引用的聚类算法之一。

2014 年，该算法在领先的数据挖掘会议 ACM SIGKDD上获得了时间考验奖（该奖项授予在理论和实践上受到广泛关注的算法）。截至 2020 年 7 月，后续论文“重新审视 DBSCAN：为什么以及如何（仍然）使用 DBSCAN” 出现在著名的ACM Transactions on Database Systems (TODS)期刊下载次数最多的 8 篇文章列表中。
广受欢迎的后续HDBSCAN*最初由 Ricardo JG Campello、David Moulavi 和 Jörg Sander 于 2013 年发布 ，随后于 2015 年与Arthur Zimek一起进行了扩展。 它修改了一些原始决策，例