Academic Journal of Science and Technology ISSN: 2771-3032 | Vol. 8, No. 1, 2023 238 Ground Point Detection Method Based on Grid Division and Plane Fitting Chao He, Yuanhong Dan School of Vehicle Engineering Chongqing University of Technology, Chongqing 400054, China Abstract: Ground point detection is an important part of unmanned driving technology, and the detection results will affect the subsequent tasks. Aiming at the problem of under-segmentation and mis-segmentation of lidar ground point segmentation in unstructured scenes, a ground point recognition method based on grid division is proposed. This method first uses the constraint conditions to preprocess and extract the ROI region; secondly, the point cloud is divided by the method of grid division; finally, the plane fitting method is used to realize the ground point recognition. Based on the structured data set KITTI and the unstructured data set ORFD data set, this paper compares them with RANSAC, LF and HDL algorithms. The experimental results show that the algorithm in this paper can segment the ground points well, which is superior to the three algorithms compared in the evaluation index, and can detect the ground points quickly and accurately. Keywords: Unmanned driving; Ground point detection; Grid division; Plane fitting. 1. Introduction Perception, localization and planning are the three key technologies of autonomous mobile robots. Reliable roads are a prerequisite for many autonomous tasks, such as path planning and decision-making. That is, in any environment, the road that the robot can pass can be accurately and quickly identified, not just limited to structured roads. Most of the existing research focuses on structured roads with obvious characteristics, and there are relatively few studies on unstructured roads [ 1 ]. For structured roads, the passable area mainly refers to conventional roads, such as urban roads and expressways, while for unstructured roads, the concept of passable area is relatively vague. Driverless cars need to pass through harsh environments such as sand, mud, desert, and grassland, which is a great challenge for driverless cars because the unstructured road environment is complex and diverse. For example, the tall grass and dwarf grass in the wild environment are very different in terms of traffic. The planning and control of the unmanned platform depends on the perception of the driving environment, which is mainly realized by different sensors installed around the platform. The salient feature of the unstructured scene is that the obstacles are complex and changeable, and the road height of the driving area is different. Therefore, the requirements for the sensor are more stringent. In addition to obtaining the basic information of the surrounding environment, it is also necessary to obtain the size and three-dimensional information of the obstacles, and it is not affected by the environment, and can operate stably in a complex environment. In the face of very complex unstructured environment, it is an urgent problem to detect ground points quickly, accurately and reliably. The three-dimensional laser radar can accurately perceive the environmental information around the robot. It has the characteristics of high ranging accuracy, wide range and not easy to be disturbed. It is an environmental sensing sensor commonly used in many unmanned self-service devices. The organizational structure of this paper is as follows: The first part reviews the previous research on ground detection. The second part introduces the method of this paper. The third and fourth parts give the specific implementation of the method and the experimental results. Finally, the fifth part gives the research results of this paper. 2. Related Work At present, domestic and foreign scholars ' segmentation algorithms for ground point clouds are mainly divided into three categories, based on plane fitting and grid map. The random sample consensus ( RANSAC ) algorithm based on plane fitting [ 3 ] determines whether it is a ground point by constructing a ground model and calculating the distance between the relevant points and the constructed ground model. On the basis of RANSAC, Li Xi et al. [ 4 ] added the least squares method ( TLS ) to remove the outliers, and then used the TLS algorithm to fit the effective point cloud. The disadvantage is that the fitting model takes a relatively long time and the accuracy is not high, which is difficult to meet the needs of unmanned driving. Zhang, W [ 5 ] et al.used a cloth simulation algorithm to fit a cloth that conforms to the ground shape under the influence of the gravity and internal force of the cloth itself through the physical characteristics of the cloth. The disadvantage of the algorithm is that the internal force of the particles between the cloth and the parameter threshold need to be determined artificially, and it is difficult to fit the ideal ground for the extreme ground elevation mutation. The segmentation algorithm based on the grid map is mainly to establish a 3D grid, divide each point into the corresponding grid, and use the height difference, maximum or minimum value to determine whether the grid is a ground grid. Xu Guoyan [ 6 ] and Wang Xiao [ 7 ] divided the point cloud into X-Y planes and used the height difference to determine. M. Himmelsbach [ 8 ] and Zhang et al. [ 9 ] divided point clouds into polar coordinates. F. Moosmann et al. [ 10 ] used the height change threshold of the point cloud on the Z-axis to segment. The threshold based on the grid and plane fitting method cannot be dynamically adjusted, and the accuracy is not high enough to meet the requirements of irregular roads ( unstructured ). 239 3. Method Overview The schematic diagram of the method proposed in this paper is shown in Figure 1, which mainly includes 6 parts: original point cloud, ROI extraction, grid division, plane fitting, convolution filtering, and output point cloud. Raw point cloud Correction and Denoising G rid division Fitting the ground Segmented result ground no ground Figure 1. Ground point recognition diagram The input data of the algorithm is 3D laser point cloud data. Since the number of point clouds in a frame is usually more than one hundred thousand points and contains a large number of noise points, after ROI extraction, it is divided into ground points and non-ground points after grid division, plane fitting and convolution filtering. 3.1. ROI Extraction Aiming at the environment of unmanned vehicles in the road scene, the region of interest (ROI) is extracted with LiDAR as the center. Since only part of the left and right parts of the vehicle is in line with the vehicle 's exerciseable area, the area with a long distance in the front and rear direction has no effect on the current position of the vehicle. The point cloud and noise of the left and right parts of the vehicle can be removed. Considering the real-time and accuracy of the segmentation algorithm, the range of 50 m before and after the vehicle and 25 m left and right is selected as the region of interest. In an unstructured environment, due to the unevenness of the road surface, the vehicle will inevitably bump during travel. The lidar will also affect the detected point cloud with the bump of the vehicle. Therefore, the current point cloud is corrected according to the current attitude of the vehicle. 3.2. Grid Division In the actual scene, the ground cannot be flat, and there will be unevenness. The point clouds in different directions are not in the same plane to a large extent. Due to the inconsistent height or the existence of occlusion, distance and other factors, the use of a single plane model fitting has great limitations, and it is difficult to segment the correct ground points. Therefore, this paper proposes a grid division method based on the emission angle to fit point clouds in different directions. Specifically, according to the emission angle of the current point cloud relative to the lidar center, which grid area the point cloud belongs to is determined. By dividing the π‘₯ 𝑦 plane range into a circle with a radius of the y axis, and dividing the π‘₯ 𝑦 plane into 𝑀 fan-shaped regions with a size of π›₯π‘Ž, as shown in the following diagram: 𝑀 (1) Where 𝑆 is the number of the 𝑖 region, and 0 𝑖 𝑀, π›₯π‘Ž is the size of each sector. For any point 𝑝 , the calculation method of the region number 𝑑 in the fan-shaped region is: 𝑑 , , , (2) Through multiple experiments on different road scenes in the data set, the grid size π›₯π‘Ž of the final experiment is 10o according to the effect of segmentation. 3.3. Plane Fitting Plane fitting generally refers to the use of mathematical models to fit a ground model. In a three-dimensional point cloud, the ground point is usually a point with a small height difference from the ground. It is difficult to fit the correct ground model by random plane fitting. In order to accurately fit the ground, this paper uses the ground seed point to fit the current ground model. For all point clouds in the fan-shaped region 𝑆 , a set is formed. The point clouds in the set are used to estimate the characteristics of the ground area in the region, and are sorted according to the height value of the point cloud in the grid. According to experience, the lower the height of the point cloud is most likely to be the ground point. Therefore, 𝑁 points with the lowest height are selected as seed points in the ordered point cloud, and the average height 𝐻 of these seed points is calculated. The point cloud below 𝐻 π‘‘β„Ž is selected as the candidate point of the ground, and π‘‘β„Ž is the height from the ground threshold. 𝐻 βˆ‘ 𝑧 , 𝑖 ∈ 1, π‘š (3) In order to avoid the situation that the grid is all obstacle points, resulting in the local threshold does not conform to the real situation, the global threshold 𝐻 is introduced for further restriction, and the smallest of the two thresholds is selected as the final threshold of the grid. All points in the grid that are less than the final threshold is added to the seed point set, and the current ground model is fitted according to the points in the seed point set. The plane model uses a linear model: π‘Žπ‘₯ 𝑏𝑦 𝑐𝑧 𝑑 0 (4) 𝑛 𝑋 𝑑 (5) 240 where, 𝑋 π‘₯, 𝑦, 𝑧 represents the mean of the seed points, and 𝑛 π‘Ž, 𝑏, 𝑐 represents the normal vector of the estimated ground model. The π‘π‘œπ‘£ ∈ 𝑅 is calculated by the covariance matrix 𝑛 of the seed point set. Due to the high ranking of the point clouds in the grid, it is ensured that the ground model estimated by the selected seed points will not differ greatly from the actual ground model. 4. Data Set In order to verify the effectiveness of the algorithm in this paper, the structured data set and the unstructured data set are verified respectively. The structured data set adopts 𝐾𝐼𝑇𝑇𝐼 data set, and the unstructured data set adopts 𝑂𝑅𝐹𝐷 data set. The 𝐾𝐼𝑇𝑇𝐼 data set contains different scenes under urban roads, and some point cloud data in 00,04 and 06 sequences are selected for experiments. The 𝑂𝑅𝐹𝐷 data set includes scenes such as grassland, woodland, farmland and rural roads in the cross-country environment. The representative 10 frames of data in each scene are selected for experiments. In the experiment, due to the different installation positions of the lidar, the point cloud in the too high area must belong to the obstacle point. At the same time, in order to avoid the interference of the points in the car 's own area, according to the prior knowledge, the point cloud can be cropped and the interference of noise points can be removed to ensure the effectiveness of the algorithm. Since the data of the 𝑂𝑅𝐹𝐷 data set is not labeled, a representative scene in the data set is selected to manually label the point cloud data, and the data is divided into ground points and non-ground points. 5. Experimental Result The computer configuration of the algorithm experiment in this paper is: i7-10700 processor, system environment is Windows, call PCL1.8 point cloud library, write in C + + language, and use Cloud-Compare software to mark point cloud and visualization. 5.1. Evaluating Indicator By comparing RANSAC, LF, HDL three algorithms. According to the method in Reference [13], the effectiveness of the algorithm is evaluated from four aspects: precision rate 𝑃, recall rate 𝑅 ,𝐹 score and accuracy rate 𝐴. The calculation method of each evaluation index is as follows. 𝑃 (6) 𝐴 (7) 𝑅 (8) 𝐹 (9) In the formula, 𝑇𝑃 is the number of ground points correctly marked, 𝐹𝑃 is the number of ground points incorrectly marked, 𝑇𝑁 is the data of non-ground points correctly marked, and 𝐹𝑁 is the data of non-ground points incorrectly marked. Among them, the larger the 𝑃 and 𝑅, the more data the ground points are correctly classified, and the better the segmentation effect. Table 1. Comparison of segmentation effects of structured data sets structure scene algorithm P 𝐹 R A 00 04 06 RANSAC 0.5891 0.6384 0.7361 0.6950 LF 0.8232 0.8354 0.8832 0.8332 HDL 0.7679 0.7845 0.7952 0.7504 Our 0.8025 0.8369 0.8784 0.8451 Table 2. Comparison of segmentation effects of unstructured data sets unstructured scene algorithm P 𝐹 R A Tsukichikando green way RANSAC 0.4439 0.2865 0.2075 0.4217 LF 0.7558 0.6841 0.6557 0.8304 HDL 0.7035 0.6426 0.5913 0.8031 Our 0.7567 0.8195 0.7934 0.7943 6. Summary In this paper, robust ground point recognition experiments are carried out in different unstructured scenes. The results show that after the initial lidar point cloud is corrected and denoised and the ROI region is selected for preprocessing, some invalid point clouds are removed. A ground point recognition method based on grid division is proposed, and the segmentation results are corrected by convolution filtering. Compared with RANSAC, LF and HDL algorithms in structured data sets and unstructured data sets, the experimental results show that the proposed algorithm has strong robustness and real-time performance in different environments, and can meet the actual engineering requirements. In the subsequent research, the fusion detection of lidar and camera will be carried out to further improve the detection range and accuracy. References [1] M. Wigness, S. Eum, J. G. Rogers, D. Han and H. Kwon, "A RUGD Dataset for Autonomous Navigation and Visual Perception in Unstructured Outdoor Environments," 2019 IEEE/RSJ International Conference on Intelligent Robots and 241 Systems (IROS), Macau, China, 2019, pp. 5000-5007, doi: 10.1109/IROS40897.2019.8968283. [2] Min, C., Jiang, W., Zhao, D., Xu, J., Xiao, L., Nie, Y., & Dai, B. (2022). ORFD: A Dataset and Benchmark for Off-Road Freespace Detection. 2022 International Conference on Robotics and Automation (ICRA), 2532-2538. [3] Li, Jiang, Wang. Robust point cloud plane fitting method based on random sample consensus algorithm [J]. Surveying and Mapping Science, 2015,40 (1): 5. [4] Li Xihan Xie Xiong. Point cloud plane fitting based on RANSAC and TLS [J]. Computer Engineering and Design, 2017,38 (1): 123-126,143. [5] Zhang, W., Qi, J., Wan, P., Wang, H., Xie, D., Wang, X., & Yan, G. (2016). An Easy-to-Use Airborne LiDAR Data Filtering Method Based on Cloth Simulation. Remote Sensing, 8(6), 501. [6] Xu Guo yan, Niu Huan, Guo Chen yang, et al., Research on target recognition and tracking based on 3D laser point cloud [J]. Automotive Engineering, 2020,42 (1): 38-46. [7] Wang Xiao, Wang Jian Qiang, Li Keqiang, et al.3D point cloud fast segmentation method for intelligent vehicles [J]. Journal of Tsinghua University: Natural Science Edition, 2014 (11): 7. [8] M. Himmelsbach, F. v. Hundelshausen and H. . -J. Wuensche, "Fast segmentation of 3D point clouds for ground vehicles," 2010 IEEE Intelligent Vehicles Symposium, La Jolla, CA, USA, 2010, pp. 560-565, doi: 10.1109/IVS.2010.5548059. [9] Zhang Mingfang, Fu Rui, Guo Yingshi, et al.. Ground segmentation algorithm based on three-dimensional irregular point cloud [J].Journal of Jilin University (Engineering Edition), 2017,047 ( 005 ) : 1387-1394. [10] F. Moosmann, O. Pink and C. Stiller, "Segmentation of 3D lidar data in non-flat urban environments using a local convexity criterion," 2009 IEEE Intelligent Vehicles Symposium, Xi'an, China, 2009, pp. 215-220, doi: 10.1109/IVS.2009.5164280. [11] Feng Shaoquan, Hua Xianghong, Duan Chengwen, etc. An adaptive slope threshold ground point cloud segmentation method [J].Surveying and Mapping Science, 2021,46 (1) : 156- 161. [12] Shen Z, Liang H, Lin L, et al. Fast Ground Segmentation for 3D LiDAR Point Cloud Based on Jump-Convolution- Process[J]. Remote Sensing, 2021, 13(16): 3239. [13] RUMMELHARD L，PAIGWAR A，LAUGIER C. Ground estima⁃ tion and point cloud segmentation using spatio temporal condition⁃ al random field [C]. Proceedings of 2017 IEEE Intelligent Vehi⁃ cles Symposium, 2017: 1105-1110.