# A Divide-and-Merge Point Cloud Clustering Algorithm for LiDAR Panoptic Segmentation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 16 Sep 2021.

## Builds on (most cited first, 15 of 15)

- [PointPillars: Fast Encoders for Object Detection from Point Clouds](https://mlsanity.com/paper/1812.05784/) (2018)
- [KPConv: Flexible and Deformable Convolution for Point Clouds](https://mlsanity.com/paper/1904.08889/) (2019)
- [PV-RCNN: Point-Voxel Feature Set Abstraction for 3D Object Detection](https://mlsanity.com/paper/1912.13192/) (2019)
- [Panoptic Segmentation](https://mlsanity.com/paper/1801.00868/) (2018)
- [Cylindrical and Asymmetrical 3D Convolution Networks for LiDAR Segmentation](https://mlsanity.com/paper/2011.10033/) (2020)
- [Seamless Scene Segmentation](https://mlsanity.com/paper/1905.01220/) (2019)
- [Panoptic-PolarNet: Proposal-free LiDAR Point Cloud Panoptic Segmentation](https://mlsanity.com/paper/2103.14962/) (2021)
- [LiDAR-based Panoptic Segmentation via Dynamic Shifting Network](https://mlsanity.com/paper/2011.11964/) (2020)
- [EfficientLPS: Efficient LiDAR Panoptic Segmentation](https://mlsanity.com/paper/2102.08009/) (2021)
- [Panoster: End-to-end Panoptic Segmentation of LiDAR Point Clouds](https://mlsanity.com/paper/2010.15157/) (2020)
- [Point Cloud Oversegmentation with Graph-Structured Deep Metric Learning](https://mlsanity.com/paper/1904.02113/) (2019)
- [A Benchmark for LiDAR-based Panoptic Segmentation based on KITTI](https://mlsanity.com/paper/2003.02371/) (2020)
- [A Surface Geometry Model for LiDAR Depth Completion](https://mlsanity.com/paper/2104.08466/) (2021)
- [A Technical Survey and Evaluation of Traditional Point Cloud Clustering Methods for LiDAR Panoptic Segmentation](https://mlsanity.com/paper/2108.09522/) (2021)
- [Graph Based Over-Segmentation Methods for 3D Point Clouds](https://mlsanity.com/paper/1702.04114/) (2017)

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

- [Uncertainty-aware Panoptic Segmentation](https://mlsanity.com/paper/2206.14554/) (2022)
- [4D-Former: Multimodal 4D Panoptic Segmentation](https://mlsanity.com/paper/2311.01520/) (2023)
- [Lidar Panoptic Segmentation in an Open World](https://mlsanity.com/paper/2409.14273/) (2024)
- [Uncertainty-aware LiDAR Panoptic Segmentation](https://mlsanity.com/paper/2210.04472/) (2022)
- [PointGL: A Simple Global-Local Framework for Efficient Point Cloud Analysis](https://mlsanity.com/paper/2401.11650/) (2024)
- [AutoInst: Automatic Instance-Based Segmentation of LiDAR 3D Scans](https://mlsanity.com/paper/2403.16318/) (2024)
- [Is clustering enough for LiDAR instance segmentation? A state-of-the-art training-free baseline](https://mlsanity.com/paper/2503.13203/) (2025)
- [Active Velocity Estimation using Light Curtains via Self-Supervised Multi-Armed Bandits](https://mlsanity.com/paper/2302.12597/) (2023)
- [DQFormer: Towards Unified LiDAR Panoptic Segmentation with Decoupled Queries](https://mlsanity.com/paper/2408.15813/) (2024)

## Abstract (arXiv)

Clustering objects from the LiDAR point cloud is an important research problem with many applications such as autonomous driving. To meet the real-time requirement, existing research proposed to apply the connected-component-labeling (CCL) technique on LiDAR spherical range image with a heuristic condition to check if two neighbor points are connected. However, LiDAR range image is different from a binary image which has a deterministic condition to tell if two pixels belong to the same component. The heuristic condition used on the LiDAR range image only works empirically, which suggests the LiDAR clustering algorithm should be robust to potential failures of the empirical heuristic condition. To overcome this challenge, this paper proposes a divide-and-merge LiDAR clustering algorithm. This algorithm firstly conducts clustering in each evenly divided local region, then merges the local clustered small components by voting on edge point pairs. Assuming there are N LiDAR points of objects in total with m divided local regions, the time complexity of the proposed algorithm is O(N)+O(m2). A smaller m means the voting will involve more neighbor points, but the time complexity will become larger. So the m controls the trade-off between the time complexity and the clustering accuracy. A proper m helps the proposed algorithm work in real-time as well as maintain good performance. We evaluate the divide-and-merge clustering algorithm on the SemanticKITTI panoptic segmentation benchmark by cascading it with a state-of-the-art semantic segmentation model. The final performance evaluated through the leaderboard achieves the best among all published methods. The proposed algorithm is implemented with C++ and wrapped as a python function. It can be easily used with the modern deep learning framework in python.