Fast Dual Decomposition based Mesh-Graph Clustering for Point Clouds

Robust object detection is one of the key tasks for autonomous vehicles. Clustering is the fundamental step for extracting objects from 3D point clouds. We propose a fast and efficient algorithm to cluster 3D point clouds provided by modern LiDAR sensors. The clustering is based on graph theory and local contextual information. Our method encodes weights of graph edges by adopting perceptual laws based on the intrinsic sensor beam pattern. This significantly increases the robustness of the segmentation process. It allows a point-wise clustering even at challenging distances and viewing angles as well as occlusions. For the sake of speed, the clustering pipeline is separated into vertical and horizontal clustering. Therefore, we split the graph into multiple vertical and horizontal line graphs which are processed in parallel. Finally, the partitioned results are merged into coherent objects using a breadth-first search algorithm. Experiments in different suburban datasets have demonstrated that our proposed method outperforms other state of the art methods, especially in complex scenes. A quantitative comparison between our method and other representative clustering methods proves the efficiency and the effectiveness of our work.