Feature-based terrain model simplification

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 surface features. A technique is developed which extends the terrain simplification to higher level features, rather than a single sample, contour line or a column of a grid. The medial axis or the skeleton has been chosen, as a tool for feature selection. The scope of the research covers applicability of skeletonization as well as skeleton regularization techniques for the terrain simplification. Extraction of the skeleton from the scattered points is based on the Voronoi diagram and the Delaunay triangulation.; 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. On 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 latter level shows superiority of the skeleton method over the reference (manual generalization supported by the Douglas-Peucker algorithm). The branches of drainage system, as obtained from the skeleton based method, also more faithfully represent the drainage system obtained from the source model. 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 method designed in this work does affect the elevation in the areas where surface features occur and causes very little effect in the featureless parts of the test model. The 2D layer simplification level show some further interesting properties of the method. Three algorithms presented in this work: stable vertex method, average vertex method and approximation by Bezier splines show other properties, the utilization of which is dependent on the user's needs. The stable vertex method is able to dramatically reduce the number of vertices needed for a shape representation, whilst stilt preserving the most important features. Additionally this method does...