# Fast Planar Detection System Using a GPU-Based 3D Hough Transform for LiDAR Point Clouds
## 2 Related Works
### Parameter Spaces Methods  
The Hough transform is a classic plane detection algorithm based on parameter space, in which optimal plane parameters are determined by a generated Hough space. Unlike the RANSAC algorithm, the global maximum of point counts can be gained after traversing all of the grid cells in Hough space.  
Thus, the Hough transform supports more stable plane information than RANSAC when processing non-ideal point cloud datasets. However, the standard Hough transform remains sensitive to noise points and occlusions, wherein the plane detection accuracy considerably depends on the parameters' resolution of the angle and radius. To improve the anti-interference performance, [PERSON] et al. [23] utilised a Gaussian kernel to generate an accumulator map in the Hough space rather than directly computing the point counts. In addition, a quad tree was also used in their proposed method to group adjacent points as a down-sample procedure during pre-process.  
To locate a more reasonable peak from the accumulator map, smoothing and gradient climbing steps were added during the peak searching process to obtain the required plane surface parameters. In the algorithm proposed by [PERSON] et al. [6], coplanar sample points were firstly clustered by a subdivision procedure to ensure that a kernel-based Hough transform was performed on clusters instead of individual points. [PERSON] et al. [24] applied a regularisation method on the Hough parameter space to correct the computation error caused by different resolutions in horizontal and vertical directions. Using this regularisation method, the line detection results from the point cloud were improved and overcame the problem that more than one lines were extracted from dense points of cylindrical distribution. [PERSON] et al. [25] proposed another point cloud down-sampling method to modify the time efficiency of plane parameter computing in the Hough transform algorithm. Using an adaptive resolution model in the point cloud space, a low-level mode was applied at an initial density to gain rough plane parameters. Before employing a high-level mode to calculate precise parameters, a density mask was developed to filter several points in the intensive area to reduce point densities. In the down-sampled point cloud space, accurate plane parameters were gained with robust performance and rapid speed. Similar to the gradient climbing step in the peak searching process, a probabilistic clustering method was employed by [PERSON] et al. [26] to improve the searching efficiency rate. Moreover, a Gaussian mixture regression model was added in the method to correct distorted planes caused by the environment sensor prior to outlier trimming process.  
The most significant advantage of parameter space methods is the stable plane detecting results without random interference. Besides, if the resolution of the Hough space and point counts were fixed, the time complexity of plane detection in every frame is also stable. Our previous work [27] adopted RANSAC algorithm to detect plane surfaces in an outdoor environment using parallel computing technology. We also applied a 2D Hough transform algorithm to detect indoor planar surface in work [28]. Due to the characteristics of LiDAR point cloud, the connectivity information is absent among the unstructured and unorganised points. To extract plane surfaces from a large number of point clouds, parameter space methods have better computation efficiency than the clustering methods. In this paper, we propose a GPU-based 3 DHT algorithm for fast planar detection in the large-scale LiDAR point clouds of outdoor environment.