Xi'an Technological University
Subject: Computer Science, Software Engineering
eISSN: 2470-8038
SEARCH WITHIN CONTENT
Wang Xu ^{*} / Liu Baolong ^{*}
Keywords : Virtual, Point Cloud, 3D Model, Segment
Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 6, Issue 1, Pages 35-40, DOI: https://doi.org/10.21307/ijanmc-2021-006
License : (CC-BY-NC-ND 4.0)
Published Online: 19-April-2021
Point cloud is an important data format that can completely express scene information. In recent years, with the dramatic increase of polygon complexity of model, the advantage of point model becomes more and more obvious. The point-based computer graphics, which takes point cloud as the research object, has aroused the attention of more and more people, and has been widely used in many fields such as computer vision, automatic driving and robot. In this paper, the point cloud segmentation methods and research status were reviewed in detail, the representative algorithms of each type of methods were analyzed and introduced, and the basic ideas, advantages and disadvantages of each type of methods were summarized. Finally, the problems faced by the segmentation technology and the development direction of the future work are prospected.
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].
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) The point belonging to the local minimum value may also have a minimum plane, in which all the minimum points are
b) When a drop of water is placed at a certain point, the water must fall to a single minimum point
c) When water is at a certain point, it will flow to more than one of these minimum points with equal probability
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.
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.
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.
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 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.
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.
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) Edge based methods: In the field of computer vision, the edge detection algorithms of image segmentation are quite mature. Radar data can be converted into depth images (such as digital surface models), making it suitable for image edge detection algorithms. The effect of segmentation depends largely on the edge detector. However, some information is inevitably lost when the 3D point cloud is converted to a 2.5D depth image. Therefore, the boundary-based segmentation method cannot be used for high-precision segmentation scenes, nor can it be used for face recognition, but it also has a place in autonomous driving and other aspects.
b) Region based methods: Region growth stops when there are no pixels or when a region meets the conditions to be added to a growing region. Advantages: the basic idea is relatively simple. Usually, point cloud regions with the same characteristic information can be segmented and good boundary information and segmentation results can be provided. It can achieve the best performance without prior knowledge and can be used for more complex image segmentation, such as natural scenes, coins, medical images, etc. Disadvantages: The segmentation algorithm based on region growth is an iterative method, but it consumes a lot of space and time. When the noise is not uniform, it will lead to voidness and over-segmentation, and the shadow effect in the image is often not perfect.
c) Cluster based method: Each point is associated with an eigenvector, which in turn contains several geometric or radiative measures. Then, the point cloud data is segmented by clustering in the feature space. Different from other methods, the clustering method is implemented in the feature space, and it can operate on point cloud, mesh and TIN triangular mesh. The performance of clustering algorithm depends on the choice of feature space and clustering method. The clustering algorithm has shown its robustness in the segmentation of airborne or ground-based laser scan point clouds.
d) Graph based methods: In terms of time efficiency, the algorithm basically has a linear relationship with the number of edges represented by the graph of the image, while the edges represented by the graph of the image are proportional to the pixel points, that is to say, the time efficiency of image segmentation has a linear relationship with the number of pixel points of the image. This algorithm has a very important property, it can keep the details of the low variation region, and can ignore the details of the high variation region. This is a very special and very important property, it’s a very good segmentation of the image, being able to find areas that are visually consistent, in short, areas of high variability have a very good aggregation, being able to separate them into the same area.
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.