A Review of Segmentation Technology Based on 3D Point Cloud

The boundary-based point cloud segmentation algorithm can obtain segmentation blocks by detecting regional boundaries. The main idea is to obtain the point cloud boundary through the drastic change of the point cloud intensity. The boundary gradient, the change of normal vector direction gradient on the point cloud surface and the 3D line matching were calculated. For the distance image, the scan line segmentation algorithm is not applicable to point cloud data with uneven density. The contour is extracted by binary data to achieve the purpose of fast segmentation[7]. One of the more representative is the famous watershed algorithm. The watershed concept is based on the visualization of the image in three dimensions: two of which are coordinates and one is grayscale. Based on this interpretation of “topographical”, we consider three categories:

Waterway segmentation method is a mathematical morphology segmentation method based on topological theory. At present, it is more famous and more used: bottom-up flood simulation algorithm. For a special region minimum, the set of points satisfying condition (b) is called the watershed of this minimum”. The set of points satisfying the condition (c) constitutes the peak line on the terrain surface, which is called the “watershed line” [8]. This is shown in Figure 2.

Figure 2.

Bottom-up flooding simulation is a recursive process. Definitions are as follows (1): (1) g ( x , y ) = g r a d ( f ( x , y ) ) = { [ f ( x , y ) − f ( x − 1 , y ) ] }

Where, f(x,y) represents the original image, and grad{.} represents the gradient operation.

Watershed algorithm responds well to over segmentation through weak edges, image noise and slight changes of object surface gray. However, we must also see that the watershed algorithm is well adapted to the weak edges, which are guaranteed by continuous, closed edges. In addition, the closed basin obtained by the tilt algorithm can be used to analyze the regional features of the image [9].

In order to reduce the excessive segmentation caused by the branching algorithm, two processing methods are commonly used. One is to use prior knowledge to remove irrelevant edge information. Another approach is to modify the gradient function so that the location responds only to the desired target.

Area growth is the process of aggregating pixels or subregions into a larger area according to a predefined standard. Its basic idea is to start from a group of growing points (the growing point can be a single pixel or a small region), and combine the pixels near the growing point or the region with similar properties with the growing point to form a new growing point. Repeat the process until the growing points fail to grow or are completely covered. The similarity criterion between growing point and adjacent area can be color, texture, gray level and other image information [10].

Steps of the algorithm: Sort the input point cloud according to the curvature value of the point cloud The point cloud with the least curvature among all the point clouds is selected as the initial seed (foreground point cloud), because the region where the point is located is the smoothest region. Starting from the smoothest region can reduce the total number of segmentation fragments and improve the segmentation efficiency [11]. Initialize the seeds of an empty sequence and empty clustering regions, from the sort of point cloud is selected after the initial seed points are added to the seed point sequence, and search for its neighborhood points, comparing each neighborhood point and normal Angle between the seed point, if the result is less than smooth threshold, then add the current point to the current area, if the neighborhood point curvature is less than the curvature threshold (artificial), it is added to the seed point in the sequence, delete the current seed points, loop through the above steps, until the seed sequence is empty is shown in Figure 3.

Figure 3.

As shown in Figure 4, the initial point cloud of the cactus point cloud model is red, and with the progress of the region growth algorithm, the white point cloud gradually increases. If the segmentation threshold is not set, the white point cloud will eventually cover the whole model. However, in this process, we choose the appropriate boundary and curvature threshold value, then we can get a reasonable segmentation result.

Figure 4.

Clustering algorithm is a very practical image segmentation algorithm. Firstly, attributes such as pixel gray level are mapped into the feature space, which is divided into many regions according to the response rules. Then according to the attributes of the voxel to determine the pixel belongs to the region, and mark out for segmentation. Clustering generally includes hard clustering, probability clustering, fuzzy clustering and other methods [12].

Figure 5.

Clustering methods are mainly divided into five categories:

A graph is composed of vertices and edges, represented as G(V, E). Each pixel represents a vertex V_i ∈ E of the graph, and two adjacent pixels constitute an edge (V_i, V_j ) ∈ E. The difference in pixel color values constitutes the weight W_{(Vi, Vj)} of the edge (V_i, V_j ), see Figure 6.

Figure 6.

The inspiration for this algorithm comes from neighborhood graphs or the construction of neighborhood graphs. The points in the same partition are closer than the points in different interesting connections [13]. Therefore, the boundary of two segmented regions must be the place where the connection is weakest. The adjacent graph is the attribute graph in the point cloud. Each node in the figure corresponds to a point in the point cloud model, and each edge has a weight, which represents the similarity of a pair of points in the point cloud. Through the graph segmentation algorithm to achieve segmentation, the point similarity between different segmented faces as small as possible, the point similarity of the same segmented face as large as possible. Segmentation can be achieved by recursive segmentation or direct multiplexing. In 1999, Kim described the development of an algorithm that could automatically detect buildings from aerial images [14]. In 2001, Fuchs proposed a graph-based approach to city modeling. In 2008, Wang proposed a graph-based segmentation method for airborne radar scan data. In 2009, Aleksey Golovinskiy proposed a point cloud segmentation algorithm based on the minimum cut value. Given the target position, this method constructs the k-nearest neighbor graph, assumes the background in advance, sets constraints on the foreground (optional background), and calculates the forest background segmentation scheme by finding the minimum cut[15].

The energy equation solved by the minimum cut algorithm is usually an energy solution method based on graph structure. Such energy equation can be generally expressed as (2): (2) E ( L ) = Σ D p + ( L p ) + Σ V p , q ( L p , L q )

Where L is the result of a label of image P. Set of 3 * 3 P images, P = [3, 8, 9, 4, 9, 8, 2, 9, 7], now want to P pixels can be divided into two kinds, the tag value is 1 or 2, L is one of the all possibility of P can be L = [1, 2, 2; 1, 2, 2; 1, 2, 2] or L = [1, 1, 2; 1, 2, 2, 2, 2, 2] (and many did not enumerated), all the possibilities for 2 ^ 9 L, The energy equation E(L) is to calculate the energy value under the current label result. Usually, we minimize the energy equation, so as to find the label value L that can make the overall energy minimum. The final pixel classification result is used to get the image segmentation and other results.