This paper presents a novel range image segmentation algorithm based on planar surface extraction. The algorithm was applied to common range image databases and was favorably compared against seven other segmentation algorithms using a popular evaluation framework. The experimental results show that, as compared to the other methods, our algorithm presents a good performance in preserving small regions and edge locations when processing noisy images. Our main contribution is an improved robust estimator, derived from the RANSAC and MSAC estimators, whose optimization process is accelerated by a genetic algorithmwith a new set of parameters and operations designed to avoid premature convergence.