# Fast Planar Detection System Using a GPU-Based 3D Hough Transform for LiDAR Point Clouds
## 1 Introduction  
In lots of environment perception and terrain analysis applications, accurate plane surfaces are significant information that are researched by lots of scholars [1]. In an outdoor environment, building surfaces are considered as fixed obstacles that assist unmanned ground vehicles (UGVs) to realize local autonomous positioning [2; 3]. Besides, plane surface detection is a fundamental function in indoor applications for building modeling and analysis [4].  
In most UGVs' applications, light detection and ranging (LiDAR) sensors are widely utilized to collect high precision point clouds with rich and reliable environment information [5]. In addition to the advantages of LiDAR point clouds (e.g., large-scale, real-time), several disadvantages are notneglected in point cloud processing, including its unstructured, irregular and unsymmetrical spatial distribution, and uneven density. To overcome these disadvantages in plane extraction applications, some researchers proposed pre-processes to balance point cloud density and re-order registration alignment [6]. However, the pre-processes require multiple iterations before executing plane detection so that the time efficiency is affected especially in initial phase [7]. Therefore, the preprocesses of density balancing and re-order registration methods are not adopted in real-time plane surface detection applications [8].  
Neighbouring point clustering is a common pre-process method of point clouds to decrease the calculation time [9]. By clustering points with the same normal vector or other spatial characteristics, point groups are regarded as individual computing units to execute the following plane detection procedures. These clustering-based methods are only suitable for a small number of point clouds with a uniform density, whereas LiDAR point clouds collected from outdoor environment are massive and unorganised.  
Without a complex pre-process, two main plane detection algorithms are applicable for both indoor and outdoor environments, namely, random sample and consensus (RANSAC) and the three-dimensional Hough transform (3 DHT). The initial phase in the fully automatic RANSAC algorithm is totally random, resulting in significant computational and time complexity to traverse a large number of LiDAR point clouds. Because the parameter searching of the plane surface is an entirely stochastic process in the RANSAC algorithm, the Hough transform is more suitable for detecting a plane surface from point clouds when compared with RANSAC [10].  
The traditional 3 DHT algorithm transforms all 3D points that belong to a whole scene into a pre-defined Hough space buffer. The higher the resolution of the angles and point counts, the more computation time is consumed for Hough space generation. To reduce the time consumption in the traditional 3 DHT, this study proposes a parallel 3D Hough transform algorithm for planar detection from LiDAR point clouds. Using a central processing unit (CPU) and graphic processing unit (GPU) hybrid framework, the processing speed performs much faster than that using the CPU method. In (CPU-GPU) addition, for decreasing the disturbance caused by the parallel and horizontal circle distribution of LiDAR point clouds, this paper adopted a fraction-to-fraction method to transform raw points gradually from Cartesian coordinate systems into the Hough space. In this way, the performance of plane surface detection in each frame is improved with a high executing efficiency.  
The remainder of this paper is organised as follows. Section 2 surveys some popular methods on 3D plane detection. Section 3 introduces the proposed planar detection system using a GPU-based 3D Hough transform. Section 4 describes the experimental procedures and evaluates the plane detection results. Finally, Section 5 provides the conclusion of the study.