Point cloud is in the same space reference frame to express target spatial distribution and the characteristics of the target surface mass point set, compared with the two-dimensional images, point cloud has its irreplaceable advantages in - depth information, not only avoid the point cloud data encountered in the process of image acquisition of pose, illumination, and itself has abundant spatial information, can effectively express the space objects in size, shape, location and direction [1]. Compared with voxel data, point cloud data has a higher spatial utilization rate, pays more attention to describing the outer surface shape of the object itself, and will not save useless redundant information to describe the occupancy of space. Point cloud segmentation is the essence of point cloud processing, and it is also the embodiment of the biggest advantage of 3D image compared with 2D image. The purpose of point cloud segmentation is to extract different objects in the point cloud, so as to achieve the purpose of divide and conquer, highlight the key points and deal with them separately [2]. Enhance cloud data processing capabilities.
The so-called image segmentation is the use of image gray, color, texture, shape and other features, the image is divided into a non-overlapping area, and make these features in the same area of similarity. There are obviously differences according to the different regions. The unique regions of the segmented image are extracted for different research [3]. Point cloud segmentation refers to the process of dividing points in three-dimensional space into smaller, coherent and connected subsets (This is shown in Figure 1). As shown in Figure 1, the left and right images show the results of segmentation from the tooth point cloud model. As the foreground point cloud (i.e. segmentation target), the white point cloud is completely segmented for further observation and research [4].
Diagram of point cloud segmentation.
After segmentation, points with similar properties are grouped together. A subset of these points should be “meaningful” and split to produce a series of objects of interest to us, such as roofs, trees, streets, and so on. These segments are usually represented as simple geometric primitives[5]. According to the mathematical methods used, Existing segmentation algorithms can be divided into the following categories [6].
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:
a)
b)
c)
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.
Diagram of watershed algorithm
Bottom-up flooding simulation is a recursive process. Definitions are as follows (1):
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.
Regional growth diagram
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.
Diagram of point cloud region growth
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].
Clustering algorithm flow diagram
Clustering methods are mainly divided into five categories:
Principle: Attempts are made to stratify all the data sets so that they form a tree cluster structure. Partitioning of a dataset can be done using both a “bottom-up” aggregation strategy and a “top down” partitioning strategy.
Principle: First, a bunch of scattered points should be determined and finally grouped into several classes, then several points should be selected as the initial center points, and then the data points should be iteratively reset according to the heuristic algorithm of pre-set number, the target effect of “intra-class point closer, inter-class point farther” is finally achieved.
Principle: Set a distance radius, the minimum number of points, and then can reach the points are connected, judge for the same kind.
Principle: The data space of point cloud number is divided into many grid units, the data object set is mapped into grid units, and the cell density of each grid unit is calculated. According to the preset threshold value to determine whether the area is high density, Grid cells with sufficient density form clusters.
Principle: A model is assumed for each cluster, and the best fitting of data to a given model is sought. This kind of methods mainly refer to the methods based on probability model and neural network model, especially the methods based on probability model.
A graph is composed of vertices and edges, represented as
Undirected graph
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):
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.
With the continuous development of technology, point cloud segmentation technology is no longer restricted to a single one or two. The data model can be segmented by different methods. But compared with several different segmentation methods, there are still different application scenarios, different segmentation methods also have their own advantages and disadvantages.
a)
b)
c)
d)
COMPARISON OF VARIOUS SEGMENTATION ALGORITHMS
Segmentation type | Tightness | To deal with noise | The processing time | Application Scenarios |
---|---|---|---|---|
|
worst | difficult | fast | Large scene segmentation with a priori capability |
|
best | perfect | Depends on the number of point | High precision segmentation scene |
|
better | suitable for detecting some objects with special shape from the chaotic point cloud | fast | Clustering is the division of a data set into different classes according to a particular criterion |
|
worst | general | It depends on the number of edges | More for image segmentation |
By analyzing the table can be seen In the context of current segmentation technology, region growing segmentation technology and clustering in noise processing and better segmentation accuracy The segmentation method combined with semiautomatic segmentation technique is more suitable used in medical, forensic, etc But higher precision means that need more electricity to describe cloud model, has led to the slower speed And figure capable of prior segmentation and semantic segmentation is more suitable big scene, such as automatic driving, etc Need fast real-time data judgment and interaction, the scenario does not require high precision Therefore, we need to make reasonable use of the advantages of different segmentation methods to better serve the purpose of human life.
From the point of research and application at home and abroad, point cloud segmentation technology can be described by fewer data points of a model advantages, has been gradually play an important role in all fields Although the point cloud segmentation has been a lot of research of geared to the needs of different applications, but because of the automatic segmentation technology also does not reach the designated position, excessive segmentation, adhesion condition can not completely eliminate, most algorithms are proposed for specific question. But from the point of view of development, with the progress of technology, the simple operation and human-computer interaction of automatic segmentation technology is the trend and trend of development.