# Two-Layer-Graph Clustering for Real-Time 3D LiDAR Point Cloud Segmentation
## 3 Proposed Method
### Segmentation Standard
#### 3.2.1 Horizontal Direction  
The continuous point clouds under a channel have the same vertical angle, and the horizontal angle between adjacent point clouds is very small, showing a dense feature. We perform the first segmentation operation of point clouds under the same channel. The primary standards used are distance and angle characteristics. In Figure 4, some adjacent points belong to different objects under the same channel, have a long-distance difference on the horizontal plane, so distance can be used as the segmentation standard directly. So we use the distance between adjacent point clouds as one of the segmentation standards. For two points under the same channel \(ver_{1}\):  
\[p_{ver1,hor1}=\{x_{1},y_{1},z_{1},d_{1},ver_{1},hor_{1},V_{1},\alpha_{1},\beta_{ 1}\} \tag{1}\]  
\[p_{ver1,hor1+1}=\{x_{2},y_{2},z_{2},d_{2},ver_{1},hor_{2},V_{2},\alpha_{2},\beta_{ 2}\} \tag{2}\]  
\(x\), \(y\), \(z\) represent 3D space coordinates, \(d\) represents the distance from the point cloud to the sensor, \(ver\) and \(hor\) are the vertical angle and the horizontal angle, \(V\) represents whether the point is valid, \(\alpha\), \(\beta\) represent the first category label and the final category label. These two parameters are both \(-1\), which means that the segmentation process has not been performed yet. We first calculate the distance on the xy plane. \[dis=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}>Th_{dis} \tag{3}\]  
In the left of Figure 4, if the distance between two adjacent points is over a certain threshold, we think they belong to different categories. However, there are also some adjacent point clouds that belong to different objects with close distance in the right of Figure 4, but it is not easy to segment them using only the distance standard. For this case, we have designed an angle-dependent segmentation standard. Different from other methods, we first calculate the vector angles on different sides of the adjacent points. This method takes into account the position relationship of five points, including the sensor position, to determine whether the adjacent two points belong to the same category. For adjacent point clouds in a short distance, we obtain the vector directions to the point clouds on different sides and then calculate the direction of the angle bisector of the two vectors. Figure 4: All point clouds in the figure are under the same channel. Yellow represents object A, and red represents object B. The adjacent point clouds of different objects on the left have a long-distance difference, which can be distinguished, but the distance on the right is short and difficult to distinguish. Using \(V_{1}\) and \(V_{2}\) in Figure 5a to represent the unit vectors from points \(p_{ver1,hor1}\) and \(p_{ver1,hor1+1}\) to adjacent point clouds on different sides. Calculate the unit vector on the bisector of the angle of the two unit vectors \(V_{angle-bisector}\). \[V_{angle-bisector}=\frac{V_{1}+V_{2}}{\|V_{1}+V_{2}\|} \tag{4}\]  
The vector from the midpoint of points \(p_{ver1,hor1}\) and \(p_{ver1,hor1+1}\) to the position of the sensor, we call it \(V_{m-o}\):  
\[V_{m-o}=(-\frac{x_{1}+x_{2}}{2},-\frac{y_{1}+y_{2}}{2}) \tag{5}\]  
\[V_{m-o}V_{angle-bisector}>0 \tag{6}\]  
\[arccos(\frac{V_{1}V_{2}}{\|V_{1}V_{2}\|})<Th_{angle} \tag{7}\]  
When Formulas (6) and (7) are met, the inner product of vector \(V_{angle-bisector}\) and vector \(V_{m-o}\) is greater than zero, and the angle between vectors \(V_{1}\) and \(V_{2}\) is less than the threshold \(Th_{angle}\), the two points are divided into different categories. If the angle bisector is located at the position enclosed by the red dashed line in Figure 5c, and the angle between \(V_{angle-bisector}\) and \(V_{m-o}\) is less than a certain threshold, the two adjacent points are classified into different categories. If it is located in the shadow of the black dashed area, the two points are of the same category.