The goal of our research in fractal terrain modeling is to build dense terrain maps that accurately represent natural surfaces. The problem is difficult in part because the familiar Euclidean geometry of regular shapes, such as surfaces of revolution, does not capture well the irregular and less structured shapes found in nature, such as a boulder field, or surf washing onto a beach.
Our research addresses two aspects of the problem: (1) estimation of the fractal dimension of a given point set as a measure of its roughness; and (2) realistic reconstruction of a natural surface from sparse, irregularly spaced data.
Estimation of Fractal Dimension
We have developed an algorithm to estimate the fractal dimension of patterns that exhibit fractional Brownian motion. The algorithm fits a line to the data points from the pattern plotted on log-log axes (log scale versus log expected change in pattern), and uses the slope to identify the fractal dimension.
We successfully demonstrated this algorithm on data acquired with a laser rangefinder viewing natural scenes. As an example, the panels below show the reflectance and range images taken of a scene including sand and rocks. The graph shows the data points taken from the region of interest (marked by a rectangle), plotted on log-log axes.
Fractal Surface Reconstruction
We have developed a new surface reconstruction method based on fractal geometry. In contrast to approaches to surface reconstruction that impose smoothness constraints, our approach to natural surface reconstruction imposes roughness constraints. The method, which follows Szeliski's approach, estimates dense surfaces from sparse data located in any configuration while preserving roughness.
Reconstructing the sparse data using regularization with the thin-plate smoothness functional as the prior model. The resulting interpolated surface is too smooth, and appears unnatural and unrealistic.
To produce a more realistic surface, instead of using the thin-plate model we employ a fractal prior model. We extend Szeliski's work by using a Gibbs Sampler temperature schedule based on the successive random addition method for synthesizing fractal patterns. These results are not too smooth; they appear natural and realistic.
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions