Review of 3D Point Cloud Data Segmentation 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 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.

Figure 1.

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.

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.

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 segmentation. [8-9].

Figure 2.

Figure 3.

Many scholars then the algorithm is improved. Zhang[10] use Otsu determining the optimal segmetation 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-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 susceptible 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 decomposing 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 segmentation 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.

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 geometric 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.

Figure 4.

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.

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.

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 between different vertices to construct weights, and combines regions. Chen[27] achieves the goal of automatic segmentation by building a k-nearest neighbor graph, adding background constraints, and finding the minimum secant line. Compared with several segmentation 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 independent regions according to the maximum posterior estimation criterion. Li et al.[29] proposed a progressive 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].

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 discriminate 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 classification 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 I.