基于改进的局部表面凸性算法三维点云分割

王雅男，王挺峰，田玉珍*，孙 涛

(1 中国科学院 长春光学精密机械与物理研究所激光与物质相互作用国家重点实验室，吉林 长春 130033;2中国科学院大学，北京 100049)

基于改进的局部表面凸性算法三维点云分割

王雅男1,2，王挺峰1，田玉珍1*，孙 涛1

(1中国科学院 长春光学精密机械与物理研究所激光与物质相互作用国家重点实验室，吉林 长春 130033;2中国科学院大学，北京 100049)

点云分割是点云分类、识别以及三维重建等处理的基础，分割结果对后续应用影响巨大。本文提出利用连通点集改进局部表面凸性算法中邻近点关系的方法，解决目前激光三维成像系统点云分割算法在处理复杂环境散乱点云时存在分割过度及分割不充分的问题，通过主顶点与周围点构成连通集，作为分割判断局部子点集，形成有效分割区域。该方法解决了常用点云分割方法无法对形状不规则物体进行有效分割的问题，提高了分割精度。算法实验结果表明，相比于最小切割算法和区域生长算法，基于连通点集的改进局部表面凸性算法对实际路面环境信息的分割效果更好，并能在一定程度上避免分割过度和分割不充分的情况，证明该方法适用于复杂环境散乱点云数据分割。

激光三维成像；点云分割；连通点集；局部表面凸性

1 引 言

近年来，激光三维成像技术[1-2]不断发展，三维成像系统在逆向工程[3]、数字城市、智能汽车等方面的应用越来越广泛，与此同时，数据的获取与处理速度[4-9]也越来越快。激光三维成像系统采集的数据是大量散乱点云数据，将具有不同属性的物体分开，需进行点云分割处理，因此，点云分割是点云数据处理的关键部分，同时为后续点云的分类和识别处理提供基础信息。

早期的点云分割算法主要是基于对象模型[10]和边缘特性[11-12]实现数据分割，模型分割的计算复杂度高，需要大量的对象模型，并且只能通过边界对特定对象进行粗定位。边缘特性点云分割的处理对象是表面平坦且具有突出边缘特性的物体数据，主要应用于工业生产中。但由于现在所探测的室外环境噪声强，物体几何形状复杂，不符合上述算法的应用条件，因此这些算法都不适用于分割室外复杂环境点云数据。

目前，对于室外大量点云数据的分割算法主要有两种[13]:一种是对恒定点分布进行分割的算法；另一种是应用于室外单扫描数据分割的算法。恒定点分布分割算法的处理对象是机载点云数据、室外地面数据和室内探测数据，主要是利用区域生长算法等快速分割方法，选取具有相同方向的法向量[14]、同样的曲率特征[15]和平面特性[16]的种子节点进行区域生长。这种算法通常是以数据点之间的几何关系作为阈值条件判断数据点是否属于同一区域，只局部地考虑单个点的归属，具有很大的局限性，容易受到噪声的影响。室外单扫描数据分割算法主要应用于智能汽车，与恒定点分布分割算法相比，针对智能汽车这种特定的应用环境做了改进。汽车行驶环境是地面，而车载扫描设备探测的数据主要是地面物体，由此将分割算法调整为首先对地面进行探测，之后再把地面障碍物进行分割，这样能够较大程度地提高处理速度。典型方法有郭春朝[17]和Klasing[18]等人在相关文献中提到的分割算法，郭春朝提出的算法主要是针对地面障碍物的分割，而Klasing的算法是通过观察距离不同和法向量的变化进行分割，对体积大的物体分割效果比较好，但无法对小体积物体分割。

虽然目前已有的算法，在实际应用方面各有优势，但它们主要适用于一些形状比较规则的常见物体，尚无对任意环境(包括植被覆盖的山区环境在内)中的任何物体分割都适用的标准准则，不能很好的用于分割复杂环境散乱点云数据。因此对于实际应用，需要研究更有效的分割算法。

本论文根据实际点云数据特点，利用连通点集对局部表面凸性算法[13]中邻近点关系进行分析并对算法改进。改进的局部表面凸性分割算法可用于散乱点云分割处理，该算法适用于复杂环境的散乱点云分割。

2 局部表面凸性

局部表面凸性点云分割算法的核心就是局部表面凸性的概念。在数学理论中，如果一个几何体上任意两点所连的线段都在它的内部，那么这个集合体就被称为凸面体。凸面可以通过计算表面曲率来确定，正曲率表示是凸面，负曲率则表示为凹面，曲率为0则表示为平面。如果把平面结构也归为凸面结构，那么自然界中大部分物体都是由具有凸面结构的部分组合而成，而不同物体之间的连接处一般为凹面结构，因此可以用表面凸性来将不同的物体分割开。将表面凸性应用到三维点云数据上，凸面的概念需适当调整。

用局部凸性衡量两个相邻测量点周围局部表面的特性。如图1所示，任意两个点pi和pj，其位移向量di, j=-dj,i，如果两个法向量ni和nj方向相同或者任一表面上的所有点都处于另一个表面之下，那这两个点就满足局部凸性(local convexity)，通常用凸度值ci, j来表示。若两个点满足局部凸性，ci, j的值就接近于1，反之，则接近于0。ci, j的定义式[13]为：

图1 局部表面凸性 Fig.1 Local surface convexity

(1)

式中，vnSim、vnSimF、vconv和vconvF都为常数，vnSim为法向相似软阈值，vnSimF为vnSim处的切线斜率，vconv为凸度软阈值，vconvF为vconv处的切线斜率。

S型函数:

(2)

式中，θ为有效阈值，m为影响阈值处切线斜率的范围参数。

3 局部表面凸性的点云分割算法

算法的主要步骤是：

(1)邻近点关系分析

为减少邻近点搜索耗费的时间，对点云数据进行预处理，通过三角剖分，建立各数据点之间的直接相邻关系，构建局部连通点集，为分割判断提供局部子点集。

(2)边界判定

由于三维点云中的邻近点不一定属于同一个物体，需要对局部连通点集中的点进行物体边界判定，判断获得的局部连通点集是否属于同一物体。根据深度值的不连续可以判断物体边界的存在以及邻近像素点是否属于同一部分，对于任意两个邻近像素点i，j，用连接值li,j判断边界情况，如果li,j越接近于1，说明这两个邻近像素点越有可能是属于同一部分的点，反之，越接近于0，则越不可能属于同一部分。利用模糊逻辑方法[19]定义的li,j的公式为:

(3)

式中，vrDiff和vrNDiff都为常数，vrDiff为深度值变化的软阈值，vrNDiff为深度值的邻近点相对变化软阈值，vrNF(r)为在vrNDiff处的切线斜率，计算公式为2·exp(-0.14r)+0.25。如(ri-rj) → 0同时(rh-ri) → 0或(rj-rk) → 0，会出现奇点，此时将连接值li,j设为1，li,j满足对称性，即li,j=lj,i。

(3)确定边界量bi,j

连接值li,j通常只能判断距离较近点是否处于边界处或处于与背面的连接处，而对于距离较远点的边界情况还需要利用边界量bi, j进行判断，bi, j的定义公式为:

(4)

式中,vrSB和vωOB为常量，vrSB为探测阴影边界的距离差，vωOB为物体边界在边界量中的权重。

(4)确定点云数据分割标准

通过前面的计算可以得到凸度值ci,j和连接值li,j，利用ci,j与li,j结合可以获得分割阈值：

(5)

式中，vst为分割标准阈值。si,j具有对称性，满足si,j=sj,i。如果si,j等于true，说明点pi和pj是属于同一部分的点。遍历点云数据中所有点，进行分割标准判断，将属于同一部分的点分到同一连通集中，将不同连通集分割开，获得分割结果。

4 邻近点关系分析改进

实际应用中获取的数据为大量散乱点云数据，在利用三角剖分进行邻近点关系分析的过程中，由于获取的路面信息数据点之间关联性较差，点与点之间没有直接的相邻关系，无法建立三角网格，不能得到有效分割，因此，本文采用连通点集代替三角网格确定邻近点关系，将获取的连通点集作为分割所需要的局部子点集进行分割。首先将三维散乱点云数据转化为虚拟深度图像，二维深度图像中的每一个像素点都带有相应距离值r的信息，相邻像素点之间具有潜在的邻域关系，通过将三维点投影到二维图像上，三维点的距离信息存储为二维图像的像素点。利用深度图像像素点的有序性，可以在点云投影深度图像的同时，建立三维数据点与像素序列之间的对应关系。将每一像素点与其周围像素点构成邻近点关系，称之为连通点集，如图2所示，得到分割所需的局部子点集。连通集内邻近点的数目可以自由设定，如可以取4、8、16等。

图2 两种连通点集 Fig.2 Two connected point sets

获取局部连通集之后，对每个连通集从主顶点开始利用公式计算li, j、bi, j和分割阈值si, j，进行分割标准判断，确定是否是同一部分的点。若为同一部分的点，则这两个点同时标示为1；若不是同一部分的点，则主顶点标示为1，另一个点标示为2；之后顺时针依次遍历所有测量点，若为不同部分的点则标示依次加1，若为同一部分的点则用相同的标示进行标记，直到将所有测量点都加上标示。通过分割标准判断把所有属于同一部分的点都带上同样的标示，这样就把同一部分的点归到一个集合中作为分割部分。将不同的分割部分分割开，直到将所有散乱点云数据都分割完为止，形成有效分割区域。

5 实验结果及分析

三维点云数据分割与数据本身特点以及应用领域密切相关。目前，对于分割效果的评价问题仍然尚未解决，没有一个定性和定量的指标对分割效果进行评估，只能利用目视分析的方法对点云数据分割效果进行定性评价。本文通过最小剪切分割算法[20]、区域生长算法[14]与改进的八连通局部表面凸性点云分割算法对同一场景数据的分割结果对比，对本文改进算法的分割效果进行评价。

为了验证文中算法的有效性，现选取实验数据进行算法评估。此处选取的分割实验数据为德国卡尔斯鲁厄理工学院和芝加哥丰田技术研究所联合创办的自主驾驶平台Annieway在卡尔斯鲁厄进行实际路面探测所获得的三维点云数据，Annieway装配有Velodyne HDL-64E激光扫描仪，可以实时釆集360°全景的三维信息。在算法评估时选取了两个不同的场景，场景A为十字路口，该区域路面开阔，但并不平坦，路面上分布着正在行驶的车辆、步行和骑自行车的人，路边还零星分布着路灯和树木，路面两侧还有围墙遮挡，路面情况复杂。场景B为拐角路口，路边有围墙遮挡，一辆汽车停放在拐角处，拐角另一边还分布有几棵树，旁边还有一个长着植物的花坛。两个场景的实际信息十分复杂，需要处理的数据点较多。

为了获得最优的分割结果，避免过分分割和不充分分割，通过多次数据测试和分割效果分析，对实验参数进行优化，将各个参数阈值分别设定为：vnSim=14.806 2°，vconv=-7.67°，vnSimF=10，vconvF=1.165，vrDiff=0.148，vrNDiff=1.907 82，vrSB=0.03 m，vωOB=2，这些参数阈值的设定值对任意场景均可适用。分割标准阈值vst的取值范围为0.2～0.5，分割某一场景时，只需调整优化vst的大小，即可获得最优分割结果。经过验证，分割场景A和B的数据时，vst取0.38分割效果最优。

图3 3种算法对场景A进行分割的结果 Fig.3 Segmentation results of three algorithms for scene A

图3和图4分别为3种分割算法对场景A和场景B的分割结果，在结果图中将分割出的不同物体利用不同颜色标示。对比两种场景的分割结果图，图3和图4中(a)图利用最小剪切算法的分割效果最差，只能将数据场景中体积较大物体的大概轮廓分割出来，无法分辨场景中具体的物体信息；图3 图4中(b)图和(c)图利用区域生长算法和八连通局部表面凸性算法获得的分割效果明显，能够将实验数据场景清晰展现出来；图3和图4中(b)图中对于地面、墙面、汽车等具有平面结构且形状较为规则的物体都是用不同颜色标示的，分割效果较好，而对于形状不规则的行人、植物等都不能较好分割。而在本文改进的八连通局部表面凸性算法的分割结果在图3和图4的(c)图中可以看到颜色标示分明，对于形状规则的地面、墙面、汽车以及形状不规则的行人、植物等都取得了较好的分割结果，不同物体之间对比明显。

图4 3种算法对场景B进行分割的结果 Fig.4 Segmentation results of three algorithms for scene B

图5 两种算法分割结果 Fig.5 Segmentation results of two algorithms

在场景A中选取一小块场景利用区域生长算法和八连通局部表面凸性算法进行分割，结果如图5所示。区域生长算法结果图5(a)中骑自行车的人只有头部附近是用与地面不同的颜色进行标示的，身体下部、自行车以及旁边的汽车下部都与地面颜色相同，不能区分，车后的路灯以及旁边站着的行人已经完全无法分辨。而本文所采用的八连通局部表面凸性算法结果图5(b)中汽车与车后的路灯及行人分割比较完整，用与地面不同的颜色标示，能够清楚分辨出来，骑自行车的人与地面颜色对比鲜明，清晰可辨，但自行车下部与地面接触的部分与地面分割到一起，说明该算法在分割细节方面仍有待改进。

选取场景A中有代表性的物体数目进行统计，如表1所示。对统计结果进行分析，区域生长算法能提取到83%的有效数据点，而八连通局部表面凸性算法能提取到90%的有效数据点，在数据点提取方面，八连通局部表面凸性算法效果较好。对于车辆等具有平面结构的规则物体，两种算法都能进行有效分割，分割效果都比较好。对于行人、路灯等形状不规则的物体的分割，区域生长算法的对物体分割的完整度远远比不上八连通局部表面凸性算法。综合分析，八连通局部表面凸性算法更适用于复杂环境散乱点云数据的分割。

表1 分割结果统计

6 结 论

本文采用连通点集的方式对局部表面凸性的点云分割算法进行改进，用连通点集代替三角网格确定邻近点关系，将获取的连通点集作为分割所需要的局部子点集进行分割。根据实际城市路面三维点云数据分割实验和3种算法的对比分析，可知本文提出的八连通局部表面凸性点云分割算法，对实际路面点云数据中的物体体积大小、形状是否规则都能够进行有效分割。由此可见，八连通局部表面凸性算法对于复杂环境散乱点云数据具有良好的分割效果，同时，算法中设置的分割标准阈值vst可以根据分割数据特点进行调整优化，较好的避免了过度分割和不充分分割。实验表明，本文改进的基于连通点集的局部表面凸性点云分割算法在实际应用中能够同时分割不平坦路面信息和形状不规则的路面物体，有较好的应用前景。

[1] 王飞,汤伟,王挺峰,等.8×8APD 阵列激光三维成像接收机研制[J].中国光学,2015,8(3):422-427. WANG F,TANG W,WANG T F,etal.. Design of 3D laser imaging receiver based on 8×8 APD detector array[J].ChineseOptics,2015,8(3):422-427.(in Chinese)

[2] 孟庆季,张续严,周凌,等.机载激光 3D 探测成像系统的关键技术[J].中国光学,2011,4(4):327-339. MENG Q J,ZHANG X Y,ZHOU L,etal.. Key technologies of airborne laser 3D detection imaging system[J].ChineseOptics,2011,4(4):327-339.(in Chinese)

[3] 周森,郭永彩,高潮,等.基于三维激光扫描的移动大尺寸圆柱体工件长度快速检测系统[J].光学 精密工程,2014,22(6):1524-1530. ZHOU S,GUO Y C,GAO CH,etal.. Rapid length measuring system for mobile and large scale cylinder workpieces based on 3D laser scanning[J].Opt.PrecisionEng.,2014,22(6):1524-1530.(in Chinese)

[4] 吕恒毅,李祥之,韩诚山,等.遥感相机静态调制传递函数的地面测试原理[J].液晶与显示,2015,30(5):851-856. LV H Y,LI X ZH,HAN CH SH,etal.. Principle of static modulation transfer function measurement for remote sensing cameras[J].ChineseJ.LiquidCrystalsandDisplays,2015,30(5):851-856.(in Chinese)

[5] 张涛.红外系统小目标成像自动调光方法[J].液晶与显示,2016,31(4):399-403. ZHANG T. Method of auto light control for small target in infrared system[J].ChineseJ.LiquidCrystalsandDisplays,2016,31(4):399-403.(in Chinese)

[6] 石俊霞,李佩玥,李洪法,等.遥感TDICCD相机侧摆成像及定位精度优化[J].液晶与显示,2014,29(5):777-784. SHI J X,LI P Y,LI H F,etal.. Scroll imaging of space TDI CCD remote sensing camera and optimazation of image location accuracy[J].ChineseJ.LiquidCrystalsandDisplays,2014,29(5):777-784.(in Chinese)

[7] 靳永亮,王延杰,丁南南,等.改进的红外弱小目标检测方法[J].液晶与显示,2011,26(4):555-560. JIN Y L,WANG Y J,DING N N,etal.. Improved method for small infrared target detection[J].ChineseJ.LiquidCrystalsandDisplays,2014,29(5):777-784.(in Chinese)

[8] 王田,刘伟宁,孙海江,等.基于复杂度和方向梯度的红外弱小目标检测方法[J].液晶与显示,2012,(5):692-696. WANG T,LIU W N,SUN H J,etal.. Detecting algorithm of infrared small dim targets based on complexity and orientation gradient[J].ChineseJ.LiquidCrystalsandDisplays,2012,(5):692-696.(in Chinese)

[9] 郭萌,赵岩,王世刚,等.基于区域选择的红外弱小目标超分辨率复原算法[J].液晶与显示,2016,31(4):415-420. GUO M,ZHAO Y,WANG SH G,etal.. Infrared dim-small target super-resolution restoration algorithm based on region selection[J].ChineseJ.LiquidCrystalsandDisplays,2016,31(4):415-420.(in Chinese)

[10] RABBANI T,VAN DEN HEUVEL F,VOSSELMANN G. Segmentation of point clouds using smoothness constraint [J].InternationalArchivesofPhotogrammetry,RemoteSensingandSpatialInformationSciences,2006,36(5):248-253.

[11] JAGANNATHAN A,MILLER E L. Three-dimensional surface mesh segmentation using curvedness-based region growing approach[J].IEEE,2007,29(12):2195-2204.

[12] ZAVODNY A,FLYNN P,CHEN X. Region extraction in large-scale urban lidar data[J].IEEE,2009:1801-1808.

[13] GUO C,SATO W,HAN L,etal.. Graph-based 2D road representation of 3D point clouds for intelligent vehicles[J].IEEE,2011,30(1):715-721.

[14] KLASING K,WOLLHERR D,BUSS M. A clustering method for efficient segmentation of 3D laser data[J].IEEE,2008:4043-4048.

[15] ZADEH L A. Fuzzy sets as a basis for a theory of possibility[J].FuzzySets&Systems,1978,1(1):3-28.

[16] GOLOVINSKIY A,FUNKHOUSER T. Min-cut based segmentation of point clouds[J].IEEE,2009:39-46.

Improved local convexity algorithm of segmentation for 3D point cloud

WANG Ya-nan1,2, WANG Ting-feng1, TIAN Yu-zhen1*, SUN Tao1

(1.StateKeyLaboratoryofLaserInteractionwithMatter,ChangchunInstituteofOptics,FineMechanicsandPhysics,ChineseAcademyofSciences,Changchun130033,China; 2.UniversityofChineseAcademyofScience,Beijing100049,China)

Segmentation for point cloud is the basis of classification, recognition and reconstruction of point cloud datasets and the segmentation result plays an important role in following research. In this paper, we propose a method using connected point sets to analyze and improve the relationship between adjacent points in the local convexity segmentation, to solve problems of oversegmentation and undersegmentation when using the existing algorithms to segment scattered point cloud data in complex environment in 3D laser imaging system. By this method we use the main vertex and neighbors to constitute connected point sets which can be local point subsets of segmentation and form the effective segmented regions. The method solves the problem of the irregular object′s segmentation, which can not be accomplished by common methods, and improves the accuracy of segmentation. Compared with the min-cut based segmentation and region growing segmentation, the improved local convexity segmentation of connected point sets is better for segmentation results of actual road information, and it can avoid oversegmentation and undersegmentation to some extent. It proved that this method is suitable for segmentation of scattered point cloud data in complex environment.

three-dimensional laser imaging;segmentation for point cloud;connected point sets;local convexity

2017-01-23；

2017-03-30

国家高技术研究发展计划(863计划)资助项目 Supported by National High-tech R&D Program of China

2095-1531(2017)03-0348-07

TN958.98

A

10.3788/CO.20171003.0348

王雅男(1992—)，女，山东德州人，硕士研究生，2014年于哈尔滨工业大学获得学士学位，主要从事激光主动探测方面的研究。E-mail:arianwang@outlook.com

田玉珍(1985—)，男，内蒙古呼和浩特人，博士，助理研究员，主要从事激光主动照明成像、激光大气传输湍流效应等方面的研究。E-mail:tianyz@ciomp.ac.cn

*Correspondingauthor,E-mailtianyz@ciomp.ac.cn