Point Cloud Clustering for Obstacle Segmentation

Zhijian Qiao

中文版(知乎) All posts

This is an English translation of my Chinese article on Zhihu.

Problem

Given a single LiDAR point cloud, identify every object in the scene and return its points and an ID.

Some open-source approaches

1. K-means based on Euclidean distance

  1. Choose initial samples as cluster centers.
  2. For each sample, calculate its distance to each center and assign it to the closest cluster.
  3. Recompute each center as the centroid of the samples assigned to that cluster.
  4. Repeat steps 2 and 3 until a stopping condition is met, such as an iteration limit or a minimum change in error.

Code: PCL’s K-means clustering functions.

2. 2D range images

Range-image-based point cloud segmentation
Source: original article.

The approach projects the point cloud onto a range image and calculates the angles between points in adjacent rows. The original notes describe using those angles to judge whether a region is traversable.

Papers:

Code: depth_clustering.

3. Scan-line methods

Scan-line segmentation illustration
Source: original article.

Cluster points layer by layer, starting from the outermost points and working inward.

Paper: Fast Segmentation of 3D Point Clouds: A Paradigm on LiDAR Data for Autonomous Vehicle Applications.

Code: plane_fit_ground_filter.

4. Supervoxel-based clustering

Supervoxels are small regions made up of points with similar features. They are used as a preprocessing step for point-cloud segmentation. Supervoxel segmentation does not cross object boundaries, avoiding over-segmentation of the point cloud. The main steps are voxelization, construction of voxel adjacency relationships, grid-based filtering, selection of seed voxels, feature and distance measurement using FPFH, and flow-constrained supervoxel clustering.

Supervoxel clustering illustration
Source: original article.

Paper: Voxel Cloud Connectivity Segmentation: Supervoxels for Point Clouds.

Code:

  1. PCL’s supervoxel clustering functions.
  2. ICCVW21 traditional point-cloud clustering survey.
  3. Supervoxel-for-3D-point-clouds.

5. Curved-voxel clustering

Curved-voxel clustering illustration
Source: original article.

First, convert point coordinates from Cartesian to spherical coordinates and assign each point to a “curved voxel,” a voxel in the spherical coordinate system. Use a hash table to associate each voxel index with its points. During clustering, use the hash table for lookup and traverse the voxels in a way similar to BFS. The reported speed is 20 Hz on an i7-8700.

Paper: Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance.

Code: Lidar-Segementation.

Related article: 基于曲率的体素聚类的三维激光雷达点云实时鲁棒分割方法.

6. GPU-accelerated density-based clustering

GPU density-based clustering illustration
Source: original article.

Paper: G-DBSCAN: A GPU Accelerated Algorithm for Density-based Clustering.

Code: Robotics with GPU computing.

References

  1. 3D point-cloud segmentation paper summary.
  2. A technical summary and evaluation of traditional point-cloud clustering methods for LiDAR panoptic segmentation.
  3. ICCV 2021 traditional point-cloud clustering survey, with code.