# Free Space Detection Algorithm Using Object Tracking for Autonomous Vehicles
## 2 Materials and Methods  
### Clustering and Object Tracking  
This is the process of identifying the behavior of obstacles around the vehicle using sensor data. LiDAR is an abbreviation of light detection and ranging. It is a radar system that measures the positional coordinates of a reflector by measuring the time it takes to emit a laser pulse, reflect it, and return it, which are output as point data. The point data output by the LiDAR sensor are clustered using the DBSCAN (density-based spatial clustering of applications with noise) algorithm [28; 29; 30]. DBSCAN is one of the clustering algorithms based on density and is a widely used algorithm for clustering point data. Figure 1 is a pictorial representation of the DBSCAN clustering process. Figure 1a shows the single-layer LiDAR raw data. Figure 1b is the result of judging data having a number of points greater than or equal to the MinPts (minimum number of points) in the eps (epsilon) radius as cluster data according to the DBSCAN algorithm, and separating the rest into noise data. Figure 1c is the result of clustering into Cluster 1 and Cluster 2 after removing noise.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Previous** & **Sensor** & **FSD with/without** \\
**Paper** & & **Obstacle Speed Information** \\ \hline
[1] & Laser Scanner & \\
[2] & LiDAR, Camera & \\
[3] & LiDAR & \\
[4] & LiDAR, Camera & \\
[5] & Camera & \\
[6] & Camera & \\
[7] & LiDAR, Camera & \\
[8] & Camera & \\
[9] & Camera & \\
[10] & Radar & \\
[11] & Camera & \\
[12] & Camera & \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of previous papers [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12].  
The boxing process is executed in multiple layers using the results of clustering in a single layer. This is to integrate and simplify multi-layered data. This process is shown in Figure 2. Figure 2a is a classification of data that recognize the same obstacle in each layer, and 3 single layers that recognize the same obstacle are shown in 3D. For integration, the data are integrated and displayed in 2D on one plane as in Figure 2b. For the simplification of the integrated data, square data are created with four points, as shown in Figure 2c. The rectangle is calculated using the x max, x min, y max, and y min values of the integrated point data. As a result, cluster data of multiple layers are represented by four-dot square data.  
An object tracking process is required to determine the speed of the obstacles [31]. Figure 3 shows the object tracking process. By comparing the previous and current positions of obstacles, it is judged whether they are the same obstacles, and an ID and Age are assigned to each obstacle. If it is judged to be the same obstacle, the same ID as before is assigned and the Age is increased. If it is determined that it is a newly measured obstacle, a new ID is assigned. Through this process, the speed can be calculated using the displacement according to the time the obstacle moves. In this case, when the position of the obstacle is changed, the data of the rectangle may also be changed. Therefore, the minimum and maximum sizes of obstacles (mainly vehicles) are reflected and tracked.