# Two-Layer-Graph Clustering for Real-Time 3D LiDAR Point Cloud Segmentation
## 1 Introduction
It traverses the point cloud from different directions, integrates multiple features as the evaluation criteria, and uses the structured neighborhood relationship between point clouds to improve the operation efficiency [15, 16]. These methods have made a lot of contributions to the point cloud storage structure. The use of a graph structure [17, 18] enables the vast data to represent the relationship between different points and make full use of the storage space. However, the segmentation standard designed by the above methods is relatively simple, and in some cases, over-segmentation occurs. [PERSON] [19] directly clusters all point clouds. They can use specially designed features to deal with complex point cloud scenes effectively. RANSAC is a classic method, and many point cloud clustering is improved based on this method; [PERSON] [20] used H-RANSAC combining 2d and 3d data, [PERSON] [21] used a weighted RANSAC for building roof plane segmentation of point clouds, and [PERSON] [22] used an improved RANSAC based on normal distribution transformation cells. [PERSON] [23] used the designed 2D and 3D features to analyze the point clouds. [PERSON] [24] used the graph model and data-driven method to cluster the point cloud. The region growing method [25, 26, 27], model fitting method [28, 29], and hierarchical clustering method [30, 31, 32] are also widely used in point cloud clustering. The method of multi feature fusion is also a mainstream research direction [33, 34, 35]. Nevertheless, most of those methods require dense point clouds and complex mathematical models, which have a negative impact on real-time performance. All the methods mentioned above are those popularly used at present. The grid map can significantly reduce the amount of data to be processed, and the mature image processing algorithm is applied. However, this kind of method loses the accuracy of clustering results. The second kind of method uses the range graph to simplify the storage, but there are some over-segmentation problems. The third method ensures the accuracy by designing features and models; however, the calculation process is complex, and the running time is long. Some single frame processing methods can reach more than 1 s, which is unacceptable for the real-time system. For a real-time system, the implementation of the whole perception system needs to be controlled within 100 ms [1]. At the same time, the accuracy of clustering results is related to the subsequent recognition task. It is necessary to ensure that more than 85% of a point cloud of a particular object can be correctly classified, and the running time of some excellent methods can be less than 40 ms [13; 16; 36]. In order to meet the real-time and accuracy requirements of autonomous vehicles, we design a Two-Layer-Graph clustering method (improved from the range graph) and use an improved BFS algorithm. In Figure 1, different objects are represented by points of different colors, our method can not only ensure the accuracy but also compress the running time as much as possible. Also, particularly, we design the segmentation standard to solve this kind of over-segmentation problem.