Accelerated patch-based planar clustering of noisy range images in indoor environments for robot mapping

This paper introduces a methodology to cluster noisy range images into planar regions acquired in indoor environments. The noisy range images are segmented based on a Gaussian similarity metric, which compares the geometric attributes that satisfy the coplanarity conditions. The algorithm is designed to cluster coplanar noisy range data by means of patch-based sampling from range images. We discuss the advantages of patch-based clustering over point-based clustering of noisy range images that eliminates computational redundancy to accelerate the clustering process while keeping the segmentation error to a minimum. The final output of the algorithm is a set of polygons, where each polygon is defined by a set of boundary points that replaces large number of coplanar data points in a given planar region. The 3D range image is acquired by a rotating 2D range scanner and stored in a 2D array. Each element in the array is explicitly stored as the range distance; the indices of the array implicitly retain neighborhood and angular information. The array is grouped into mutually-exclusive patches of size (k×k)(k×k) and the Hessian plane parameters are computed for each patch. We propose a graph-search algorithm that compares the plane parameters of neighboring patches by searching breadth-wise and clusters the coplanar patches into respective planes. We compare the proposed Patch-based Plane Clustering (PPC) algorithm with the point-based Region Growing (RG) algorithm and the RANSAC plane segmentation method to analyze the performance of each of the algorithms in terms of speed and accuracy. Experimental results indicate that the PPC algorithm shows a significant improvement in computational speed when compared with the state-of-the-art segmentation algorithms while maintaining a high accuracy in segmenting noisy range images.