Point Cloud Clustering for Obstacle Segmentation
Zhijian Qiao
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
- Choose initial samples as cluster centers.
- For each sample, calculate its distance to each center and assign it to the closest cluster.
- Recompute each center as the centroid of the samples assigned to that cluster.
- 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
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:
- Efficient Online Segmentation for Sparse 3D Laser Scans
- Fast Range Image-Based Segmentation of Sparse 3D Laser Scans for Online Operation
Code: depth_clustering.
3. Scan-line methods
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.
Paper: Voxel Cloud Connectivity Segmentation: Supervoxels for Point Clouds.
Code:
- PCL’s supervoxel clustering functions.
- ICCVW21 traditional point-cloud clustering survey.
- Supervoxel-for-3D-point-clouds.
5. Curved-voxel clustering
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.
Code: Lidar-Segementation.
Related article: 基于曲率的体素聚类的三维激光雷达点云实时鲁棒分割方法.
6. GPU-accelerated density-based clustering
Paper: G-DBSCAN: A GPU Accelerated Algorithm for Density-based Clustering.
Code: Robotics with GPU computing.