A FAST GIBBS SAMPLER FOR SYNTHESIZING CONSTRAINED FRACTALS

It is well known that the spatial frequency spectrum of membrane and t hin plate splines exhibit self-affine characteristics and, hence, beha ve as fractals. This behavior was exploited in generating the constrai ned fractal surfaces, which were generated by using a Gibbs sampler al gorithm in the work of Szeliski and Terzopoulos. The algorithm involve s locally perturbing a constrained spline surface with white noise unt il the spline surface reaches an equilibrium state. In this paper, we introduce a fast generalized Gibbs sampler that combines two novel tec hniques, namely, a preconditioning technique in a wavelet basis for co nstraining the splines and a perturbation scheme in which, unlike the traditional Gibbs sampler, all sites (surface nodes) that do not share a common neighbor are updated simultaneously. In addition, we demonst rate the capability to generate arbitrary order fractal surfaces witho ut resorting to blending techniques. Using this fast Gibbs sampler alg orithm, we demonstrate the synthesis of realistic terrain models from sparse elevation data.