Paper Title (use style: paper title) International Journal of Advanced Network, Monitoring and Controls Volume 05, No.01, 2020 DOI: 10.21307/ijanmc-2020-010 66 Review of 3D Point Cloud Data Segmentation Methods Ruan Xiaoyi School of Computer Science and Engineering Xi’an Technological University Xi’an, 710032, China E-mail: 2827538117@qq.com Liu Baolong School of Computer Science and Engineering Xi’an Technological University Xi’an, 710032, China E-mail: liu.bao.long@hotmail.com Abstract—3D point cloud segmentation is one of the key steps in point cloud processing, which is the technology and process of dividing the point cloud data set into several specific regions with unique properties and proposing interesting targets. It has important applications in medical image processing, industrial inspection, cultural relic’s identification and 3D visualization. Despite widespread use, point cloud segmenta- tion still faces many challenges because of uneven sampling density, high redundancy, and lack explicit structure of point cloud data. The main goal of this paper is to analyse the most popular algorithms and methodologies to segment point clouds. To facilitate analysis and summary, according to the principle of segmentation we divide the 3D point cloud segmentation methods into edge-based methods, region-based methods, graph-based methods, model-based methods, and machine learning-based methods. Then analyze and discuss the advantages, disadvantages and application scenarios of these segmentation methods. For some algorithms the results of the segmentation and classification is shown. Finally, we outline the issues that need to be addressed and important future research directions. Keywords-Line Point Cloud; Segmentation; Classification I. INTRODUCTION Image segmentation is one of the basic research directions of computer vision, and its purpose is to subdivide a digital image into multiple regions with similar properties[1]. Segmentation of 2D images has more than 50 years of research history, but 3D point cloud data is a highly redundant and irregularly ordered structure, point cloud segmentation also faces many challenges. The segmentation of point clouds into foreground and background is a fundamental step in processing 3D point clouds. Given the set of point clouds, the 3D point cloud segmentation can be defined with the sets: Let the surface set },...,{ 21 n FFFF  reconstructed from the point set S, and the set },...,{ 21 n RRRR  be a subset of the power set of S . Each element in R is a set of point sets corresponding to a certain characterist- ic surface in F , which represents a region obtained by segmentation. If the following conditions are met, R is called a partition of the point set S : 1)  n i i SR 1  , indicates that the union of the divi-ded regions is the measured point set S , that is, each measurement point is divided into a certain region. 2)  ji RR Ø, indicates that the point sets obta- ined by segmentation do not intersect each other, and each measurement point cannot belong to two different regions at the same time. 3) The points in each region have the same characteristics, and any two adjacent regions do not have the same characteristics. 4) ),...,2,1( niVi  , R are all connected regions. II. METHODS SUMMARY We divide the 3D point cloud segmentation method into:edge-based methods, region-based methods, graph-based methods, model-based methods, and machine learning-based methods based on the basis of the current segmentation. A. Edge-based methods The edge-based segmentation method is currently the most studied method[2]. Edges are the basic features that describe the shape of point cloud objects (Figure 1). The edge-based segmentation method first detects the geometric boundary points of the data points. The edge of the point cloud is usually composed of the normal vector of the point cloud or the boundary points with abrupt curvature. These boundary points International Journal of Advanced Network, Monitoring and Controls Volume 05, No.01, 2020 67 are connected and then the entire data set is divided into the independent multiple point sets achieve the purpose of segmenting the point cloud. Therefore, the edge detection technology is the key to edge-based segmentation. Bhanu[3] first used gradients to detect edges, fitting 3D lines to set points, and detecting changes in the direction of the unit normal vector on the surface. Subsequently, Jiang[4] proposed a fast segmentation method using scanline grouping technology. The scan lines of the distance image are divided into curves and then they are clustered to represent the surface. This method is better than Bhanu 's method in segmentation quality and running time , but it is not suitable for point clouds with uneven density. Sappa[5] proposed a new edge detection method. By performing edge detection on binary maps, extracting closed contours for fast segmentation; Wang et al.[6] proposed a fast point cloud edge detection algorithm. First, the point cloud data is grid-organized to exclude non-edge discrete points. Finally, AlphaShapes judgment conditions are used to fficiently extract edges, which can effectively avoids the problem of extracting outer boundaries and holes. (a)original point cloud (b) the edge of data a. Figure 1. Point Cloud and Its Edge The advantage of edge-based segmentation is that it has good segmentation results for data with strong contrast in different regions, and can detect the edges of different regions very intuitively. The disadvantage is that although it detects all the edges, it is difficult to determine the detection, the relationship between the edge of the target area and the boundary of the target area. In addition, such algorithms are very sensitive to noise and are not suitable for objects with smooth surface changes. B. Area-based methods The region-based method classifies nearby points with similar attributes by searching for neighborhood information to achieve the purpose of segmentation. In 1976 Zucker[7] proposed a " Region Grow " should be split for 2D images, the researchers used after being 3D point cloud. The segmentation as shown in follows the Figure 2. Firstly, a small piece of seed region is given to the segmentation target, and the seed region is used as a starting point to search for the neighborhood; the curvature, normal vector, and geometric features of the point cloud are used as standards; if a point meets the criteria for seed growth, the point is incorporated into the seed region, and the process is repeated as a new seed point, until all points are detected, a growth region is formed. The segmentation results are shown in Figure 3. However, this method has the problems of being easily affected by noise and easily causing the problem of segmentation holes and excessive segmen- tation. [8-9]. Figure 2. Area-based methods flow chart (a)original point cloud (b)segmented by Region Grow Figure 3. Example of Region grow segmentation Many scholars then the algorithm is improved. Zhang[10] use Otsu determining the optimal segmetati- on threshold as a constraint condition of growth, better than the traditional segmentation methods, but is susceptible to noise; Angelina et al.[11] improved the region growing method with region merging and genetic algorithms, and its segmentation efficiency has been improved to some extent, but the boundary retention is poor; Xiao et al.[12] proposed clustering- International Journal of Advanced Network, Monitoring and Controls Volume 05, No.01, 2020 68 based adaptive region growth for road image segmentation Method, but its scope of application is limited; Besl et al.[13] divide the image into 8 regions based on the curvature characteristics by calculating the Gaussian and average curvature of the point cloud surface, set seed nodes for these 8 regions, and then use polynomial simulation This method is highly suscep- tible to noise and is time-consuming; Chen et al.[14] calculated the ratio of the minimum eigenvalue of each point and the sum of the three eigenvalues by decom- posing the covariance matrix, and the ratio was minimum point as a seed point, the process is mainly used in the building plane extraction rule, the high cost of time; Vosselman et al.[15] use randomly selecting seed sampling points, is determined these seed point whether neighborhood can be fitted to a predetermined model, but the method is prone to false segmentation; Koster[16] using the generated information in a relatively irregular pyramid FIG between the storage area, for comparing and merging adjacent regions; Pu [17] planar surface of the growth surface segmentation algorithm laser transactions; Ning seats[18] proposed a two-step method based on the coarse segmentation and fine segmentation, for extracting the main subject in the scene and finer details. The region-based method is more accurate than the edge-based method. For the seed method, the segmen- tation effect is directly related to the selection of the seed points. The quality of the seeds and the merge rules determine the segmentation effect, and this method is extremely susceptible to noise, causes over or under segmentation. C. Model-based approach This method is based on geometric shapes such as spheres, cones, planes, and cylinders to group point clouds. According to these shapes, points with the same mathematical model will be divided into the same region. The most typical algorithm is Fischer[19] random sample consensus algorithm (RANSAC) and the improvement of the method. RANSAC achieves segmentation by detecting features with regular geome- tric shapes such as planes, spheres, and cylinders. The basic principle of the algorithm is to calculate the mathematical model parameters of the data based on a set of sample data sets containing abnormal data to obtain valid sample data. Figure 4 compares the least squares method with the RANSAC algorithm. The results are shown in noisy data In addition, RANSAC can more effectively fit the target. RANSAC is widely used in the extraction of building surfaces; Li[20] proposed an efficient RAN- SAC based algorithm on traditional RANSAC, which has good performance. Noise immunity to segment millions of point clouds of a sample in less than a minute. Hough transform the detection points into Hough space[21]. Then a voting algorithm is used to detect objects with a specific shape, so that the problem of detecting arbitrary shapes is transformed into a statistical peak problem[22], which is mostly used for the detection of circles and ellipses. Document[23] compared RANSAC and 3D Hough transform results show 3D Hough transform segment parameter values slower and more sensitive, RANSAC the detection result in the time segments and run more efficiently. However, when RANSAC is applied to plane detection, the “pseudo-plane” problem often occurs. To solve this problem, an improved RANSAC method[24] based on Normal Distribution Transfor-mation (NDT) units, which is accurate. The rate can reach more than 88.5 %, and the plane integrity exceeds 85.0 %. In most cases, the method based on model fitting it needs to provide the geometric model to be detected. Zhang et al.[25] provide a multi-model fitting method based on splitting and merging, which can eliminate the need to set the number of models in advance. In this case, automatic segmentation of point cloud is realized. (a) Least squares fitting (b) RANSAC Figure 4. Comparison of Least Squares Fitting and RANSAC The model-based method has pure mathematical principles, is fast and powerful, and has heterogeneity. The main limitation of this method is the inaccuracy of dealing with different point clouds. This method has been implemented in point cloud libraries based on various models based on lines, planes, circles, and so on. D. Graph theory-based approach Graph theory image segmentation uses the principle of graph segmentation to segment the point cloud. This type of algorithm models the point cloud into a graph model composed of nodes and edges that reflect the relationship between the nodes. Graph theory-based optimal segmentation is typified by the FH algorithm proposed by Felzensawalb and Huttenloch[26] . This method constructs a weighted undirected graph using point clouds as vertices, calculates RGB differences International Journal of Advanced Network, Monitoring and Controls Volume 05, No.01, 2020 69 between different vertices to construct weights, and combines regions. Chen[27] achieves the goal of auto- matic segmentation by building a k-nearest neighbor graph, adding background constraints, and finding the minimum secant line. Compared with several segmen- tation methods, the results show that this method is suitable for segmenting foreground and background, suitable for specified target extraction, or implementing multi-objective extraction in a supervised classification manner. Ural et al.[28] suppose that a conditional random field model exists, and use graph cut algorithm to disconnect part of the graph model to form indepen- dent regions according to the maximum posterior estimation criterion. Li et al.[29] proposed a progre- ssive form of a two-level optimal segmentation algorithm. First, the topological relationship and the distance measurement characteristics of points were calculated under the Riemann geometry frame. The k- means clustering method was used to obtain the segmented voxels as the bottom layer. Segmentation result. Then, the voxels of the point cloud are modeled as nodes, the minimum spanning tree is constructed, and the high-level feature information of the nodes is extracted. The region segmentation effect of the point cloud details is obtained by using graph optimization. Much of the work of graph-based methods has been invested in probabilistic inference models, such as the conditional random field (CRF) method, which uses CRFs to label points with different geometric surface primitives. Graph theory-based methods can still efficiently segment point clouds in complex backgrounds, but these methods often lack real-time performance[30]. E. Machine learning-based methods Machine learning treats point cloud segmentation as classifying point cloud data. YU[31] proposed a neural network learning method that combines segmentation and classification simultaneously for target recognition;Yang[32] uses support vector machines to classify geometric features; Guan et al.[33] converts point clouds into voxels data to extract features and then use AdaBoost for training and target extraction; currently the most well-known is Charles et al.[34] use neural network for Point Set for 3D classification and segmentation-PointNet. Although PointNet can discri- minate the type of object, it lacks robustness to noise and data. To solve this problem, Charles et al. Proposed PointNet++, which can extract local features at different scales and obtain deep features through a multilayer network structure. In addition, Zhao et al. [35] proposed a deep neural network model based on multi-scale features and PointNet for feature classifi- cation of LiDAR point cloud data in complex scenes. This method improves the local feature rxtraction of PointNet. Ability to realize the automatic classification of LiDAR point clouds in complex scenes; Niu[36] improved the problem of the lack of local topological information of the generated features, and proposed a method that uses bisymmetric functions and spatial transformation networks to obtain more robust and stronger discrimination Compared with PointNet++, the training time is reduced by 20% with the same accuracy. The advantages of machine learning-based methods are good classification results and high accuracy. But these algorithms require the training process large amounts of data have been tagged to do the training sample, and dividing the object is defined as the target has been trained, it is difficult to point to complete the modeling of the relationship, so that the algorithm is difficult to comprehensively promote. Comparison of various point cloud segmentation methods is shown in Table Ⅰ. TABLE I. COMPARISON OF VARIOUS POINT CLOUD SEGMENTATION METHODS segmentation methods Advantage Disadvantage edge-based methods Can detect the edges of different areas very intuitively for point cloud. sensitive to noise and not suitable for objects with smooth surface changes. region-based methods More accurate than edge- based methods. The segmentation result depends on the quality of the seeds and the merging rules. There will be over- segmentation or under- segmentation. model-based methods Fast segmentation speed, and heterogeneous,suitable for simple geometric models. Difficult to use in complex scenarios. graph-based methods Suitable for complex scenes. Lack of real-time. machine learning- based methods. Point cloud segmentation has high accuracy, good recognition effect. lack of real-time. International Journal of Advanced Network, Monitoring and Controls Volume 05, No.01, 2020 70 III. CONCLUSION Point cloud segmentation is a necessary link for target detection and 3D reconstruction. This paper investigates some classic point cloud segmentation methods and analyzes their advantages and disadvantages. As can be seen from this article, although point cloud segmentation has undergone a long period of research, there are still limitations. Segmentation methods based on edges and regions have good real-time performance but are sensitive to noise, and the segmentation effect is often not ideal. The method based on model fitting has great limitations and it is difficult to adapt to the segmentation requirements of complex environments. Although graph-based and machine learning-based methods can overcome noise and efficiently segment point cloud data, it is difficult to meet real-time system requirements. Therefore, how to overcome the influence of noise and how to improve the real-time performance of the segmentation system is still the focus of point cloud segmentation research. ACKNOWLEDGMENT The completion of this paper is inseparable from the patient guidance of Prof. Liu Baolong, Prof. Chen Hua, Teacher Wu Qiong, and Teacher Lipeng Si. I also thank other teachers and students in this laboratory for their help. Finally, I would like to thank the science and technology program of Weiyang District of Xi'an City (Project No.: 2018036) for its fund support. REFERENCES [1] Shapiro L, Stockman G. Computer Vision Prentice Hall [J]. 2001:62(3): 271-279. [2] Luo Xiping, Tian Jie, Zhuge infants, and the like. Summary of image segmentation [D]. 1999. [3] B. Bhanu, S. Lee, C. Ho, and T. Henderson, Range data processing: Representation of surfaces by edges [J]. In proc.int. Pattern recognition conf. 1896: 236-238. [4] XY Jiang, H. Bunke, and U. Meier, Fast range image segmentation using high-level segmentation primitives [J], In 3rd IEEE Workshop on Applications of Computer Vision. 1996. [5] A. Sappa, M. Devy, Fast range image segmentation by an edge detection strategy. In 3D Digital Imaging and Modeling. 2001. [6] Wang Zongyue, Ma Hongchao, Xu Honggen, et al. Research on water body contour extraction method based on LiDAR point cloud data [J]. Wuhan University Journal of Information Science. 2010:31-26. [7] Zucker SW. Regiorowing: childhood and adolescence [J], Computer Graphics and Image Processing. 1976, 17(1): 99-125. [8] Li Renzhong, Liu Yangyang, Yang Man, et al. 3D point cloud segmentation based on improved region growth [J]. Chinese Journal of Optics, 2018:23-26. [9] Gao F. 375 cases of MATLAB image processing [M]. Beijing: Posts and Telecommunications Press, 2015. [10] Zhang L, Guo LM, He W, et al. An image segmentation algorithm based on maximal variance between-class and region growing [J] . Information and Electronic Engineering. 2005 .:45-48 [11] Angelina S, Suresh LP, Veni SH K. Image segmentation based on genetic algorithm for region growth and region merging [C]. Computing, Electronics and Electrical Technologies, 2012. [12] Xiao Xiaoming, Ma Zhi, Cai Zixing, et al. An adaptive region growing algorithm for road segmentation [J]. Control Engineering, 2011, 18(3): 364. [13] Besl P J, Jain R C. Segmentation through variable-order surface fitting [J]. IEEE Transactions on pattern analysis and machine intelligence, 1988, 10(2): 167-192. [14] Chen J, Chen BQ. Architectural modeling from sparsely scanned range data [J]. International Journal of Computer Vision, 2008. [15] Vosselman G, Gorte B G H, Sithole G, et al. Recognising structure in laser scanner point clouds[J]. International archives of photogrammetry, remote sensing and spatial information sciences, 2004, 46(8): 33-38. [16] 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. [17] Pu S, Vosselman G. Automatic extraction of building features from terrestrial laser scanning [J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, 36(5): 25-27. [18] X. Ning, X. Zhang, Y. Wang, M. Jaeger, Segmentation of architecture shape information from 3D point cloud[J]. In VRCAI, 2009:77-81 [19] Nguyen A, Le B. 3D point cloud segmentation: A survey[C].2013 6th IEEE conference on robotics, automation and mechatronics (RAM). IEEE, 2013. [20] Yan Li, Xie Hong, Hu Xiaobin, et al. A new hybrid point cloud plane segmentation method [J]. Journal of Wuhan University (Information Science Edition), 2013:128-130. [21] Schnabel, Ruwen. Efficient RANSAC for point ‐ cloud shape detection [J]. Computer graphics forum, 2007, 8(06): 1259-1284. [22] PVC Hough (1962) Method and Means for Recognizing Complex Patterns, US Patent 3069654. [23] Tarsha-Kurdi, Fayez, Tania Landes, and Pierre Grussenmeyer. Hough-transform and extended ransac algorithms for automatic detection of 3d building roof planes from lidar data [J], 2007. [24] Li L, Yang F, Zhu H, et al. An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells [J]. Remote Sensing, 2017:160-163. [25] ZHANG Liangpei, Z Yun, C Zhenzhong, et al. Splitting and Merging Based Multi-model Fitting for Point Cloud Segmentation. Acta Geodaetica et Cartographica Sinica, 2018. [26] Felzenszwalb P F, Huttenlocher D P. Efficient graph-based image segmentation [J]. International journal of computer vision, 2004, 59(2): 167-181. [27] Chen X, Golovinskiy A, Funkhouser T. A benchmark for 3D mesh segmentation [J]. Acm transactions on graphics (tog), 2009, 28(3): 1- 12. [28] URAL S, SHAN J. Min-cut Based Segmentation of Airborne LiDAR Point Clouds[C]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXIX-B3. Melbourne, Australia:ISPRS, 2012:167-172. [29] Li Minglei, Liu Shaochuang, Yang Huan, etc. A Two-level Optimized Lidar Point Cloud Scene Segmentation Method. Journal of Surveying and Mapping, 2018, 47 (2): 269-274. [30] ANDONI A, INDYK P. Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[C]//Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. Berkeley, CA, USA: IEEE, 2006:459-468. [31] YU Yongtao, LI J, GUAN Haiyan, et al. Learning Hierarchical Features for Automated Extraction of Road Markings from 3-D Mobile LiDAR Point Clouds[J]. IEEE Journal of Selected Topics in International Journal of Advanced Network, Monitoring and Controls Volume 05, No.01, 2020 71 Applied Earth Observations and Remote Sensing, 2015, 8(2): 709– 726. [32] PANG Guan, NEUMANN U. Training-based Object Recognition in Cluttered 3D Point Clouds[C]. Proceedings of 2013 International Conference on 3D Vision-3DV 2013. Seattle, WA, USA: IEEE, 2013:87-94. [33] Yang Bisheng, Mei Baoyan. Research on 3D City Model Visualization [D]. 2000. [34] Qi C R, Su H, Mo K, et al. Pointnet: Deep learning on point sets for 3d classification and segmentation[C]. Proceedings of the IEEE conference on computer vision and pattern recognition. 2017: 652- 660. [35] Zhao Zhongyang, Cheng Yinglei, Shi Xiaosong, et al. LiDAR point cloud feature classification method based on multi-scale features and PointNet [J]. Progress in Laser and Optoelectronics, 2019, 56 (5): 052804. [36] Niu Chengeng, Liu Yujie, Li Zongmin, et al. Method of 3D target recognition and model segmentation based on point cloud data [J]. Journal of Graphics, 2019, 40 (2): 274-281.