Traversable ground detection and object segmentation algorithm using graph representation of 3d lidar scans for autonomous navigation on rough terrain

Abstract

Perception of traversable areas and objects of interest from a 3D point cloud is one of the critical tasks in autonomous navigation. In particular, a ground vehicle needs to look for traversable terrains that are explorable by wheels. Then, to make safe navigation decisions, the segmentation of objects positioned on those terrain has to be followed up. However, under/over-segmentation can negatively influence such navigation decisions. To that end, we propose TRAVEL, which performs traversable ground detection and object clustering simultaneously using the graph representation of a 3D point cloud. To segment the traversable ground, a point cloud is encoded into Tri-Grid Field, which treats each tri-grid as a node and forms a graph structure. Then the traversable terrains are searched and redefined by examining local convexity and concavity of edges that connect nodes. On the other hand, our above-ground object segmentation employs a graph structure by representing a group of horizontally neighboring 3D points as a node and vertical/horizontal relationship between nodes as an edge. Fully leveraging the proposed graph structures, the proposed algorithm ensures real-time operation and mitigates under-segmentation and over-segmentation. Through experiments using simulations, urban scenes, and our own datasets, we have demonstrated that the proposed segmentation algorithm, TRAVEL, outperforms other state-of-the-art methods in terms of the conventional metrics and under-/over-segmentation entropies.