# Two-Layer-Graph Clustering for Real-Time 3D LiDAR Point Cloud Segmentation
## 5 Conclusions  
In this article, we propose a point cloud clustering algorithm with a Two-Layer-Graph structure. Through the merging of graph nodes, we get the simulation results, which show that our method has a high-quality accuracy (the accuracy rate of objects in the road is 93.64%) while the running time of our method is less than 20 ms. We test it on the actual vehicle and find that our method meets the requirements of real-time operation with different LiDARs.  
The accuracy of our proposed method in segmentation performance is better than some classic methods. The possible reasons are as follows: (1) more effective selection of the vectors from adjacent points to different sides, and (2) the consideration of the relationship with the position of the sensor devices. Compared with other methods, our method, i.e., the TLG method, uses the least information to represent the characteristics of the object itself and the location relationship with the autonomous vehicle. It not only satisfies the richness of information but also saves the computing time, using the  
Figure 12: The red curve is the running time of the Bogoslavskyi method, the green is [PERSON]’s method, and the blue is the method we proposed. The proposed method has relatively little running time.  
Figure 13: Different LiDAR operation time increases with the number of laser channels, and the time complexity is linear.  
local concave features to distinguish different objects close to each other with as little information as possible.  
The running time of TLG has been greatly compressed compared with other methods. The TLG clustering algorithm mainly improves the point cloud structure, segmentation standard and search algorithm. Its point cloud structure is closely related to the search algorithm, which can greatly improve the operation speed and omit some unnecessary calculations. When updating, instead of performing operations on all adjacent points in the vertical direction, it can merge in the form of nodes, which greatly improves the operating efficiency. In the worst case, its time complexity is linear. In recent years, the laser channel of LiDAR has been increased to obtain more environmental information, so the linear time complexity is very important, so that TLG clustering can do a good job. The biggest contribution of this paper is to reduce the processing time to less than 20 ms, and ensure high accuracy.  
Our method also has limitations. The segmentation standard is designed for traffic objects, and we mainly evaluated the method on a large number of urban scenes. It is not tested in the complex wild environment, where there are more disordered objects on the road (weeds, shrubs, etc.) and those may affect the segmentation results.  
In the promising future direction, we will consider how to use the clustering results for real-time target recognition and point cloud clustering of multiple LiDAR. In addition, we plan to introduce continuous time to help two-layer-graph point cloud clustering.  
Conceptualization, H.Y. and L.L.; methodology, H.Y.; formal analysis, H.Y.; investigation, W.H. and F.X.; resources, Z.W.; data curation, L.L.; writing--original draft preparation, H.Y.; writing--review and editing, Z.W. and L.L.; visualization, H.Y.; supervision, Z.W.; project administration, H.L. All authors have read and agreed to the published version of the manuscript.  
This work was supported by the National Key Research and Development Program of China (Nos. 2016 YFD0701401, 2017 YFD0700303 and 2018 YFD0700602), Youth Innovation Promotion Association of the Chinese Academy of Sciences (Grant No. 2017488), Key Supported Project in the Thirteenth Five-year Plan of Hefei Institutes of Physical Science, Chinese Academy of Sciences (Grant No. KP-2019-16), Equipment Pre-research Program (Grant No. 301060603), Natural Science Foundation of Anhui Province (Grant No. 1508085 MF133) and Technological Innovation Project for New Energy and Intelligent Networked Automobile Industry of Anhui Province.  
The authors declare no conflict of interest.