# AOMC: An Adaptive Point Cloud Clustering Approach for Feature Extraction

Authors: Zhengyu Zhang; Mengdi Jin
Journal: Scientific Programming
 (2022)

---

## Abstract

Point cloud local feature extraction places an important part of point cloud deep learning neural networks. Accurate extraction of point cloud features is still a challenge for deep learning networks. Oversampling and feature loss of point cloud model are important problems in the accuracy of image point cloud deep learning network. In this paper, we propose an adaptive clustering method for point cloud feature extraction—adaptive optimal means clustering (AOMC)—and apply it to point cloud deep learning network tasks. This method solves the problem of determining the number of clustering centers in the process of point cloud feature extraction so that the feature points contain the whole point cloud model and avoid the problem of losing detail features. Specifically, according to the loss characteristics of point cloud clustering, AOMC selects a different number of clustering centers for various models. Moreover, in light of the density distribution of the point cloud, the radius of the clustering subset is determined. This method effectively improves the accuracy of the point cloud deep learning network on object classification and parts segmentation. Our method reaches demand on Modelnet10 and shapenetcore_partanno_segmentation_benchmark datasets. In terms of deep learning network optimization, it has good performance. Additionally, our method has high accuracy and low algorithm complexity.


---

## Body

## 1. Introduction

With the rapid development of point cloud intelligence, researchers have paid much attention to the application of deep learning networks in point cloud recognition [1–3]. Moreover, machine learning algorithms are gradually being applied to improve the performance of point cloud recognition. Point cloud intelligence is widely used in surveying mapping, machine recognition, model design, virtual reality, and other fields [4–8].Point cloud intelligence algorithm based on a deep learning network mainly focuses on object classification, object detection, parts segmentation, and semantic segmentation [9, 10]. Point cloud deep learning networks gather different functions in the same network to realize the integration of various tasks [11–15]. Figure 1 shows the main task and processing flow of the point cloud deep learning network, which includes two main parts: point cloud feature extraction and deep learning computing. The aim of point cloud feature extraction is to extract effective features from the point cloud model. The extracted features are used for analysis to meet different task requirements. The deep learning network is composed of different convolution kernels. The purpose of convolution is to use features to optimize the loss function, so as to realize the segmentation and classification of the point cloud model.Figure 1
The architecture of point cloud deep learning network.For the shape analysis task based on the point cloud, it is a fundamental problem to realize the effective representation of local shape features (normal, curvature, etc.). The representation of local shape features is affected by many interference factors, including noise, dynamic sampling density, complex geometric details, and defective parts. These interference factors undoubtedly affect the local shape feature representation of the point cloud and then affect the performance of related applications. To solve this problem, we usually use the local neighborhood estimation of each point in the point cloud to establish an implicit surface representation to realize the simulation of local features.Because point cloud is of disordered and irregular data structure, unlike 2D data, it is impossible to simply use convolutional neural networks (CNN) for feature extraction. Before deep neural networks were envisioned, three-dimensional operators were commonly used to achieve point cloud parts segmentation [16, 17]. To capture finer structures and more accurate boundaries, numerous refinement strategies have been proposed. In 2015, the VoxNet model was presented based on the voxelization model [8]. At the same time, a multiview convolutional neural network (MV-CNN) was proposed based on the multiview sampling method [18]. However, none of these methods can directly act on point cloud data to extract the features of the point cloud.Clustering is a typical unsupervised learning algorithm. The main idea is to divide the data set into different subsets according to the different attribute features of the undetermined data [3]. The main way to evaluate the clustering effect is to see if objects of the same category are classified into the correct subcategory. Compared with objects between groups, objects within groups have a high degree of similarity, while objects between different groups are very different. For 2D and 3D data, a clustering algorithm can realize effective segmentation of objects, which includes segmentation between different categories and segmentation of parts within objects.Figure2 shows the process of feature extraction of the 3D point cloud deep learning network. Firstly, the feature center of the point cloud is carried out. Then, taking the feature center as the center of the sphere and selecting the radius to extract the hierarchical feature points of the point cloud, the purpose is to obtain the local features of the point cloud model. Finally, the extracted feature points are input into the deep learning network to realize the task of point cloud classification and parts segmentation.Figure 2
Hierarchical feature extraction process of point cloud deep learning.Figure3 shows the process of point cloud feature extraction; if the feature center is not selected reasonably, it will lead to the loss of local features of the point cloud, which will affect the accuracy of the point cloud deep learning network [19, 20]. In practice, supervised learning and unsupervised learning can be used to select feature points of the point cloud [21–23]. However, the time complexity of some methods is high, and the accuracy of other methods is too low. Moreover, the algorithm parameters are not reasonable for the point cloud category, which leads to the waste of computing resources [24, 25]. Therefore, it is very important to propose a point cloud feature extraction method with low computational complexity, high accuracy, and adaptability for the optimization of the point cloud deep learning network.Figure 3
Problems in hierarchical feature learning of point cloud: (a) the sampling area does not cover the whole point cloud model and (b) the overlapping of sampling space leads to repeated feature extraction.
(a)(b)In this paper, we primarily consider point cloud classification and parts segmentation, two model tasks in the point cloud processing world. We propose a feature extraction method based on unsupervised learning. The number and radius of clustering are determined according to different cloud types by statistical method. The adaptive feature extraction of the point cloud is realized by parallel optimization. This method not only can ensure the complete coverage of the point cloud range but also can avoid the occurrence of repeated sampling and missing sampling. Moreover, compared with the traditional adaptive clustering method, this algorithm has lower algorithm complexity and higher practicality in parameter settings.This method includes the process of determining the number of clustering centers and feature points extraction of the point cloud model. The purpose is to achieve accurate feature extraction of the point cloud model and avoid the loss of detail feature points. And we apply the feature points in the training process of the point cloud deep learning network, improving the training speed and accuracy of the network.Compared with the existing clustering methods, this method has some advantages. We also compare the convergence speed of the deep learning network during the training process to evaluate the effect of how this algorithm improved the process of network training. Experimental results show that this method has a certain effect on the optimization of the point cloud deep learning neural network. In summary, our major contributions are as follows:(i)
We propose a point cloud feature extraction method based on clustering and adaptive optimization. When extracting the feature points of point cloud models, it not only can keep details of the local feature but also can reduce the complexity of the algorithm.(ii)
Our method sets different sampling centers and sampling radii for different point cloud types. The purpose is not only to cover the whole range of the point cloud and avoid missing detection but also to ensure that the overlapping part of the clustering subregion is small and prevent resampling.(iii)
We conduct comprehensive experiments on several benchmark data sets: Modelnet10 [26] and shapenetcore_partanno_segmentation benchmark [27], to validate the effectiveness and efficiency of our proposed method for point cloud classification and parts segmentation tasks. In the point cloud deep learning network optimization, it has a significant effect.This paper is organized as follows. In Section2, we provide an overview of the literature on point cloud feature extraction. We propose an adaptive point cloud clustering method in detail in Section 3. Section 4 shows the detailed experimental results. Finally, Section 5 concludes this paper.


## 2. Related Work

In the process of point cloud feature extraction, machine learning algorithms, including supervised learning [1, 2, 28, 29] and unsupervised learning [3, 30, 31], are widely applied. And the feature points are used to train deep learning networks [27, 32]. Point cloud feature extraction affects the performance of the deep learning network.


### 2.1. Supervised Learning

Supervised learning is to adjust the parameters of the classifier according to the class label of the sample space. Typical supervised learning includes SVM, naive Bayesian model (NBM), decision tree, and so on. In three-dimensional space, supervised learning determines the classification plane according to the category of the point cloud, so as to ensure the generalization ability of the classifier [28, 29].Yu and Yang proposed a point cloud sampling method based on the k-nearest neighbor algorithm (k-NN) [1]. The k-NN algorithm determines the center of the sampling based on the category of point cloud data and calculates the radius of the sampling area. The algorithm fully considers the category attributes of each point in the point cloud and makes full use of the distribution of points in the point cloud.But, for not categorized point cloud data, the k-NN algorithm cannot be used. At the same time, the amount of point cloud data collected by point cloud acquisition devices such as LiDAR is very large [12–14], and the amount of input data for training deep learning networks is also very large. Therefore, it is impossible to label the category of each point. Besides, the algorithm ignores the sparse degree of point cloud distribution, lacking certain self-adaptability. In addition, for point cloud models with more complex distributions, this algorithm increases the number of sampling points that increases the computational complexity of the deep learning network.


### 2.2. Unsupervised Learning

Unsupervised learning is an algorithm that divides the classification space without prior knowledge. Typical supervised learning includes PCA [30], agglomerative clustering, density-based spatial clustering of applications with noise (DBSCAN), and so on [31]. In the three-dimensional space, the clustering method can divide and extract the target of the point cloud without knowing the classification of the point cloud.Han studied the point cloud clustering segmentation algorithm based on k-means [3]. This method is implemented based on a certain number of cluster centers, which lacks self-adaptability for different types of point clouds. At the same time, the k-means algorithm needs to initialize the cluster center number before clustering. Therefore, if the cluster center is not well selected, it will have a great impact on the k-means algorithm, which will lead to negative effects such as poor clustering or slow convergence speed.There is a problem with unsupervised learning. Without knowing the exact number of samples, it is impossible to select the best number of clustering centers. If the number of feature points is too small, the feature information of the point cloud will be lost [33], and the task of point cloud recognition is impossible. If the number of feature points is too large, the complexity of the network will be too high, and the computing resources will be wasted [34, 35].The unsupervised learning clustering algorithm has some limitations for unknown data. If the initial point of clustering is not selected well, it may affect the convergence effect of the clustering algorithm [9, 16]. Therefore, it is very important to select the initial points, which can cover the whole point cloud model for point cloud feature extraction [8, 10].At the same time, for different point cloud categories, the value of the cluster subset number is different [1]. For the point cloud model with simple distribution, fewer clustering centers can cover the whole point cloud model. For the point cloud model with complex density distribution and more detailed features, uniform feature extraction is needed to achieve effective feature extraction.Although DBSCAN clustering algorithm can determine the number of clusters center according to the classification of point cloud [36, 37], in practical application, it is necessary to determine the distance between core points and the minimum number of sample points (MinPts) in the classification subset. Sometimes, due to the accuracy of point cloud computing, the actual application effect of the DBSCAN algorithm needs to be improved. And DBSCAN algorithm has high complexity.


### 2.3. Point Cloud Deep Learning Network

In 2017, Qi et al. proposed a network model: PointNet [28], which directly targets disordered point clouds. At the same time, in order to obtain hierarchical features such as the CNN model and extract the local features of the point cloud, Qi et al. then proposed a point cloud deep learning network using hierarchical feature learning: PointNet++ [29]. PointNet++ network uses the farthest point sampling and ball query method, which fully covers all the points in the point cloud to avoid outliers in the sampling process. An array of improved algorithms are gradually applied to a deep learning network [38–41] in the past several years. Their main thought is to improve the effect of point cloud feature extraction for developing the performance of a deep learning network.In the basic PointNet++ network, point cloud feature extraction uses the farthest point sampling and the ball query method, which has a certain degree of randomness and ignores the distribution features of the point cloud. Therefore, the feature clustering method is used here to extract and sample the feature of the point cloud. And the time complexity (ON2) of farthest point sampling is high. At the same time, due to the random selection of sampling centers, there may be overlap between different sampling points areas, causing repeated sampling. In addition, the sampling radius of the basic algorithm is of fixed value, which will cause the lack of self-adaptability of sampling, and it is impossible to sample reasonably according to the specific situation of the point cloud distribution.


## 2.1. Supervised Learning

Supervised learning is to adjust the parameters of the classifier according to the class label of the sample space. Typical supervised learning includes SVM, naive Bayesian model (NBM), decision tree, and so on. In three-dimensional space, supervised learning determines the classification plane according to the category of the point cloud, so as to ensure the generalization ability of the classifier [28, 29].Yu and Yang proposed a point cloud sampling method based on the k-nearest neighbor algorithm (k-NN) [1]. The k-NN algorithm determines the center of the sampling based on the category of point cloud data and calculates the radius of the sampling area. The algorithm fully considers the category attributes of each point in the point cloud and makes full use of the distribution of points in the point cloud.But, for not categorized point cloud data, the k-NN algorithm cannot be used. At the same time, the amount of point cloud data collected by point cloud acquisition devices such as LiDAR is very large [12–14], and the amount of input data for training deep learning networks is also very large. Therefore, it is impossible to label the category of each point. Besides, the algorithm ignores the sparse degree of point cloud distribution, lacking certain self-adaptability. In addition, for point cloud models with more complex distributions, this algorithm increases the number of sampling points that increases the computational complexity of the deep learning network.


## 2.2. Unsupervised Learning

Unsupervised learning is an algorithm that divides the classification space without prior knowledge. Typical supervised learning includes PCA [30], agglomerative clustering, density-based spatial clustering of applications with noise (DBSCAN), and so on [31]. In the three-dimensional space, the clustering method can divide and extract the target of the point cloud without knowing the classification of the point cloud.Han studied the point cloud clustering segmentation algorithm based on k-means [3]. This method is implemented based on a certain number of cluster centers, which lacks self-adaptability for different types of point clouds. At the same time, the k-means algorithm needs to initialize the cluster center number before clustering. Therefore, if the cluster center is not well selected, it will have a great impact on the k-means algorithm, which will lead to negative effects such as poor clustering or slow convergence speed.There is a problem with unsupervised learning. Without knowing the exact number of samples, it is impossible to select the best number of clustering centers. If the number of feature points is too small, the feature information of the point cloud will be lost [33], and the task of point cloud recognition is impossible. If the number of feature points is too large, the complexity of the network will be too high, and the computing resources will be wasted [34, 35].The unsupervised learning clustering algorithm has some limitations for unknown data. If the initial point of clustering is not selected well, it may affect the convergence effect of the clustering algorithm [9, 16]. Therefore, it is very important to select the initial points, which can cover the whole point cloud model for point cloud feature extraction [8, 10].At the same time, for different point cloud categories, the value of the cluster subset number is different [1]. For the point cloud model with simple distribution, fewer clustering centers can cover the whole point cloud model. For the point cloud model with complex density distribution and more detailed features, uniform feature extraction is needed to achieve effective feature extraction.Although DBSCAN clustering algorithm can determine the number of clusters center according to the classification of point cloud [36, 37], in practical application, it is necessary to determine the distance between core points and the minimum number of sample points (MinPts) in the classification subset. Sometimes, due to the accuracy of point cloud computing, the actual application effect of the DBSCAN algorithm needs to be improved. And DBSCAN algorithm has high complexity.


## 2.3. Point Cloud Deep Learning Network

In 2017, Qi et al. proposed a network model: PointNet [28], which directly targets disordered point clouds. At the same time, in order to obtain hierarchical features such as the CNN model and extract the local features of the point cloud, Qi et al. then proposed a point cloud deep learning network using hierarchical feature learning: PointNet++ [29]. PointNet++ network uses the farthest point sampling and ball query method, which fully covers all the points in the point cloud to avoid outliers in the sampling process. An array of improved algorithms are gradually applied to a deep learning network [38–41] in the past several years. Their main thought is to improve the effect of point cloud feature extraction for developing the performance of a deep learning network.In the basic PointNet++ network, point cloud feature extraction uses the farthest point sampling and the ball query method, which has a certain degree of randomness and ignores the distribution features of the point cloud. Therefore, the feature clustering method is used here to extract and sample the feature of the point cloud. And the time complexity (ON2) of farthest point sampling is high. At the same time, due to the random selection of sampling centers, there may be overlap between different sampling points areas, causing repeated sampling. In addition, the sampling radius of the basic algorithm is of fixed value, which will cause the lack of self-adaptability of sampling, and it is impossible to sample reasonably according to the specific situation of the point cloud distribution.


## 3. Our Method

We propose a novel point cloud sampling method based on unsupervised learning: adaptive optimal means clustering for point cloud feature extraction (AOMC), which improves the clustering effect of nonmeans clustering. It can be roughly divided into two steps: cluster center number determination and adaptive optimal cluster. Figure4 shows the process of AOMC.Figure 4
Adaptive optimal means clustering for neural networks.Firstly, our method determines the number of clustering centers for different categories of point cloud according to the change of the within-cluster sum of squared errors (SSE), raising the adaptability between the selection of the number of cluster centers and the point cloud category. The density of point cloud distribution is different among point cloud models. And various objects have different details, so it is a significant way to select suitable clustering center numbers for each of the point cloud models. Then, adaptive clustering is carried out. The requirement of clustering is not only to realize the uniform distribution of feature points in the point cloud model but also to avoid the loss of detail feature points. At the same time, AOMC avoids the repeated sampling caused by the excessive overlap of each subclass. AOMC makes the clustering centers reasonably and evenly distributed in the point cloud model, so as to improve the clustering effect. After sampling feature points, we input them into the deep learning network. CNN-based deep learning network can learn hierarchical features to achieve the parts segmentation and object detection tasks for point cloud models. The method is applied to the PointNet++ network. By the point cloud classification accuracy and parts segmentation tasks, the degree of improvement of the point cloud deep learning network by this algorithm is analyzed.Figure5(a) reflects the effect of common point cloud feature extraction. Because the number of clustering centers is uncertain, the position of the clustering center is unreasonable. Meanwhile, the cluster radius of different cluster subsets is the same, which leads to repeating sampling and missing sampling. The above factors will lead to the loss of point cloud features, which will affect the performance of the deep learning network.Figure 5
Comparison between common feature extraction and adaptive feature extraction: (a) common point cloud feature extraction and (b) adaptive point cloud feature extraction.Figure5(b) is the result of adaptive point cloud feature extraction. Points are divided into two categories according to their distribution position. Each category has its own clustering center. According to the distance from the cluster center to the farthest point of the cluster subset, the radius of each cluster range is determined. It can be seen from Figure 4 that the adaptive clustering algorithm can effectively reflect the distribution features of the point cloud model. Therefore, the point cloud feature extraction through clustering can effectively reflect the structural features and distribution features of the point cloud. The loss of detailed features of the point cloud caused by randomness is avoided. The method we proposed is to use adaptive clustering to improve the performance of the deep learning network.


### 3.1. Number of Cluster Centers Generation

The error of the cluster algorithm is measured bySSE, where μj is the center point of the cluster j (j∈1,2,…,k). It is generally considered that the clustering solution process is a problem of optimization (minimization) of the SSE. We set the number of clustering samples as n. If the sample xi (i∈1,2,…,n) belongs to the jth cluster, then wi,j = 1; otherwise, wi,j = 0.(1)SSE=∑i=1n∑j=1kwi,j=xi−μj22.Based on the visualization tool of SSE, the optimal number of cluster centers is estimated for a given task. The basic method to determine the elbow point is to find the parameter of the cluster center when the clustering deviation increases abruptly. If the curve attenuation is gentle and there is no obvious elbow point, is the best sampling value when the SSE is set to be a threshold, usually less than 300.We can draw the clustering deviation diagram with different values of the cluster center and observe the position of the elbow point.Figure6 is an image in which the SSE of the clustering changes with the number of cluster centers. It can be seen that the SSE decreases with the increase of cluster center number. When the number of cluster centers is three, the curve of Figure 6(b) presents an obvious elbow shape, which is called the elbow point. Therefore, three is a better choice for this set of data in Figure 6(a). The selection of elbow points should not only consider the degree of error change but also consider the absolute size of the error. If the error changes more gently with the increase of cluster centers or the elbow point appears in the place with a large error, the number of cluster centers with a small error should be selected as the best parameter.Figure 6
Elbow point selection schematic: (a) two dimensional of three cluster centers and (b) the relationship between the change of clustering number centers and SSE in (a). When the number of cluster centers is 3, the curve appears obvious “elbow point.”
(a)(b)


### 3.2. Adaptive Optimal Clustering

After obtaining the optimal clustering center of each point cloud model, we then determine the location of the cluster center and divide the point cloud model into different subsets.The main idea of AOMC is that the mutual distance between the initial cluster centers is as far apart as possible. We set the point cloud model as a setx. Our aim is to obtain a set of clustering results xcluster. Initially, the point cloud model is a set of n sample points. We take μ to record each selected cluster center point.We set an empty setM to record the selected cluster center points, then randomly select the first center point μ1 from the input sample, and add it to the set M.For each sample pointxi (i∈1,2,…,n−1) outside the set M, we calculate the shortest Euclidean distance dxi,M2 between each sample point and the current cluster center set M. According to the distance, the probability distribution dxi,M2/∑idxi,M2 is constructed. Then, based on the weighted distribution of distance, generate a probability value p between 0 and 1 and select the next central point μp from xi to M. In light of the probability distribution, the point in a set of xi farther away from M is more likely to be selected as the next cluster center μp. This ensures the uniform distribution of the initial cluster centers in the point cloud model.By repeating the above steps, the initial adaptive cluster centers are obtained. Compared with the random selection of initial cluster centers, the AOMC method ensures that the distance between the initial cluster center points is longer, and the distribution is uniform in the point cloud model.The remaining points ofx are classified into the cluster subsets corresponding to the cluster centers in M and initialize the SSE value of M. Then, set a threshold value for SSE. Based on the distribution of the points in the subset, the sample center of the subset is updated as the new cluster center in M. Update the current SSE of the point cloud model clustering result. Finally, when SSE is less than the threshold, we get the cluster result xcluster.The adaptive optimal means clustering (AOMC) algorithm is summarized in Algorithm 1:Algorithm 1: AOMC: adaptive optimal means clustering for point cloud feature extraction.
Input: Point cloud model xOutput: Clustering results xcluster(1)
M←μ1(2)
for 1 to k do(3)
Computedxi,M2(4)
Generate a valuep∈0,1(5)
ifp∈dxi,M2/∑idxi,M2(6)
M←xi(7)
end if(8)
end for(9)
Initialize SSE forM(10)
for SSE > threshold do(11)
xclusterj⟶SSE, j∈1,…,k(12)
UpdateM to the sample centers(13)
Updatexcluster(14)
Update SSE(15)
end for(16)
returnxcluster


### 3.3. Determination of Feature Points and Loss Function

After dividing the point cloud model into different adaptive clustering subsets, we then sample the data points of each subset. Sampling radius and loss function are defined as follows:Sampling radius. We carry out cluster sampling of point clouds according to different types of point clouds. First, in order to prevent the occurrence of outliers, the maximum coverage is the entire sample space. The sampling radius is defined from the center point to the farthest point in the class:(2)rj=xjf−μj22j∈1,…,k.Loss function. In the point cloud deep learning network, the maximum cross-entropy function is used as the measurement of the loss function. As shown in formula (3), it is the maximum cross-entropy function.First of all, the input class of the neural network is normalized here, which is defined as follows:(3)LS=eSi∑i=1keSi,whereSi denotes the output value of the multilayer perceptron for each point cloud class and k represents the number of point cloud classes in the sample. This operation is equivalent to the softmax layer function and ⋯S is output as a vector form. Next, the cross-entropy calculation is carried out between the output and the label, which is defined as follows:(4)L=−1k∑i=1kyilnLSi,whereyi is the actual label of each point cloud class; the label of each point cloud class is multiplied by the natural logarithmic form output by the normalization layer, and finally, the mean loss of the point cloud class is calculated by means of the mean value as the loss function of the deep learning network.


## 3.1. Number of Cluster Centers Generation

The error of the cluster algorithm is measured bySSE, where μj is the center point of the cluster j (j∈1,2,…,k). It is generally considered that the clustering solution process is a problem of optimization (minimization) of the SSE. We set the number of clustering samples as n. If the sample xi (i∈1,2,…,n) belongs to the jth cluster, then wi,j = 1; otherwise, wi,j = 0.(1)SSE=∑i=1n∑j=1kwi,j=xi−μj22.Based on the visualization tool of SSE, the optimal number of cluster centers is estimated for a given task. The basic method to determine the elbow point is to find the parameter of the cluster center when the clustering deviation increases abruptly. If the curve attenuation is gentle and there is no obvious elbow point, is the best sampling value when the SSE is set to be a threshold, usually less than 300.We can draw the clustering deviation diagram with different values of the cluster center and observe the position of the elbow point.Figure6 is an image in which the SSE of the clustering changes with the number of cluster centers. It can be seen that the SSE decreases with the increase of cluster center number. When the number of cluster centers is three, the curve of Figure 6(b) presents an obvious elbow shape, which is called the elbow point. Therefore, three is a better choice for this set of data in Figure 6(a). The selection of elbow points should not only consider the degree of error change but also consider the absolute size of the error. If the error changes more gently with the increase of cluster centers or the elbow point appears in the place with a large error, the number of cluster centers with a small error should be selected as the best parameter.Figure 6
Elbow point selection schematic: (a) two dimensional of three cluster centers and (b) the relationship between the change of clustering number centers and SSE in (a). When the number of cluster centers is 3, the curve appears obvious “elbow point.”
(a)(b)


## 3.2. Adaptive Optimal Clustering

After obtaining the optimal clustering center of each point cloud model, we then determine the location of the cluster center and divide the point cloud model into different subsets.The main idea of AOMC is that the mutual distance between the initial cluster centers is as far apart as possible. We set the point cloud model as a setx. Our aim is to obtain a set of clustering results xcluster. Initially, the point cloud model is a set of n sample points. We take μ to record each selected cluster center point.We set an empty setM to record the selected cluster center points, then randomly select the first center point μ1 from the input sample, and add it to the set M.For each sample pointxi (i∈1,2,…,n−1) outside the set M, we calculate the shortest Euclidean distance dxi,M2 between each sample point and the current cluster center set M. According to the distance, the probability distribution dxi,M2/∑idxi,M2 is constructed. Then, based on the weighted distribution of distance, generate a probability value p between 0 and 1 and select the next central point μp from xi to M. In light of the probability distribution, the point in a set of xi farther away from M is more likely to be selected as the next cluster center μp. This ensures the uniform distribution of the initial cluster centers in the point cloud model.By repeating the above steps, the initial adaptive cluster centers are obtained. Compared with the random selection of initial cluster centers, the AOMC method ensures that the distance between the initial cluster center points is longer, and the distribution is uniform in the point cloud model.The remaining points ofx are classified into the cluster subsets corresponding to the cluster centers in M and initialize the SSE value of M. Then, set a threshold value for SSE. Based on the distribution of the points in the subset, the sample center of the subset is updated as the new cluster center in M. Update the current SSE of the point cloud model clustering result. Finally, when SSE is less than the threshold, we get the cluster result xcluster.The adaptive optimal means clustering (AOMC) algorithm is summarized in Algorithm 1:Algorithm 1: AOMC: adaptive optimal means clustering for point cloud feature extraction.
Input: Point cloud model xOutput: Clustering results xcluster(1)
M←μ1(2)
for 1 to k do(3)
Computedxi,M2(4)
Generate a valuep∈0,1(5)
ifp∈dxi,M2/∑idxi,M2(6)
M←xi(7)
end if(8)
end for(9)
Initialize SSE forM(10)
for SSE > threshold do(11)
xclusterj⟶SSE, j∈1,…,k(12)
UpdateM to the sample centers(13)
Updatexcluster(14)
Update SSE(15)
end for(16)
returnxcluster


## 3.3. Determination of Feature Points and Loss Function

After dividing the point cloud model into different adaptive clustering subsets, we then sample the data points of each subset. Sampling radius and loss function are defined as follows:Sampling radius. We carry out cluster sampling of point clouds according to different types of point clouds. First, in order to prevent the occurrence of outliers, the maximum coverage is the entire sample space. The sampling radius is defined from the center point to the farthest point in the class:(2)rj=xjf−μj22j∈1,…,k.Loss function. In the point cloud deep learning network, the maximum cross-entropy function is used as the measurement of the loss function. As shown in formula (3), it is the maximum cross-entropy function.First of all, the input class of the neural network is normalized here, which is defined as follows:(3)LS=eSi∑i=1keSi,whereSi denotes the output value of the multilayer perceptron for each point cloud class and k represents the number of point cloud classes in the sample. This operation is equivalent to the softmax layer function and ⋯S is output as a vector form. Next, the cross-entropy calculation is carried out between the output and the label, which is defined as follows:(4)L=−1k∑i=1kyilnLSi,whereyi is the actual label of each point cloud class; the label of each point cloud class is multiplied by the natural logarithmic form output by the normalization layer, and finally, the mean loss of the point cloud class is calculated by means of the mean value as the loss function of the deep learning network.


## 4. Experiments

### 4.1. Data Sets

We conduct the experiments on two benchmark data sets. ModelNet10 contains 4,899 meshed CAD models from 10 categories. Each point cloud contains 10,000 coordinate points. Each point consists of three-dimensional position coordinate information (x, y, and z) and normal vector information (Nx, Ny, and Nz).Shapenetcore_partanno_segmentation_benchmark data set includes 16,846 point cloud models from 19 types. Each point cloud contains about 2,500 coordinate points. Each point consists of three-dimensional position coordinate information and part segmentation information, whose purpose is to compare the prediction results of a deep learning network with real value.Figure7 is the example of the point cloud model in this research. As can be seen from Figure 7, the point cloud model has a large amount of data, and features need to be refined; otherwise, the processing algorithm will be time-consuming. Point cloud data is measurable. It can directly obtain three-dimensional coordinates, distance, azimuth, and surface normal vector on the point cloud and can also calculate the surface area and volume of the target expressed by the point cloud. Due to the limited laser penetration, the point cloud obtained by LiDAR scanning basically reflects the surface condition of the target, and there is almost no internal information about the target.Figure 7
Examples of our point cloud model (top: shapenetcore_partanno_segmentation_benchmark and bottom: Modelnet10): (a) airplane, (b) bag, (c) chair, (d) bed, (e) dresser, and (f) table.
(a)(b)(c)(d)(e)(f)


### 4.2. Evaluation Metrics

We use shapenetcore_partanno_segmentation_benchmark data set to test the network performance, randomly select 10 point cloud classes from them, and carry out parts segmentation analysis. We use mean intersection over union (mIoU) to evaluate the effect of a deep learning network on parts segmentation of point clouds [20–22].(5)mIoU=1k+1∑i=0kpii∑j=0kpij+∑j=0kpji−pii,wherei represents the real value, j is the predicted value, pij is the probability that i is predicted to be j, and k is the number of categories in the sample. The larger the mIoU is, the more parts that prove that the predicted value coincides with the real value, the better the effect of network segmentation.In order to verify the classification effect of this algorithm, the mean class accuracy (m A P) is used to evaluate the overall performance of network classification:(6)mAP=1k∑i=1kAPi,wherek represents the number of point cloud classes and AP is the classification accuracy of each point cloud class.


### 4.3. Evaluation of Feature Point Extraction

The first two parts have already introduced the flow of the AOMC algorithm. Next, we use these methods to extract feature points from different types of point clouds. We use the Modelnet10 data set for analysis.As shown in Table1, the “elbow point method” is used to select the best clustering center number for 10 different types of the point cloud model in the data set.Table 1
Selection of cluster number of different point clouds based on “elbow point method.”
ClassBathtubBedChairDeskDresserMonitorNightstandSofaTableToiletNumber of cluster centers1713911121215111116Figure8 illustrates the point cloud feature sampling using the AOMC algorithm, compared with the random feature sampling method, and the AOMC point cloud sampling points are more evenly distributed and can better capture local feature information, which achieves the purpose of improving the accuracy of point cloud deep learning network.Figure 8
Comparison of point cloud feature sampling point between AOMC and random sampling. A total of 10m24 feature points are collected for each point cloud model; the left is random sampling; and the right is using AOMC to sample feature points. (a) Details of the wing are lost by random sampling. (b) and (c) Point cloud distribution of AOMC is more uniform than random sampling. (a) Airplane, (b) chair, and (c) car.
(a)(b)(c)


### 4.4. Overall Performance and Parameter Analysis of the Proposed Method

To better explain the beneﬁts of the proposed AOMC clustering method, we make a comprehensive analysis from run time (time complexity), mAP, and mIoU. We compare and analyze the AOMC algorithm and other cluster methods, including farthest selection [27], random selection [34], DBSCAN [42], k-means [3], and agglomerative clustering [43]. Table 2 shows the performance of the combination of time complexity. What’s more, Table 3 indicates the mIoU of each method on every point cloud model. Table 4 displays the comparison of mAP of various methods.Table 2
Comparison of run time on local feature point extraction.
Feature points number1,0241,5362,048Farthest selection1.51 s3.56 s5.83 sRandom selection7 × 10−4 s1.11 × 10−3 s15 × 10−3 sDBSCAN0.07 s0.08 s1.01 sk-means (k = 10)0.32 s0.36 s0.47 sAgglomerative clustering (n = 10)2.91 s2.96 s3.01 sOurs0.55 s0.58 s0.64 sTable 3
Comparison of mIoU on parts segmentation task. The best and the second-best methods are highlighted in red and green colors, respectively.
MethodMean intersection over union (mIoU)Avg (%)Airplane (%)Bag (%)Chair (%)Laptop (%)Knife (%)Mug (%)Rocket (%)Cap (%)Table (%)Earphone (%)Farthest selection81.6082.4081.1090.7090.6086.1095.1054.5089.908268.50Random selection78.8080.3080918983.1090.1051.4087.707362DBSCAN79.7079.20788990839556828065k-means (k = 10)80.7083.1074889184875790.108172Agglomerative clustering79.3081.4073838483.40915988.4080.4069.40Ours83847991.7089.4089.9094.3061838474Table 4
Comparison of the map on the classification task. The best and the second-best methods are highlighted in red and green colors, respectively.
MethodMean intersection over union (mIoU)Avg (%)Airplane (%)Bag (%)Chair (%)Laptop (%)Knife (%)Mug (%)Rocket (%)Cap (%)Table (%)Earphone (%)Farthest selection81.6082.4081.1090.7090.6086.1095.1054.5089.908268.50Random selection78.8080.3080918983.1090.1051.4087.707362DBSCAN79.7079.20788990839556828065k-means (k = 10)80.7083.1074889184875790.108172Agglomerative clustering79.3081.4073838483.40915988.4080.4069.40Ours83847991.7089.4089.9094.3061838474We evaluate the run-time performance of our method with a GTX 2080TI GPU, Core i9-9900K CPU, and 32 GB memory.


#### 4.4.1. Run-Time Comparison

Run time is an important measure of algorithm complexity. Here, we calculate the run time of different point cloud feature extraction algorithms. In the Modelnet10 data set, there are 4,899 point cloud models. Each cloud model consists of 10,000 points. We set different feature points to comprehensively analyze and compare the time complexity of different feature extraction algorithms.As can be seen from the data in Table2, compared with the farthest selection, the algorithm complexity of AOMC is relatively low. In the actual experiment, due to the uneven density and dense arrangement of point cloud samples, it is difficult to adjust the parameters of the DBSCAN (ON∗Eps, where Eps means the spending time finding each neighborhood point) algorithm, and the actual application effect is limited. The algorithm complexity of agglomerative clustering (ON3) is the highest among them. Random selection has the highest sampling speed (O1), but it has a large loss of local characteristics of the point cloud. In practice, the time complexity of AOMC is slightly longer than that of k-means (ON∗logN). The main reason is the determination of the number of cluster centers.


#### 4.4.2. mIoU Comparison

Next, we analyze the performance of the feature extraction algorithm in parts segmentation tasks by comparing the mIoU of different point cloud models.It can be seen from Table3 that AOMC, the method we proposed based on adaptive point cloud clustering feature extraction, is applied in the task of point cloud model parts segmentation. The mIoU of some point cloud models parts segmentation is improved.We can see that AOMC obtains an average of 1.4% improvement over the second-best method: farthest selection. Compared with the random selection sampling method, AOMC has the best relative performance, which is about 4.2% enhancement. Although agglomerative clustering has the highest time complexity, its performance of parts segmentation is not better.As shown in Figure9, it is the effect of point cloud parts segmentation. The interior of the point cloud model is divided into several parts. Random selection leads to a large number of point cloud classification errors, and it loses an array of model details. The engine of an airplane is almost confused with the wing. The parts of the guitar are not well differentiated.Figure 9
Point cloud parts segmentation example diagram. The point cloud model is divided according to the internal category (left: airplane, middle: lamp, and right: guitar). (a) random selection, (b) farthest selection, (c) DBSCAN, (d) k-means, (e) agglomerative clustering, and (f) ours.
(a)(b)(c)(d)(e)(f)The same problem exists in the DBSCAN sample method. In the airplane model, part of the fuselage point cloud is mistaken for the wing. And, of the lamp model, the base is confused with a lampshade. There are some classification errors on the guitar. In agglomerative clustering models, the lamp is only divided into two parts, and there are a few classification errors on the aircraft fuselage.Although k-means and farthest selection has better segmentation effect, there are still a few mistakes. Compared with the above method, our method performs well in these point cloud models. The base, middle part, and shade of the lamp are clearly divided into three parts, and there is no error on the fuselage of an airplane. We can find that the point cloud deep learning network enables to capture better semantic information by adaptive clustering with parts segmentation task. This strategy suppresses the noises of redundant local details and brings significant improvement to the edge performance.


#### 4.4.3. Accuracy Analysis

Feature extraction plays an important role in the optimization process of a deep learning network. Among them, it has a great influence on the accuracy of network classification. We calculate the classification accuracy of each point cloud model and then analyze the influence of feature extraction on network accuracy by average value.It can be seen from Table4 that the point cloud feature extraction method based on adaptive clustering has achieved good results in some point cloud models. The average mAP is 89.09%, which is the best performance among these feature extraction methods. Similar to the performance on parts segmentation, the AOMC clustering method has a 0.84% benefit over the second-best clustering algorithm. What’s more, DBSCAN still performs not well in classification; the proposed method has a 6.67% advantage over that. Because of the inaccurate extraction of detailed information, the random selection method cannot accomplish the tasks of a deep learning network well.Figure10 shows the visual comprehensive comparison of different cluster feature extraction methods. From the comparison results, it can be seen that our method has high real-time performance. In the task of point cloud segmentation, the performance of this algorithm is the best. However, in the classification task, the comprehensive performance of this algorithm is not good, and it only performs well in several point cloud models. The comprehensive performance of the AOMC algorithm is better than that of other models. We can choose different scale point cloud densities according to different task requirements, which makes the algorithm more flexible.Figure 10
Comprehensive comparison of our method with other cluster feature extraction methods.As can be seen from Figure11, the point cloud feature extraction method based on adaptive unsupervised learning makes the loss function optimization speed of the deep learning network faster and the loss value smaller. The main reason is that the adaptive clustering method can extract more detailed information, thus increasing the classification gap between hierarchical learning features of point cloud categories. At the same time, due to the high complexity of the farthest selection point sampling algorithm, the network convergence rate is slow. Because of the neglect of more detailed information in point cloud models, the random selection method has the lowest overall accuracy and the biggest loss value among all experimental methods.Figure 11
Training loss curve of the classified network.It can be seen from Figure12 that when the number of training times reaches a certain number, the accuracy of the deep learning network using the adaptive clustering method is higher than that of the other point cloud feature extraction methods. It is proved that the deep learning network using an adaptive clustering algorithm has a relatively high optimization speed. At the same time, the deep learning network used for feature extraction has higher accuracy. Compared with some point cloud feature extraction methods, the adaptive point cloud feature extraction method obtains more detailed targets, to improve the hierarchical feature learning effect.Figure 12
Training accuracy curve of classification network.The experiments provide strong evidence for the advantages of adaptive unsupervised clustering for point cloud feature extraction. Adaptive point cloud clustering feature extraction method obtains better performance in time complexity. The reason is that the algorithm we proposed avoids the overall traversal of the point cloud model and reduces the amount of calculation. In the point cloud deep learning task, the adaptive point cloud feature extraction method obtains higher accuracy of point cloud classification and parts segmentation. In the training process of the point cloud deep learning network, an adaptive feature extraction algorithm can improve the convergence rate of the network. Compared with the random selection method, the point cloud deep learning network achieves higher mean accuracy.


## 4.1. Data Sets

We conduct the experiments on two benchmark data sets. ModelNet10 contains 4,899 meshed CAD models from 10 categories. Each point cloud contains 10,000 coordinate points. Each point consists of three-dimensional position coordinate information (x, y, and z) and normal vector information (Nx, Ny, and Nz).Shapenetcore_partanno_segmentation_benchmark data set includes 16,846 point cloud models from 19 types. Each point cloud contains about 2,500 coordinate points. Each point consists of three-dimensional position coordinate information and part segmentation information, whose purpose is to compare the prediction results of a deep learning network with real value.Figure7 is the example of the point cloud model in this research. As can be seen from Figure 7, the point cloud model has a large amount of data, and features need to be refined; otherwise, the processing algorithm will be time-consuming. Point cloud data is measurable. It can directly obtain three-dimensional coordinates, distance, azimuth, and surface normal vector on the point cloud and can also calculate the surface area and volume of the target expressed by the point cloud. Due to the limited laser penetration, the point cloud obtained by LiDAR scanning basically reflects the surface condition of the target, and there is almost no internal information about the target.Figure 7
Examples of our point cloud model (top: shapenetcore_partanno_segmentation_benchmark and bottom: Modelnet10): (a) airplane, (b) bag, (c) chair, (d) bed, (e) dresser, and (f) table.
(a)(b)(c)(d)(e)(f)


## 4.2. Evaluation Metrics

We use shapenetcore_partanno_segmentation_benchmark data set to test the network performance, randomly select 10 point cloud classes from them, and carry out parts segmentation analysis. We use mean intersection over union (mIoU) to evaluate the effect of a deep learning network on parts segmentation of point clouds [20–22].(5)mIoU=1k+1∑i=0kpii∑j=0kpij+∑j=0kpji−pii,wherei represents the real value, j is the predicted value, pij is the probability that i is predicted to be j, and k is the number of categories in the sample. The larger the mIoU is, the more parts that prove that the predicted value coincides with the real value, the better the effect of network segmentation.In order to verify the classification effect of this algorithm, the mean class accuracy (m A P) is used to evaluate the overall performance of network classification:(6)mAP=1k∑i=1kAPi,wherek represents the number of point cloud classes and AP is the classification accuracy of each point cloud class.


## 4.3. Evaluation of Feature Point Extraction

The first two parts have already introduced the flow of the AOMC algorithm. Next, we use these methods to extract feature points from different types of point clouds. We use the Modelnet10 data set for analysis.As shown in Table1, the “elbow point method” is used to select the best clustering center number for 10 different types of the point cloud model in the data set.Table 1
Selection of cluster number of different point clouds based on “elbow point method.”
ClassBathtubBedChairDeskDresserMonitorNightstandSofaTableToiletNumber of cluster centers1713911121215111116Figure8 illustrates the point cloud feature sampling using the AOMC algorithm, compared with the random feature sampling method, and the AOMC point cloud sampling points are more evenly distributed and can better capture local feature information, which achieves the purpose of improving the accuracy of point cloud deep learning network.Figure 8
Comparison of point cloud feature sampling point between AOMC and random sampling. A total of 10m24 feature points are collected for each point cloud model; the left is random sampling; and the right is using AOMC to sample feature points. (a) Details of the wing are lost by random sampling. (b) and (c) Point cloud distribution of AOMC is more uniform than random sampling. (a) Airplane, (b) chair, and (c) car.
(a)(b)(c)


## 4.4. Overall Performance and Parameter Analysis of the Proposed Method

To better explain the beneﬁts of the proposed AOMC clustering method, we make a comprehensive analysis from run time (time complexity), mAP, and mIoU. We compare and analyze the AOMC algorithm and other cluster methods, including farthest selection [27], random selection [34], DBSCAN [42], k-means [3], and agglomerative clustering [43]. Table 2 shows the performance of the combination of time complexity. What’s more, Table 3 indicates the mIoU of each method on every point cloud model. Table 4 displays the comparison of mAP of various methods.Table 2
Comparison of run time on local feature point extraction.
Feature points number1,0241,5362,048Farthest selection1.51 s3.56 s5.83 sRandom selection7 × 10−4 s1.11 × 10−3 s15 × 10−3 sDBSCAN0.07 s0.08 s1.01 sk-means (k = 10)0.32 s0.36 s0.47 sAgglomerative clustering (n = 10)2.91 s2.96 s3.01 sOurs0.55 s0.58 s0.64 sTable 3
Comparison of mIoU on parts segmentation task. The best and the second-best methods are highlighted in red and green colors, respectively.
MethodMean intersection over union (mIoU)Avg (%)Airplane (%)Bag (%)Chair (%)Laptop (%)Knife (%)Mug (%)Rocket (%)Cap (%)Table (%)Earphone (%)Farthest selection81.6082.4081.1090.7090.6086.1095.1054.5089.908268.50Random selection78.8080.3080918983.1090.1051.4087.707362DBSCAN79.7079.20788990839556828065k-means (k = 10)80.7083.1074889184875790.108172Agglomerative clustering79.3081.4073838483.40915988.4080.4069.40Ours83847991.7089.4089.9094.3061838474Table 4
Comparison of the map on the classification task. The best and the second-best methods are highlighted in red and green colors, respectively.
MethodMean intersection over union (mIoU)Avg (%)Airplane (%)Bag (%)Chair (%)Laptop (%)Knife (%)Mug (%)Rocket (%)Cap (%)Table (%)Earphone (%)Farthest selection81.6082.4081.1090.7090.6086.1095.1054.5089.908268.50Random selection78.8080.3080918983.1090.1051.4087.707362DBSCAN79.7079.20788990839556828065k-means (k = 10)80.7083.1074889184875790.108172Agglomerative clustering79.3081.4073838483.40915988.4080.4069.40Ours83847991.7089.4089.9094.3061838474We evaluate the run-time performance of our method with a GTX 2080TI GPU, Core i9-9900K CPU, and 32 GB memory.


### 4.4.1. Run-Time Comparison

Run time is an important measure of algorithm complexity. Here, we calculate the run time of different point cloud feature extraction algorithms. In the Modelnet10 data set, there are 4,899 point cloud models. Each cloud model consists of 10,000 points. We set different feature points to comprehensively analyze and compare the time complexity of different feature extraction algorithms.As can be seen from the data in Table2, compared with the farthest selection, the algorithm complexity of AOMC is relatively low. In the actual experiment, due to the uneven density and dense arrangement of point cloud samples, it is difficult to adjust the parameters of the DBSCAN (ON∗Eps, where Eps means the spending time finding each neighborhood point) algorithm, and the actual application effect is limited. The algorithm complexity of agglomerative clustering (ON3) is the highest among them. Random selection has the highest sampling speed (O1), but it has a large loss of local characteristics of the point cloud. In practice, the time complexity of AOMC is slightly longer than that of k-means (ON∗logN). The main reason is the determination of the number of cluster centers.


### 4.4.2. mIoU Comparison

Next, we analyze the performance of the feature extraction algorithm in parts segmentation tasks by comparing the mIoU of different point cloud models.It can be seen from Table3 that AOMC, the method we proposed based on adaptive point cloud clustering feature extraction, is applied in the task of point cloud model parts segmentation. The mIoU of some point cloud models parts segmentation is improved.We can see that AOMC obtains an average of 1.4% improvement over the second-best method: farthest selection. Compared with the random selection sampling method, AOMC has the best relative performance, which is about 4.2% enhancement. Although agglomerative clustering has the highest time complexity, its performance of parts segmentation is not better.As shown in Figure9, it is the effect of point cloud parts segmentation. The interior of the point cloud model is divided into several parts. Random selection leads to a large number of point cloud classification errors, and it loses an array of model details. The engine of an airplane is almost confused with the wing. The parts of the guitar are not well differentiated.Figure 9
Point cloud parts segmentation example diagram. The point cloud model is divided according to the internal category (left: airplane, middle: lamp, and right: guitar). (a) random selection, (b) farthest selection, (c) DBSCAN, (d) k-means, (e) agglomerative clustering, and (f) ours.
(a)(b)(c)(d)(e)(f)The same problem exists in the DBSCAN sample method. In the airplane model, part of the fuselage point cloud is mistaken for the wing. And, of the lamp model, the base is confused with a lampshade. There are some classification errors on the guitar. In agglomerative clustering models, the lamp is only divided into two parts, and there are a few classification errors on the aircraft fuselage.Although k-means and farthest selection has better segmentation effect, there are still a few mistakes. Compared with the above method, our method performs well in these point cloud models. The base, middle part, and shade of the lamp are clearly divided into three parts, and there is no error on the fuselage of an airplane. We can find that the point cloud deep learning network enables to capture better semantic information by adaptive clustering with parts segmentation task. This strategy suppresses the noises of redundant local details and brings significant improvement to the edge performance.


### 4.4.3. Accuracy Analysis

Feature extraction plays an important role in the optimization process of a deep learning network. Among them, it has a great influence on the accuracy of network classification. We calculate the classification accuracy of each point cloud model and then analyze the influence of feature extraction on network accuracy by average value.It can be seen from Table4 that the point cloud feature extraction method based on adaptive clustering has achieved good results in some point cloud models. The average mAP is 89.09%, which is the best performance among these feature extraction methods. Similar to the performance on parts segmentation, the AOMC clustering method has a 0.84% benefit over the second-best clustering algorithm. What’s more, DBSCAN still performs not well in classification; the proposed method has a 6.67% advantage over that. Because of the inaccurate extraction of detailed information, the random selection method cannot accomplish the tasks of a deep learning network well.Figure10 shows the visual comprehensive comparison of different cluster feature extraction methods. From the comparison results, it can be seen that our method has high real-time performance. In the task of point cloud segmentation, the performance of this algorithm is the best. However, in the classification task, the comprehensive performance of this algorithm is not good, and it only performs well in several point cloud models. The comprehensive performance of the AOMC algorithm is better than that of other models. We can choose different scale point cloud densities according to different task requirements, which makes the algorithm more flexible.Figure 10
Comprehensive comparison of our method with other cluster feature extraction methods.As can be seen from Figure11, the point cloud feature extraction method based on adaptive unsupervised learning makes the loss function optimization speed of the deep learning network faster and the loss value smaller. The main reason is that the adaptive clustering method can extract more detailed information, thus increasing the classification gap between hierarchical learning features of point cloud categories. At the same time, due to the high complexity of the farthest selection point sampling algorithm, the network convergence rate is slow. Because of the neglect of more detailed information in point cloud models, the random selection method has the lowest overall accuracy and the biggest loss value among all experimental methods.Figure 11
Training loss curve of the classified network.It can be seen from Figure12 that when the number of training times reaches a certain number, the accuracy of the deep learning network using the adaptive clustering method is higher than that of the other point cloud feature extraction methods. It is proved that the deep learning network using an adaptive clustering algorithm has a relatively high optimization speed. At the same time, the deep learning network used for feature extraction has higher accuracy. Compared with some point cloud feature extraction methods, the adaptive point cloud feature extraction method obtains more detailed targets, to improve the hierarchical feature learning effect.Figure 12
Training accuracy curve of classification network.The experiments provide strong evidence for the advantages of adaptive unsupervised clustering for point cloud feature extraction. Adaptive point cloud clustering feature extraction method obtains better performance in time complexity. The reason is that the algorithm we proposed avoids the overall traversal of the point cloud model and reduces the amount of calculation. In the point cloud deep learning task, the adaptive point cloud feature extraction method obtains higher accuracy of point cloud classification and parts segmentation. In the training process of the point cloud deep learning network, an adaptive feature extraction algorithm can improve the convergence rate of the network. Compared with the random selection method, the point cloud deep learning network achieves higher mean accuracy.


## 4.4.1. Run-Time Comparison

Run time is an important measure of algorithm complexity. Here, we calculate the run time of different point cloud feature extraction algorithms. In the Modelnet10 data set, there are 4,899 point cloud models. Each cloud model consists of 10,000 points. We set different feature points to comprehensively analyze and compare the time complexity of different feature extraction algorithms.As can be seen from the data in Table2, compared with the farthest selection, the algorithm complexity of AOMC is relatively low. In the actual experiment, due to the uneven density and dense arrangement of point cloud samples, it is difficult to adjust the parameters of the DBSCAN (ON∗Eps, where Eps means the spending time finding each neighborhood point) algorithm, and the actual application effect is limited. The algorithm complexity of agglomerative clustering (ON3) is the highest among them. Random selection has the highest sampling speed (O1), but it has a large loss of local characteristics of the point cloud. In practice, the time complexity of AOMC is slightly longer than that of k-means (ON∗logN). The main reason is the determination of the number of cluster centers.


## 4.4.2. mIoU Comparison

Next, we analyze the performance of the feature extraction algorithm in parts segmentation tasks by comparing the mIoU of different point cloud models.It can be seen from Table3 that AOMC, the method we proposed based on adaptive point cloud clustering feature extraction, is applied in the task of point cloud model parts segmentation. The mIoU of some point cloud models parts segmentation is improved.We can see that AOMC obtains an average of 1.4% improvement over the second-best method: farthest selection. Compared with the random selection sampling method, AOMC has the best relative performance, which is about 4.2% enhancement. Although agglomerative clustering has the highest time complexity, its performance of parts segmentation is not better.As shown in Figure9, it is the effect of point cloud parts segmentation. The interior of the point cloud model is divided into several parts. Random selection leads to a large number of point cloud classification errors, and it loses an array of model details. The engine of an airplane is almost confused with the wing. The parts of the guitar are not well differentiated.Figure 9
Point cloud parts segmentation example diagram. The point cloud model is divided according to the internal category (left: airplane, middle: lamp, and right: guitar). (a) random selection, (b) farthest selection, (c) DBSCAN, (d) k-means, (e) agglomerative clustering, and (f) ours.
(a)(b)(c)(d)(e)(f)The same problem exists in the DBSCAN sample method. In the airplane model, part of the fuselage point cloud is mistaken for the wing. And, of the lamp model, the base is confused with a lampshade. There are some classification errors on the guitar. In agglomerative clustering models, the lamp is only divided into two parts, and there are a few classification errors on the aircraft fuselage.Although k-means and farthest selection has better segmentation effect, there are still a few mistakes. Compared with the above method, our method performs well in these point cloud models. The base, middle part, and shade of the lamp are clearly divided into three parts, and there is no error on the fuselage of an airplane. We can find that the point cloud deep learning network enables to capture better semantic information by adaptive clustering with parts segmentation task. This strategy suppresses the noises of redundant local details and brings significant improvement to the edge performance.


## 4.4.3. Accuracy Analysis

Feature extraction plays an important role in the optimization process of a deep learning network. Among them, it has a great influence on the accuracy of network classification. We calculate the classification accuracy of each point cloud model and then analyze the influence of feature extraction on network accuracy by average value.It can be seen from Table4 that the point cloud feature extraction method based on adaptive clustering has achieved good results in some point cloud models. The average mAP is 89.09%, which is the best performance among these feature extraction methods. Similar to the performance on parts segmentation, the AOMC clustering method has a 0.84% benefit over the second-best clustering algorithm. What’s more, DBSCAN still performs not well in classification; the proposed method has a 6.67% advantage over that. Because of the inaccurate extraction of detailed information, the random selection method cannot accomplish the tasks of a deep learning network well.Figure10 shows the visual comprehensive comparison of different cluster feature extraction methods. From the comparison results, it can be seen that our method has high real-time performance. In the task of point cloud segmentation, the performance of this algorithm is the best. However, in the classification task, the comprehensive performance of this algorithm is not good, and it only performs well in several point cloud models. The comprehensive performance of the AOMC algorithm is better than that of other models. We can choose different scale point cloud densities according to different task requirements, which makes the algorithm more flexible.Figure 10
Comprehensive comparison of our method with other cluster feature extraction methods.As can be seen from Figure11, the point cloud feature extraction method based on adaptive unsupervised learning makes the loss function optimization speed of the deep learning network faster and the loss value smaller. The main reason is that the adaptive clustering method can extract more detailed information, thus increasing the classification gap between hierarchical learning features of point cloud categories. At the same time, due to the high complexity of the farthest selection point sampling algorithm, the network convergence rate is slow. Because of the neglect of more detailed information in point cloud models, the random selection method has the lowest overall accuracy and the biggest loss value among all experimental methods.Figure 11
Training loss curve of the classified network.It can be seen from Figure12 that when the number of training times reaches a certain number, the accuracy of the deep learning network using the adaptive clustering method is higher than that of the other point cloud feature extraction methods. It is proved that the deep learning network using an adaptive clustering algorithm has a relatively high optimization speed. At the same time, the deep learning network used for feature extraction has higher accuracy. Compared with some point cloud feature extraction methods, the adaptive point cloud feature extraction method obtains more detailed targets, to improve the hierarchical feature learning effect.Figure 12
Training accuracy curve of classification network.The experiments provide strong evidence for the advantages of adaptive unsupervised clustering for point cloud feature extraction. Adaptive point cloud clustering feature extraction method obtains better performance in time complexity. The reason is that the algorithm we proposed avoids the overall traversal of the point cloud model and reduces the amount of calculation. In the point cloud deep learning task, the adaptive point cloud feature extraction method obtains higher accuracy of point cloud classification and parts segmentation. In the training process of the point cloud deep learning network, an adaptive feature extraction algorithm can improve the convergence rate of the network. Compared with the random selection method, the point cloud deep learning network achieves higher mean accuracy.


## 5. Conclusion

In this paper, we propose a novel point cloud feature extraction method based on unsupervised learning and adaptive optimization. AOMC point cloud feature extraction method consists of the cluster centers’ number generation, adaptive clustering, and the applying tasks of the deep learning network. The accuracy and speed of the deep learning network are improved effectively. The performance of classification and parts segmentation is better.Comparison results demonstrate the efﬁcacy of the proposed methods. As can be seen from the experimental results, the method we proposed improves the effect of point cloud feature extraction and achieves the purpose of point cloud hierarchical feature learning. The accuracy of the point cloud deep learning network is improved. AOMC clustering algorithm improves the accuracy of the initial point of the clustering center, so as to improve the convergence rate and accuracy of the clustering processing. In the meantime, the method of selecting the best clustering center number by quantization SSE is put forward so that the point cloud clustering number and the point cloud category can be adapted to each other, and the fixed value method is no longer used to determine the amount of clustering center. As a result, it improves the rationality and accuracy of the point cloud deep learning. What is also worth noticing is that our clustering method realizes the purpose of improving the classification accuracy, parts segmentation accuracy, and convergence rate of the deep learning network.The proposed method still has some drawbacks. It does not achieve the best performance in all point cloud models. And the steps of the algorithm are complicated. In the future, we plan to simplify the algorithm steps of AOMC. And improve accuracy for all models.



---

*Source: 3744086-2022-08-08.xml*