Abstract

In this paper, we present a stochastic algorithm by effective Markov chain Monte Carlo (MCMC) for segmenting and reconstructing 3D scenes. The ob jective is to segment a range image and its associated reffectance map into a number of surfaces which fit to various 3D surface models and have homogeneous reffectance (material) properties. In com- parison to previous work on range image segmentation, the paper makes the following contributions. Firstly, it is aimed at generic natural scenes, indoor and outdoor, which are often much complexer than most of the ex- isting experiments in the “polyhedra world”. Natural scenes require the algorithm to automatically deal with multiple types (families) of sur- face models which compete to explain the data. Secondly, it integrates the range image with the reffectance map. The latter provides material properties and is especially useful for surface of high specularity, such as glass, metal, ceramics. Thirdly, the algorithm is designed by reversible jump and difiusion Markov chain dynamics and thus achieves globally optimal solutions under the Bayesian statistical framework. Thus it real- izes the cue integration and multiple model switching. Fourthly, it adopts two techniques to improve the speed of the Markov chain search: One is a coarse-to-fine strategy and the other are data driven techniques such as edge detection and clustering. The data driven methods provide im- portant information for narrowing the search spaces in a probabilistic fashion. We apply the algorithm to two data sets and the experiments demonstrate robust and satisfactory results on both. Based on the seg- mentation results, we extend the reconstruction of surfaces behind oc- clusions to fill in the occluded parts.