# A Particle PHD Filter for Dynamic Grid Map Building towards Indoor Environment
## 3 The Proposed Framework for Building Dynamic Grid Map
### Parallel Implementation  
The calculation of the measurement grid is very time-consuming. For example, the map size is \(20m\times 20m\), and the resolution is \(0.05m\), so the number of grid cells needed to be calculated is \((20/0.05)^{2}=160000\). Under the conditions of serial computing, in order to meet the real-time requirements, it is usually necessary to make a trade-off between the map size and the grid resolution. The occupancy grid map is a computing intensive environment characterization scheme. Due to the limited computing resources, users have to choose between map size and grid resolution. In a dynamic environment, especially for the perception of dynamic objects, it is necessary to ensure a sufficient sensing range (map size) and perceptual accuracy (resolution). This will cause a huge computational load because a large number of grid cells need to be calculated. Some researchers have proposed that GPU (Graphics Processing Units) can be used to accelerate the establishment of a traditional static grid map [33; 34]. Here, the method of the paper [34] is used to calculate the measurement grid maps in parallel. Each grid cell contains two information \(p_{occ}\) and \(p_{freq}\). Suppose \(n\) measurements \((ranges_{k+1}^{1:n},thetas_{k+1}^{1:n})\) are obtained at time \(k+1\). When  
Figure 6: Segmentation of dynamic objects. \(ranges_{k+1}^{i}\) is greater than the sensing range, it is considered infinite. Then, the calculation process can be summarized into two steps. 1. Use the GPU to calculate the polar coordinate measurement grid map in parallel. Assuming that the grid \(c_{j,i}\) in the polar coordinate system corresponds to the laser measurement \((ranges_{k+1}^{i},\)\(theta_{k+1}^{i})\), the inverse sensor model can be used to calculate the occupancy probability of the grid cell \(c_{j,i}\): \[p_{occ}(c_{j,i}|ranges_{k+1}^{i})=\frac{\alpha(ranges_{k+1}^{i})}{\sqrt{2 \pi\sigma^{2}}}e^{-\frac{(c_{j,i}-range_{k+1}^{i})^{2}}{2}}.\] (39) At the same time, it is also necessary to use measurement \(ranges_{k+1}^{i}\) to estimate the free mass value \(p_{free}(c_{j,i}|ranges_{k+1}^{i})\) of grid cell \(c_{j,i}\). For its calculation, please refer to the paper [26]. 2. After calculating the measurement grid map in polar coordinates, it needs to be converted into the measurement grid map in Cartesian coordinates. Here, the polar coordinate grid needs to be correctly mapped to the grid under Cartesian coordinates, and the value in the grid can be interpolated correctly. Here, it is necessary to correctly map the grid cell in polar coordinates to the corresponding grid cell in Cartesian coordinates and correctly interpolate \(p_{occ}\) and \(p_{free}\) in the grid cell. In the paper, different conversion methods are compared, including the exact algorithm and the sampling approach. Here, we use the better texture mapping method and use the OpenGL library to convert the measurement grid map in the polar coordinate system to the measurement grid map in the Cartesian coordinate system. In order to ensure the accuracy of dynamic grid map estimation, a large number of particles need to be used. At the same time, operations on each particle are involved in the particle prediction phase, update phase, grid statistical moment calculation, and resampling phase. Due to the characteristics of particle filter, these operations can be accelerated through parallel computing [35; 36]. After the particle prediction step is performed using the parallel method, since the update of the particle weight and the calculation of the statistical moment are all based on the grid cell, each grid cell must record the particles in the grid cell. Here, we first sort the particles according to their grid coordinates. After sorting the particles, each grid cell only needs to store two particle subscripts: the first subscript and the last subscript of all particles in this grid cell.