1.3.1 点云聚类

基于激光雷达的点云聚类是指，将点云数据按照一定规则分割成有意义的独立子集。激光雷达扫描周围交通环境得到的三维点云呈不均匀分布，场景内包含的障碍物个数未知，同时点云数据量较大，具有较高的采样噪声，选用的点云聚类算法需要能够适应空间分布密度差别较大的点云类簇。通常采用聚类算法划分出的同一组或簇的元素对象“相似”，即被认定为同一类别、同一整体或具有某种共同的规律性、相似性或关联性。其基本原理是，根据元素对象的某些属性来度量元素对象之间的相似性，将元素对象划分成不同的组或簇，使得同一组或簇的元素对象“相似”而不同组或簇的元素对象明显不同[8]。

聚类算法主要有基于距离的聚类、均值偏移聚类、基本划分聚类、层次聚类、基于密度的聚类和基于网格的聚类等方法[9-14]。

图1-20 基于激光雷达的环境感知数据处理流程

基于距离的均值偏移（mean shift）聚类算法，一般是指一个迭代的步骤。即，先算出当前点的偏移均值，移动该点到其偏移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。

给定d维空间R_d的n个样本点，在空间中任选一点x，则均值偏移向量的基本形式定义为

式中，i=1，…，n；S_k为一个半径为h的高维球区域，且满足式（1-21）的y点的集合；k为在这n个样本点x_i中，有k个点落入S_k区域中。

均值偏移聚类算法原理及效果如图1-21所示。