Unmanned ground vehicle (UGV) technology benefits for intelligent transportation and automatic digital map reconstruction in smart city domain. In most urban areas, the planes are usually existed in buildings and infrastructures, which consist of massive 3D points detected by the sensors on UGV. This paper aims to study planar detection from 3D point clouds and represent the planes using a mesh instead of plenty of points in 3D reconstruction. A fast planar detection method using GPU-based Random Sample Consensus (RANSAC) is developed to estimate the planar parameters existed in surrounding environment. The sensed 3D point clouds are segmented into several planes. Each planar surface is reconstructed and rendered using only four vertices, so that the memory usage is reduced in 3D reconstruction. For improving the time efficiency in plane recognition process, GPU is utilized to fasten RANSAC algorithm using CUDA parallel programming technology.
requires massive iterations in plane detection. In order to improve the accuracy and speed performance of environment perception of UGV, this paper proposed a fast planner detection method in LiDAR point clouds using GPU-based RANSAC algorithm. In our method, raw 3D point cloud is segmented into several sub-spaces to detect planes. To recognize plane in individual sub-spaces, a preset plane model is initialized to record the point count of which suitable to the plane model. After test several different plane model, the plane model of the most registered points is considered as the plane in the sub-space. Thus, the optimum plane model in each sub-space is computed in parallel by a CUDA development kit. The remainder of this paper is organized as follows, Section 2 overviews related work. Section 3 discusses the method of plane detection. Section 4 describes the experiments using the proposed method. Section 5 concludes this paper. 2
In mobile robot and intelligent vehicle domain, plane recognition methods based on 3D point clouds are widely researched in 3D environment sensing technology. Ishida et al. [5] detected planes from depth pixels by using a 3D Hough transform algorithm in unknown environment. In the method, the Hough space was divided into several parts to extract plane parameters through several votes and iterations. Hulik et al. [4] utilized a 3D Hough transform to extract large planes from point cloud collected from LiDAR sensor. In order to preserve the accuracy of the plane detection process, a Gauss smoothing function was used to eliminate the noise distribution in the Hough space after executing Hough transform on LiDAR points. To increase the speed performance of updating process in Hough space, a caching technique was applied in point registration. Compared with 2D Hough transform algorithm, 3D Hough transform utilized more time consumption in plane detection process. The detection precision of plane parameters is not accurate enough to support the decision making of UGV so that 3D Hough transform always utilized in indoor environment. In 3D environment scene, the RANSAC algorithm is widely researched to extract parameters from LiDAR point cloud. Schnabel et al. [12] utilized tradition RANSAC algorithm to compute plane parameters from three random and dispersed points. Through several iterations, a goal function was utilized to search the optimum plane model with the most fitting counts of the remaining points. To improve operational efficiency of RANSAC, Choi et al. [1] reduced unknown number of plane equation model. Wang et al. [15] proposed a preprocessing model based on bucketing mode. Nevertheless, RANSAC algorithm is hard to achieve fast speed due to its iterative computation characteristics. CPU is well suited for complex and intensive computing tasks. However, it has been difficult to improve the computational efficiency of the RANSAC algorithm implemented on large-scale datasets. In the past few years, GPU have transformed from a graphics-rendering device to a high-performance computing device that solves the parallelism problems [8,2]. Data-intensive computing tasks perform more efficiently on large-scale datasets using GPU. Utilize the inherent parallelism of RANSAC and the high computational efficiency of the GPU, this paper proposes a fast planner detection method in LiDAR point clouds. 3
To estimate the plane parameters from the raw 3D point cloud accurately, a plane detection framework is proposed as shown in Figure 1. The framework mainly is consist of three procedures, including the segmentation of 3D point cloud, mapping the point cloud to the GPU, plane detection and plane fitting. 3.1
It is difficult to extract plane fromLiDAR points cloud because the distribution characters of uneven
density and discontinuous spatial. Firstly, raw 3D point clouds sensed from 3D space are divided to some
subspaces. The 3D point count existed in each subspace is assumed asDnumi. Dnummax is the maximum
count in all 3D point clouds. The changing rate of 3D point cloud density between adjacent spaces is
formulated using the equation (
Framework of the proposed planner detection method in LiDAR point
If the difference between the normal vectors of two planes is less than threshold , expressed as equation
(
arcos (ni; nj ) Page 30 of 40
Dden_changei =
3; Hi [ Hi+1
The entire space of 3D point cloud is divided into a few subspaces Hi by maximum and minimum of z-axis. After establishing the statistical histogram of change rate in point cloud density, 3D point clouds are merged if changing rate of 3D point cloud density Dden_changei is lower than a threshold з. 3.2
After the 3D point clouds are segmented into several subspaces and registered into the terrain model on
the CPU, each data in spatial is processed independently. Because GPU has many blocks and there are
many threads in each block. In order to improve computing efficiency of algorithm, the registered 3D point
cloud datasets are copied to the GPU memory, which are able to be executed in parallel. The 3D points in
each subspace Pi are executed four procedures as follow:
1. Plane L’ is constructed by three point selected from Pi, the normal vector of the plane L’ is n’.
2. Angle i is calculated as the angle between n’ and the other points in Pi. Score SL’ of plane L’ records
the number of angles less than a threshold.
3. After repeating 1),2) for T times, plane L’ with the highest score is chosen. T is formulated using the
equation (
T =
log (1
log 1
(
is the proportion outside the
(
In the other plane fitting constraint, centroid-centroid vector Mij is the line vector calculated from the
plane Li centroid to the plane Lj centroid. When the angles between centroid-centroid vector and the
planes’ normal vectors ni or nj are approximately vertical to each other, the two planes Li and Lj are
considered as belong to a same plane. Thus, if the angles between the two vectors less than a threshold '
after subtracting 90-degrees, the plane fitting constraint is satisfied as shown in equation (
The variable ' is nearly to zero. 4
In this section, we analyze the performance of the proposed plane detection method from LiDAR points. The experiments were implemented on a 3.20 GHz Intel® Core™ Quad CPU computer with a GeForce GT 770 graphics card, 4 GB RAM. The applied HDL-32E Velodyne LiDAR had capability to sense 32 × 12 3D points in a packet per 560.96 ms. In our experiment, the 3D point clouds were built using DirectX software development kits. Figure 2 presents the raw datasets of 180 × 32 × 12 points tested by a stationary LiDAR. In the experiment, all the sensed 3D points were divided into 20 groups according to their y coordinates. The changing rate of 3D point cloud in density histogram is shown in Figure 3. Then, using a threshold to merge point cloud based on the histogram, some redundant points were removed as shown in Figure 4. Finally, a series of initial plane models was calculated after initialization detection. In Figure 5, the optimum plane was detected after plane fitting. Page 31 of 40 Page 32 of 40 not perform in real time. Final detection results of CPU-optimized and GPU plane detection methods were shown as in Figure 6 and Figure 7. It was obvious that our proposed method was implemented fast and accurately.
To contribute efficient planar detection method for urban terrain modeling, this paper demonstrated a GPU-based RANSAC method in LiDAR point clouds. The point segmentation and plane fitting processes reduced iteration times. Using GPU programming technology, the improved RANSAC method performed planar detection much faster than CPU-based method. CPU executed the complex computation processes, while GPU executed the interactive and repeated processes of low computation complexity. This way, the proposed method combined the advantages of CPU and GPU. The proposed method was able to reduce the memory consumption for the urban terrain reconstruction for smart city modeling and intelligent transportation. In the future, we will apply this plane detection method in the 3D terrain modeling on UGV.
ACKNOWLEDGMENTS This research was supported by the National Natural Science Foundation of China (61503005), by NCUT “The Belt and Road” Talent Training Base Project, by NCUT “Yuxiu” Project, by Beijing Natural Science Foundation (4162022), and by High Innovation Program of Beijing (2015000026833ZK04). Page 33 of 40 Page 34 of 40