A recursive planar feature extraction method for 3D range data segmentation

This paper presents a recursive method for extracting planar surfaces from noisy range data. The method first transforms the range image into a so-called Enhanced Range Image (ERI) that encodes the local geometric information (surface normals) and global spatial information (coordinates) of the 3D range data. The ERI is then clustered into a number of homogenous groups called Super-Pixels (SPs). By treating the SPs as the nodes a graph is constructed. A new similarity function is proposed to compute the edge weights between the nodes, base on which the graph is recursively partitioned into two segments by the Normalized Cuts (NC) method until an exit condition is met. In this work, the exit condition is that each of the resulting segments is a plane or contains only one SP. After the partitioning process, neighboring planar segments are merged based on their spatial relationships. The recursive approach eliminates the need for a pre-specified segment number that is necessary in the existing NC based image segmentation methods. The ERI coding enhances object surfaces and edges while the effect of its sensitivity to surface normals is suppressed by the similarity function that takes into account the spatial information in computing the edge weights of the graph. The proposed method can be applied to navigation of mobile robots, symbolic map-building, and range data understanding. In this work the range data are captured from a 3D Time-of-Flight imaging sensor-the Swissranger SR-3000.