## 3 Methodology
### Parking Space Automatic Annotation
#### 3.3.2 Obstacle Vehicle Detection and Vacancy Annotation  
The implementation of obstacle vehicle detection and vacancy annotation based on fitted lines requires the extraction of vehicle contours from the point cloud. In this section, the extraction of vehicle contours is performed on the obstacle grid map after erosion and dilation. The specific method in Figure 11 is as follows: first, use the grid occupancy point density information to cluster the point cloud, retaining vehicle point clouds based on vehicle size constraints; next, draw a convex hull on the retained vehicle point clouds and fit the vehicle contour lines on the convex hull; finally, use the fitted lines as prior information combined with vehicle size constraints to mark vacant parking spaces. We categorize parking spaces into three types based on the parking method: perpendicular parking spaces, angled parking spaces, and parallel parking spaces, as shown in Figure 12. The method described in this section is applicable to all three types of parking spaces. The grids in the obstacle grid map contain occupancy point density information. Based on this density, the DBSCAN algorithm is used to cluster the obstacle points on the planar grid, resulting in different point cloud clusters \(\mathbf{p}_{cluster}\). The DBSCAN effectively handles noise points and outliers, does not require predefined numbers of clusters, and is robust to varying cluster shapes. The DBSCAN algorithm uses a neighborhood sample count threshold of \(minPts=3\) and a neighborhood distance threshold of \(\varepsilon_{r}=30\) cm. To more accurately filter out vehicle point clouds, vehicle size is used as prior information:  
Figure 10: Schematic diagram of the barrier grid marking method based on erosion and dilation. \[\mathbf{p}_{vehicle_{i}}=\Big{\{}\mathbf{p}_{cluster_{i}}\big{|}\text{max}\big{|}p_{k_{1} }-p_{k_{2}}\big{|}_{l}\geq size_{l},\text{max}\big{|}p_{k_{1}}-p_{k_{2}}\big{|}_ {w}\geq size_{w},p_{k_{1}},p_{k_{2}}\in\mathbf{p}_{cluster_{i}}\Big{\}}. \tag{26}\]  
where in our method, \(size_{l}=4\) m, \(size_{w}=2\) m.  
Based on the Graham algorithm, the convex hull is drawn for the retained obstacle clustering targets to achieve obstacle recognition. The obstacle convex hull \(\mathbf{p}_{\text{CH}}\) satisfies:  
\[\mathbf{p}_{\text{CH}_{i}}\subset\mathbf{p}_{vehicle_{i}}. \tag{27}\]  
Figure 11: Flow chart of obstacle vehicle detection and vacancy annotation. Figure 12: Parking slots classification (based on grid projection). (**a**) Perpendicular parking space; (**b**) Angled parking space; (**c**) Parallel parking space. The vehicle contour straight line is fitted using Hough transform on the grayscale image. Therefore, a density grayscale image is first generated based on the obstacle grid image. The grid grayscale calculation formula is:  
\[Gray=\frac{D_{i}}{D_{max}}\times 255. \tag{28}\]  
where \(D_{i}\) is the point cloud density value in the current grid and \(D_{max}\) is the maximum point cloud density value of the entire grid map. The obstacle boundary is intercepted in the generated grayscale image, and the boundary straight line is extracted based on the Hough transform with the following conditions as the convergence conditions:  
\[\left\{ \begin{aligned} density_{i}\gg density_{o}\\ e_{l}=\left|l_{l}^{\text{Hough}}-size_{l}\right|\leq\varepsilon_{l}, \text{ or }e_{w}=\left|l_{w}^{\text{Hough}}-size_{w}\right|\leq\varepsilon_{w}.\end{aligned} \right. \tag{29}\]  
where \(density_{o}\) represents the point cloud density outside the extracted boundary line and \(density_{i}\) represents the point cloud density inside the extracted boundary line. \(l_{l}^{\text{Hough}}\) denotes the length of the long side of the extracted line for perpendicular or angled parking slots, while \(l_{w}^{\text{Hough}}\) denotes the width of the extracted line for parallel parking slots.