Splitting and Merging Based Multi-model Fitting for Point Cloud Segmentation

doi:10.11947/j.JGGS.2019.0209

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

Liangpei ZHANG,Yun ZHANG,Zhenzhong CHEN,Peipei XIAO,Bin LUO. Splitting and Merging Based Multi-model Fitting for Point Cloud Segmentation[J]. Journal of Geodesy and Geoinformation Science, 2019, 2(2): 78-89.

Figures/Tables 8

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Tab.1

Fig.6

Tab.2

References 40

[1]	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. https://www.researchgate.net/publication/228652854_Shape_Recognition_in_3D_Point-Clouds
[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, 2011http://dl.acm.org/citation.cfm?id=1964947
[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. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7298901
[5]	GONG Yusong. Research on 3D Modeling of Indoor Objects and Scenes Based on RGBD Data[D]. Nanjing: Nanjing University, 2015. http://cdmd.cnki.com.cn/Article/CDMD-10284-1015321515.htm
[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. DOI: 10.3390/s8117323
[7]	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 CC , 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. https://www.researchgate.net/publication/282828645_RANGE_DATA_PROCESSING_REPRESENTATION_OF_SURFACES_BY_EDGES
[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.DOI: 10.1006/cviu.1998.0715
[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. DOI: 10.1109/34.857001
[12]	ROTTENSTEINER F . Automatic Generation of High-quality Building Models fromLidar Data[J]. IEEE Computer Graphics and Applications IEEE, 2003,23(6):42-50.DOI: 10.1109/MCG.2003.1242381
[13]	TÓVÁRI D, PFEIFER N . Segmentation Based Robust Interpolation-A New Approach to Laser Data Filtering[M] //International Archives ofPhotogrammetry, Remote Sensing and Spatial Information Sciences. Enschede, The Netherlands:[s. n. ], 2005: 12-14.
[14]	WANGZhe, 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. https://www.computer.org/csdl/proceedings/cvpr/2013/4990/00/4989c027-abs. html
[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. http://ieeexplore.ieee.org/document/5691038/
[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. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5651749
[22]	SALLEM N K, DEVY M . ExtendedGrabCut 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. http://ieeexplore.ieee.org/document/6949960/
[24]	YANGJingyu, 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 fromLiDAR Data[C]// Proceedings of the ISPRS Workshop on Laser Scanning, Espoo: ISPRS. 2007, 36: 407-412. https://www.mendeley.com/research-papers/houghtransform-extended-ransac-algorithms-automatic-detection-3d-building-roof-planes-lidar-data/
[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.DOI: 10.1080/01431161.2012.690083
[29]	GELFAND N, GUIBAS L J. Shape Segmentation Using Local Slippage Analysis[C]// Proceedings ofEurographics/ACM SIGGRAPH Symposium on Geometry Processing. Nice, France: ACM, 2004: 214-223. http://dl.acm.org/citation.cfm?id=1057461
[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. http://ieeexplore.ieee.org/document/7026223/
[31]	WANGYanmin, 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]	MATeng, 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. http://ieeexplore.ieee.org/document/5690596/
[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. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6411672
[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. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=7139875
[35]	GREEN W R, GROBLER H. Normal Distribution Transform Graph-based Point Cloud Segmentation[C]// Pattern Recognition Association of South Africa and Robotics andMechatronics International Conference. Port Elizabeth, South Africa: IEEE, 2015: 54-59. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=7359498
[36]	VINCENT É, LAGANIÈRE R . Detecting PlanarHomographies 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. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=938625
[37]	KANAZAWA Y, KAWAKAMI H. Detection of Planar Regions withUncalibrated Stereo Using Distributions of Feature Points[C]// Proceedings of the British Machine Vision Conference.[s. l.]: BMVA Press, 2004: 247-256. https://www.researchgate.net/publication/228961987_Detection_of_Planar_Regions_with_Uncalibrated_Stereo_using_Distributions_of_Feature_Points
[38]	ZULIANI M, KENNEY C S, MANJUNATH B S. TheMultiransac Algorithm and Its Application to Detect Planar Homographies[C]// IEEE International Conference on Image Processing. Genova, Italy: IEEE, 2005: Ⅲ-153. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1530351
[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. http://www.researchgate.net/publication/242504244_A_densitybased_algorithm_for_discovering_clusters_in_large_spatial_databases
[40]	COMANICIU D, MEER P . MeanShift:A Robust Approach Toward Feature Space Analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(5):603-619.DOI: 10.1109/34.1000236

Method	Area A	Area B
MeanShift	554	390
MultiRANSAC	230	132
Ours	70	30

Algorithms	Area A	Area B	Area C
MeanShift	73.6	81.2	61.5
MutliRANSAC	76.8	71.4	56.2
Ours	83.2	85.7	81.3