# Two-Layer-Graph Clustering for Real-Time 3D LiDAR Point Cloud Segmentation
## 2 Data and Problem Analysis
### Analysis of Clustering Tasks  
The ability to run point cloud clustering in real time needs to be optimized in multiple aspects. We mainly focus on the following aspects to make our proposed clustering algorithm faster than other methods.  
(1) **Storage structure:** The general point cloud is disordered, but the data of the rotary LiDAR has a certain organizational structure because of its collection principle. By organizing it into an orderly structure, the speed of reading is greatly improved. In addition to the storage structure of the point cloud, the data attributes of a single point are also what we need to pay attention to. How to update the attributes of each point quickly is the key to improving the speed of calculation, so it is necessary to design the storage structure of a point cloud with suitable data attributes. The range graph is useful in the presence of the neighborhood relationship of point clouds, easy to search, and will not waste storage space; this storage structure has been used in many researches [13; 16]. A graph structure can effectively represent the relationship between points [38; 39], and a single graph node can represent point cloud groups. According to the characteristics of the original point cloud data, we design a Two-Layer-Graph structure based on a range graph and use edges to represent their neighborhood relationship. This structure combines the advantages of a range graph (save space, easy to read and write) and graph structure (application of fast search algorithm), which dramatically improves the efficiency of the algorithm.  
(2) **Segmentation standard:** For the original point cloud, each point has its own angle information and 3D space position information. Whether to classify different points into one category or different categories is also the focus of attention, so suitable segmentation standards are very important. Standards can affect the accuracy of the clustering results, but complex segmentation standards will consume more running time. In the face of different application requirements, we need to choose some suitable segmentation standards. The standard method is to use Euclidean distance and segments according to the distribution characteristics of continuous points or to calculate the angle relationship of adjacent point clouds [13; 15], and an optimal neighborhood should be selected [40]. Considering the difference in point cloud density, we design different segmentation standards in horizontal and vertical directions. In the horizontal direction, we use the Euclidean distance and the angle between the vectors on both sides of the adjacent points and the sensor position as the segmentation standard, and the distance of the horizontal projection in the vertical direction.  
(3) **Category update:** In the process of point cloud clustering, the category of a single point cloud or a partial area point cloud can not be determined at once. It is necessary to update the category of point cloud. The method to update the category greatly affects the real-time performance of the point cloud clustering. [PERSON] [15] updates the categories after the initial segmentation usingconnection maps in different directions. It is a common practice to use a breadth-first-search algorithm in the search, which is used in many fields of automatic vehicles [13; 41]. In the graph structure storage model we designed, we improved the breadth-first-search method for data characteristics.