# Automatic Extraction of High-Voltage Power Transmission Objects from UAV Lidar Point Clouds
## 3 Method
### Preprocessing  
Traditional point cloud data management and search methods are often computationally costly [55; 56]. Therefore, in this paper, PLs were segmented by means of data partitioning based on a memory- and computing-efficient data structure.  
**Planar compression and hash storage scheme:** The voxel grid was set as the unit to organize by the hashing storing scheme, which contains the index of all voxels. The spatial hash [57; 58; 59; 60; 61; 62; 63] data structure dealt with the voxels of observed space by marking them in the hash table with a pointer stored in it. Additionally, structured data can be read and written effectively, allowing for faster calculation of features [64]. The grid blocks were stored using this scheme, combined with the sparse matrix. Unlike conventional or hierarchical grid data structure, this 3D hashing matrix can substitute memory intensively and can compactly deal with sparse grids (grids that contain few points). In fact, many grids did not contain laser points; they conformed to sparse matrix logic [65], and thus were stored in the spatial hashing structure which sparsely and efficiently managed compressed point clouds in grid blocks. Consequently, a large number of data-free grids were eliminated to save memory. The processing with 3D grid as the unit improved the efficiency of the subsequent clustering for local PL segmentation.  
**2D grid generation:** Due to the high volume, high density, and unordered distribution of the point cloud data, planar 2D gridding was exploited to manage the contextual features. Local grid features (the density and height at the level of individual grid) were calculated during the process of planar gridding, which facilitated the rapid identification of HV pylons candidate areas. First, the distribution range of the original points was computed to estimate the number of grids [66]. Each point  
Figure 1: The workflow of transmission power line and pylon extraction and reconstruction.  
was re-calculated with regard to the new planar coordinate system to allocate it to its grid. The process iterated until all points were allocated. The formula used is as follows:  
\[\left\{\begin{array}{l}\mathrm{m}=\left(\mathrm{y}-\mathrm{y}_{\mathrm{min}}^{ \mathrm{G}}\right)/\mathrm{d}2\\ \mathrm{n}=\left(\mathrm{x}-\mathrm{x}_{\mathrm{min}}^{\mathrm{G}}\right)/ \mathrm{d}2\end{array}\right., \tag{1}\]  
where (x, y) refers to the candidate horizontal coordinates, \(\mathrm{x}_{\mathrm{min}}^{\mathrm{G}}\) represents the minimum value of the x-coordinate in the overall point cloud data, \(\mathrm{y}_{\mathrm{min}}^{\mathrm{G}}\) refers to the minimum y-coordinate, d2 represents the size of the planar grid, and m and n are the row and column numbers corresponding to the grid where the point is located.  
**Voxel Hashing:** The 3D hashing scheme stores 2D grids in the beginning. Subsequently, in each 2D grid, new coordinates of each point are calculated during the dynamic update of voxels with regard to hashing voxels, as follows:  
\[\left\{\begin{array}{l}\mathrm{r}=\left(\mathrm{y}-\mathrm{y}_{\mathrm{min}}^ {\mathrm{L}}\right)/\mathrm{d}3\\ \mathrm{c}=\left(\mathrm{x}-\mathrm{x}_{\