## 3 Methodology
### Parking Space Automatic Annotation
#### 3.3.1 Ground Point Segmentation and Grid Map Construction  
Lidar point cloud mapping generates a 3D map containing ground point cloud and elevation data. In order to reduce the impact of redundant ground point data and elevation data on parking space detection and accurately identify obstacle vehicles, the ground points need to be segmented and filtered first, and then BEV projection is performed to construct a grid map.  
The ground point segmentation adopts the vertical angle evaluation method [42]. Figure 9 is a schematic diagram of the vertical angle evaluation method. The point strip is a point cloud in the same horizontal orientation (i.e., on the same vertical plane, with the same \(\theta_{h}^{\mathrm{k}}\)) in a single-frame point cloud. The vertical angles between the point clouds are calculated in order from small to large according to the point cloud depth \(I(row,col)\), and compared with the vertical angle threshold to determine the ground points, thereby eliminating the ground points. Based on the above method, all ground points in a single-frame point cloud can be eliminated. The ground-filtering process is in frames. When all the lasers included in the point cloud map have completed the ground-filtering process, the remaining point cloud is the required point cloud. For example, in Figure 9, it is assumed that \(p_{a}=\{x_{a},y_{a},z_{a}\}\) is the determined ground point cloud, \(p_{b}=\{x_{b},y_{b},z_{b}\}\) and \(p_{c}=\{x_{c},y_{c},z_{c}\}\) are the laser point clouds to be determined, and the vertical angle threshold is \(\epsilon_{ab}^{\mathrm{h}}=10.0^{\circ}\). Connect point clouds \(p_{a}\) and \(p_{b}\), and calculate the vertical angle \(\theta_{ab}^{\mathrm{h}}\) of the point cloud connecting line \(ab\):  
\[\begin{cases}x_{ab}=x_{b}-x_{a}\\ y_{ab}=y_{b}-y_{a}\\ z_{ab}=z_{b}-z_{a}\end{cases}, \tag{24}\]  
\[\theta_{ab}^{\mathrm{h}}=\left|arctan2\left(\frac{z_{ab}}{\sqrt{x_{ab}^{2}+y_ {ab}^{2}}}\right)\right.\times\frac{180}{\pi}\Bigg{|}. \tag{25}\]  
where if \(\theta_{ab}\) is less than \(\epsilon_{ab}^{\mathrm{h}}\), then \(p_{b}\) belongs to the ground point. Connect points \(p_{b}\) and \(p_{c}\), and use the above method to determine whether \(p_{c}\) belongs to the ground point; if \(\theta_{ab}\) is greater than \(\epsilon_{ab}^{\mathrm{h}}\), then \(p_{b}\) does not belong to the ground point. Connect points \(p_{a}\) and \(p_{c}\), and use the above method to determine whether \(p_{c}\) belongs to the ground point.  
For the scene map with ground point clouds filtered out, it is necessary to extract the ROI and construct a BEV grid map based on the ROI, using erosion and dilation algorithms to mark obstacle grids. The bounding box of the ROI is set according to the actual scene dimensions, \(\epsilon_{\mathrm{ROI}}=\{\epsilon_{\mathrm{X}},\epsilon_{\mathrm{Y}},\epsilon _{\mathrm{Z}}\}\). The ROI \(\mathbf{M}_{\mathrm{ROI}}\) is extracted from the point cloud map and projected into a BEV grid map with a scale of \(scale_{\mathrm{X}}=1\mathrm{m}:3\) cm and \(scale_{\mathrm{Y}}=1\mathrm{m}:3\) cm. In the grid map, as shown in Figure 10: the first step is, if the point cloud density in a single  
Figure 9: Schematic diagram of the vertical angle evaluation method.  
grid is not less than two, the grid is marked as occupied; otherwise, it is marked as free. To further refine this map, erosion removes small clusters of noise or isolated points that may falsely indicate occupancy. This step ensures that the occupied grids more accurately represent significant obstacles or structures in the environment, thereby improving the overall reliability of the map. The second step is, traverse the occupied grids and check the status of their eight surrounding grids. If at least one of the surrounding grids is also occupied, the grid is marked as an obstacle; otherwise, it is marked as noise. The third step is, traverse all obstacle grids and mark the eight surrounding grids as obstacles.