A fast Gibbs sampler for synthesizing constrained fractals

It is well known that the spatial frequency spectra of membrane and thin-plate splines exhibit self-affine characteristics and hence behave as fractals. This behavior was exploited in generating the constrained fractal surfaces in the work of Szeliski and Terzopoulos (1989), which were generated by using a Gibbs sampler algorithm. The algorithm involves locally perturbing a constrained spline surface with white noise until the spline surface reaches an equilibrium state. In this paper, we introduce a very fast generalized Gibbs sampler that combines two novel techniques, namely a preconditioning technique in a wavelet basis for constraining 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 demonstrate the capability to generate arbitrary-order fractal surfaces without resorting to blending techniques. Using this fast Gibbs sampler algorithm, we demonstrate the synthesis of realistic terrain models from sparse elevation data.