Classification method for imbalanced LiDAR point cloud based on stack autoencoder

1.   Introduction

LiDAR ^[1] can obtain the geometric coordinates of the spatial points and the intensity information of the laser echo signal. It has the advantages of high spatial resolution, accurate spatial positioning, and objective reality ^[2], and is widely used in forest ecosystem ^[3], atmospheric remote sensing ^[4], autonomous driving technology ^[5], and 3D city models ^[6], etc. The necessary guarantee for the realization of these applications is the construction of classification algorithms for LiDAR point clouds with high precision and real-time performance.

Point cloud classification is to divide the point clouds into various object instances, such as buildings, ground and vegetation. The classification methods of LiDAR point clouds mainly fall into two categories: machine learning-based method and deep learning-based method. In the former method, feature vectors are extracted, constructed or fusioned, and then machine classification algorithm is used to classify point clouds. Song et al. ^[7] extracted geometrical features including volume, density, and eigenvalues in the three principal directions as a basis for classification to classify objects into five types by back-prop agation neural network(ANN) model. Li et al. ^[8] proposed a point cloud classification algorithm: multilevel features of a single point are constructed by multi-resolution of the point cloud and multi-neighborhood spaces, and then the points are classified by the support vector machine(SVM) based on a Gaussian kernel function. Sun et al. ^[9] selected 20 statistical features and used the optimized random forest(RF) algorithm to classify the vegetation point cloud. According to the processing mode of point cloud data, classification methods based on deep learning mainly include projection-based method ^[10], point-based method ^[11] and graph-based method ^[12].

These methods are almost based on the assumption that each class is balanced, without considering the imbalanced class problem. Imbalanced data refers to the data with a very small proportion of one or more classes in the original samples ^[13]. Usually, the class with fewest samples is called the positive class, and the class with a relatively large number of samples is called the negative class. If the data set is imbalanced, the classification algorithm cannot correctly learn the feature of positive sample, and tends to the negative class, which may lead to the bias of classification results and decision errors.

The classification effect of imbalanced data is mainly improved by optimizing the sampling algorithm ^[14], which is an improvement at the data level. Because the sampling algorithm can effectively solve the problem of imbalanced distribution of positive and negative samples, and the optimization design of the sampling algorithm is relatively easy, the performance of positive sample classification accuracy can be significantly improved. According to the different ways of adjusting data, the traditional sampling algorithms can be divided into three categories: undersampling, oversampling, and hybrid sampling ^[15]. Undersampling algorithms ^[16] remove data from the negative class until both contain an equal number of samples, which may suffer from feature loss due to data deletion. Oversampling algorithms ^[17] generate data in positive class until both contain an equal number of samples, which may have the problem of overfitting the training data, such as synthetic minority oversampling technique(SMOTE) ^[18] and adaptive semi-unsupervised weighted oversampling (ASUWO) ^[19]. Hybrid sampling algorithms ^[13] balance the datasets by combining undersampling and oversampling algorithm, thus having the advantages and disadvantages of these two algorithms.

In addition, there are many improved methods of classifier for processing imbalanced data, which is an improvement at the algorithm level. They can also be divided into three categories ^[20]: ensemble based on Bagging, Boosting, and Hybrid, it depends on the ensemble learning algorithm they are based on.

At present, there are few researches on imbalanced point cloud classification. Table 1 compares the methods of several research papers in the last three years. From Table 1, we can find some shortcomings of the existing research: 1) The amount of point cloud data is relatively large, but the current data processing methods are all using the traditional imbalanced data sampling method. 2) Excessive selection of classification features increases the complexity and difficulty of calculation. 3) The classifiers are not been improved or optimized to be more suitable for the classification of imbalanced data.

Therefore, our research motivation is to find a suitable classification method for imbalanced point cloud. The research contributions include:

1) Propose an oversampling algorithm suitable for big data by using deep network. Stack autoencoder(SAE) ^[24] is an unsupervised deep neural network with excellent properties of learning data rules. It is often used in dimensionality reduction ^[25,26], denoising ^[27,28], feature extraction ^[29,30], outlier detection ^[31,32], and so on. In this study, SAE is used for oversampling the class with least samples ^[33]. The SAE realizes automatic generation of synthetic samples by learning the distribution characteristics of the class with least samples, which improves the balance of training data. Compared to SMOTE and ASUWO, it is not affected by negative class and is better suited to imbalanced multi-class problems.

2) Minimize the dimension of feature vectors used for point cloud classification. As the input layer of the SAE, geometric coordinates and intensity information of the point clouds do not need feature construction or fusion. All kinds of point clouds, such as ground, vegetation, vehicles, and buildings in urban scenes, can be well identified by using only geometric coordinates and intensity information.

3) Select a classification method suitable for imbalanced point cloud by comparing eight classifiers. Kaur et al. ^[17] pointed out that the optimization of classifier can also improve the classification performance of imbalanced data to a certain extent. The experimental study in this paper also verified this point. The improvement and optimization of classifier had a significant effect on the increase of ACC value. If the oversampling algorithm is combined with classifier optimization, the classification performance of imbalanced point cloud is greatly improved.

The rest of this paper is organized as follows. Section 2 reviews two oversampling algorithms(SMOTE and ASUWO) for imbalanced data and expounds the oversampling method based on SAE for imbalanced LiDAR point cloud. Section 3 introduces the source of experimental data and the evaluation index of classification performance. Section 4 analyzes the influence of classifiers, sampling number and oversampling algorithms on classification results. In Section 5, the thesis is summarized and the future research direction is pointed out.

2.   Oversampling method

After reviewing the sampling principle of the two algorithms and the network structure of SAE, the idea and step of oversampling method based on SAE for imbalanced LiDAR point cloud are described.

2.1.   SMOTE

SMOTE is the most representative oversampling method, the basic idea of which is to randomly generate a new sample between each positive sample and its $k$ nearest neighbors. Since the generated samples are random values between two samples, SMOTE solves the problem of sample diversity. The main process of SMOTE algorithm is shown as follows.

In order to improve the quality of synthetic samples, researchers proposed a series of improved algorithms based on smote. Han et al. ^[34] put forward the Borderline SMOTE to solve the problem that samples in the boundary area are easy to be misclassified by the classifier. Bunkhumpornpat et al. ^[35] came up with Safe-level SMOTE to generate positive samples by calculating the weight of $k$ nearest neighbors, which avoided the problem of synthetic data crossing the boundary of positive samples. Douzas et al. ^[36] presented an oversampling method based on k-means clustering and SMOTE, which avoids the generation of noise and effectively overcomes imbalances between and within classes.

2.2.   ASUWO

ASUWO clusters the positive samples using a semi-unsupervised hierarchical clustering approach and adaptively determines the size to oversample each subcluster using its classification complexity and cross validation. Then, the positive samples are oversampled depending on their Euclidean distance to the negative class. ASUWO address the problem of over-generalization by identifying positive boundary samples and assigning them different weights, which also mitigate the between-class imbalances and within-class imbalances by combining with clustering algorithms ^[15]. The main process of ASUWO algorithm is shown as follows.

2.3.   SAE-based oversampling method

The above-mentioned oversampling methods are almost based on the imbalanced two-classification problem, and the generation of synthetic samples is greatly affected by the neighborhood and boundary problems.

An autoencoder(AE) ^[37] is a self-supervised network whose output is equal to its input under ideal conditions. By establishing a reasonable loss term, the hidden layer features can be extracted under unsupervised learning. Especially when the input features are correlated with each other, the autocoding learning algorithm can extract the correlation in the input data. Furthermore, the extracted features are taken as the new input, and the corresponding encoding features can be obtained through parameter learning. The AE structure is shown in Figure 1(a).

The AE consists of the input layer, the encoding layer, and the decoding layer. Suppose $X = \{X(1), \cdots, X(m)\}$ is the input data and $f(x) = 1/(1+e^{-x})$ represents the activation function, the encoding layer is defined as:

where $Z^{(2)}$, $W^{(1)}$, $b^{(1)}$ and $a^{(2)}$ denote the input data, the weight matrix, the bias vector, and the output data of encoding layer, respectively.

In a similar way, the decoding layer is defined as:

where $Z^{(3)}$, $W^{(2)}$, $b^{(2)}$ and $a^{(3)}$ denote the input data, the weight matrix, the bias vector, and the output data of decoding layer, respectively.

The multiple AEs are connected in succession to obtain a stacked autoencoder(SAE) model ^[24]. The network structure of the SAE with three hidden layers is shown in Figure 1(b).

SAE is typically trained using a layer-by-layer greedy approach. The outputs of encoding layer of an AE are fed to the next AE as their inputs. Each AE learns in the same way as a single AE and the first AE uses the original input from the data as inputs. The network calculation formula of SAE is as follows:

The training process of SAE is to find a set of parameters($W^{(k)}, b^{(k)}, k = 1, \cdots, K$) to solve the following optimization problems ^[37]:

The first term is the reconstruction error between the input $X$ and output $a^{(K)}$. The second term aims to reduce the magnitude of weight and prevent overfitting. $\lambda$ is the regularization parameter, $W$ is a matrix consisting of the weight matrices ($W^{(k)}, k = 1, \cdots, K$). Usually, the parameters of SAE are optimized using the back-propagation method.

In order to overcome the influence of negative samples and mine the depth features of positive samples in big data, to generate better synthetic samples for solving unbalanced multi-classification problems, we propose a SAE-based oversampling method, the main steps of which are as follows: 1) Construct the network structure of SAE; 2) Take the samples with least samples as the input data of the input layer; 3) Extract features in the hidden layer; 4) Generate synthetic samples in the output layer. The main process of SAE-based oversampling is shown Algorithm 3.

The process of proposed method for classification of imbalanced LiDAR point cloud is as follows:

Step 1. Preprocess the point cloud data, and extract the geometric coordinates and intensity information $(x, y, z, i)$ of each point. The training set and the testing set are randomly generated in a certain ratio, such as 3:1.

Step 2. Oversample the class with least samples in the training set using the proposed method. Network structure of SAE includes: $1$ input layer, $K$ hidden layers, $1$ output layer. Both the input layer and the output layer have 4 neurons corresponding to four features $(x, y, z, i)$. The neurons of each hidden layer are respectively: $s_1, s_2, \cdots, s_K$. $s_1, s_2, \cdots, s_K$ and $K$ need to be obtained through experimental debugging.

Step 3. Train the relative balanced samples after oversampling with the classifier to get the classification model.

Step 4. Obtain the classification results of the test samples using the model.

The operation process of this method is shown in Figure 2.

3.   Experimental study

In order to test the effectiveness and excellence of the proposed method, we perform classification for point clouds in Pandaset-LidarData dataset, and compare the performance of three oversampling methods, eight classifiers and their combinations.

3.1.   Data source

PandaSet contains 2560 frame preprocessed organized point clouds of various urban scenes captured using the Pandar64 sensor. Each point cloud contains 13 classes of semantic segmentation labels. Several frame point clouds are randomly selected for this research. Figure 3 shows the first frame point cloud.

The initial 13 classes include unlabelled, vegetation, ground, road, road markings, sidewalk, car, truck, other vehicle, pedestrian, road barriers, signs, buildings. Because some classes have fewer points, the 13 classes are adjusted to 5 classes: ground, vegetation, vehicle, building, and other. Ground, road and sidewalk all fall into the class "ground". Car, truck and other vehicle are all included in the class "vehicle". Unlabelled, road markings, pedestrian, road barriers and signs are classified into the class "other". Figure 4 shows the scatter diagram of the first frame point cloud after class adjustment. Table 2 shows the distribution of each class in some frames.

It can be clearly seen from Table 2 that the classification of each frame is an imbalanced problem. Such as the first frame, the ground class is far lower than other classes and the difference is up to 20 times, which means "ground" is the positive class. We should generate a fair amount of "ground" data to balance the training set, then build a classification model to get the results on test set.

3.2.   Evaluation indicator

In order to better quantitatively analyze the results, we introduce the confusion matrix ^[38] and several evaluation indicators including true positive rate(TPR), positive predictive value(PPV), and accuracy(ACC). The confusion matrix is shown in Figure 5. The calculation formulas are as follows:

where TP is to predict the original positive class as the positive class, FN is to predict the original positive class as the negative class, FP is to predict the original negative class as the positive class, TN is to predict the original negative class as the negative class. Higher values of ACC, TPR and PPV indicate better classification effect.

4.   Results and analysis

All algorithmic programs covered in this work were implemented using Matlab R2022a. Furthermore, Cross-validation was used for classification. The number of folds in the cross-validation technique was five. After debugging, parameters set for each algorithm in this section are as follows: $K = 50$ in both SMOTE and ASUWO algorithms. There are $3$ hidden layers, and the number of neurons is respectively $15$, $5$, $15$ in SAE algorithm. $T = 1000$.

4.1.   Influence of Sampling number

SAE-based oversampling method can fully excavate the features of positive samples and randomly generate synthetic data. To verify the effectiveness of SAE-based Oversampling method and discuss the relationship between number of synthetic samples and classification results, the first frame was chosen as the experimental object.

$75\%$ of the $82,423$ points, namely, $61,818$ are randomly selected as the training set and the rest as test set. The training set contains points for each class: 1225, 7195, 11,551, 16,512 and 25,335. We took 1225 ground points as the basis to generate 1, 2, up to 20 times of ground data, conducted separately classification training using RUS-ODT, and got results on the test set. As the number of samples gets larger, the value of ACC is stable around 0.978 without big fluctuation, and the values of TPR and PPV of each class have different changes. Figure 6 presents the variation charts of TPR and PPV with respect to number of synthetic samples, where the abscissa represents a multiple of 1225.

It is easy to see from Figure 6 that: 1) Buildings and vehicles may have obvious classification characteristics, so the values of TPR and PPV are relatively high. Ground and vegetation, especially ground and dwarf vegetation, are not easy to distinguish, so both TPR and PPV values are low. Therefore, other features can be introduced to better realize the classification of ground and vegetation.

2) As the value of abscissa increases, that is, the number of synthetic samples enlarges, TPR and PPV of the ground class show an obvious increase, while indicators of other classes do not change significantly. This indicates that the oversampling method based on SAE can significantly improve the classification effect of the positive class without affecting the other classes. Therefore, in the follow-up discussion, we only focused on ACC and indicators of positive class.

3) When the multiple approaches 6, 13 and 20, the number of ground points is similar to the vegetation points, buildings and vehicles, respectively. But there is little difference between TPR and PPV. Therefore, which class is taken as the negative class in the oversampling has little influence on the classification effect. Therefore, the proposed method is not affected by negative class, so it can be applied to both imbalanced two-classification and multi-classification problems.

4) When the multiple is equal to 1, the indicators of ground class are greatly improved, and those of other classes reach the maximum. In order to reduce the amount of computation, we can generate twice as much data as the positive class for oversampling.

5) When the sampling multiple is greater than or equal to 5, TPR and PPV of vegetation class become the smallest, which means that the classification effect of vegetation class is the worst. This may be because the number of ground class exceeds that of vegetation, so vegetation class becomes the minimum class.

4.2.   Comparison for classifiers

In order to select a classifier suitable for imbalanced LiDAR point cloud, we discussed the influence of SAE-based oversampling algorithm on different classifiers, and carried out the following experiments. 1) Taking the vegetation class as the negative class, the proposed method was used to generate the same amount of ground data to obtain the training set. 2) Experimental data was trained with different classifiers to establish the classification model. 3) The models are applied to the test set, and the classification results are obtained.

With the help of Matlab(2022a) Classification Learner App, eight classifiers were selected for comparison, including ANN, SVM, decision tree(DT), RUS-Boost ^[39], multilayer perception artificial neural network (MPL-ANN) ^[40], fine Gaussian support vector machine(FG-SVM) ^[41], Optimal randomized classification trees(OR-CT) ^[42] and optimizable RUS-Boosted decision tree ensemble(RUS-ODT) ^[43]. The first four are traditional classifiers, and the last four are improvements of the first four using Bayesian optimizer. Table 3 shows the parameter settings of four optimized classifiers, which are obtained through experimental debugging. Table 4 lists the classification indexes of eight classifiers on the test set.

As can be seen from Table 4, 1) SAE-based oversampling method can improve the performance of each classifier, because all the indexes of sampling are higher than those of Unsampled.

2) Compared with the improvement of sampling method, the optimization of classifier has more obvious effect on the increase of ACC value. Therefore, for imbalanced classification problems, the optimization of classifier and the improvement of sampling method can be combined to obtain better classification results.

3) The training time of each classifier in the unsampled state and the oversampling state does not increase or decrease significantly, so there is no need to worry about the problem of sampling affecting the training time.

4) RUS-ODT is the classifier with highest index value, while OR-CT is the one with relatively high index value and less time consuming. In imbalanced point cloud classification, RUS-ODT can be selected if accuracy is pursued, and OR-CT can be selected if efficiency is pursued.

4.3.   Comparison for oversampling methods

To compare the performance of three oversampling methods, we first randomly selected several frames for research, and then carried out experiments on 7 UCI datasets. The smallest class is regarded as the positive class, which is oversampled by the three methods respectively, and then the classification result of the test set is obtained by RUS-ODT. Tables 5 and 6 show the classification results with different oversampling methods of point cloud and UCI data sets respectively. Figure 7 shows the scatter diagram of the positive class of the first frame point cloud before and after oversampling.

The following points can be seen from Table 5: 1) The proposed method can solve the imbalanced point cloud classification problem well.

2) Three oversampling methods have improved the values of TPR and PPV, which shows that oversampling is useful to improve the classification effect of positive class. SAE has the most significant improvement effect, as it obtained higher TPR and PPV values than the other two methods.

3) Three methods have little effect on ACC value. Because ACC has become less important in imbalanced classification. If the positive samples are less than $1.0\%$, the accuracy can still reach $99\%$ even if all positive samples are divided into negative class, but such classification has no practical significance.

4) Both SMOTE and ASUWO need negative class as references to generate samples of positive class, but SAE does not. So the synthetic samples of SAE are generated only by the features of positive class, and will not be affected by negative class samples.

In Table 6, positive classes of each data set are listed, while other classes are taken as negative classes. Therefore, the classification of each data set is an imbalanced binary classification problem. As can be seen from Table 6, the proposed method is also effective on other imbalanced data sets and can obtain better ACC values than the other two methods. So he proposed method performs better than the other two methods for both imbalanced multiclassification (Table 5) and binary classification problems (Table 6).

5.   Conclusions

Through the research on classification of LiDAR point cloud in urban scenes, we find that the phenomenon of imbalanced class is quite common. However, existing classification methods are almost based on the assumption that each class is balanced, and rarely directly use the geometric coordinates and intensity information of point clouds as classification features. In order to make up for the lack of existing research, we propose an oversampling method based on SAE for imbalanced point cloud classification. Only 4 features (three-dimensional coordinates and intensity information) are selected to participate in the classification, which ensures the accuracy of classification and reduces the complexity of calculation. And combined with the optimization of classifier, the classification performance of imbalanced point cloud is improved.

Our research also has some shortcomings. 1) It focuses on the improvement effect of positive class, and the improvement of ACC value is not significant enough. 2) The proposed method is an improvement of machine learning-based method for point cloud classification, but does not involve the optimization of deep learning-based method. That is also the direction of our further research in the future.

Conflict of interest

The authors declare there is no conflicts of interest.