# Learning to Optimally Segment Point Clouds

arXiv: https://arxiv.org/abs/1912.04976 · HTML: https://mlsanity.com/paper/1912.04976/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2019.

## Built on by (most cited first, 8 of 8)

- [Better Call SAL: Towards Learning to Segment Anything in Lidar](https://mlsanity.com/paper/2403.13129/) (2024)
- [SeMoLi: What Moves Together Belongs Together](https://mlsanity.com/paper/2402.19463/) (2024)
- [Lidar Panoptic Segmentation in an Open World](https://mlsanity.com/paper/2409.14273/) (2024)
- [LRGNet: Learnable Region Growing for Class-Agnostic Point Cloud Segmentation](https://mlsanity.com/paper/2103.09160/) (2021)
- [ElC-OIS: Ellipsoidal Clustering for Open-World Instance Segmentation on LiDAR Data](https://mlsanity.com/paper/2303.04351/) (2023)
- [Active Velocity Estimation using Light Curtains via Self-Supervised Multi-Armed Bandits](https://mlsanity.com/paper/2302.12597/) (2023)
- [Region-Transformer: Self-Attention Region Based Class-Agnostic Point Cloud Segmentation](https://mlsanity.com/paper/2403.01407/) (2024)
- [ProtoGuard-guided PROPEL: Class-Aware Prototype Enhancement and Progressive Labeling for Incremental 3D Point Cloud Segmentation](https://mlsanity.com/paper/2504.01648/) (2025)

## Abstract (arXiv)

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.