Learning to Optimally Segment Point Clouds

Peiyun Hu1 David Held1* Deva Ramanan1,2*
1Robotics Institute, Carnegie Mellon University
2Argo AI

teaser teaser
Our proposed algorithm takes a pre-processed LiDAR point cloud with background removed (left) and produces a class-agnostic instance-level segmentation over all foreground points (right). For visualization, we use a different color for each segment and plot an extruded polygon to show the spatial extent.
thumbnail PDF / BibTeX


We focus on the problem of class-agnostic instance segmentation of LiDAR point clouds. We propose an approach that combines graph-theoretic search with data-driven learning: it searches over a set of candidate segmentations and returns one where individual segments score well according to a data-driven point-based model of “objectness”. We prove that if we score a segmentation by the worst objectness among its individual segments, there is an efficient algorithm that finds the optimal worst-case segmentation among an exponentially large number of candidate segmentations. We also present an efficient algorithm for the average-case. For evaluation, we repurpose KITTI 3D detection as a segmentation benchmark and empirically demonstrate that our algorithms significantly outperform past bottom-up segmentation approaches and top-down object-based algorithms on segmenting point clouds.

Illustration of the main ideas

Qualitative results



We've released our code at https://github.com/peiyunh/opcseg.


This work was supported by the CMU Argo AI Center for Autonomous Vehicle Research.