Fast Detection of Polygons in 3D Point Clouds from Noise-Prone Range Sensors

3D sensing and modeling is increasingly important for mobile robotics in general and safety, security and rescue robotics (SSRR) in particular. To reduce the data and to allow for efficient processing, e.g., with computational geometry algorithms, it is necessary to extract surface data from 3D point clouds delivered by range sensors. A significant amount of work on this topic exists from the computer graphics community. But the existing work relies on relatively exact point cloud data. As also shown by others, sensors suited for mobile robots are very noise-prone and standard approaches that use local processing on surface normals are doomed to fail. Hence plane fitting has been suggested as solution by the robotics community. Here, a novel approach for this problem is presented. Its main feature is that it is based on region growing and that the underlying mathematics has been re-formulated such that an incremental fit can be done, i.e., the best fit surface does not have to be completely re-computed the moment a new point is investigated in the region growing process. The worst case complexity is O(n log(n)), but as shown in experiments it tends to scale linearly with typical data. Results with real world data from a Swissranger time-of-flight camera are presented where surface polygons are always successfully extracted within about 0.3 sec.