Feature-based terrain model simplification

Abstract

Terrain models play an important role in many scientific disciplines. They are widely used in cartography, urban planning, computer simulations and many more. A common problem with terrain models is the amount of data required for their representation. This fact creates the need for sophisticated simplification algorithms. Unfortunately, the typical simplification techniques expose various limitations. Grid based techniques usually pay little attention to the terrain curvature, contour line simplification methods simply treat curves as separate entities, not as a part of a whole and triangulated irregular network (TIN) based methods rely on a computation of an error measure between a sample point and its neighbours. The work presented in this study aims to design an algorithm to simplify terrain models by the removal of less important surface features. A technique is developed which extends the terrain simplification to higher level features, rather than a single sample, contour line or a grid column. The medial axis or the skeleton has been chosen, as a tool for feature selection. The simplification algorithm proposed in this work starts from the constructing of the skeleton of an input model. The skeleton is utilized to detect the surface features as well as to indirectly compute their importance values. This is followed by the removal of all features smaller than some previously selected thresholds. It is pointed out that construction of a 3D skeleton is expensive in terms of both computing time and memory used. As an alternative an approximation of the 3D skeleton is proposed. The approximation is made by skeletons of 2D slices of a terrain model. These slices are in fact the equivalent of contour line terrain models. The 3D skeleton approximation does not serve as a precise geometric equivalent of a 3D skeleton but rather as an aid to describe relationships between skeletons of slices of a 3D feature. The removal of a three dimensional feature is performed by the coordinated retraction of the 2D skeletons. The definition of a hierarchy of a two dimensional skeleton is performed by computing boundary potential functions, but the area of a feature is also taken into consideration as the simplification parameter. The results of the proposed surface simplification method are analyzed on three levels: skeleton-based simplification approach, reduction of the simplification problem from 3D to 2D and simplification of 2D layers of a model. The first level the results are analyzed by using the drainage system as obtained from the source and the simplified version of a terrain model. This level shows superiority of the skeleton method over the reference (manual generalization supported by the Douglas-Peucker algorithm). The correctness of the reduction of the problem from 3D to 2D is shown by testing elevation errors occuring between source and simplified models. The 2D layer simplification level show some further interesting properties of the method. Three algorithms presented in this work: stable vertex method, and approximation by Bezier splines show other properties, the utilization of which is dependent on the user's needs. Experiments show that these algorithms perform well for real data. The contour lines, however, must be properly represented in a triangulation.