基于KDTree树和欧式聚类的越野环境下行人识别的研究*

范晶晶，王 力，褚文博，罗禹贡

（1.北方工业大学，城市道路交通智能控制技术北京重点实验室，北京 100144；2.国汽（北京）智能网联汽车研究院有限公司，北京 100176； 3.清华大学，汽车安全与节能国家重点实验室，北京 100084）

前言

行人识别作为环境感知技术的重要组成部分，可为自动驾驶车辆的决策和路径规划提供准确的边界约束条件输入。越野环境下的行人识别，是实现班组伴随自动驾驶车辆的基本前提，这也给行人识别算法的设计和实施提出了更高的要求。

程健［1］和Kidono等［2］基于行人简单几何特征，采用SVM分类器对行人进行识别，但SVM分类器的输出并不稳定。胡顺玺［3］通过提取点云中行人的几何和形状特征，设计线性分类器，实现行人识别，但识别效果鲁棒性不高。Nagashima等［4］针对激光雷达的每一条扫描光束分别独立计算行人识别结果，然后再进行集成，得到最终的行人识别效果，但当其中某一条扫描光束的识别效果出错时，整个结果均会受到影响。Sato等［5］结合GPS数据将激光雷达点云映射到网格地图上，通过占用网格法、卡尔曼滤波和全局最近邻的方法进行行人识别，具有较好的效果，但由于增加了GPS设备，成本有所提高。Yamamoto等［6］基于激光雷达的点云数据提出了一种针对行人的似然估计方法，该方法虽有效，但计算繁琐，仅适合离线计算。Li等［7］针对稀疏行人点云的工况，提出了一种新的密度增强方法，用于提高行人识别效果，但该方法对密度正常的行人点云效果并不明显。Mokni等［8］结合惯性传感器和测距激光雷达，对室内行人的运动跟踪进行了研究，该方法增加了惯性传感器，对成本影响较大。Tang等［9］利用距离感知扩展方法将三维点云映射到二维平面上，提取二维轮廓和特征，达到行人识别目的，但三维点云映射到二维平面涉及复杂的坐标系映射，增加了标定的工作量。Ogawa等［10］和Premebida等［11］在拥挤的城市交通环境中基于Lidar的特征提取用于行人检测的信息，设计了高鲁棒性和强跟踪能力的行人识别算法，但并未针对复杂的越野环境进行适应性设计和研究。Oliveira等［12］针对常规滑动窗口方法的固有缺陷，在非独立同分布概率框架内，提出了一种基于关联部件的行人检测方法，取得了优异性能，但实时性较差。Szarvas等［13］基于CNN神经网络研究了激光雷达对于行人的识别，但在实时运行速率上存在明显短板。Benedek［14］则利用旋转激光雷达对三维人体数据进行检测和建模，但在聚类算法加速方面并没有研究。

本文中针对班组伴随自动驾驶系统对于越野复杂环境下行人识别的需求，将激光雷达作为环境感知传感器，在聚类思想的基础上，设计了基于KDTree和欧式聚类方法的行人识别算法，并结合人的几何物理特征加以约束，提高行人识别算法的准确度。在理论分析与计算的基础上，通过小型履带式车辆平台，在越野环境下进行实车测试。结果表明，所设计的激光雷达行人识别算法能准确识别激光雷达点云数据中的行人，在越野环境下有良好的识别率。本文有两点创新：一是搭建了小型履带式车辆验证平台进行越野复杂环境下的行人识别验证；二是设计了一种基于加速搜索方法的点云聚类算法，提升了行人识别的效率和准确度。

1 系统构成

基于KDTree和欧式聚类的越野环境行人识别系统构成如图1所示。

图1 行人识别系统构成

图1 中通过Ubuntu 16.04下的Ros系统和网口连接，采集得到rosbag格式的激光雷达点云数据，通过技术手段将rosbag格式转换成PCL（point cloud learning）库可以识别的PCD格式，作为整个行人识别系统的原始输入。点云数据首先通过VoxelGrid体素滤波器进行下采样，此操作可在保持点云主要形状特征的基础上减少点的数量和点云数据量，可提高配准、曲面重建和形状识别的计算速度。随后创建KDTree对象，该对象是由二分搜索树（binary search tree，BST）演变而来的一种高维度索引树形结构，一般用在大规模的高维数据查找的场景中。在此基础上应用欧几里得算法对激光雷达点云进行欧式分割，得到若干个点云簇。针对若干个点云簇再使用行人几何物理特征进行约束，便可得到最终的行人聚类识别效果。

2 方法设计

2.1 VoxelGrid体素滤波器下采样

通过激光雷达采集的原始点云数据量较大，且与激光雷达的线数直接相关，线数越大，激光雷达数据输出量就越大。为避免大的数据量对后面的处理算法造成较大的计算压力，须寻找一种合适的滤波器算法来对点云数据进行下采样，从而在保证点云主要特征的前提下，尽可能减少点云的数据量。

VoxelGrid体素滤波器主要思路如下：根据点云数据的特点建立最小三维体素栅格，选取小立方栅格的边长，根据边长将三维体素栅格划分成m×n×l个小栅格，并将点云数据填充至对应的小栅格中，每个小栅格中，用该小栅格的质心来近似显示体素中的其他点。这种方法简洁高效，无须建立较为复杂的拓扑结构即可达到简化点云数量的目的，同时满足三维点云曲面快速重构的需求。每个小栅格中，质心的计算公式为

式中h为小三维栅格中点云的数目。用小三维栅格的质心来近似显示体素中的其他点，实现点云的下采样过程。

VoxelGrid滤波器下采样效果如图2所示。图2中，VoxelGrid滤波器中三维栅格为边长等于30 cm的正方体，滤波前后点云的轮廓形状基本保持不变，滤波之前点的数量为24 722，滤波之后点的数量为7 577，点的数量大大减少，节省了大量的计算资源。使用VoxelGrid滤波器过程中，可根据实际情况来调节VoxelGrid滤波器中三维栅格的边长大小，在减少点云数量和保持点云轮廓形状之间达到平衡。

图2 VoxelGrid滤波器下采样效果

2.2 KDTree对象创建

KDTree是由二分搜索树演变而来的用于大规模高维度数据查找场景当中的索引树形结构，主要用于最近邻查找和近似最近邻查找的场景。在图像识别领域的主要功能是比对和查找高维特征向量。

二分搜索树是一种二分树，具有以下特点：

式中：Tl_sub为左子树；Tl_root为左子树Tl_sub的根节点；Tr_sub为右子树；Tr_root为右子树Tr_sub的根节点。

对于激光雷达产生的三维点云数据，普通的二分树已无法满足存储需求，此时须利用KDTree的数据结构。KDTree本质上仍然是一种二分搜索树，每一次对点云数据空间的划分均建立在某一维度的基础上，划分完成后的左右子空间数据量应尽可能保证数目相等，其构建流程如下。

①按式（3）计算K维数据集合中每一维度的方差，并从中选取具有最大方差的维度k。

②将维度k上的数据从小到大进行排列，得到数据集合｛K1，K2，K3，…，KNk｝，其中K1＜K2＜K3＜…＜KNk，Nk为维度k上数据的个数。按式（4）计算维度k上的中值m：

③将阈值设置为步骤②中得到的中值m，得到两个集合Ksub_low和Ksub_high，并创建一个用于存储的树节点。集合满足式（5）的要求。

④对步骤③得到的两个子集合重复进行上述操作，直到所有的子集合都不能再进行划分为止；若某子集合不能再进行划分时，将该子集合中的数据保存到没有子节点的叶子节点中。

在建立KDTree数据结构后，一般情况下只须在其子节点和父节点中查找邻近点，即可大大减少搜索邻近点所带来的额外计算量，提高搜索效率。KDTree数据结构如图3所示。

图3 KDTree数据结构

2.3 欧式聚类

欧式聚类算法是一种基于欧式距离度量的聚类算法。三维空间中，点（x1，y1，z1）与点（x2，y2，z2）之间的欧式距离定义为

基于KDTree的最近邻查询算法是加速欧式聚类过程的前提，其流程如图4所示。

图4 KDTree最近邻点查询

图4 中对于给定的查询数据点P，须从KDTree的根节点开始进行比较，其中P（k）为当前节点划分维度k上数据点P对应的值，m为当前节点划分的阈值。若P（k）＜m，则访问左子树；否则访问右子树，直至到达叶子节点Q。此时Q就是当前最近邻点，而P与Q之间的距离就是当前最小距离Dc，min。随后沿着原搜索路径往上回退至根节点，若此过程中发现和P之间距离小于Dc，min的点，则须将未曾访问过的子节点均纳入搜索范畴，并及时更新最近邻点，直至所有的搜索路径都为空，整个基于KDTree结构的最近邻点查询过程便告完成。

欧式聚类的流程如图5所示。

图5 欧式聚类流程

图5 中对于欧式聚类来说，距离判断准则为前文提到的欧式距离。对于空间某点P，通过KDTree近邻搜索算法找到k个离P点最近的点，这些点中距离小于设定阈值的便聚类到集合Q中。如果Q中元素的数目不再增加，整个聚类过程便结束；否则须在集合Q中选取除P点以外的点，重复上述过程，直到Q中元素的数目不再增加为止。

2.4 行人几何约束

激光雷达原始点云数据经过VoxelGrid体素滤波器、KDTree对象创建和欧式聚类后，会得到一系列离散的点云集合。这些点云集合可能包含不同类别的物体，如轿车、货车、摩托车和行人等等，须结合行人的几何物理特征对感兴趣的行人目标进行筛选。

针对任意一个筛选出来的点云集合，首先须找到x，y，z 3个维度上的最大值和最小值，假设它们分别为xmin，xmax，ymin，ymax，zmin和zmax，则三维点云集合的边界尺寸为

一般来讲，行人的厚度相对于行人的宽度和高度基本可以忽略不计。假定z方向为行人高度方向，则行人应满足：

式中：hhigh，hlow分别为高度的上下限值；rhigh，rlow分别为高宽比的上下限值。行人的高度和高宽比均应在合理的阈值范围内，通过该法则可提高行人提取的准确率。

3 试验验证

为验证所设计的算法对于越野环境下行人识别的效果，首先搭建了履带式车辆验证平台，如图6所示。图6中履带式车辆验证平台搭载的激光雷达为16线雷达Velodyne VLP-16，它可提供360°的横向视角和30°的纵向视角，在水平／方位角方向可提供0.1°的角分辨率和5 Hz的旋转频率或0.4°的角分辨率和20 Hz的旋转频率，每秒可获取288 000个数据点，完全满足本文对于行人点云数据采集的要求。

图6 履带式车辆验证平台

通过履带式车辆验证平台搭载的激光雷达采集越野环境下的原始点云数据，并运用前文所述的算法进行聚类运算，分别针对单人和多人的场景进行验证，统计结果显示行人识别准确率可达95%以上，数据处理速度在24 fps以上，满足实时运行的需要。

单人识别效果如图7所示。由图7可见，上半部分原始点云数据中成分较复杂，包含各种各样的目标物体数据，而下半部分的行人点云聚类提取效果图中仅包含当前环境下存在的行人目标，此过程中VoxelGrid体素滤波器减少了约70%数目的点。提取到的行人点云簇的高度为1.80 m，高宽比在4.5左右，完全符合行人的几何特征。结果表明本文所设计的行人识别算法具有较好的识别效果，达到了预期的设计目标。

图7 单人工况识别效果

多人工况识别效果如图8所示。由图可见，上半部分点云数据较为复杂，除3个行人目标外还包含大量干扰目标，而下半部分仅包含提取出来的3个行人目标点云聚类结果，此过程中Voxel Grid体素滤波器减少了约70%数目的点。3个行人目标点云簇的高度均在1.70～1.80 m之间，高宽比均在4.5左右，完全符合行人的几何特征。结果表明，所设计的算法在多人工况下仍有较好的效果。

图8 多人工况识别效果

4 结论

针对班组伴随自动驾驶系统对于越野环境下行人识别的需求，将激光雷达作为环境感知元件，设计了一种结合KDTree数据结构、欧式聚类和人体几何约束的行人识别算法，并在越野环境下通过履带式车辆平台进行试验验证，结果表明所设计的算法是有效的，并得到以下结论。

（1）所设计的行人识别算法能准确识别激光雷达原始点云数据中的行人，且在越野环境下具备良好的识别率。

（2）VoxelGrid体素滤波器可在保持点云轮廓基本不变的情况下大幅减少点云的数量，显著缩减计算量。

（3）KDTree数据结构可大幅减少近邻搜索的计算量，对于欧式聚类有明显的加速效果。

试验中发现，单纯激光雷达的可视化效果相对较差，今后拟引入摄像头，对照图像数据和激光雷达数据，以提升整体的可视化效果。