## 5 Deep-Learning-Based Methods for Point Cloud Understanding
### Discretization-Based Methods  
Discretization methods aim to transform raw, unstructured point clouds into a grid structure for enabling 3D indexing and storing agent neighborhood information. Discretization-based approaches can be classified into two types: dense volumetric discretization and sparse permutohedral discretization. **Dense discretization** representation methods first compute the boundary box surrounding the total point cloud and then subdivide the box space into a user-defined grid. Grid instances are called voxels and can be imagined as pixels in 3D. The position of a voxel is inferred from its position to other voxels. Neighboring voxels can be retrieved by alternating the index. The point cloud is subdivided by the grid, and every voxel is checked for the occupancy of points. In the simplest case, a voxel is labeled as _true_ if occupied by points and _false_ if not. In a more sophisticated version, the algorithm calculates a density value by counting how many points lie within each cell [131]. This regular data can be fed to a 3D fully convolutional neural network for voxel-wise semantic segmentation. Finally, all points within a voxel are assigned the same predicted semantic label as the voxel. Among deep learning on 3D data, volumetric CNNs are the pioneers in applying 3D CNNs on voxelized shapes [17]. Adopted from [PERSON] et al. [5], Figure 15 represents the basic steps of voxel discretization, the prediction of class labels per voxel, and the mapping back to the unordered point cloud. The stepwise snapshots illustrate one of the main drawbacks of voxelized data representation: voxelization involves point cloud downsampling, which introduces data loss and causes classification artifacts from back-projection. An inherent limitation of this technique is its sensitivity to the granularity of the voxels. Increasing the voxel resolution can alleviate some of these issues. However, the voxel size is a complex trade-off between the level of detail (LOD) of the output, memory usage, and computational complexity. Thus, identifying an optimal voxel resolution is a challenging task [25]. Furthermore, it should be noted that dense discretization strategies with fixed-size voxel structures entail the storage of not only occupied spaces but also free or inner spaces [121]. As a result, this approach may lead to memory overhead, particularly in the case of large scenes common for construction. **Sparse discretization** representation methods decrease inefficiencies by omitting unoccupied space. Earlier approaches like OctNet [132] hierarchically partition the sparse point cloud, using a set of unbalanced octrees. Tree structures allow memory allocation and computation to focus on relevant dense voxels without sacrificing resolution. However, empty space still imposes computational and memory burdens in OctNet. [PERSON] et al. [133] proposed a novel submanifold sparse convolutional network (SSCN) based on indexing,  
Figure 15: Process steps for 3D semantic segmentation on voxelized point clouds. The steps show the voxel discretization, including point cloud downsampling, the per-voxel class prediction, and the label back-projection onto the unstructured point cloud. Prediction artifacts can be optimized to produce final results. Originally shown in [5]. which does not perform computations in empty regions, overcoming the drawback of OctNet. Based on these findings, MinkowskiNet [134] enables the direct processing of 3D sequences (e.g., LiDAR streams) with 4D spatiotemporal ConvNets with generalized sparse convolutions. Contrary to cubic discretization, approaches like LatticeNet [135] tessellate the scene space with \(d\)-dimensional permutohedral lattices into \(d\)-dimensional simplices (simplices are triangles for \(d=2\) and tetrahedrons for \(d=3\)). The vertices of the permutohedral lattice store only the simplices, which contain non-empty regions. This sparse allocation allows for efficient implementation of all typical operations in CNNs.