一种融合区域生长和RANSAC的稠密点云平面分割方法
2022-05-06张建伟权庆乐
张建伟 权庆乐
摘要：为提高三维信息的准确度，提出一种在稠密的点云数据中采用融合区域生长和随机抽样一致性（RANSAC）的平面分割方法。利用统计滤波、体素滤波对稠密点云去噪和精简，通过邻域统计特性剔除孤立点。采用点域区域生长分割出平面点，并采用面域区域生长合并平面附近点。采用曲率值检测出异常弯曲的平面。在异常弯曲的平面中采用RANSAC评估平面点的模型误差并剔除粗差点。实验选取公寓、阁楼、办公室等4个典型室内场景数据进行测试。实验表明，该方法可有效从稠密点云中分割出平面结构，分割结果准确度均值可达到95%以上。相比于传统RANSAC方法，可以更好地保证平面结构的连通性。相比于传统区域生长方法分割结果，准确度提升约2%，完整度平均提高约17%，对于后续三维重建和机器人的导航有着借鉴作用。
关键词：稠密点云;平面分割;区域生长;RANSAC分割;点云曲率
中图分类号：TP 391.41文献标志码：A
文章编号：1672-9315（2022）02-0341-08
DOI：10.13800/j.cnki.xakjdxxb.2022.0219开放科学（资源服务）标识码（OSID）：
A plane segmentation method of region growing
and RANSAC for dense point cloudZHNAG Jianwei，QUAN Qingle
（Department of Information Engineering，Henan University of Animal Husbandry and Economy，Zhengzhou 450004，China）
Abstract：In order to improve the 3D information accuracy，this paper proposes a plane segmentation method using fusion of region growing and random sampling consensus（RANSAC）in dense point cloud data.First，statistical and voxel filtering are applied to denoise and simplify the point cloud，which removes outliers based on neighborhood statistical properties.Then，planar points are segmented using point-based region growing，and the points around plane are further merged using plane-based region growing.Next，the curvature is used to detect abnormally curved planes.Finally，RANSAC is applied to evaluate the model errors of planar points among abnormally curved planes and then to remove outliers.In the experiment，four typical indoor datasets such as apartment，loft，and offices are used to verify the proposed method.Experimental results demonstrate that the average segmentation accuracy can reach over 95%.The planar connectivity is preserved better than that by traditional RANSAC method.Compared with the traditional region growing method，the segmentation accuracy improves about 2%，and completeness increases about 17% on average.It is of great significance for the subsequent 3D reconstruction and robot navigation.
Key words：dense point cloud;plane segmentation;region growing;RANSAC segmentation;curvature of point cloud
0引言
近年來，随着三维激光扫描技术的快速发展，高精度、数据海量的稠密点云已广泛应用于逆向工程[1]、文物修复[2]、3D打印[3]、自动驾驶[4]等领域。如何从点云中快速、准确地提取出真实场景目标信息，已逐渐成为国内外众多学者的研究热点。平面结构由于具有良好的几何特性，广泛地存在于室内外各场景中。鲁棒的平面结构可为场景结构建模[5]、机器人导航定位[6]等提供稳定的特征信息。稠密点云由于其数据细节丰富，可以较为鲁棒地反映真实地物信息，但由于其数据海量，如何高效准确处理成为难题。因此稠密点云中快速准确地提取平面结构已成为计算机领域中重要的研究内容[7-8]。
国内外众多学者针对平面提取已做了部分研究，而目前的平面分割方法可总体分为模型拟合类方法、深度学习类方法和区域生长类方法。
1）模型拟合类方法。主要包括随机采样一致性算法（RANSAC）[9-10]和霍夫变换算法（Hough transformation）[11]。RANSAC算法首先预先设定平面参数，依据点到平面的距离，在全局范围内将三维点分为外点与内点，并将内点数最多的点集作为最终平面分割结果。部分学者对RANSAC方法进行改进，SCHNABEL等提出采用八叉树优化RANSAC算法，以提高平面提取效率[12]。熊风光等提出将K均值聚类与RANSAC相结合，以提高算法中的粗差点剔除率，在一定程度上提高了RANSAC算法的准确度[13]。RAGURAM等采用附加法向矢量的方式提取数据中的三角面片。以上方法虽然有较好的抗噪性，但计算效率较低，同时未考虑空间连通性，易在稠密点云数据中产生伪平面[14]。
霍夫变换算法将原始空间中平面检测问题转化为寻找参数空间峰值问题。目前主要模型有球体、直线、柱体和平面等。田朋举等提出一种基于2DHough变换和八叉树相结合的方法，实现建筑平面的有效分割[15]。HULIK等采用矢量约束来提高Hough变换算法检测平面的准确度。但该类方法存在一定的平面误识别现象[16]。
2）深度学习类方法。通过构建卷积神经网络，对点云数据进行语义信息分割。以PointNet[17]、PointNet++[18]、PointCNN[19]等深度神经网络为代表，可有效实现在真实场景下，提取点云数据中平面结构。YU等针对稀疏点云特性，提出网络模型，提高平面拟合精度，但在稠密点云数据中的计算效率仍有待提高[20]。该类方法需大量样本清洗及模型训练等工作，当处理大规模稠密点云时，与传统方法相比并无显著优势。
3）区域生长类方法[21-22]。通常是利用法线、曲率等几何属性，分析点云局部空间的邻接关系，进而实现平面点云的生长。薛婧雅等提出基于超体素与区域生长相结合的方式提高屋顶平面的分割精度[23]。王冲等采用动态分配权重的方法来提高法线解算精度，进一步提高区域生长算法的准确性[24]。FOTSING等采用ICP算法选取可靠的候选种子点，并在生长过程中采用体素表达点云，改善平面分割质量[25]。ZHANG等提出一种基于2D和3D相互投影的区域生长方法，通过点云以及投影平面的几何信息选取初始种子点，并通过区域生长条件判断每个点的通视性，改善分割效果[26]。该类方法提取平面精度较高，但受到区域生长条件限制，平面结构的完整度有待提高。同时该方法更关注于点云局部空间变化，对于平面结构的整体考虑不足。
近年来一些学者也提出一些新方法，ZHU等将平面分解为多个平面段合并的结果，采用准逆理论（quasi-a-contrario theory）利用误警值（false alarms）评估每个平面段的分割效果[27]。WANG等用L0梯度最小化算法的區域生长以及图分割（graph cut）提取物体表面[28]。FATEMEH等提出多平面算法用于区分多平面立面的结构和非结构元素，从统计上考虑点组相对于其邻居的位置，以进行识别的隔离多平面建筑的主立面[29]。
目前众多研究方法多集中于某一类平面分割方法，并在此基础上进行优化，而忽略各类方法之间的关联性。模型拟合类方法具有严格的数学模型，但是忽略了局部空间结构的连续性。区域生长类方法强调局部空间中连续，而未对数据进行整体限制考虑，而过于严格的曲率阈值则会导致平面结构的不完整。因此，综合以上各类平面分割方法的特点，提出一种区域生长和RANSAC相结合的稠密点云平面分割方法。融合2类平面分割方法中数学模型以及局部空间约束的优点，克服空间不连续及平面完整度不高的缺点。首先采用3种滤波方法实现点云初步的预处理，然后采用混合区域生长算法实现平面结构的初分割，其次利用平面弯曲度约束对平面结构的几何状态进行判断，最后采用RANSAC算法剔除异常平面的粗差点，从整体提高平面分割的准确度。该方法综合RANSAC和区域生长平面分割方法的优点，在一定程度上提高平面分割的准确度与完整度。
1平面分割方法
1.1技术路线
平面分割技术路线如图1所示。首先对原始稠密点云进行预处理，利用无效点剔除、统计滤波、体素滤波，显著降低点云数据量，滤除大量离群噪声点。然后提出一种混合区域生长分割方法实现场景中平面点云的初分割。其次以整个平面为基础对平面进行弯曲度约束分析，检测出弯曲度异常平面。最后采用RANSAC算法剔除平面粗差点，提高平面分割准确度和完整度。
1.2数据预处理
由于稠密点云数据海量，对其直接处理，严重影响处理效率，因此在平面分割前对其进行预处理，为后续平面特征提取做准备。
首先对稠密点云数据P进行数据格式检查，寻找数据中存在的“非法”格式，如点云中常见的“NAN”，并对其进行剔除。然后采用统计滤波滤除噪声点，其原理如公式（1）所示。最后采用体素滤波，在保证点云数据整体轮廓的前提下，降低点云数据量，其中体素滤波采用边长为l（0.02 m）的三维网格。在预处理后得到点云数据PV。
1.3点域区域生长
在预处理后，以三维点为基础，结合局部邻域空间分析，制定邻域生长条件，进行点域内的区域生长。主要包括以下步骤。
1.4面域区域生长
由于区域生长条件的限制，点域区域生长后的剩余点云Ple中仍包含部分属于但未被归类到相应平面结构的三维点。文中进一步采用面域区域生长进一步处理未分类的平面点。图2为面域区域生长的示意，主要包括以下步骤。
1）平面筛选。琐碎的平面点云，通常并非真正的实体结构，或对场景结构的表达的意义不大。因此如图3所示，对于提取的平面点云，通过外接矩形面积近似作为平面点云面积，并经验性地设置面积阈值s（0.02 m2），剔除面积较小的平面，将其放回至剩余点云Ple中。
2）建立邻域结构。以平面为基础，再次采用KD-tree在剩余点云中，对平面点云建立邻域结构，并去除重复的邻域点（图2中黄色点）。
3）平面生长。在每一个平面邻域中，计算其到平面的距离，若小于距离阈值d1（0.03 m），则将其归类为当前平面点云。
1.5平面弯曲度约束
平面分割后，以每一平面点云为基础，计算平面的整体平均曲率，将其作为整个平面的弯曲度评价指标，主要包括以下步骤。
1）在公式（4）中，采用最小二乘法拟合平面方程，并计算整个平面点云重心点pc。
1.6RANSAC检核平面
平面弯曲度约束分析后，平面点云分为正常平面和弯曲度异常平面。如图4在异常平面中采用RANSAC拟合平面点云方程，并计算整体平面的点云的误差，将点到平面距离大于阈值d2（0.02 m）的点，作为粗差值点，进行剔除，提高平面分割准确度。而弯曲度正常平面则无需进行RANSAC检测，可认为其已基本满足几何一致性原则，直接保存为最后的平面分割点云。最后输出所有平面点云。
2实验结果与分析
2.1实验数据与环境
实验环境为Intel Core i7-5500U CPU@2.40 GHz 2.39 GHz，8.0 GB RAM，采用Ubuntu 16.04系统，C++编程实现。实验采用4组数据，其中前2组数据来自PARK学者公布的公寓及阁楼场景点云数据[30]，后2组数据来自苏黎世大学（UZH）的可视化与多媒体实验室提供的办公室扫描数据（https：//www.ifi.uzh.ch/en/vmml/research/datasets.html）。
图5是采用文中预处理方法后的点云结果，体素滤波采用边长为0.02m的三维体素网格进行体素化处理。从图中预处理效果可以看出，在保持整体场景特征信息的前提下，点云数据量在一定程度上有所降低、大部分离群噪声点得到有效剔除。
2.2平面分割对比实验
在平面分割实验中，选取传统的区域生长和RANSAC方法作为对比实验。各方法的分割效果如图6所示，其中不同颜色表示不同平面点云。从图中分割效果可以看出，RANSAC方法仅使用数学模型对点云进行分割，未能保证平面点云的连通性，致使多处不邻的平面段误识别为同一个平面点云。区域生长方法的分割效果总体较为良好，但平面分割受到生长条件的限制，未能保证平面的完整度，位于平面边缘附近的点云未能很好进行归类。目视效果上可见，文中方法可提取处场景中的大部分平面，同时平面之间的边缘点云也得到良好归类，平面结构的区分度较高，在保证准确度的同时也保证了平面结构的完整度。
2.3未分类点分布
为进一步对比分析平面分割方法性能，如图7提取出各方法分割后未归类到具体平面的剩余点云。在剩余点分布方面，RANSAC方法由于仅采用空间数学模型，保留剩余点数量最少。其次是文中方法，最后是传统区域生长方法。相比于区域生长方法，文中方法可以更好地處理平面边缘点，减少剩余点数量，提高平面完整度。
2.4精度评估
进一步量化分析分割方法的性能，采用式（7）和式（8）中准确度（Corrrectness，Cr）、完整度（Completeness，Cm）[31]指标评估各算法。实验中采用CloudCompare软件的标记功能，勾选数据中的平面点并添加Label作为评估的真值。
式中TP为正确分割平面点;FP为错误识别的平面点;FN为漏检的平面点。
表1记录了实验中3种分割方法在4个数据的分割结果的平面数量、剩余点数、准确度和完整度。其中RANSAC方法由于空间几何模型在全局范围提取平面，可提取出场景中的绝大部分平面点。但由于实验数据中存在大量的平面，致使RANSAC方法所提取的大部分平面点是空间非连续的，这与空间平面的几何属性相矛盾。区域生长方法和文中方法所分割平面均由空间连续三维点构成，符合空间平面的几何特性。同时相比于区域生长方法，文中方法在准确度与完整度方面均所有提升，4个场景中准确度均提升2%左右，均达到95%以上。完整度提高效果为：公寓场景提升约20%;阁楼场景提升约27%;办公室1场景提升约12%;办公室2场景提升约11%。文中方法更加鲁棒地提取稠密点云中的平面结构，并提高平面特征的完整度。为后续场景建模以及机器人定位导航提高更加鲁棒的特征结构。
3结论
1）利用点域内区域生长和面域内区域生长相结合，可以有效克服传统区域生长在平面边缘分割时的欠分割现象，平面分割的完整度提高约17%。
2）采用曲率值近似表达平面弯曲度，并对所分割的平面点云进行检核，可以有效检测出异常弯曲的平面，有利于检测平面中的粗差点。
3）利用RANSAC检核平面，可以在保证平面分割的连通性的基础上，进一步提高平面分割的准确度，在典型的室内场景中，分割的准确度可达到95%。
4）基于稠密点云数据的平面分割方法可为基于平面结构的特征建模以及室内机器人导航定位提供可靠的特征基础。
参考文献（References）：
[1]雷婉南，赵鹏飞.逆向工程椭圆柱构件的拟合计算[J].大地测量与地球动力学，2010，30（5）：102-105，112.LEI Wannan，ZHAO Pengfei.Fitting calculation of elliptical cylinder component in reverse engineering[J].Journal of Geodesy and Geodynamics，2010，30（5）：102-105，112.
[2]高杨.三维激光扫描的文物破损区域修复研究[J].激光杂志，2021，42（1）：187-191.GAO Yang.Restoration of relics damaged area by 3D laser scanning[J].Laser Journal，2021，42（1）：187-191.
[3]徐文鹏，苗龙涛，侯守明，等.基于体素模型的3D打印支撑算法[J].图学学报，2018，39（2）：228-234.XU Wenpeng，MIAO Longtao，HOU Shouming，et al.Construction of support structure based on voxelization models for 3D printing[J].Journal of Graphics，2018，39（2）：228-234.
[4]霍桂利.基于智能控制算法的自动驾驶系统优化研究[J].现代电子技术，2019，42（20）：177-180.HUO Jiali.Optimization of automatic driving system based on intelligent control algorithm[J].Modern Electronics Technique，2019，42（20）：177-180.
[5]白云.煤礦救援蛇形机器人环境建模方法研究[J].西安科技大学学报，2014，34（4）：485-489.BAI Yun.Research on environment modeling method of the coal mine rescue snake-like robot[J].Journal of Xian University of Science and Technology，2014，34（4）：485-489.
[6]杨林，马宏伟，王川伟，等.校园巡检机器人智能导航与控制[J].西安科技大学学报，2018，38（6）：1013-1020.YANG Lin，MA Hongwei，WANG Chuanwei，et al.Intelligent navigation and control of campus inspection robot[J].Journal of Xian University of Science and Technology，2018，38（6）：1013-1020.
[7]CEDRIQYE F，NAREPH M，CHRISTOPHE B.Iterative closest point for accurate plane detection in unorganized point clouds[J].Automation in Construction，2021，125：103610.
[8]ABNER M C A，MANUEL M O.A robust statistics approach for plane detection in unorganized point clouds[J].Pattern Recognition，2020，100：107115.
[9]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.
[10]胡伟，卢小平，李珵，等.基于改进RANSAC算法的屋顶激光点云面片分割方法[J].测绘通报，2012（11）：31-34.HU Wei，LU Xiaoping，LI Cheng，et al.Extended RANSAC algorithm for building roof segmentation from LiDAR data[J].Bulletin of Surveying and Mapping，2012（11）：31-34.
[11]DUDA R O，HART P E.Use of the hough transformation to detect lines and curves in pictures[J].Cacm，1972，15（1）：11-15.
[12]SCHNABELR，WAHL R，KLEIN R.Efficient RANSAC for point cloud shape detection[J].Computer Graphics Forum，2007，26（2）：214-226.
[13]熊风光，霍旺，韩燮，等.三维点云中关键点误匹配剔除方法[J].光学学报，2018，38（2）：128-138.XIONG Fengguang，HUO Wang，HAN Xie，et al.Removal method of mismatching keypoints in 3D point cloud[J].Acta Optica Sinica，2018，38（2）：128-138.
[14]RAGURAM O C，POLLEFEYS M，MATAS J，et al.USAC：A universal framework for random sample consensus[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（8）：2022-2038.
[15]田朋举，花向红，康停军，等.一种基于点云数据的建筑物平面精细分割方法[J].测绘科学，2021，46（2）：122-129.TIAN Pengju，HUA Xianghong，KANG Tingjun，et al.Fine segmentation of building planar feature from large scale unorganized point cloud[J].Science of Surveying and Mapping，2021，46（2）：122-129.
[16]HULIK R，SPANEL M，SMRZ P，et al.Continuous plane detection in point-cloud data based on 3D hough transform[J].Journal of Visual Communication & Image Representation，2014，25（1）：86-97.
[17]GRAHAM B.Spatially-sparse convolution neural networks[J].Computer Science，2014，34（6）：864-867.
[18][18]CHARLES R Q，SU H，KAICHUN M，et al.PointNet：Deep learning on point Sets for 3D classification and segmentation[C]//Symposium on Computer Vision and Pattern Recognition （CVPR），July 21-16，2017， Honolulu，HI：IEEE，c2017：77-85.
[19]QI C R，LI Y，HAO S，et al.PointNet++：Deep hierarchical feature learning on point sets in a metric space[C]//Symposium on 31st Annual Conference on Neural Information Processing Systems（NIPS），December 4-9 2017，Long Beach，California：Neural Information Processing Systems Foundation，c2017：5100-5109.
[20]YU Y，LI F，ZHENG Y，et al.Clustering-enhanced pointcnn for point cloud classification learning[C]//Symposium on International Joint Conference on Neural Networks（IJCNN），July 14-19，2019，Budapest，Hungary：IEEE，c2019：1-6.
[21]NURUNNABI A，BELTON D，WEST G.Robust segmentation in laser scanning 3D point cloud data[C]//Symposium on International Conference on Digital Image Computing Techniques & Applications，December 3-5，Fremantle，WA：IEEE，c2012：1-8.
[22]SHI P，YE Q，ZENG L.A Novel indoor structure extraction based on dense point cloud[J].International Journal of Geo-Information，2020，9（11）：660.
[23]薛婧雅，李禮，龚烨，等.一种基于超体素与区域生长的机载点云屋顶平面分割方法[J].测绘地理信息，2021，46（S1）：232-236.XUE Jingya，LI Li，GONG Ye，et al.A method for roof plane segmentation by supervoxel and regional growth[J].Journal of Geomatics，2021，46（S1）：232-236.
[24]王冲，李锻能，邓君裕，等.改进法线方向的点云实时分割提取平面方法研究[J].计算机测量与控制，2018，26（5）：210-213.WANG Chong，LI Duanneng，DENG Junyu，et al.Real-time point clouds plane segmentation based on improved normal direction[J].Computer Measurement & Control，2018，26（5）：210-213.
[25]FOTSING C，MENADJOU N F，BOBDA C.Iterative closest point for accurate plane detection in unorganized point clouds[J].Automation in Construction，2021，125：103610.
[26]ZHANG W，ZHOU F，WANG L，et al.Region growing based on 2-D 3-D mutual projections for visible point cloud segmentation[J].IEEE Transactions on Instrumentation and Measurement，2021，70：1-13.
[27]ZHU X，LIU X，ZHANG Y，et al.Robust 3-D plane segmentation from airborne point clouds based on Quasi-A-Contrario theory[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2021，14：7133-7147.
[28]WANF X，JI S.Roof plane segmentation from LiDAR point cloud data using region expansion based L0 gradient minimization and graph cut[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2021，14：7133-7147.
[29]FATEMEH H.Point cloud segmentation and classification of structural elements in multi-planar masonry building facades[J].Automation in Construction，2020，118：103232.
[30]PARK J，ZHOU Q Y，KOLTUN V.Colored point cloud registration revisited[C]//Symposium on International Conference on Computer Vision，October 22-29，Venice：IEEE，c2017：134-152.
[31]AWRANGJEB M，FRASER C S.An automatic and threshold-free performance evaluation system for building extraction techniques from airborne LiDAR data[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2014，7（10）：184-4198.
