Flood Fill
A plane segmentation algorithm for lidar point clouds designed for floor plan matching.
Abstract
The plane segmentation of point clouds is intimately connected to the utilization of a
multitude of depth sensors, such as depth cameras and LiDARs, which are widely applied
in computer vision and robotics. However, conventional point cloud plane segmentation
methods are mainly aimed at dense point clouds obtained from depth cameras, which are
not entirely appropriate for sparse point clouds obtained from LiDARs. On the other
hand, since LiDARs are usually used in mobile robots and autonomous driving scenarios,
there is an intense demand for real-time algorithms for these tasks. A qualified algorithm
must achieve a computation speed of dozens of frames per second, which is sufficiently
practical. Hence, exploring an algorithm that balances accuracy and speed in LiDAR
point cloud plane segmentation is of great significance. Based on method research, we
referenced DDPFF’s flood-fill algorithm and applied it to the plane segmentation task
of LiDAR point clouds. We further proposed methods such as range function and normal
adaptation for the unique features of LiDAR point clouds, including sparsity and cloud
density inconsistency. These methods enable the flood-fill algorithm to expand the plane
according to a variable threshold, thus increasing the robustness of the plane segmentation
result. By introducing efficient flood-fill-based LiDAR point cloud plane segmentation,
we were able to resolve the problem of localization failure in complex or cluttered environments encountered in our previous localization work FP-Loc. Furthermore, it can
handle even more common and complicated situations encountered in indoor environments. We evaluated our algorithm using the publicly available dataset VECtor, and
the experimental results have shown that our algorithm can operate in real-time with minimal time cost while maintaining its accuracy in LiDAR point clouds. Additionally, it
can be easily embedded as modules into existing SLAM-related localization work with
positive prospects.
Code