三维点云数据分割原理及应用

师域轩++褚智威

摘 要：点云数据呈现海量增长趋势，对点云数据进行有效分割是数据处理的基础与前提，其在3D打印、虚拟现实、增强现实、智慧城市、智能交通等领域均有极其广泛的应用。本文通过阅读国内外文献，总结了点云分割的基本原理和特征，对比了各类点云分割算法的特点和适用场景，最后，结合实践应用需要，指出了现阶段点云分割算法存在的问题和发展趋势。

关键词：点云数据 分割算法 混合分割

中图分类号：TP39 文献标识码：A 文章编号：1672-3791（2017）08（c）-0242-05

Abstract： Point cloud segmentation is an important research topic of pointcloud processing， and it has many important applications in the field of intelligent vehicle driving， scene recognition and understanding. This paper introduces the basic principles and characteristics of point cloud segmentation. And the principle， characteristics and application environment of various point cloud segmentation algorithms aresummarized and analyzed. Finally， the problems and development trend of the existing segmentation algorithms are also discussed.

Key Words： Point cloud； Segmentation； Hybrid Segmentation

图形图像技术飞速发展，激光扫描仪、深度扫描仪、Kinect等硬件三维扫描设备的广泛使用产生了大量的点云数据，与此同时，3D打印、虚拟现实、增强现实、场景重建的应用环境对点云数据的处理提出种种需求。2011年，Rusu[1]提出并建立了点云实验室，专注先进的三维感知技术和处理算法的研究。点云数据的处理，特别是点云分割是三维重建、场景理解[2]和目标识别跟踪[3]等各项应用或任务处理的基础，分割结果有利于对象识别与分类，是人工智能领域的研究热点问题，也是难点问题，已经受到越来越多科研院所和科技公司的关注。

点云分割是通过一定的方式方法，将使用特定设备获取到的杂乱无章的点云数据，分割成若干个互不相交的子集，每一个子集中的数据具有基本相同的属性特征或一定的语义信息，这样的话，在场景理解或虚拟重建时，能将这些点云数据视为一个独立物体上的数据，如此处理，就可以方便的确定目标的形状、大小等属性特征。

目前，由于采集设备的技术局限性，通过各种方式获得的点云数据的采样密度是不均匀的，通常是无序、稀疏的，并且掺杂有大量的噪声点和异常点。此外，点云数据的表面形状和分布可以是符合物理特性的任意的形式，没有固定或者鲜明的统计分布特点，同时，点云数据冗余性高、采样密度不均匀且缺少明确的结构特征。以上点云数据自身的种种特点，决定了实现点云数据分割的技术难度相当大，因此也成为一个研究的热点和难点。

1 点云分割算法分类

笔者通过阅读国内外文献，整理出目前用于点云分割的6种主要方法：基于边缘的分割算法、基于区域增长的分割算法、基于属性的分割算法、基于模型的分割算法、基于图的分割算法和混合分割算法。分别对其原理和应用详细介绍如下。

1.1 基于边缘的分割方法

物体的边缘线条能够简单的勾勒出其形状特性。基于边缘的点云分割算法，通过检测边缘区域即点云强度快速变化或者表面法向量急剧变化的区域，勾勒出点云数据中隐藏的边缘信息來得到分割区域。

基于边缘的分割算法是Bhanu等[4]在1896年首先提出的，其通过计算点云数据的梯度信息、检测单位法向量的方向变化来检测点云数据边缘。1999年，Jiang等[5]提出了一种基于扫描线的边缘检测算法。该算法给出了最优边缘检测的定义，提供了保证边缘强度的原理和几何解释。和Bhanu的算法相比，该算法不仅提高了点云的分割质量，而且大大提升了算法的运行时间，但其只适用于深度图像的分割，且对于密度分布不均匀的深度图像分割效果差。2001年，Sappa[6]提出了一种通过二维边缘图提取闭合轮廓的边缘检测策略来实现点云的快速分割。

基于边缘的分割算法原理简单、分割速度快，在早期车牌识别[7]、机场快速安检[8]，机场跑道识别[9]等领域有较好的应用，但是由于受噪声和点云的密度影响较大，算法的分割精度较低，不适合处理复杂的点云数据。

1.2 基于区域增长的分割算法

基于区域增长的点云分割算法是在邻域范围内，将具有相同属性的点结合组成孤立区域，同时保证其余周围区域的差异性最大。与基于边缘分割算法相比，基于区域增长的算法抗噪声能力强，但因为其无法得到确定的分割边缘，因此易产生过分分割或者分割不足的结果。

基于区域增长的分割算法以种子曲面作为种子起点，通过相似度（如接近程度、坡度、曲率和曲面法向量等）度量，对各个种子曲面周围的离散点云进行分组，从而使种子逐步扩展到更大的曲面片。这种方法是Besl等[10]在1988年首先提出的。该算法主要包括两个步骤一是确定种子曲面；二是通过特定方式实现区域生长。2000年，Koster等[11]利用不规则图来存储区域之间的相对信息，即区域之间的相似性度量，基于相对信息对相邻区域进行比较合并，2003年，Rottensteiner等[12]利用激光雷达观测获得点云并自动生成三维模型，其首先检测建筑物的整个区域，然后利用曲率作为区域增长的条件进行平面分割，检测屋顶平面。2005年，Tovari[13]提出了一种基于区域增长的分割算法来处理机载激光点云数据。其将点云数据的法向量和点到种子平面的距离进行综合后作为相似性度量进行区域增长。2012年，Wang[14]提出一种基于区域增长的快速平面分割算法，成功应用于智能设备在室内场景中检测障碍物体。Jeremie等[15]在2013年提出一种新的超像素分割算法，可以将点云数据分割得到依附于物体边界信息的超像素块。该算法首先体素化处理点云数据并生成种子区域，在距离种子最近的连通区域内，综合考虑颜色信息、空间距离和几何特征进行区域增长，直到达到搜索边界或者没有相邻体素可以搜索时迭代过程结束。endprint

基于区域增长的分割算法适合处理大规模、复杂场景的点云数据，对噪声信息不敏感，容易实现且计算成本较低。但是这类算法性能依赖于种子的选取和区域增长策略，很难确定精确的区域边界，容易出现过分分割或者分割不足的情况。同时，约束条件或者兼容性阈值对分割结果的好坏影响较大。

1.3 基于属性的分割算法

基于属性的分割算法是一种利用点云的特征属性进行聚类的分割算法。在该算法中，每个点都对应一个特征向量，该特征向量内包含了若干个属性不同的特征值。

2001年，Filin[16]提出了一种基于表面纹理特征聚类激光点云数据的平面分割算法。该算法可以在激光点云数据上直接进行处理而不需要栅格化。Vosselman等[17]利用Hough变换实现激光点云数据的平面分割。2010年，Zhan[18]提出了一种利用法向量和颜色信息作为属性特征进行聚类的点云分割算法，之后还提出一种改进的基于欧式距离聚类的点云分割算法[19]。2012年，Dirk Holz[20]提出了一种利用表面法向量进行实时平面分割的算法，其可以实时感知周围场景中的主要目标物体，实验结果可以成功应用于机器人导航和避障。

基于属性的分割算法是一种比较稳定的分割算法，其在特征空间中实现，不受点云空间关系的影响。特征空间和聚类方法的选择很大程度上决定了算法的性能，且点云密度变化对算法影响较大，在处理大规模复杂分布的点云数据时，时间复杂性也大。

1.4 基于模型的分割算法

基于模型的分割算法利用原始几何形态的数学模型（例如平面、圆柱体、圆锥体、球体等）作为先验知识进行分割，将具有相同数学表达式的点云数据归入同一区域。

Fischer[21]在1981年提出随机抽样一致性估计算法（RANSAC算法）。算法从样本中随机抽选出一个样本子集，使用最小方差估计法对这个子集进行模型参数计算，计算所有样本与该模型的偏差，与预先设定的阈值进行比较，重复迭代直到满足结束条件为止。许多基于几何模型的点云分割算法都是在该算法的基础上发展起来的。

2007年，Schnabel等[22]对以上算法进行了改进设计，可以自动检测杂乱点云数据中的基本几何形状，用来进行网格和点云数据的分割。改进后的算法不仅增加了速度优化的步骤，同时保证了分割结果的准确性。为了打破算法对原始形状的局限性，Gelfand等[23]提出一种检测Slippable形状的分割算法，Slippable形状被定义为旋转和平移对称的形状，包括球、螺旋、平面和气缸等。算法可以通過合并原始的Slippable表面形状来进一步处理点云数据中可能包含的复杂形状。2011年，Li等[24]在RANSAC算法的基础上提出一种改进算法，在局部范围内使用RANSAC算法检测基本的几何模型，然后在全局范围内进行融合，分割并且融合得到更为复杂的目标模型。

2014年，Awadallah M[25]提出了一种基于模型的点云分割算法，算法首先将点云数据投影到二维图像网格，然后利用Snake模型来划分点云集合，实现稀疏、有噪声点云数据的良好分割。2015年，Wang等[26]介绍一种基于局部采样和统计推理的点云分割算法，利用RANSAC来确定点云数据中的平面、圆柱体和曲面。

基于模型的分割算法以数学原理为基础，算法处理速度快，而且对于噪声点和异常点不敏感。这类算法的主要限制是无法处理大规模复杂场景下的点云数据。

1.5 基于图的分割算法

基于图的分割算法利用点云数据构造图结构，每个点云在图中对应一个顶点，两个顶点之间的边连接相邻两个点云数据。每条边都被分配一个权重，用它来表示点云数据中一对点的相似性。分割的过程需保证不同分割区域之间相似性最小，而同一分割区域上相似性最大。

很多基于图的点云分割算法将分割问题转换成概率推理模型，如条件随机场模型或马尔科夫随机场模型。Schoenberg等[27]提出了一种利用马尔科夫随机场模型的分割算法，该算法处理的是将单光学相机和激光扫描仪得到的数据通过数据融合得到的深度图像。利用光学图像数据的约束条件，对稀疏的激光数据进行插值处理得到稠密的具有纹理信息的点云数据。通过综合考虑欧氏距离、像素密度和表面法线作为像素点间的相似性进行分割。该算法处理速度快，可以对城市场景的点云数据进行实时的分割处理，在场景重建中应用较广。GrabCut是一种经典的图像分割算法，利用迭代的能量函数最小化和少量的用户交互实现图像的切割。2013年，Nizar等[28]提出一种改进的GrabCut算法，并将其应用于RGBD点云数据的分割上。2014年，Geetha M[29]介绍一种利用最小生成树分割点云的算法。算法基于距离和法线信息将点云聚类为若干部分，在聚类结果基础上构建加权平面图，然后利用图对应的最小生成树对分割结果作进一步细化处理。2015年，Yang等[30]利用图模型的方法进行区域融合，通过最小化能量函数得到边界清晰的RGBD图像分割结果。

基于图的分割算法可以处理大规模复杂场景的点云数据，特别是对于带噪声或者点云密度分布不均匀的点云数据分割效果很好。然而，这类算法通常无法实现实时处理。

1.6 混合的分割算法

2010年，Ma等[31]提出一种针对点云数据形状分割的算法。该方法综合考虑谱聚类和图分割两种分割原理，用谱聚类的方法代替K最近邻算法计算的领域区间，可以更好地适应点云的采样密度，使得分割结果更精确、更贴合物体的形状。并且通过删除多余的特征向量降低了空间维度，降低了算法的计算复杂性。

2012年，Abdul Nurunnabi[32]提出一种鲁棒性激光点云分割算法，该算法结合主成分分析和基于区域增长的分割算法。该算法可以避免噪声干扰对分割造成的影响，提高分割算法的性能。endprint

2015年，D. Wolf等[33]介紹一种利用超像素和机器学习的语义分割框架，利用聚类和条件随机场结合的算法实现点云数据的分割和场景理解。

2015年，William R[34]提出了一种应用八叉树理论和图论进行点云分割的算法。算法的思想是通过融合空间关系、几何特征和外观作为特征向量，利用图论的原理进行点云分割。利用八叉树的结构来组织点云数据，通过概率的方式在体素空间内创建一个正态分布变换的特征模型，利用Hellinger距离来计算八叉树结构内点云数据的邻域距离，该算法可以提高分割结果在边界处的精确度。

2 讨论

从国内外研究和应用现状来看，尽管点云分割已经进行了大量的、面向不同应用问题的研究，但是还没有一种适合所有应用的分割算法。绝大多数算法都是针对具体问题提出的。点云分割算法中容易被忽略的重要信息是点云数据的语义信息。Anand等[35]利用点云数据的语义信息改进了分割算法，利用局部视觉外观、三维空间下的几何关系和形状特征，结合室内场景的语义信息对复杂的点云数据进行处理并取得良好的分割效果。

由于噪声、点云密度不均匀、存在大量遮挡区域等原因，很难在复杂场景中找到合适的几何特征。有学者研究利用机器学习的分割算法，且初步试验表明该类算法的效果优于只考虑点云空间连通性和几何特性的算法，但是该类算法运算速度较慢，实验结果对特征提取过程的依赖性较大，还有极大的改进空间。点云数据的应用会越来越广泛，因此对点云数据的应用和处理算法研究也会保持持续的热度，了解其基本方法和原理，对今后开展相关领域的研究或应用都具有极大价值。

参考文献

[1] Rusu R B， Cousins S. 3D is here： Point cloud library （PCL）[C]// IEEE International Conference on Robotics & Automation. 2011：1-4.

[2] Song S， Lichtenberg S P， Xiao J. SUN RGB-D： A RGB-D scene understanding benchmark suite[C]// Computer Vision and Pattern Recognition （CVPR），2015 IEEE Conference on. IEEE.2015：567-576.

[3] Hane C， Savinov N， Pollefeys M. Class Specific 3D Object Shape Priors Using Surface Normals[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE Computer Society.2014：652-659.

[4] B. Bhanu， S. Lee， C. Ho， and T. Henderson， Range data processing：Representation of surfaces by edges[M]. In proc.int.Pattern recognitionconf， 1896.

[5] Jiang X Y， Meier U， Bunke Fast range image segmentation using high-level segmentation primitives[C]// Applications of Computer Vision， 1996. Wacv '96.Proceedings， IEEE Workshop on. IEEE.1996：83-88.

[6] A. Sappa， M.Devy， Fast range image segmentation by an edge detectionstrategy[M]. In 3D Digital Imaging and Modeling， Los Alamitos， CA，USA，2001：292-299.

[7] 张海涛，姚雪，刘万军.利用车辆边缘的遮挡车辆曲线分割算法[J].计算机应用研究，2014，31（7）：2191-2194.

[8] 陈旭光，林卉.边缘分割算法在机场识别中的应用[J].微计算机信息，2012（1）：163-165.

[9] 王昭莲，吴乐华，杨琬.一种有效的基于边缘图像的机场跑道识别算法[J]. 光电技术应用， 2008， 23（1）：70-73.

[10] P.J. Besl， R.C. Jain， Segmentation through variable order surfacefitting[M]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 1988.

[11] K.K¨oster， M. Spann： An approach to robust clustering application to range image segmentation[M]. IEEE Transaction on Pattern Pattern Analysis， 2000.

[12] Rottensteiner F. Automatic Generation of High-Quality Building Models from Lidar Data[J]. Computer Graphics & Applications IEEE， 2003， 23（6）：42-50.endprint

[13] D.Tovari， Segmentation based robust interpolation - A new approach to laser data filtering， International Archives of Photogrammetry[J].Remote Sensing and Spatial Information Sciences，2005，36（3/W19）：79-84.

[14] Wang Z， Liu H， Qian Y， et al. Real-Time Plane Segmentation and Obstacle Detection of 3D Point Clouds for Indoor Scenes[M]// Computer Vision ECCV 2012. Workshops and Demonstrations. Springer Berlin Heidelberg.2012：22-31.

[15] Papon.J，Abramov.A，Schoeler. M，Worgotter.F. Voxel Cloud Connectivity Segmentation -Supervoxels for Point Clouds[M]. Computer Vision and Patterrn Recognition （CVPR 2013） 10.1109＼CVPR.2013：264.

[16] S. Filin， Surface clustering from airborne laser scanning data[M]. International Archives of Photogrammetry， Remote Sensing and Spatial Information Sciences，2001：117124.

[17] G. Vosselman 3D building model reconstruction frompoint clouds and ground plans， Int. Arch. Photogramm[J]. Remote Sens.，2001（34）：37-43.

[18] Zhan Q， Yu L， Liang Y. A point cloud segmentation method based on vector estimation and color clustering[C]//Information Science and Engineering （ICISE）， 2010 2nd International Conference on. IEEE.2010：3463-3466.

[19] Zhan Q， Yu L. Segmentation of LiDAR Point Cloud based on Similarity Measures in Multi-Dimension Euclidean Space[C]//Proceedings of 2010 International Conference on Remote Sensing Volume 2.2010.

[20] Holz D， Holzer S， Rusu R B， et al. Real-Time Plane Segmentation Using RGB-D Cameras[M]// RoboCup 2012：Robot Soccer World Cup XV. Springer Berlin Heidelberg.2012：306-317.

[21] Fischler M A， Bolles R C. Random Sample Consensus： A Paradigm for Model Fitting with Applications To Image Analysis and Automated Cartography[J]. Communications of the Acm，1981，24（6）：381-395.

[22] R.Schnabel， R. Wahl， R.Klein， Efficient ransac for point cloud shape detection. Comput[J].Graph，2007，26（2）：214-226.

[23] N. Gelfand， L. Guibas， Shape segmentation using local slippage analysis[M]. In Proceedings of Eurographics， ACM， New York，2004：214-223.

[24] Y. Li， X.， Y. Chrysathou， A. Sharf， D. Cohenor， N.J. Mitra， Globfit： Consistently fitting primitives by discovering global relations[M]. ACM Trans. Graph， 2011.

[25] Wang Y， Shi A segmentation method for point cloud based on local sample and statistic inference[J]. Communications in Computer and Information Science， 2015（482）：274-282.

[26] Wang Y， Shi H. A segmentation method for point cloud based on local sample and statistic inference[J]. Communications in Computer and Information Science， 2015（482）：274-282.endprint

[27] J. Schoenberg， A. Nathan， and M. Campbell， Segmentation of denserange information in complex urban scenes[M]. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS），2010：2033-2038.

[28] Sallem N K， Devy M. Extended GrabCut for 3D and RGB-D Point Clouds[M]// Advanced Concepts for Intelligent Vision Systems. Springer International Publishing.2013：354-365.

[29] Geetha M， Rakend. An improved method for segmentation of point cloud using Minimum Spanning Tree[C]// Communications and Signal Processing （ICCSP）， 2014 International Conference on. IEEE.2014.

[30] Yang J， Gan Z， Li K， et al. Graph-Based Segmentation for RGB-D Data Using 3-D Geometry Enhanced Superpixels[J]. Cybernetics IEEE Transactions on， 2015，45（5）：913-926.

[31] Ma T， Wu Z， Feng L， et al. Point cloud segmentation through spectral clustering[C]// International Conference on Information Science and Engineering. IEEE. 2010：1-4.

[32] Nurunnabi A， Belton D， West G. Robust Segmentation in Laser Scanning 3D Point Cloud Data[C]// Digital Image Computing Techniques and Applications （DICTA）， 2012 International Conference on. IEEE.2012：1-8.

[33] Wolf，J Prankl，M Vincze. Fast semantic segmentation of 3D point clouds using a dense CRF with learned parameters[C]// 2015 IEEE International Conference on Robotics and Automation （ICRA）.2015.

[34] Green W R，Grobler H. Normal distribution transform graph-based point cloud segmentation[C]// Pattern Recognition Association of South Africa and Robotics and Mechatronics International Conference.IEEE.2015.

[35] A. Anand，T.Joachims，A.Saxena，Contextually Guided Semantic Labeling and Search for 3D Point Clouds[M].In IJRR，2012.endprint