Fast plane detection and polygonalization in noisy 3D range images

A fast but nevertheless accurate approach for surface extraction from noisy 3D point clouds is presented. It consists of two parts, namely a plane fitting and a polygonalization step. Both exploit the sequential nature of 3D data acquisition on mobile robots in form of range images. For the plane fitting, this is used to revise the standard mathematical formulation to an incremental version, which allows a linear computation. For the polygonalization, the neighborhood relation in range images is exploited. Experiments are presented using a time-of-flight range camera in form of a Swissranger SR-3000. Results include lab scenes as well as data from two runs of the rescue robot league at the RoboCup German Open 2007 with 1,414, respectively 2,343 sensor snapshots. The 36ldr10⁶, respectively 59ldr10⁶ points from the two point clouds are reduced to about 14ldr10³, respectively 23ldr10³ planes with only about 0.2 sec of total computation time per snapshot while the robot moves along. Uncertainty analysis of the computed plane parameters is presented as well.