On the reconstruction of height functions and terrain maps from dense range data

This paper describes a method for combining multiple, dense range images to create surface reconstructions of height functions. Height functions are a special class of three-dimensional (3-D) surfaces, where one 3-D coordinate is a function of the other two. They are relevant for application domains such as terrain modeling or two-and-half dimensional surface reconstruction. Dense range maps are produced by either a range measuring device combined with a scanning mechanism or a triangulation scheme, such as active or passive stereo. The proposed method follows from a statistical formulation that characterizes the optimal surface estimate as the one that maximizes the posterior probability conditional on the input data and prior information about the application domain. Because the domain of the reconstruction is a two-dimensional (2-D) scalar function, the optimal surface can be expressed as an image, and the variational form of that optimization produces a 2-D partial differential equation (PDE). The PDE consists of two parts: a first-order data term and a second-order smoothing term. Thus optimal surface reconstruction is formulated as the solution to a second-order, nonlinear, PDE on an image, which is related to the family of PDE-based image processing algorithms in the literature. This paper presents the theory for reconstruction and some particular aspects of the numerical implementation. It also analyzes results on both synthetic and real data sets, which show a 75%-95% reduction of the RMS sensor error.