# Two-Layer-Graph Clustering for Real-Time 3D LiDAR Point Cloud Segmentation
## 1 Introduction  
With the rapid development of autonomous vehicle technology in the past decade, the performance of the sensors and the perception algorithm have been greatly improved. The perception system is the first stage of the autonomous vehicle system to process data. In order to ensure the vehicles' safety when they are running at a high speed, it is generally required to complete all sensing tasks within 100 ms [1]. Furthermore, the accurate performance of perception ensures that the vehicle decision system operates correctly, which is crucial for autonomous vehicle safety [2]. 3D LiDAR sensors have been applied more and more for robotics and autonomous vehicles in recent years [3]. Compared with the digital image, LiDAR has specific characteristics, such as high measurement accuracy and insensitiveness for different light conditions; it can work in both the day and the night. Considering common in-vehicle LiDAR data has a large amount of information, there areoften more than 100,000 points in one frame, and it can acquire the data at a fast speed. Therefore, it is the most popular sensor in the autonomous vehicle research currently, and how to deal with such massive data has become an essential topic in the perception system [4, 5]. A city environment is complex for autonomous vehicles due to a large number of traffic objects. Segmentation is an effective way to deal with this kind of cluttered point cloud, and unsupervised segmentation is instrumental in dealing with a 3D point cloud of a real scenario [6]. Point cloud clustering is the process of dividing indistinguishable points into different categories according to objects' characters. Clustering is crucial since it reduces the amount of data at the level of 100,000 to hundreds, which can facilitate the systems ability for object detection and target tracking [7]. In point cloud clustering, the accuracy and running time are the key indicators of the system; the high-accuracy of the segmentation can reduce errors in the informed decision of the autonomous vehicle, and real-time performance enables vehicles to respond quickly in complex traffic environments, which can improve the safety of autonomous vehicles. For dealing with the point cloud data, a method was proposed by [PERSON] [8] to put the point cloud data into a certain size grid. He separates the ground by calculating the height difference of the point cloud in the grid. This method creatively uses a grid map to process the point cloud, which significantly improves the speed and makes an important contribution to the development of automatic driving technology. [PERSON] [9] proposes a polar grid method, which divides the point cloud data into different sectors and extracts the point cloud in the sector to fit and segment the point cloud in line with certain line characteristics. His method can reduce the dimensions of a point cloud to a grid map, which improves the operation speed. [PERSON] [10] uses Gaussian distribution to cluster different objects on a grid map. The methods mentioned above are representative of the grid map method. [PERSON] [11] uses a voxel and graph-based strategy to reduce point cloud density, and [PERSON] [12] also reduces the number of regions by voxel. Although this kind of method can significantly reduce the running time, the accuracy of the results depends on the grid or voxel accuracy, and there are a lot of blank areas in the grid map, which waste space. [PERSON] [13] proposed a clustering algorithm based on a range graph. The method uses the angle on the vertical channel to segment the ground, calculates the change of vector between the adjacent point cloud, and then carries out the Breadth-First-Search in four neighbor areas to cluster the non-ground point cloud. [PERSON] [14] proposed a new method to utilize some seed points and two thresholds to estimate the ground fitting equation, calculate the distance from points to the fitting equation and get the result of the ground points and non-ground points. [PERSON] proposed a mesh-graph based clustering.