  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(m^2)$. 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.
