融合图像边缘的区域生长点云分割算法

施庭雨,黄丽婷,林靖宇,,谢胜利

1(广西大学 电气工程学院,南宁 530004)2(广东工业大学 自动化学院,广州 510006) E-mail：tyshi123@sina.cn

1 引 言

点云是无序的三维点集.点云分割是根据点云中的局部特征对三维点进行分类,将具有相似属性的点归为一类,使之划分为互不相交的集合、同一集合内的点具有相似特征,从而得到感兴趣的目标对象.点云分割有助于场景分析,如定位和对象识别、分类和特征提取、物体识别等,是点云数据处理的关键环节之一[1].

区域生长源于图像分割算法,后来扩展到点云分割算法.其思想是先选定种子点,由种子点开始扩散,判断其周围邻域点是否属于同一个曲面,直到扩散至邻域不存在连续点集为止,最后组合这些邻域构成区域[2,3].这种算法复杂度低,容易实现,因此得到了广泛应用.

区域生长算法对种子点的选择以及相关生长策略的设计非常依赖.如果种子点选择不当或者生长策略设计不当,会出现欠分割或者过分割现象,从而影响到分割精度[4].对于种子点的选择,许多区域生长算法都是以平面分割为目标,Ning等[5]对于种子点的选择是先为某个点及其相邻点设计一个拟合平面,然后选择对拟合平面残差最小的点作为种子点,残差通常由一个点与其拟合平面之间的距离或点的曲率来估计,残差最小的点作为种子点会从点云中最平滑的区域开始分割,对于特征变化显著的部分通常会被识别成噪点而移除.Vo等[6]根据不同的数据集进行预定义和调整,不同的数据集种子点的选择也会较大的差异,如果种子点选择有误会使区域增长产生非均匀性问题.稠密点云数据量较大,并具有较多的邻域点,使用常规的点云分割算法会使分割效率偏低,Chen等[7]根据数据的特征进行相应的下采样,但是下采样会使具体的分割结果需要在精度和效率之间进行权衡.Huang等[8]采用随机采样一致性(Random Sample Consensus,RANSAC)算法获取种子点,但是基于此法进行区域生长容易出现分割不稳定的情况,即分割结果出现欠分割或者过分割现象.对于相关生长策略的设计,需要根据不同的点云特征设计出与之相应的相似性判定依据,通常使用几何特征如欧几里得距离、法向量或曲率作为相似性的判定依据.Ning等[5]以法向量为法向量作为判定依据,使得共面可以共享共同的法向量,但是在特征变化幅度较大的点云中,会因共同的法向量较少影响到分割精度.Xu等[9]应用法向量、相邻点到调整平面的距离以及当前点和候选点之间的距离作为将点合并到种子区域的标准,该种子区域是在手动过滤边缘附近区域后从数据集中随机选取的,对于分割结果好坏的影响会有一定随机性.Dong等[10]采用两点之间的法向量夹角以及当前点的曲率作为相似性度量的依据,但是使用该几何特征作为判定依据容易因种子点特征造成的阈值设定不当而影响到分割精度,如阈值设置过大会导致分割不完全;阈值设置过小会导致很多点被识别成噪点.

点云中一般将强度变化显著的三维点定义为边缘点,边缘主要存在于目标与目标、目标与背景、区域与区域之间.点云的边缘可以描述点云物体形状的基本特征,可以划分出目标分割的区域,作为分割的界限[11,12],所以设定边缘三维点为种子点向目标对象点云内部进行分割可以一定程度上避免欠分割和过分割现象.但是直接使用现有的算法提取目标点云边缘不够准确.利用多传感器融合技术,采用具有互补特性的不同传感器来增强感知能力,可以解决边缘定位问题.例如融合激光雷达与RGB相机,利用二维RGB图像丰富的颜色信息和纹理信息快速定位目标对象,采用图像边缘提取算法提取出目标对象边缘[13],再通过标定后得到的对齐关系提取出与图像相对应点云中目标对象的边缘.

综上,本文提出一种以目标点云的边缘点作为种子点的区域生长分割算法,借助图像提取目标点云的边缘作为种子点,并根据边缘性质设计出相应的生长策略进行分割,可以以高精度分割出稠密点云中的目标点云,并且可以较大程度地避免欠分割与过分割现象.本文算法的实验数据和MATLAB代码可以在https：//github.com/SCVision/PointCloud-Image-Segmentation下载.

2 算法描述

2.1 概述

本文的点云分割算法具体可以分为两个部分：标定部分和分割部分.

标定部分建立二维RGB图像和三维点云之间的对齐关系.首先将相机和激光雷达组成采集系统,并采用该系统采集标定板在不同角度和不同位置的二维RGB图像和三维点云数据;然后使用张正友标定法[14]获得相机内部参数矩阵;接着提取棋盘格内角点的像素坐标和三维点云坐标并使用透视三点(Perspective-three-Point,P3P)算法[15]获得联合外参;最后是将得到的联合外参与相机内参结合建立出相机像素点和激光雷达三维点的对齐关系.本文所涉及的坐标系和相关参数定义如表1所示.

表1 坐标系和相关参数定义Table 1 Coordinate system and related parameters

分割部分通过融合RGB图像提取目标点云的边缘并将边缘点设定为种子点进行区域生长分割得到目标点云.首先利用已经标定过的相机和激光雷达分别采集目标对象的RGB图像和三维点云数据,并对图像中的目标对象边缘进行提取,计算原始点云中所有点的法线与曲率;然后根据联合标定得到的对齐关系,对原始点云建立三维点到像素点的映射关系,计算点云三维点对应的像素点到目标点云边缘点的欧氏距离与距离阈值比较来判断目标点云的边缘,将小于阈值的三维点确定为边缘点;接着将目标点云的边缘点划入种子点集中,并通过目标点云边缘确定分割界限,从种子点集中选择一个种子点进行区域生长分割,通过搜索种子点的邻域点,对邻域点是否在分割界限内进行判断,如果在界限内则将其曲率与阈值进行比较,小于阈值的划入种子点集中,大于阈值的计算邻域点与种子点的法线夹角,如果夹角小于阈值则将种子点与邻域点放入聚类点集中并从种子点集中删除该种子点,大于阈值则继续搜索下一个邻域点;最后当种子点集为空时结束,将聚类点集作为分割结果.具体分割流程如图1所示.

图1 分割流程图Fig.1 Flowchart of the segmentation

2.2 相机与激光雷达标定

进行相机与激光雷达标定的目的是为了获取相机与激光雷达的联合外参,建立相机坐标与激光雷达坐标的对齐关系,实现激光雷达坐标到像素坐标的映射,为后续的目标点云边缘提取做准备.

(1)

(2)

在获得相机内参矩阵后,需要对相机与激光雷达的联合外参进行求解.P3P算法[15]可以将3D-2D问题转换为3D-3D问题,即把透视n点(Perspective-n-Point,PnP)问题转换为最近点迭代(Iterative Closest Point,ICP)问题[17],从而求解出相机与激光雷达联合外参.

根据投影原理建立激光雷达点PL(i)与像素点pP(i)的几何关系,具体如图2所示.

图2 激光雷达点与像素点的几何关系Fig.2 Geometric relationship between LiDAR points and pixels

根据图2的几何关系,结合相似三角形原理可以得到激光雷达点PL(i)与像素点pP(i)的关系

(3)

在激光雷达采集到的含有标定板的三维精细点云中,可以提取出标定板的点云.用随机采样一致性(Random Sample Consensus,RANSAC)算法[8]对提取出的标定板点云进行平面拟合并提取标定板的4个顶点,根据Z值由高到低进行排序,得到标定板点云4个顶点的激光雷达坐标PL-vtx(i)(XL(i),YL(i),ZL(i)),其中i=1,2,3,4,Z1≥Z2>Z3≥Z4.通过PL-vtx(2)-PL-vtx(1)可以得到x轴向量x,PL-vtx(3)-PL-vtx(1)可以得到y轴向量y.设根据Z值从高到低排序后的标定板点云内角点激光雷达坐标为PL-cnr(i,j)(XL(i,j),YL(i,j),ZL(i,j)),其中i=1,2,…,m-1,j=1,2,…,n-1,可以建立转换关系：

(4)

由此可以计算出标定板点云内角点激光雷达坐标PL-cnr(i,j),其中i=1,2,…,m-1,j=1,2,…,n-1,ZL(i,j)≥ZL(i+1,j+1).

代入根据v值从高到低排序好的标定板棋盘格内角点像素坐标pP-cnr(i,j)和激光雷达坐标PL-cnr(i,j)到公式(3)中,经过求解可以得到激光雷达坐标P′L(i,j)(XL(i,j),YL(i,j),ZL(i,j))及其对应的像素坐标P′P(i,j)(XP(i,j),YP(i,j),ZP(i,j)).

根据P3P算法,两组三维点存在变换关系：

∀i,P′P(i,j)=RP′L(i,j)+t

(5)

代入P′P(i,j)与P′L(i,j)到公式(5)中,计算出联合外参的旋转矩阵R和平移向量t.

最后根据相机内参矩阵K、联合外参的旋转矩阵R,平移向量t,得到像素点pP与激光雷达点PL之间的对齐关系：

pP=K·R·(PL-t)

(6)

标定结果的精度高低会直接影响到后续目标点云边缘提取的效果.造成标定误差的因素有很多,其中包含标定板制作、相机分辨率、目标对象距离和使用的特征提取算法精度等.在使用分辨率较低的相机进行图像采集时,目标物体会因为分辨率较低而造成特征不明显,在进行内角点提取时会有较大的偏差;在世界场景中,当激光雷达距离目标物体较远时,会使点云中目标物体部分的三维点比较稀疏,从而造成目标物体点云的边缘特征不显著,在进行平面边缘拟合时会有较大的误差;联合外参的旋转矩阵也会受到目标对象距离的影响,距离越远,偏移越大,旋转矩阵的误差也越大.本文无法对影响标定精度的因素逐一分析,本文假设在标定板制作、特征提取算法精度高的理想情况下,使用高分辨率(5184×3456)相机与激光雷达构建固定的采集系统,设定采集系统与目标物体距离不超过激光雷达有效测量距离1/2的情况下进行数据采集,以保证标定产生的误差不会对后续的目标点云边缘提取造成影响.

2.3 目标点云边缘提取

确定目标点云的边缘并以边缘进行分割有助于提高分割的效率与精度,但是点云包含的空间信息多于二维图像,其对应几何结构更复杂,无序点云的邻域结构非常复杂,同时也存在噪声、密度不均匀、遮挡等问题,通常需要对原始的三维点云数据进行手动分割、目标识别等步骤,再根据某一特定目标检测边缘,所以直接对点云边缘进行提取与分割的效率与精度都比较低[17].从图像中进行边缘检测与提取的方法效率与精度都比较高,因此可以借助与点云相对应的二维图像进行目标点云边缘的提取.

在对点云进行目标对象边缘的三维点提取之前,需要先对图像中的目标对象进行边缘提取.由于本文的研究重点为点云分割算法,故对图像中的目标对象采用手动提取.提取出目标对象后,采用Canny算法[18]行边缘提取,获得边缘的所有像素点集合{pP-edge(u,v)}.

根据公式(6)的对齐关系,原始点云中的所有三维点{PL(XL,YL,ZL)}转换为对应图像的像素点{pL(u,v)},同时在转换的过程中为每一个从原始点云三维点转换的像素点建立该像素点映射到其对应三维点的索引pL(i)→PL(i),供之后在提取目标点云边缘时调用并查询,即：

(ui,vi)→(XL(i),YL(i),ZL(i))

(7)

在将原始点云中所有的三维点从三维坐标PL(XL,YL,ZL)转换为像素坐标pL(u,v)并建立好索引表{(pL,PL)}后,取其中一个像素点pL(i)(ui,vi),计算该点到图像中目标对象边缘像素点任意一点pP-edge(j)(uj,vj)的欧氏距离d(i,j),即：

(8)

在公式(8)中依次代入{pP-edge}和{pL}中所有的像素点进行计算,设定距离阈值ε,当d(i,j)<ε时,将点pL(i)确定为目标点云的边缘点,再调用索引表{(pL,PL)}查询pL(i)→PL(i)的映射关系,将与pL(i)对应的点PL(i)划入目标点云边缘的候选集{P′L-edge(XL,YL,ZL)}中,最后将候选集中重复点去除并对孤立的离群点进行滤波,得到目标点云的边缘点集{PL-edge(XL,YL,ZL)}.目标点云边缘的密集程度与ε成正比,点云数据中每一个点表达一定的信息量,某个区域点越密集有用的信息量越大.孤立的离群点信息量较小,其表达的信息量可以忽略不计.

2.4 种子点和生长策略的设定

传统的基于区域生长点云分割算法中因种子点选取不当或特征提取不准确、无法得到确定的分割边缘等问题,易出现目标点云出现欠分割或过分割现象[4].针对这些不足,本文通过目标点云边缘确定分割界限,并将边缘点划入种子点集来进行区域生长分割.边缘点具有强度变化显著的特点,因此可以有效确定目标分割的区域,避免出现欠分割以及过分割现象.最后根据边缘的性质设计出相应的生长策略进行分割,从而得到分割结果.

目标点云的分割界限可以通过目标点云的边缘确定.在目标点云边缘点集合中,从所有边缘点坐标中取最大的X值,Y值和Z值作为分割的上限,记为Xmax,Ymax和Zmax;从所有边缘点坐标中取最小的X值,Y值和Z值作为分割的下限,记为Xmin,Ymin和Zmin.

在进行区域生长分割点云之前需要求解原始点云的法向量与曲率.由于法向量的特性是垂直于其当前点所在的切平面,所以需要先通过当前点的邻近点拟合出一个局部平面再进行法向量的求解.拟合出的平面应当具有候选点到这个平面距离最小的性质.用主元分析(Principal Component Analysis,PCA)算法[19]可以找到一组新的变换后的正交基,这组正交基是给定点集的最佳表达,使得变换后的数据有着最大的方差.具体来说,根据原始点云中的当前点选择k个近邻点,并建立一个平面,使得当前点与选出的k个近邻点到这个平面的距离最小,计算得到趋近拟合平面中心点的目标点,将k个近邻点到目标点的向量组成矩阵Y,求出协方差矩阵S=YYΤ的特征值λ1,λ2,λ3,并从中选出最小的特征值λmin,对应的单位特征矢量n就是法线矢量,该点的曲率H为：

(9)

计算得到{PL}中每个点的法向量n与曲率H后完成对原始点云的预处理.

由于传统的区域生长算法需要根据选定的种子点的性质设定相应的生长策略进行点云分割,不同的种子点性质各不相同,故本文根据边缘点性质设计出了相应的分割算法.将上一步得到的目标点云分割界限Xmax,Ymax,Zmax,Xmin,Ymin,Zmin,近邻点数k以及计算出每个点法向量n与曲率H后的原始点云{PL};第2.3节得到的目标点云边缘{PL-edge};设定的法向量角度阈值θth和点法向量阈值Hth作为输入,聚类三维点集C作为分割结果并作为输出.

将{PL-edge}设置为种子点集合Q={PL-seed}后,对种子点PL-seed进行近邻点搜索,在分割界限内的近邻点设为PL-ngb,如果PL-ngb的曲率HL-ngb

(10)

其中nL-seed为PL-seed的法向量,nL-ngb为PL-ngb的法向量.

表2 基于边缘的区域生长分割算法实现Table 2 Algorithm for region growing segmentation with edge

如果θL-ngb<θth且PL-seed和PL-ngb不属于C,将PL-seed和PL-ngb划入C中,并将PL-seed从Q中删除,直到Q为空停止,输出C作为分割结果.

基于边缘的区域生长分割算法的具体伪代码表述如表2所示.

3 实验结果与分析

3.1 相机与激光雷达标定

实验系统的相机采用佳能EOS 1300D数码单反相机(分辨率5184×3456);三维激光雷达采用北阳URG-4LX-UG01和旋转云台构成,可以采集稠密三维点云(垂直684点,水平3600点).具体采集装置如图3所示.

图3 数据采集装置Fig.3 Data acquisition device

标定中采用7×10的黑白棋盘格标定板,采用数码单反相机和激光雷达所构建的数据采集系统同时采集10组不同位姿下标定板的图像和点云进行标定.由于激光雷达的有效测量距离为5米,故设定标定板摆放的位置与采集系统之间的距离不超过2米.对相机进行内参标定后可以得到相机内参K,对相机与激光雷达进行标定后采用Levenberg-Marquardt(L-M)算法[20]进行非线性优化可以得到联合外参的旋转矩阵R与平移向量t,其中具体结果为：

根据以上参数可以建立图像与点云的对齐关系(6).

为了验证标定精度,使用标定后的设备分别采集10组包含不同矩形目标对象的图像和点云来进行标定误差分析.通过包含矩形目标对象的图像提取出矩形的几何中心像素坐标,再手动分割出矩形点云并采用对齐关系重投影到对应的图像中,提取出重投影的几何中心像素坐标,最后计算重投影的几何中心像素坐标到几何中心像素坐标的u轴与v轴偏移像素,具体如表3所示.

表3 标定中的像素偏移误差Table 3 Pixel offset error in calibration

根据表3的结果,可以看出u轴和v轴的偏移像素最大不超过10.最后计算出重投影的几何中心像素坐标到几何中心像素坐标u轴的平均偏移像素为-2.5685,v轴的平均偏移像素为5.1410.由于图像的分辨率为5184×3456,则u轴的平均相对误差为0.0495%,v轴的平均相对误差为0.1488%,u轴和v轴的平均相对误差均没有超过0.15%,由此可得u轴和v轴像素偏移基本不会影响到目标点云边缘点提取精度.

3.2 目标点云分割

使用已标定的设备进行数据采集,分别对含有规则几何体、不规则几何体以及多个目标物体的场景下进行数据采集.将采集到的图像进行目标对象边缘的提取,再根据公式(6)的对齐关系提取出目标点云的边缘三维点,最后根据当前原始点云的状况设定相关的阈值并以目标点云的边缘三维点作为种子点对原始点云进行区域生长分割,得到目标点云.在包含不同目标对象场景下使用本文算法进行稠密点云分割的可视化实验流程具体如图4所示.

3.3 对比实验

从图4的实验结果可以看出,使用本文算法对原始稠密点云进行目标点云的分割后,可以比较完整地分割出原始点云中的目标点云,但是也存在少量的欠分割以及过分割问题.本文分别对含有规则几何体、不规则几何体以及多个目标物体的场景进行图像和点云数据的采集,其中每种场景下分别采集包含不同目标物体的5组数据,三种场景下总共采集到15组数据.再分别采用基于最小曲率值选择种子点的区域生长分割算法[21],基于RANSAC算法选择种子点的区域生长分割算法[22],基于RANSAC算法的欧氏聚类算法[23]与本文算法对原始稠密点云进行分割,将不同算法的分割结果分别与手动分割出的目标点云进行对比,以此来验证本文算法的欠分割与过分割状况以及分割精度.部分数据组的实验结果如图5所示.

图4 在包含不同目标对象场景下使用本文方法分割的可视化实验流程Fig.4 Visualization experiment procedures of our method in the scene with different objects

图5 在包含不同目标对象场景下使用不同算法分割的实验结果Fig.5 Results of different algorithms in scenes with different objects

从图5中的实验直观结果可以看出,在目标物体为不规则物体的实验场景下,本文算法与基于最小曲率值选择种子点的区域生长分割算法、基于RANSAC算法选择种子点的区域生长分割算法以及基于RANSAC算法的欧氏聚类算法相比具有较好的分割结果.其它算法的分割结果都有较明显的欠分割现象和过分割现象.

为了评价本文算法与其它算法的分割性能,本文分别采用欠分割率(Under-Segmentation Rate,UR)、过分割率(Over-Segmentation Rate,OR)和交并比(Intersection-over-Union,IoU)[24]作为评价标准来评价各算法的分割结果,UR、OR和IoU定义如下：

(11)

(12)

(13)

其中,RS表示手动分割出的目标点云三维点集合;TS表示算法分割出的目标点云三维点集合;RS∩|RS-TS|表示本应该包含在分割结果中,实际却不在分割结果中的三维点集合;TS∩|RS-TS|表示本不应该包含在分割结果中,实际却在分割结果中的三维点集合;RS∩TS表示正确分割的三维点集合.其中UR∈[0,1],UR越大表明欠分割现象越严重;OR∈[0,1],OR越大表明过分割现象越严重;IoU∈[0,1],IoU越大表明分割精度越高.

具体对比实验数据如表4所示.其中数据集分类中原始点云均值表示每种场景下5组原始点云数据的平均三维点数,手动分割结果均值表示每种场景下5组原始点云数据手动分割出的目标点云的平均三维点数;算法中curvature+RGS,RANSAC+RGS与RANSAC+ECS分别表示基于最小曲率值选择种子点的区域生长分割算法,基于RANSAC算法选择种子点的区域生长分割算法与基于RANSAC算法的欧氏聚类算法;评价指标中UR、OR、IoU分别表示欠分割率、过分割率和交并比.

表4 不同场景下的不同区域生长分割算法实验结果对比Table 4 Comparison of different region growing segmentation algorithm experimental results in different scenes

根据表4的结果,本文算法在对不同场景下的原始稠密点云进行目标点云分割时,交并比分别为89.93%,86.28%,85.73%,均达到了85%以上.在目标物体为规则几何体的场景中,由于目标物体特征变化强度不大,其他算法都可以比较完整地分割出目标对象,本文算法相比其他算法没有显著优势;在目标物体为不规则几何体的场景中,其他算法会受到目标物体特征变化强度较大的影响而导致分割精度下降,本文算法通过边缘确定分割界限可以显著提高分割精度,相比其他算法有显著优势;在多个目标物体的场景中,由于目标物体包含规则几何体与不规则几何体,在不规则几何体较多的场景中,本文算法相比其他算法有显著优势.

4 结 论

为了解决传统的区域生长法因种子点选取不当以及生长策略设计不当而导致出现欠分割与过分割现象的问题,本文通过边缘特征变化显著的性质提出了一种融合图像提取目标点云边缘并将边缘点作为种子点的区域生长分割算法.实验结果表明,该算法在借助图像提取出目标点云边缘并将边缘点作为种子点的条件下进行分割,可以从数据量大的稠密点云中以较高的精度分割出目标点云,使得分割结果在很大程度上避免了欠分割与过分割现象.

本文没有对算法中的相关阈值设置进行研究,而是采用人工设定,用不同阈值进行分割与滤波,从中选取最优的分割结果.下一步的研究工作是寻找点云数据特征的变化规律,尝试自动选取合理的阈值参数的方法,进一步提高算法效率.有兴趣的读者可以下载本文算法的实验数据和MATLAB代码进行研究.