Fast Multi-Pass 3D Point Segmentation Based on a Structured Mesh Graph for Ground Vehicles

Point-cloud segmentation of 3D LiDAR scans is an important preprocessing task for autonomous vehicles in on-road and especially in off-road scenarios. Clustering point measurements with the same properties into multiple homogeneous regions is a challenging task due to an uneven sampling density and lack of explicit structural information. This paper presents a novel technique to achieve a robust and fast point-cloud segmentation using the characteristic intrinsic sensor pattern. This pattern is characterized by the mounting position of each laser diode. A structured mesh graph is created by taking the beam calibration and the chronology of incoming data packets into account. The proposed graph-based, multi-pass point segmentation algorithm compares this pattern with a flat-world model to detect discontinuities and to set label attributes such as obstacle or free space for each vertex. Furthermore, we directly detect missing measurements and therefore generate artificial vertices considering the laser beam intrinsics. Finally, a region-growing algorithm is applied in order to obtain cohesive objects. Experimental results show that we achieve a reliable overall performance and a good trade-off between segmentation quality and runtime of 15ms in rough terrain as well as suburban areas.