基于3D LiDAR点云的图分割算法

朱丽娟

摘 要：随着无人车应用领域的不断扩大以及激光雷达扫描技术的飞速发展，针对3D激光雷达点云数据处理技术研究对于人车领域的发展有重要意义.环境感知作为无人车系统的重要组成部分，对整车起着至关重要的作用.针对无人车基于激光雷达点云的环境感知中障碍物检测问题进行研究，提出了一种基于3D激光雷达点云的检测算法.该算法使用了基于图的点云分割方法.该方法可以对激光雷达点云进行快速分割，高效的将点云分割出障碍物点.针对城市道路中的车辆、行人等障碍物的实验效果表明，该方法对这类障碍物有良好的分割效果.该算法具有高的实时性，能够满足无人车的需求.

关键词：激光雷达；环境感知；障碍物检测；点云分割；图分割

1 引言

中国是全球最大的汽车产销国，2016年中国汽车产量和销量分别超过2800万辆，连续八年稳居全球第一.汽车的智能化和电动化是历史送给中国汽车人的天赐良机，适逢其会，无人驾驶技术的应用必将引起产业的重大颠覆.更为了减少交通事故，提高运输效率，减轻驾驶员劳动负荷，无人车自动驾驶技术应运而生.无人车是一个复杂的系统性工程，涉及环境感知、行为预测、规划控制、智能互聯、车载硬件、人机交互等多项自动驾驶相关的核心技术，涵盖了模式识别、图像处理、控制与决策、传感器等多个学科的科研成果.

作为无人驾驶流程中最为底层也最重要的感知层对无人驾驶技术发展起着至关重要的作用.目前，无人车感知方法使用的传感器大致可分为视觉传感器、激光传感器、微波传感器等.其中激光雷达能够获取车身周围百米内的三维环境，通过对激光点云的处理能够准确的进行场景分割.激光雷达的优点在于精度高，能够直接获取物体的三维空间信息.对光照环境的变换不敏感，能够全天候使用.障碍物检测是激光雷达最基本的环境感知能力.激光雷达能够准确定位障碍物位置并能从三维场景中提取出障碍物信息.

本文使用点云分割方法对障碍物进行检测.分割是将三维空间中的点划分成更小的、连贯和连接的子集过程.经过分割后，具有相似属性的点归为一类.分割后的结果应该得到一系列我们感兴趣的对象，如城市道路中车辆、行人、树木等.点云分割将点云自动划分为特征单一且互不重叠的区域.

1999年 Jain指出著名的图论分割聚类算法的主要思想是：构造一棵关于数据的最小生成树（minimal spanning tree，简称MST），通过删除最小生成树的最长边来形成类.基于图的图像分割算法是图像中经典的分割算法，本文参考这一算法的思想将其应用到3D点云分割中，实现对3D点云数据的快速有效自动分割.

本文第2节给出算法的详细描述.第3节结合具体例子将本文算法与人工分割结果进行实验比较和分析.第4节给出结论.

2 图分割算法

2.1 图的定义

我们使用基于图的方法分割3D点云.图是由顶点集V和边集E组成，表示为G=（V，E），顶点v∈V，在本文中顶点集V是点云中点的集合，这些点将会被分割为区域；一对顶点的边，表示为（νi，νj）∈E，每条边有权值w（νi，νj），本文中权值是一个非负数，表示νi，νj顶点之间的差异性.权值w设为一对顶点间的欧式距离，我们用欧式距离来衡量两点之间的差异性（即非相似度）.算法思想是把顶点集V中相似的点分割成区域C，区域中的点属于一类.设点云分割后的结果为分割集S，C是分割集S的一部分，表示为C∈S， 并且分割区域C也是一个图G`=（V，E`），E`∈E.我们希望在一个区域内点是相似的，区域间点是非相似的.这意味着在区域内的两点之间的边权值差异性是相对低的，区域间边权值差异性是高的.

2.2 区域的定义

我们定义D，来判断两个区域间是否存在边界.首先我们定义一个区域的类内差异Int（C），表示为一个区域内部最大的差异值，它的取值是区域最小生成树MST（C，E）的最大边权值.直观上我们可以用此值代表一个区域.

（1）

我们定义两个区域中类间差异Diff（c1，c2），表示为两个区域最相似的地方的差异值，它的取值为连接两个区域所有的边中权值最小的.如果两个区域之间没有边相连，则Diff（c1，c2）=∞.

（2）

由以上两个定义，我们可以判断两个区域间是否存在边界.如果存在边界，则两个区域的类内差异Diff（c1，c2）至少比这两个区域的类内差异要大.

（3）

（4）

2.3 自适应阈值

在公式（4）中引入自适应阈值函数τ（C），从而实现动态调节阈值，使得分割结果不会过分割或欠分割.

（5）

其中k是常量，控制所形成区域的大小，即表示分割的粒度，k值越大对应的分割区域越大.|C|表示区域内点的个数.

2.4 算法主要步骤

基于图的3D点云分割算法

输入：点云的图G=（V，E），设点云中有n个顶点，m条边.

输出：分割区域的集合S=（c1，c2...，cr）.

1）计算每个点与其8领域点的边权值，即非相似度，由此得到边集E.

2）边集E排序.将边按非相似度从小到大排序.

3）初始化分割集S0.S0集合中的区域元素由每一个点组成.

4）从Sq-1构建Sq，对当前选中的第q条边进行合并判断.

1>假设第q条边由νi，νj两点连接，如果νi，vj在Sq-1中不属于同一个区域，即Sq-1中两个区域ciq-1和cjq-1，νi∈ciq-1，vj∈cjq-1，并且（ciq-1≠cjq-1）

2>这条边的权重w（oq）区域间的非相似度不大于区域内的非相似度，即 ，则执行5），否则执行6）.

5）将中两个区域和，并更新阈值

.

6） ，如果q，按边集顺序选择下一条边转到4），否则执行7）.

7）得到分割结果，即分割集 .

2.5 算法实现技术

为了实现更好的分割效果以及加快分割效率，我们对输入的点云进行预处理操作，我们将点云分割出前景点云和背景点云，其中背景点云为地面点云，通过PCL中提供的平面模型RANSAC检查去除点云中的地面；前景点云为算法输入的点云.

算法第一步，需要计算每点的8领域边权值，为了快速查找领域采用最近邻搜索，在K为半径的空间中寻找最近点.这一步算法的复杂度从 降低到 ，其中N为边集的边数目.

算法第五步，需要查找两点是否在同一区域，以及合并两个区域的操作.本文中采用并查集的数据结构存储区域.通过这个数据结构提供的两种操作：

Find操作： 确定顶点属于哪个区域，从而确定顶点是否属于同一个区域.

Union操作：将两个区域合并为一个区域.

第五步算法的复制度为

综上所述算法时间复杂度为 ，可以做到快速点云分割

3 实验结果与分析

本文实验数据采用64线LiDAR，每秒钟输出10帧点云，每帧点云在10万个点以上.实验中对比1万帧点云人工标注结果与本文算法分割结果.点云在60米范围内准确率如表1所示.表中距离表示点云中点距离采集原点的距离.单帧的平均准确率为85.75%，满足后续环境感知分类需求.在windows平台，单帧运行时间为72ms，满足无人车需求.本文算法综合考虑了空间区域的边缘和区域邻接关系特征，分割结果比较有效的将不同区域物体分割开.自适应阈值的使用，保证了当两个区域有较大的差异，但两个区域相邻的比较近时，也能够分割开.

5 结论

通过对3D点云分割算法的实验和实验分析对比，我们认为本文提出的分割算法对于3D点云具有良好的分割效果，其中自动适应阈值有助于动态调节阈值更好的控区域合并的规则.实验分割结果与人工分割结果具有良好的一致性，其分割结果可用于無人车环境感知的基于区域的障碍物检测、基于区域的障碍物分类等.

在未来的工作中，可以将3D点云激光反射值的特征融入算法中，使得分割性能得到进一步的提高，也增加算法的鲁棒性.

参考文献

[1]X Guo. Research of automatic vehicle identification and loading system[J]： Industry &Mine Automation，2014.

[2]Dominic Zeng Wang， Ingmar Posner ， Paul Newman. What Could Move？ Finding Cars， Pedestrians and Bicyclists in 3D Laser Data： IEEE International Conference on Robotics & Automation， 2012，20（10）：4038-4044

[3]J Strom ， A Richardson ， E Olson：Graph-based segmentation for colored 3D laser point clouds.IEEE/RSJ International Conference on Intelligent Robots & Systems（IROS）， 2013 ， 25 （1） ：2131-2136

[4]朱德海，郭浩，苏伟.点云库PCL学习教程.北京航空航天大学出版社出版发行， 2012，10（1）.227-253