基于分裂合并的多模型拟合方法在点云分割中的应用

doi:10.11947/j.AGCS.2018.20180131

摘要/Abstract

摘要： 本文基于机器视觉探讨数字摄影测量三维构像下的智能数据处理要素之二：海量点云分割处理技术。多模型拟合方法通过将点云拟合到不同模型中，依照点云空间分布特征和几何结构特征进行分割。针对点云数据量巨大、分布不均匀、结构复杂等特性，本文提出一种基于多模型拟合的点云分割方法。首先通过降采样，采用基于密度分布的聚类方法，实现对点云的预分割。在预分割基础上，利用基于分裂合并的多模型拟合方法对点云进行后续拟合分割。针对平面和弧面，本文采用不同的拟合方式，最终实现对室内密集点云分割。试验结果表明，该方法能够在无须提前设置模型数目的情况下实现点云的自动分割。且相较于现有的点云分割技术，此方法相较于现今的常规方法能取得更好的分割效果，在分割的正确率上要高于现有的常规分割方法，在处理相同数据量的点云分割时，能够达到远低于常规方法的时间消耗。通过本文提出的三维点云分割方法能够实现将大规模、复杂三维点云数据分割为较为精细、具有准确模型参数的三维几何图元，为后续实现大规模、复杂场景的精确三维构象提供有力支持。

关键词: 机器视觉, 三维构像, 点云分割, 分裂合并, 多模型拟合

Abstract: This paper deals with the massive point cloud segmentation processing technology on the basis of machine vision,which is the second essential factor for the intelligent data processing of three dimensional conformation in digital photogrammetry.In this paper,multi-model fitting method is used to segment the point cloud according to the spatial distribution and spatial geometric structure of point clouds by fitting the point cloud into different geometric primitives models.Because point cloud usually possesses large amount of 3D points,which are uneven distributed over various complex structures,this paper proposes a point cloud segmentation method based on multi-model fitting.Firstly,the pre-segmentation of point cloud is conducted by using the clustering method based on density distribution.And then the follow fitting and segmentation are carried out by using the multi-model fitting method based on split and merging.For the plane and the arc surface,this paper uses different fitting methods,and finally realizing the indoor dense point cloud segmentation.The experimental results show that this method can achieve the automatic segmentation of the point cloud without setting the number of models in advance.Compared with the existing point cloud segmentation methods,this method has obvious advantages in segmentation effect and time cost,and can achieve higher segmentation accuracy.After processed by method proposed in this paper,the point cloud even with large-scale and complex structures can often be segmented into 3D geometric elements with finer and accurate model parameters,which can give rise to an accurate 3D conformation.

Key words: machine vision, 3D conformation, point cloud segmentation, splitting and merging, multi-model fitting

中图分类号:

TP391

张良培, 张云, 陈震中, 肖佩珮, 罗斌. 基于分裂合并的多模型拟合方法在点云分割中的应用[J]. 测绘学报, 2018, 47(6): 833-843.

ZHANG Liangpei, ZHANG Yun, CHEN Zhenzhong, XIAO Peipei, LUO Bin. Splitting and Merging Based Multi-model Fitting for Point Cloud Segmentation[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(6): 833-843.

参考文献

[1] 李德仁, 姚远, 邵振峰. 智慧城市的概念、支撑技术及应用[J]. 工程研究-跨学科视野中的工程, 2012, 4(4):313-323. LI Deren, YAO Yuan, SHAO Zhenfeng. The Concept, Supporting Technologies and Applications of Smart City[J]. Journal of Engineering Studies, 2012, 4(4):313-323.
[2] SCHNABEL R, WAHL R, WESSEL R, et al. Shape Recognition in 3D Point-clouds[C]//The 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2008. Czech Republic:UNION Agency-Science Press, 2008:65-72.
[3] LI Yangyan, WU Xiaokun, CHRYSATHOU Y, et al. GlobFit:Consistently Fitting Primitives by Discovering Global Relations[C]//Proceeding of ACM SIGGRAPH. Vancouver, British Columbia, Canada:ACM, 2011:52.
[4] MAHABADI R K, HANE C, POLLEFEYS M. Segment Based 3D Object Shape Priors[C]//IEEE Computer Vision and Pattern Recognition. Boston, MA:IEEE, 2015:2838-2846.
[5] 宫钰嵩. RGBD数据驱动的室内景物三维建模方法研究[D]. 南京:南京大学, 2015. GONG Yusong. Research on 3D Modeling of Indoor Objects and Scenes Based on RGBD Data[D]. Nanjing:Nanjing University, 2015.
[6] DORNINGER P, PFEIFER N. A Comprehensive Automated 3D Approach for Building Extraction, Reconstruction, and Regularization from Airborne Laser Scanning Point Clouds[J]. Sensors, 2008, 8(11):7323-7343.
[7] 秦彩杰, 管强. 三维点云数据分割研究现状[J]. 宜宾学院学报, 2017, 17(6):30-35. QIN Caijie, GUAN Qiang. Research Status of 3D Point Cloud Data Segmentation[J]. Journal of Yibin University, 2017, 17(6):30-35.
[8] BHANU B, LEE S, HO C C, et al. Range Data Processing:Representation of Surfaces by Edges[C]//Proceedings of the Eighth International Conference on Pattern Recognition. Paris, France:[s.n.], 1986:236-238.
[9] JIANG Xiaoyi, BUNKE H. Edge Detection in Range Images Based on Scan Line Approximation[J]. Computer Vision and Image Understanding, 1999, 73(2):183-199.
[10] BESL P J, JAIN R C. Segmentation through Variable-order Surface Fitting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 10(2):167-192.
[11] KOSTER K, SPANN M. MIR:An Approach to Robust Clustering-application to Range Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(5):430-444.
[12] ROTTENSTEINER F. Automatic Generation of High-quality Building Models from Lidar Data[J]. IEEE Computer Graphics and Applications IEEE, 2003, 23(6):42-50.
[13] TÓVÁRI D, PFEIFER N. Segmentation Based Robust Interpolation-A New Approach to Laser Data Filtering[M]//International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. Enschede, The Netherlands:[s.n.], 2005:12-14.
[14] WANG Zhe, LIU Hong, QIAN Yueliang, et al. Real-Time Plane Segmentation and Obstacle Detection of 3D Point Clouds for Indoor Scenes[M]//FUSIELLO A, MURINO V, CUCCHIARA R. Computer Vision-ECCV 2012. Berlin, Heidelberg:Springer, 2012:22-31.
[15] PAPON J, ABRAMOV A, SCHOELER M, et al. Voxel Cloud Connectivity Segmentation-Supervoxels for Point Clouds[C]//IEEE Computer Vision and Pattern Recognition. Portland, OR:IEEE, 2013:2027-2034.
[16] FILIN S. Surface Clustering from Airborne Laser Scanning Data[J].International Archives of Photogrammetry and Remote Sensing, 2002:XXXⅡ, 3A:119-124.
[17] VOSSELMAN G, DIJKMAN S. 3D Building Model Reconstruction From Point Clouds and Ground Plans[J]. International Archives of Photogrammetry & Remote Sensing, 2001, 34(Part 3/W4):37-43.
[18] ZHAN Qingming, YU Liang, LIANG Yubing. A Point Cloud Segmentation Method based on Vector Estimation and Color Clustering[C]//IEEE 2nd International Conference on Information Science and Engineering. Hangzhou, China, China:IEEE, 2011:3463-3466.
[19] ZHAN Qingming, YU Liang. Segmentation of LiDAR Point Cloud based on Similarity Measures in Multi-Dimension Euclidean Space[M]//ZENG D. Advances in Computer Science and Engineering. Berlin, Heidelberg:Springer, 2012:349-357.
[20] HOLZ D, HOLZER S, RUSU R B, et al. Real-Time Plane Segmentation Using RGB-D Cameras[M]//RÖFER T, MAYER N M, SAVAGE J, et al. RoboCup 2011:Robot Soccer World Cup XV. Berlin, Heidelberg:Springer, 2012:306-317.
[21] SCHOENBERG J R, NATHAN A, CAMPBELL M. Segmentation of Dense Range Information in Complex Urban Scenes[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei, Taiwan:IEEE, 2010:2033-2038.
[22] SALLEM N K, DEVY M. Extended GrabCut for 3D and RGB-D Point Clouds[M]//BLANC-TALON J, KASINSKI A, PHILIPS W, et al. Advanced Concepts for Intelligent Vision Systems. Cham:Springer, 2013:354-365.
[23] GEETHA M, RAKENDU R. An Improved Method for Segmentation of Point Cloud Using Minimum Spanning Tree[C]//IEEE International Conference on Communications and Signal Processing. Melmaruvathur, India:IEEE, 2014:833-837.
[24] YANG Jingyu, GAN Ziqiao, LI Kun, et al. Graph-based Segmentation for RGB-D Data Using 3-D Geometry Enhanced Superpixels[J]. IEEE Transactions on Cybernetics, 2017, 45(5):927-940.
[25] FISCHLER M A, BOLLES R C. Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[M]//Readings in Computer Vision.[s.l.]:Elsevier, 1987:726-740.
[26] TARSHA-KURDI F, LANDES T, GRUSSENMEYER P. Hough-Transform and Extended RANSAC Algorithms for Automatic Detection of 3D Building Roof Planes from LiDAR Data[C]//Proceedings of the ISPRS Workshop on Laser Scanning, Espoo:ISPRS.2007, 36:407-412.
[27] SCHNABEL R, WAHL R, KLEIN R. Efficient RANSAC for Point-Cloud Shape Detection[J]. Computer Graphics Forum, 2010, 26(2):214-226.
[28] CHEN Dong, ZHANG Liqiang, LI J, et al. Urban Building Roof Segmentation From Airborne Lidar Point Clouds[J]. International Journal of Remote Sensing, 2012, 33(20):6497-6515.
[29] GELFAND N, GUIBAS L J. Shape Segmentation Using Local Slippage Analysis[C]//Proceedings of Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. Nice, France:ACM, 2004:214-223.
[30] AWADALLAH M, ABBOTT L, GHANNAM S. Segmentation of Sparse Noisy Point Clouds Using Active Contour Models[C]//IEEE International Conference on Image Processing. Paris, France:IEEE, 2015:6061-6065.
[31] WANG Yanmin, SHI Hongbin. A Segmentation Method for Point Cloud Based on Local Sample and Statistic Inference[M]//BIAN F, XIE Y. Geo-Informatics in Resource Management and Sustainable Ecosystem. Berlin, Heidelberg:Springer, 2015:274-282.
[32] MA Teng, WU Zhuangzhi, FENG Lu, et al. Point Cloud Segmentation Through Spectral Clustering[C]//IEEE 2nd International Conference on Information Science and Engineering. Hangzhou, China:IEEE, 2011:1-4.
[33] NURUNNABI A, BELTON D, WEST G. Robust Segmentation in Laser Scanning 3D Point Cloud Data[C]//IEEE International Conference on Digital Image Computing Techniques and Applications. Fremantle, WA, Australia:IEEE, 2013:1-8.
[34] WOLF D, PRANKL J, VINCZE M. Fast Semantic Segmentation of 3D Point Clouds Using a Dense CRF with Learned Parameters[C]//IEEE International Conference on Robotics and Automation. Seattle, WA:IEEE, 2015:4867-4873.
[35] 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. Port Elizabeth, South Africa:IEEE, 2015:54-59.
[36] VINCENT É, LAGANIÈRE R, Detecting Planar Homographies in an Image Pair[C]//Proceedings of the 2nd International Symposium on Image and Signal Processing and Analysis. Pula, Croatia, Croatia:IEEE, 2001:182-187.
[37] KANAZAWA Y, KAWAKAMI H. Detection of Planar Regions with Uncalibrated Stereo Using Distributions of Feature Points[C]//Proceedings of the British Machine Vision Conference.[s.l.]:BMVA Press, 2004:247-256.
[38] ZULIANI M, KENNEY C S, MANJUNATH B S. The Multiransac Algorithm and Its Application to Detect Planar Homographies[C]//IEEE International Conference on Image Processing. Genova, Italy:IEEE, 2005:Ⅲ-153.
[39] ESTER M, KRIEGEL H P, SANDER J, et al. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining.[s.l.]:AAAI Press, 1996:226-231.
[40] COMANICIU D, MEER P. Mean Shift:A Robust Approach Toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5):603-619.