应用于无人驾驶车辆的点云聚类算法研究进展
欢迎引用
王子洋, 李琼琼, 张子蕴, 王康, 杨家富. 应用于无人驾驶车辆的点云聚类算法研究进展[J]. 世界科技研究与发展, doi: 10.16507/j.issn.1006-6055.2020.12.025.
王子洋，李琼琼，张子蕴，王康，杨家富（南京林业大学机械电子工程学院）
随着近年来人工智能的快速发展，无人驾驶汽车的出现引发了各界人士的大量关注，这将对传统汽车行业形成巨大的冲击。无人驾驶车辆通过多种车载传感器来识别车辆所处的周边环境和状态，并根据所获得的环境信息自主做出分析和判断，从而自主地控制车辆运动，最终实现无人驾驶。其中，环境感知、导航定位、路径规划、决策控制是无人驾驶汽车的四大核心技术。环境感知是用来获取周围环境信息的，是实现无人驾驶的基础。目前主流的有以谷歌为代表采用激光雷达的方案和以特斯拉为代表采用视觉的方案。点云聚类是环境感知重要部分之一，其利用激光雷达对点云进行聚类分割，同时也为点云分类奠定了重要基础。点云聚类算法是人工智能和无人驾驶领域中新型的算法，该算法不仅是研究热点还得到了广泛的推广。经典的点云聚类算法也包括K-means算法、DBSCAN算法等。
无人驾驶汽车通过激光雷达发射出的激光束对周围环境进行旋转扫描形成的点云图，每个点都会有相应的坐标位置信息， 点云聚类的任务就是将点云图中的各个点云聚类成若干个整体，具有相似程度的对象构成一组，降低后续计算的计算量，也有利于后续的聚类。目前在无人驾驶汽车的研发中，点云聚类主要应用于对障碍物、道路、行人等方面检测。其中绝大多数是研究在结构化道路上的检测问题，而非结构化道路上的检测问题还有待进一步深入研究。本文简要阐述了点云聚类的基本概念，分析了应用于无人驾驶车辆中点云聚类的六类聚类方法，并将这六类聚类方法在点云聚类应用中的性能进行了对比，最后提出了无人驾驶车辆点云聚类的未来研究方向。
所谓的点云聚类就是将没有任何结构的原始点云按照某些特征分割成一系列的点云簇，同一类的点云簇具有相似或相似度较高的特征，不同类点云簇间的点云具有不相似或相似度较低的特征，聚类阶段如图1所示。近年来在无人车的感知层中点云聚类开始得到了广泛的应用，其中主要的点云聚类方法如表1所示。
1.1 基于划分的聚类算法
基于划分的聚类算法的基本思想是预先指定聚类数目和聚类中心，计算每个点与其他点的距离，对于每个数据点都有n-1个距离值，对这些距离值进行排序，找出最接近的数据点，算出这些距离的和值。并进行下次迭代，这时数据中心点位置改变，继续按照上方的步骤，逐步降低目标函数的误差值，直到目标函数值收敛时，得到最终聚类的结果。代表算法有K-means算法。
k-means算法其思想能够追溯到1957年的Hugo Steinhaus，术语“k-均值”于1967年才被James MacQueen首次使用，K-means算法是基于划分的聚类算法，其思想是以k 为参数，把n 个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。该算法是研究得最多的分区聚类算法，同时由于其简单性该算法也被大量学者广泛使用。
龚亮等采用K-means算法利用机载激光雷达点云数据的强度信息对道路进行提取，可以分离道路轮廓。Diaz-Vilarino等使用K-means算法对石头和沥青两种不同路段进行聚类，较好地分辨出两种不同的路段，但仅限于沥青和石头两种特定的材料。Xia等将强度信息作为特征进行聚类以区分同距离的不同目标，再利用阈值限定聚类中心间的最小距离，其聚类准确率达到90%以上，较好地解决了同一距离不同目标的激光雷达点云聚类问题，但还存在对输入参数预先选取问题。
然而K-means算法在处理点云数据过程中，常会受到k值和初始聚类中心的选取等相关因素的影响，导致其聚类的准确率较低。为了解决k值难以选取的问题，Li等开始尝试利用熵代价函数来确定合适的聚类数目，但未解决选取聚类中心问题。Khan等为了解决在聚类开始前对初始聚类中心难以选取的问题，提出了一种计算k均值聚类初始聚类中心的算法，但还存在对k值选取问题。在上述问题的基础上，Limwattanapibool等采用了基于密度的思想自动找到k-means的合适k值和初始聚类中心。而Li等利用局部最大密度区域的个数来确定k值的选取，再根据数据点的坐标值计算出各个局部最大密度区域的重心，将初始聚类中心选取为距离重心最近的点，有效地解决了k值和初始聚类中心两个初始参数的选取问题，提升了聚类结果，但降低了聚类速度。
K-means算法简单实用，对高维或低维点云数据聚类的效率较好。但不能够对任意形状的簇进行聚类，同时由于依赖k值、聚类中心点的选取，参数的选取直接会影响到聚类结果的好坏，因此该算法的聚类准确率不稳定。
模糊c-均值聚类算法（Fuzzy C-means Algorithm, FCM）。该算法是由美国的Bezdek教授最早提出的，该算法是基于划分的聚类算法，FCM算法是对目标函数进行优化的聚类算法，主要是根据各个对象之间的相似性来完成目标对象的聚类，算法的主要思想是确定好聚类数和聚类中心初值去计算每个点与聚类中心的距离，构建模糊分类矩阵以及重新计算聚类中心，最终直到相邻两次的聚类中心小于规定值时聚类结束，得到聚类结果。
FCM算法较为简单，运算速度快并且算法容易实现。但FCM算法也存在着自身的不足，受参数的影响较大，在聚类之前要先确定聚类数目和初始聚类中心的值，并且聚类数目与初始聚类中心的值会直接影响到聚类的结果，在FCM算法逐步优化的过程中，也会容易陷入到局部最优解，也可能会使得最后得到的结果与预想的差别很大。
针对以上FCM算法存在的一些缺陷，Chiu等提出了一种自适应模糊c-均值聚类算法，该算法可事先根据输入样本点的数据来确定和划分聚类数目和初始聚类中心的值，简化了算法的计算难度并且优化了聚类的结果，但未解决易陷入局部最小值问题。于是Wang等和Wang等都采用了改进的粒子群算法和FCM相结合的算法，通过利用改进的粒子群算法解决了传统FCM易陷入局部最小值问题，通过实验验证该算法具有更快的收敛速度和更少的迭代次数，点云聚类效果更加准确，但还存在对输入参数敏感问题。Fu等采用遗传算法确定FCM的聚类数目，很好的克服了输入参数敏感问题，但还存在计算时间长，聚类效果较差的问题。而Chen等在Fu等的基础上提出了一种改进的遗传FCM聚类算法，通过改进了GA的交叉、选择和变异来提高全局搜索能力，减低了设置遗传参数的难度，很好的提高了收敛速度与聚类结果。
K-means算法与FCM算法很相似，两者都是基于划分的聚类方法，并且在聚类之前都要事先确定好聚类数目和聚类中心值，两个算法都较为简单，容易实现，但在实际使用中使用K-means算法的人相对较多一些。
1.2 基于层次的聚类算法
基于层次的聚类算法的主要思想是把每个对象都看成是一个类，去计算任意两个子类的相似度并根据相似度的大小进行排序，把相似度最大的两个子类合并或者把相似度大于一定阈值的若干个子类合并去得到新的类，再重新计算类与类之间的相似度再进行排序，直到满足终止条件才完成聚类。该算法通常可解释性好、能产生较好的聚类，与K-means算法相比较可解决非球形簇的问题，但也存在时间复杂度高等缺点。目前在处理点云聚类问题中，层次聚类常被作为其他聚类算法的辅助算法使用。
部分学者也对传统的基于层次的聚类算法做了一些改进，张名芳提出了一种在线学习合并阈值的层次聚类算法，通过确定聚类数搜索范围上界和初始聚类中心的待选点集，利用距离乘积最大化方法对待选点集进行初始化排序，结合点云的空间密度分布从而提高运算速度并较好的改善了聚类结果。而Zhao等提出了一种基于表面特征描述的基于层次聚类算法，该算法不需要先验知识和特定的阈值，可以快速简化密集点云，同时还保留特征点，减少了聚类时间，也使得点云精度损失较小。
基于层次的聚类算法与基于划分的聚类方法相比，在点云聚类方面应用相对较少，该算法可以去识别形状复杂、大小不一的类，并且孤立点以及噪声点也可被滤除。但两者也存在相似之处，在聚类之前都需要预先知道子类的数目。
1.3 基于密度的聚类算法
大多数的聚类方法是以数据集在空间分布上的距离作为依据进行聚类，而基于密度的聚类方法是以数据集在空间分布上的稠密度为依据进行聚类，无需预先设定簇的数量，因此特别适合对未知内容的数据集进行聚类。此外，该方法不仅可以发现任意形状的簇，还可有效去除噪声点。
DBSCAN算法是在1996年被Martin Ester、Hans-Peter Kriegel等率先提出的，该算法是基于密度的聚类算法中最常用的一种聚类方法，该算法通过引入密度的概念，即要求聚类空间中的一定区域内所包含对象的数据不小于某一给定阈值。该方法能够在具有噪声的空间数据库中发现任意形状的簇，可将密度足够大的相邻区域连接，能够有效的处理异常数据，主要用于对空间数据的聚类。
DBSCAN算法是点云聚类算法中较为常用的算法，杨思远等采用DBSCAN算法去除噪声点云实现车辆点云聚类，Liu等利用DBSCAN算法对非结构化环境中的障碍物点云进行聚类。
为了提高算法的聚类速度，Guan等通过设置扫描点搜索角领域ε来改变搜索扩展域范围并结合自适应DBSCAN算法，大大减少了聚类搜索时间实现点云快速聚类，Zhao等提出了VG-DBSCAN算法，将三维点云进行体素栅格划分，大幅减少了搜索范围，通过实验验证该算法可实现点云的快速聚类，而Li等将区域生长算法与自适应DBSCAN算法相结合，对预处理后的点云数据进行两阶段聚类，实现对障碍物的快速检测，该方法不仅加快了聚类速度，还具有较好的鲁棒性。
考虑到激光雷达距离会造成点云近密远疏的特点，Xue等利用聚类半径与距离作用模型对半径进行自适应调整，摆脱了传统的固定半径，提高了点云聚类效果，Mao等在Xue等的基础上采用了改进的半径参数DBSCAN算法结合距离图像对点云目标进行分割，而Tekbir等提出了递归分区DBSCAN算法，将密度不均匀点云划分成若干个密度相对均匀的分区，再对各个分区进行局部聚类，最后将各个局部聚类进行结合，形成最终聚类，通过实验验证该算法与原始DBSCAN相比较，在运算时间和检测精度上都有了很大的提高。
由于DBSCAN算法严重依赖半径（Eps）和阈值（MinPts）两个参数的选取，所以参数的选取往往会直接影响到最终的聚类结果，虽然部分学者将DBSCAN算法改进成自适应的DBSCAN算法，但仅实现了半径的自适应，还存在阈值自适应的问题有待解决，所以希望以后会有更多的研究人员尝试解决阈值的选取，实现两个参数的自适应，从而达到最佳的聚类效果。
OPTICS算法也是一种基于密度的聚类算法，可以说是对DBSCAN算法的扩展。与DBSCAN算法不同的是，OPTICS算法可以获得不同密度的聚类，其实就是通过OPTICS算法的处理，理论上应该可以获得任意密度的聚类。OPTICS算法思想与DBSCAN算法较相似，OPTICS和DBSCAN的输入参数一样是半径（Eps）和阈值（MinPts），但该算法对Eps输入不敏感，先通过固定的MinPts和无穷大的Eps去得到有序列表，然后再得到决策图，最后通过决策图可知Eps取特定值时数据的聚类情况。
OPTICS算法不需要去提前确定簇是个数就可以去发现任意形状的簇，同时还对输入的参数不敏感，但不同的Eps也会影响算法最终的聚类效果，并且传统算法还存在不会对噪点区分问题。针对传统OPTICS算法存在的一些缺陷，Feng等提出了一种与OPTICS算法相结合并利用网格优化的DBSCAN算法，该算法首先将DBSCAN中的核心点转换为网格中心点进行处理，然后以栅格为最小处理对象，最后减少了耗时，提高了运算效率。而Moosmann等提出了一种基于加权欧氏距离的改进算法,解决了传统OPTICS算法受参数约束问题，改善了点云聚类效果，同时也增强了目标提取的准确性，但对提取出的目标类别有限。
OPTICS算法与DBSCAN算法都是基于密度的聚类算法，两者的输入参数一样均为半径（Eps）和阈值（MinPts）。但DBSCAN算法对输入的参数过于敏感，选择不同的参数会导致千差万别的聚类结果，而OPTICS算法的提出可以说就是为了改善DBSCAN算法，帮助其选择合适的参数，从而降低对输入参数的敏感度。但目前使用DBSCAN算法的较多，而采用OPTICS算法很少，希望以后会有更多的学者将OPTICS算法运用到无人驾驶点云聚类方面。
1.4 基于网格的聚类算法
先把对象空间量化为有限数目的单元，这些单元形成了网络结构，所有的聚类操作都在该结构上进行。这种方法的优势在于运算速度快，其处理的时间独立于数据对象数，而仅依赖于量化空间中每一维的单元数。
基于网格的聚类算法主要思想是首先对网格进行划分，然后使用网格单元内数据的统计信息对数据进行压缩表达，再根据这些统计信息去判断出高密度网格单元，最后将相连的高密度网格单元识别成簇。
由于传统的网格聚类自身存在局限性，所以一些研究人员在传统算法的基础上加以了适当的改进，Huang等提出了一种基于最小聚类单元的新算法，通过结合K-means与网格聚类的优缺点，解决了定值k和网格聚类中数据密集的难点。Qiu等提出了一种相交的网格划分与密度估计相结合的方法，通过分区可以大大减少高维点云数据中的网格数量，并且使得领域搜索变得简单，该算法不仅可以去发现任意形状的簇，还可以加快聚类速度，但还需要输入一个初始参数。而Lou等提出了一种基于动态距离阈值的网格聚类算法，通过实验表明，改进后的动态阈值与传统的固定阈值相比，能够解决处理激光雷达点云近密远疏的问题，同时还能够更好的对障碍物进行正确聚类。
基于网格的聚类算法运算速度很快，但还存在对参数敏感、无法处理不规则分布的数据等问题。并且该类算法效率的提高是以聚类结果的精准性为代价的，因此通常与基于密度的算法结合使用。
1.5 基于距离的聚类算法
欧式聚类（又称欧几里得聚类）通过计算欧氏距离将相近的点云聚类在一起，也是目前最受欢迎的点云聚类算法之一。
刘畅等提出了一种基于点云射线角度约束以及改进的欧式聚类算法，加快了算法运算速度，同时有效解决了传统欧式聚类面对点云密度不均匀导致聚类效果差问题，最终通过实车实验验证该算法可以快速准确的对障碍物进行聚类，但只对一定范围内的障碍物有效。Zong等对传统欧式聚类进行了改进，先通过KD-tree对点云数据进行快速搜索，再引入距离的变阈值思想使得阈值距离随着点云距离的变化而改变。最后经过试车实验得出改进后的方法能够更快速准确地识别障碍物，同时还具有较强的抗干扰能力，而Fan等也采用了KD-tree与欧式聚类相结合的思想，先通过体素滤波进行下采样，再通过KD-tree快速搜索，提高欧式聚类的聚类速度和聚类效果，最终通过实车实验表明在越野环境下可以准确识别行人，具有良好的识别率。
欧式聚类简单易懂，运算速度快、具有良好通用性同时可用于处理高维数据。虽然目前该算法发展较为成熟，阈值选取问题已被大多研究人员所解决，但还需要结合一些辅助方法（通常是用KD-tree）去达到更好的聚类效果。
1.6 混合聚类算法
近年来，混合聚类算法逐渐吸引国内外研究人员的关注。基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法和基于距离的聚类算法虽然在一定程度上可以去实现无人驾驶汽车的点云聚类，但传统算法都有其各自的优缺点。如果单单仅使用一种算法，那将很难去达到聚类结果的准确性以及算法的高效性。故采用多种方法相结合，并利用其各自优势的混合算法将是该领域的研究重点。
在对改善点云聚类效果方面，郑兰香等将基于相对距离和密度的聚类算法相融合，不仅校正了点云的偏移量，还有效地对密度不均匀的点云进行聚类，具有较好的鲁棒性。Fan等通过结合深度图和改进的自适应DBSCAN算法对非地面障碍物点云进行聚类，提升了聚类时间效率和聚类的准确度。Mark Junjie Li等提出了一种凝聚模糊K-均值聚类算法，通过在目标函数中引入了惩罚项来确定聚类数，解决了K值选取问题，提高了聚类效果，加快了算法的聚类速度。Yuan等提出了一种DBSCAN和RIC相结合的算法，采用自适应Eps领域选择方法来代替全局参数，经过实车实验验证表明，该方法能够将点云分布不同但密度相近的连接对象分离出来，从而达到更好的聚类效果。
在对点云聚类算法优劣势互补方面，Duan等提出了一种DBSCAN与K-means相结合的方法，在K-means中加入了密度聚类的思想，较好了克服了k值难以选取和无法分割密度相邻的障碍物问题。Yuan等将信息聚类和自适应DBSCAN聚类相融合，不仅克服了传统DBSCAN算法全局参数的缺点，还保留了去噪能力强的特点，同时也改善了聚类结果。李海伦等将遗传算法和模糊聚类算法相结合提出一种遗传模糊聚类算法。利用遗传算法去解决FCM算法可能陷入局部极小值问题，从而避免了陷入局部最小值情况，同时减少了FCM的迭代次数也提高了算法的运算速度，最终实现快速、准确的点云聚类。Zhou等提出了一种基于密度峰值和空间领域信息的改进FCM算法，通过选择局部密度峰值较大的点为初始中心点，不仅解决了输入参数敏感问题，还具有更好的抗噪能力和聚类性能。Wang等提出了改进的粒子群优化算法与模糊C-均值算法相结合的SPSO-FCM算法。利用粒子群算法具有较强的全局搜索能力特点，可有效避免过早捕获局部极小值，同时也改善了初始化聚类中心的高灵敏度所带来的局限性，最终可以寻找到全局的最优解，大大提高了算法的效率，也改善了聚类结果。
此外，基于层次的K-means算法、遗传算法和K-means算法、基于密度和空间分布的点云聚类算法、结合椭球准则与FCM聚类算法等。这些混合算法都在一定程度上改善了传统算法的性能，提高了点云聚类的效果。
在点云聚类应用中的性能对比
每种点云聚类算法在对点云聚类时都会存在自身的一些不足之处，综上所述，总结的结果如表2所示。
由表2分析可以看出基于划分聚类、基于密度聚类和基于距离聚类，这三种聚类算法都存在需要预先设定参数的问题，并且严重依赖参数的选取，往往会因为参数的取值问题而影响到最终的聚类结果。基于划分聚类、基于网格聚类和混合聚类都具有运算速度快的优势，同时基于层次聚类、基于距离聚类和混合聚类的聚类效果都不错。经过综合对比可以看出混合聚类算法优势更好一些，但由于混合聚类算法种类太多，需要根据聚类问题选取与其相应合适的混合聚类算法，这样才能更好的发挥其聚类效果。
综上所述，尽管国内外学者在对点云聚类做了大量的研究，到目前为止还并没有一种适用于所有场景的通用算法，伴随着激光雷达线数的增多，聚类算法在往云数据方向发展。未来点云聚类算法将在以下几个方面成为研究热点：
1）在对点云数据处理方面，传统聚类算法在处理大规模点云数据时运算速度慢，难以满足无人驾驶车辆的实时性，引入边缘算法将是无人驾驶车辆的发展趋势。
2）激光雷达会使得点云近密远疏、分布不均匀以及会丢失部分云点，采用混合算法，设计出具有更好的鲁棒性和准确性的点云聚类算法保证无人驾驶车辆的实时性和安全性。
3）目前点云聚类算法大部分都是采用围绕K-means、DBSCAN和欧式聚类等算法，使得在处理无人驾驶点云聚类方面的聚类算法过于单一，可以尝试将灰色聚类、基于模型的聚类、谱聚类和量子聚类等算法运用到无人驾驶点云聚类中，从而进一步为无人驾驶车辆点云聚类方面的发展提供参考。
长
按
关
注
解锁更多精彩内容
编辑部信息
邮箱：bj@clas.ac.cn
电话：028-85223853
网站：www.globesci.com