# Two-Layer-Graph Clustering for Real-Time 3D LiDAR Point Cloud Segmentation
## 3 Proposed Method
### Category Update  
A category update requires the use of a search algorithm. The search algorithm is a method of traversing the point cloud. The fewer times the point cloud is traversed, the less time it takes. We traverse the two-layer-graph structure twice according to the segmentation steps. The first traversal is on the range graph. It uses the horizontal segmentation standards to divide the points under each channel into different sets. In Algorithm 1, first initialize the range graph (line 1), segment according to each channel (line 2), first set the category label to 0 (line 3), traverse in the order of the horizontal rotation angle (line 4), if it encounters an invalid point, skip and continue searching (line 5-6)in Figure 6a, If it is the first valid point of the current channel (line 7), add 1 to the category label, use the current position as the start position and Pre Pos, and mark the first label of this point on the range graph (line 8-11). If the segmentation condition is met, the current point and Pre Pos point belong to different categories, assign the end position to Pre Pos, add a node in the set graph, add 1 to the category label, and use the current position as the new start position and Pre Pos (line 13-18). If the segmentation condition is not met, Pre Pos is updated, and marks the current label for the current position (line 19-21) in Figure 6b. ```
Input:Range graph of 3D point cloud \(G_{r}\), distance and angle threshold \(Th_{d}\)\(Th_{z}\) Output:Set graph \(G_{c}\)
1\(Init(G_{r})\)
2 for\(i=0;i<row;i++\)do
3\(L_{cnt}=0\)
4 for\(j=1;j<col;j++\)do
5 if\(G_{r}(i,j)->\)\(valid=F\)then
6 continue;
7 if\(L_{cnt}==0\)then
8\(L_{cnt}++\); Start \(Pos=j\);
9\(Pre\ Pos=j\); \(G_{r}(i,j)->\alpha=L_{cnt}\)
10 else
11 if\(Dis(G_{r}(i,j),G_{r}(i,Pre\ Pos))>Th_{d}\|(Ang(G_{r}(i,j),G_{r}(i,Pre\ Pos))<Th_{d} \&V_{angle-bisector}V_{o-m}>0)\)then
12\(End\ Pos=Pre\ Pos;L_{cnt}++\);
13\(Start\ Pos=j\); \(Pre\ Pos=j\); \(G_{r}(i,j)->\alpha=L_{cnt}\)
14
15 else
16\(Pre\ Pos=j\); \(G_{r}(i,j)->\alpha=L_{cnt}\)
17
18
19
20
21 end if
22
23 end for
```  
**Algorithm 1**First segmentation Algorithm  
### Category Update  
A category update requires the use of a search algorithm. The search algorithm is a method of traversing the point cloud. The fewer times the point cloud is traversed, the less time it takes. We traverse the two-layer-graph structure twice according to the segmentation steps. The first traversal is on the range graph. It uses the horizontal segmentation standards to divide the points under each channel into different sets. In Algorithm 1, first initialize the range graph (line 1), segment according to each channel (line 2), first set the category label to 0 (line 3), traverse in the order of the horizontal rotation angle (line 4), if it encounters an invalid point, skip and continue searching (line 5-6)in Figure 6a, If it is the first valid point of the current channel (line 7), add 1 to the category label, use the current position as the start position and Pre Pos, and mark the first label of this point on the range graph (line 8-11). If the segmentation condition is met, the current point and Pre Pos point belong to different categories, assign the end position to Pre Pos, add a node in the set graph, add 1 to the category label, and use the current position as the new start position and Pre Pos (line 13-18). If the segmentation condition is not met, Pre Pos is updated, and marks the current label for the current position (line 19-21) in Figure 6b.