Real-time 3D object proposal generation and classification under limited processing resources

Point cloud segmentation is used to infer objects of interest (OOIs) from a point cloud and is based on the assumption that 3D objects are sufficiently separated and there are no relevant intersections between adjacent objects. There are usually two main procedures involved: ground removal, and the clustering of the remaining set of points. Himmelsbach et al. [15] represented the terrain with a circle of infinite radius, centered around the robot itself, and split this circle into a number of circular sectors with fixed interval angles; Then the ground is searched by extracting horizontal lines at a low altitude, from the point sets of every segment. The remaining non-ground points are mapped into a 2D occupancy grid image, and clustering is done efficiently by finding connected components of occupied grid cells. Moosmann et al. [16] constructed an undirected graph in which every point is treated as a node. The normal of the local surface is estimated for every node against its neighbouring points, and the similar local surfaces, which either form local convexities or are approximately vertical normal vectors, are merged together to grow the ground plane or obstacle area.

Douillard et al. [17] formulated the ground surface detection as non-ground outlier rejection and proposed a Gaussian Process Incremental Sample Consensus, based on the variance of the height of an outlier from the mean of a Gaussian distribution, to propagate the ground surface labels in an iterative manner to eventually include all ground points, while the remaining non-ground points are subsequently segmented into different clusters. Point segmentation approaches, after the removal of all ground points, often bring about issues of under-segmentation or over-segmentation. To alleviate segmentation errors, Held et al. [18] built a probabilistic model to combine the spatial, temporal, and semantic cues for every segment. The probabilistic model iterates through every individual segment when conducting splitting and through all pairs of segments when merging. Zermas et al. [19] started with an approximate coarse ground plane based on a deterministically extracted set of seed points with low height values, and iteratively refined the ground plane fitting by selecting seed points belonging to previously estimated ground surface. After removing the ground points, line segments are found efficiently for every scan and subsequently merged across neighbouring scans. One of the drawbacks in all these methods is that they include the assumption that one even plane should be able to fit the ground in the point cloud, but this assumption may fail in various real-life situations. In contrast, our ground removal approach adopts multiple small planes to fit the ground surface, resulting in a more robust approach.

The conventional pipeline in 3D object detection involves segmenting a point cloud, then classifying the clusters into objects. After point cloud segmentation, Teichman et al. [20] adopted two classifiers, i.e., the segment and holistic classifiers, to classify feature vectors. The results were then combined with a discrete Bayes filter in a boosting framework. Wang et al. [21] proposed a feature-centric voting algorithm which convolutes the 3D point space in a sliding window with a voting scheme in a manner similar to feature transformation, enabling it to find new features describing object locations and orientations. An SVM classifier was subsequently applied to classify 3D candidates into different categories. As CNN-based approaches have become more and more dominant in computer vision tasks, a number of related 3D object detection approaches have been proposed. Chen et al. [22] proposed multi-view 3D object detection and converted the point cloud into bird-view representations, consisting of multiple height maps, one density map, and one intensity map. The mature 2D CNN framework used for object detection in images was applied to these bird-view images to generate 3D object candidates.

Ku et al. [14] designed AVOD-FPN, which generates 3D proposals on the bird-view images of the point cloud with a 2D CNN, then crops the corresponding features from RGB and bird-view images for each proposal and predicts the 3D bounding boxes based on fused features. Zhou et la. [23] adopted PointNet to extract features from the low resolution raw point cloud for each voxel, then employed a shallow 3D CNN network to convert 3D feature maps into 2D feature maps for 3D object detection. Other methods [26, 10] use sparse CNN [27, 28] to learn 3D feature maps from sparse 3D data, then compress them into 2D feature maps for object detection. Even though a large part of the computation for the sparse CNN is shifted to a CPU, these methods still require a GPU to achieve real-time performance. Although they can achieve desirable detection performance, these deep-learning-based approaches require a large training dataset and powerful processor, and cannot run in real-time without a GPU. To maintain both efficiency and accuracy, our framework employs point cloud segmentation to generate proposals and design an efficient classification model based on a CNN.

Pre-processing the data by removing points that belong to the ground has been shown empirically to improve segmentation performance significantly. The typical method employed in urban ground detection is to estimate an approximate 3D plane via model-fitting techniques, such as Random Sample Consensus (RANSAC). However, a simple plane is usually not sufficient for approximating the ground surface. A more powerful representation involves using a PWML approximation, such as in [12], or even more constrained cases, such as PWC with fixed partitions. The PWC assumes that in each region of the partition, the ’altitude’ of the nominal ground is constant (i.e. the nominal surface of the terrain is flat and horizontal). In order to infer the altitude of the nominal surface in a subregion, a histogram of the altitudes of the points whose XY coordinates belong to this subregion can be generated. Additional basic rules, which consider the continuity of the properties of adjacent subregions, enable this process to avoid being misled by plateaus. The PWC requires very low processing effort, and performs better than the more sophisticated RANSAC.

Fig. 2 summarizes ground modelling based on a fixed-size PWC approximation. The coverage in XY ($W\times L$) of the entire point cloud, is partitioned into multiple sub-regions, $W_{sub}\times L_{sub}$. For each subregion, a histogram of points’ heights (given simply by the points Z coordinates) is built. It is assumed that the ratio between the number of ground points and the number of non-ground points in every sub-region is larger than a certain user-defined threshold. According to this rule, the minimum bin value, whose frequency in the histogram is over this threshold, is assumed to be ground height. This operation can be implemented efficiently in parallel. The pseudo-code of the algorithm can be found in A. Since the assumption may fail when a sub-region contains the flat plane belonging to an object, such as the roof of a car, we design the post-processing step to amend such false detections. The post-processing will compare the height of every sub-region with those of its adjacent regions, and its ground height value will be updated with the lowest height found in the neighbourhood. Once the ground planes are inferred, points can be classified as either being part of the ground (’close enough’) or not. Based on this classification, only the points of interest (those above the ground) are kept for the posterior proposal generation of OOIs.

The remaining points, i.e. the points ’over the ground’, belong mostly to the OOIs, such as vehicles, cyclists, pedestrians, and background objects (buildings and plants). These objects are usually well separated when the ground points are removed. Therefore, we can perform clustering on these remaining points to find the potential 3D proposals.

Two methods are used to do point cloud clustering: distance-based and scan-based clustering. For the distance-based clustering method, the only criterion used to decide whether two points belong to the same cluster or not is their Euclidean distance. Hence, the distances between all point pairs are calculated and compared with a pre-defined distance threshold $T_{d}$. A random point $P_{0}$ is first selected and put into a separate list $C$. Then, the distances of other points from $P_{0}$ are calculated; Those points with distances from $P_{0}$ less than $T_{d}$, are removed and added to the same list $C$. Similar operations are performed repeatedly between points in $C$ and the rest of the points until no more points are added to list $C$, and $C$ is treated as a cluster. After this first cluster is complete, a new list will be created to search for the next cluster and so on until no more points are left. The algorithm details are shown in B. Distance-based clustering, which does not require the ordering information among points, can be generalized to any point cloud dataset. However, processing a large number of point clouds takes a considerable amount of time, since every point is sequentially required to do a comparison against the rest of the points.

The 3D point cloud, generated by the LiDAR, has a multi-layer structure and every layer, also called a scan, produced from the same LiDAR ring includes contiguous points. Based on this characteristic, the scan-based clustering method is proposed to speed up processing. The points in every scan, or single layer, are first segmented into line segments, then these line segments are compared with their vertical neighbouring segments. Finally, the line segments which are close together are merged into one segment.

It is assumed that points traverse in a raster in a counterclockwise fashion, starting from the top scan-line. $H_{d}$ is used to decide whether two points in the same scan belongs to the same segment or not, and $V_{d}$ is set to distinguish two points in neighbouring scans. We save all clusters, called $Global\_segs$, in the form of dictionary variables, in which the key and value are label number and corresponding points, respectively. All line segments begin with the first scan and are saved into a dictionary with the label as the key and the point group as the value, called $Above\_segs$.

The first $Above\_segs$ is appended to $Global\_segs$. Then line segments are extracted from the second scan and saved in another dictionary, $Current\_segs$. Next, every line segment $seg\_i$ in $Current\_segs$ is compared with all segments in $Above\_segs$. If $Above\_segs$ has no segment whose distance from $seg\_i$ is smaller than $V_{d}$. Then, the key for $seg\_i$ in $Current\_segs$ is assigned a new label number, and this new key and its points are added to $Global\_segs$. If $Above\_segs$ includes one connection with $seg\_i$, no new key is generated, and the key for $seg\_i$ is the same as the one in $Above\_segs$; all points in $seg\_i$ are appended to the point group with the same key in the $Above\_segs$ and $Global\_segs$. If $Above\_segs$ includes more than two connections with $seg\_i$, the minimum key for the connected segments in $Above\_segs$ is selected as the unique key for these connected clusters.

Merging operations are implemented in the $Above\_segs$ and $Global\_segs$. After processing a current scan, the $Current\_segs$ becomes the $Above\_segs$ and the algorithm starts to process the next scan. The pseudo-code of scan-based clustering can be found in C. The author in [19] designed a complicated label management system to handle label conflict and merge issues, while this paper employs the dictionary to save the points in all clusters directly, making our algorithm easier to implement.

In contrast to the distance-based clustering method, the scan-based approach takes the advantage of the ordering of the points along the LIDAR scan-lines and covert clustering problem in 3D space into the line segmentation, and only the Euclidean distance between one point and its neighbouring points along the scan line is required, resulting in much lower algorithm complexity. Therefore, it can achieve a real-time running performance. But the scan-based approach is only applicable to point cloud which is generated by the Lidar or other sensors with fixed multi-layer scanning structure, and is not as generalized as the distance-based method.

Three-dimensional proposals, generated by the clustering method, could also be for some background objects, such as super-large and tiny objects, which could be the buildings or leaves, respectively. To remove some improper background proposals and reduce the number of proposals, we set up two criteria to filter background proposals: 1) the size of the desired proposal should be within a certain range, and 2) the number of points in the non-occluded proposals should have a minimum. For the first criterion, we choose the maximum values for length and width to filter out very large objects, and the minimum value for height is defined to remove objects which are too flat, since objects of interest, such as pedestrians, cars, and cyclists, have certain height value.

As for the second criterion, the occlusion should be inferred first. The horizontal angle span of every 3D proposal is calculated against the location of the LiDAR and is compared with the angle spans of other proposals. A proposal is labelled as a non-occlusion proposal if it satisfies one of the following cases: 1) its angle scan does not overlap those of other proposals, and 2) its angle scan has overlapped with those of other proposals, but it is closer to the LiDAR than the other proposals. The details of this occlusion labelling algorithm are presented in D. To estimate the minimum number of points in non-occluded proposals, we investigate the relationship between the number of points and the distance from proposals to LiDAR, as shown in Fig. 3. The number of points and the distance to LiDAR are collected from all the ground truth bounding boxes in the training dataset provided by the KITTI benchmark [29]. The distance, which can be represented as either the range or the distance along X-axis to LiDAR, is sampled with an interval of $0.5$ $m$, and its corresponding number of points is the minimum number of points in all the ground truth bounding boxes, whose centre points are located in the distance interval. The exponential function is used to fit these sample points, see the green line in Fig. 3. Three-dimensional proposals with fewer than the minimum number of points are discarded.

The PointNet-based, efficient, and lightweight classification model is designed to identify the class of 3D region proposals [24]. There are numerous techniques available in the existing literature for processing raw point clouds in every proposal for classification, such as 3D CNN on a 3D voxelization grid [26], or a 2D CNN for bird-view images [22]. In contrast to these methods, the PointNet can consume the raw points directly without altering the data representation, and it also employs an efficient and shared MLP to process the features on each point independently (i.e. pointwise $1\times 1\times 1$ CNN) and max-pooling operation, which can achieve real-time performances under constrained processing resources. Therefore, we choose the PointNet to build our proposal classification network, as shown in Fig. 4.

In terms of the classification model, the input consists of 3D coordinates $(x,y,z)$ along with $N$ points for one proposal. The raw point-cloud can be encapsulated int an $N\times 3$ matrix. The affine transformation on the point set (such as rotation) should not change the classification results for a geometric object. Therefore, a $3\times 3$ transformation matrix generated by a spatial transformer network is first learned to transform the input points in order to make the model invariant to certain transformations. This type of transformation matrix is known as input ’TNet’ [24]. The PointNet in [24] also include an $64\times 64$ feature transformation matrix to align the features, but this matrix and corresponding feature ’TNet’ is omitted in our classification model, as it increase a lot of computation with limited accuracy gain. To increase the channel features from $3$ to $1024$, three layers of MLP are applied with weights shared among all the $N$ point features. A max-pooling network is used to aggregate point features in order to generate $1\times 1024$ global feature vector, and three layers of MLP are applied in order to decrease the channel features from $1024$ to $256$, then outputs the classification scores for $5$ classes: background, car, pedestrian, van, and cyclist. In addition, batch normalization [30] is applied to all layers via ReLU [31] and dropout layers [32] are used for the fully-connected neural network.

The parameters in the proposal segmentation model include the distance threshold $H_{d}$ for the line segmentation done in one scan, merging threshold $V_{d}$ between adjacent scans, and filtering distance $D_{o}$ to the ground plane. The objective of the proposed segmentation method is to achieve the highest possible recall of objects via using PSO to optimize parameters. The PSO searches the space of an objective function by adjusting the trajectories of individual agents, called particles. Every particle, $x_{i}$, represents a solution, namely, $x_{i}=[H_{d},V_{d},D_{o}]$ in our case, and the objective function is the recall of objects, as shown in Equation (1).

where $TP$ is the number of true positives, i.e. the correctly segmented objects, and $FN$ is the number of false negatives, i.e. the missed objects.

The movement of a swarming particle consists of two components: the stochastic and deterministic movements. Each particle is attracted towards the position of a current global best $g^{*}$ and its own best location $x^{*}_{i}$ in history, while, at the same time, it tends to move randomly. For each iteration, the particle $x^{t}_{i}$ is updated by Equations (2) and (3). The pseudo-code of PSO can be found in E.

where $\alpha$, $\lambda$ and $\theta$ are acceleration constants for different terms, and $r_{1}$ and $r_{2}$ are the random number used to simulate diversity in the quality solutions.

Considering that the number of labels in the different categories is balanced, we define a naive classification loss function, i.e. negative log-likelihood loss, with the following equation:

where $N$ is the number of training samples in one batch, and $\hat{y}_{i}$ is the predicted probability of $i$ belonging to the labelled class.

Since there exists a differentiable equation between the loss function (4) and parameters $W$, the gradient-based optimization method can be used to optimize the parameters $W$. The gradient descent method, i.e. AdamOptimizer [33], is applied to do the optimization in our classification model with an initial learning rate of 0.0002 and an exponential decay factor of 0.8 for every 18570 steps.

In order to compare our ground removal approach with R-
ANSAC qualitatively, we set up a criterion $\gamma$, i.e. the ratio between the number of removed points $N_{g}$ and the number of all points $N_{a}$, see Equation (5). The majority of points can be removed if the plane fits the real landscape of the ground plane. Therefore, given the same offset distance $D_{o}$ to the detected ground plane, the higher $\gamma$ is, the more effective the method is at removing the ground points. The qualitative experimental results and visualization of the ground removal performance can be found in Fig. 5 and 6.

The $\gamma$ is calculated by averaging all the ratio values of $1000$ point clouds randomly selected from the training dataset. From Fig. 5, we can see that, when the offset distance is small, such as $0<D_{o}<0.3$ $m$, the $\gamma$ ratio for the proposed method is higher than that for RANSAC. This finding validates the effectiveness of the proposed method, as it can effectively remove more points on the ground surface and match the detected ground planes of the real landscape. In the case of a larger offset, it does not matter whether the detected plane fits the landscape closely or not. Thus, the ratios of the two methods converge towards each other.

In order to make experimental data, which is meaningful for robots with limited processing capabilities, we force our code into one core when running the experiments. Proposal generation consists of three steps: ground removal, clustering, and proposal filtering. For the scan-based clustering method, the processing times for these steps are $0.002$, $0.03$, and $0.006$ $s$, respectively. More experimental data is presented in Table I, which shows that the scan-based method is much faster than the distance-based one. The distance-based method is slower because it calculates the distances from one point to all available points and searches a large number of adjacent points in each iteration. The performance of the proposal generation is very similar to that of the distance-based method, since both of them employ distance as the discriminative criterion regardless of the clustering mechanism used.

The proposal generation method with clustering has a higher recall (%) and three times the number of proposals compared to the combination of clustering and filtering, since the filtering procedure can filter out a number of false positives and reduce the number of proposals. However, it also removes some true positives and leads to a decrease in the recall value. In terms of the processing time, the clustering takes up to $0.032$ $s$, while the filtering only consumes $0.006$ $s$ and can decrease the number of proposals greatly. A large number of proposals will require a long processing time for the next classification task. Therefore, for a task involving limited computational resources, the filtering procedure is very important for achieving a real-time performance.

To enhance the performance of the proposal generation me-
thod, $D_{o}$, $H_{d}$, and $V_{d}$, are optimized using the PSO algorithm. For every generation in the PSO, the recall value is calculated by running the proposal generation algorithm through $500$ training samples randomly selected from the entire training dataset. A total of 1000 generation and 50 particles are set for optimization. The convergences of the recall value and all parameters are illustrated in Fig. 7. All parameters are randomly initialized between $0$ and $1.2$ $m$. From Fig. 7 (b), we can see that the parameters fluctuate at the beginning, then slowly converge to their optimal values. Since these parameters are constrained by each other, the combination of parameter values will decide the final fitness value. All parameter convergences fluctuate instead of moving in one direction. The convergence graph shows that the best values for $D_{o}$, $H_{d}$, and $V_{d}$ are $0.26$, $0.49$, and $0.58$ $m$, respectively.

To reduce the overfitting and generalize the model, two basic techniques for data augmentation are introduced:

To evaluate the performance, we assemble two sub-modules, i.e. proposal generation and classification, together into an object detection method. In Fig. 9, the overall detection performance is presented¹¹1More visuliazaiton results can be found in vedios: https://youtu.be/poSbDQ1LCR0, https://youtu.be/7C4kOnLrtig, https://youtu.be/QhXHMC4wsMc, https://youtu.be/LrXg3J_4FKY. It can be observed that we can find bounding boxes which fit nearby objects well, but the bounding boxes are much smaller than the real sizes of the objects that are far away from the Lidar. For instance, in the top middle image, the 2D bounding boxes for cars, which are far away, only cover the bottom halves of these cars because the density of points on the surface of the object is inversely proportional to the distance between the object and Lidar. The proposal of a nearby object includes a number of points and these points can represent its real shape, while, for a far object, there are only a small number of points and only a part of the object can be captured.

The comparison of the computational efficiency of our met-
hod with other 3D detection methods is provided in Table II, which shows that the proposed method is much faster than other existing methods and can achieve a real-time performance on either a GPU ($0.035$ $s$) or CPU ($0.082$ $s$) hardware platform. As for the performance of the object proposal, AVOD-FPN [14] and MV3D [22] can obtain better recall value than ours, but their efficiency is very low, especially on the CPU platform, since they employ the CNN backbone networks to extract features images for generating proposals.