In this paper range image segmentation is studied in the framework of maximum a posteriori estimation and Markov random field modeling. A novel range image segmentation model is proposed. The model will serve as an evaluator for a small number of segmentation candidates obtained through a fast edge detection algorithm. A local method is employed to search for the optimal segmentation firom the candidates. Experimental results show that such combination of heuristics and model-based evaluation leads to a fast and accurate segmentation.