Aggregation in Map Generalization by Combinatorial Optimization
Leibniz Universität Hannover, Germany, Dissertation, (2009)Abstract
This thesis presents a new method for aggregating area objects in topographic databases. Aggregation is an important sub-problem of automatic generalization, which in cartography and geoinformatics means to derive representations of higher abstraction and smaller scale from given datasets. The developed method aims to create results of maximum quality and to ensure standards like minimal dimensions that are given with database specifications. Basically, two quality criteria are considered relevant: (1) Large-scale objects are to be represented by small-scale objects of semantically similar classes - this aim is formalized by defining a semantic distance between classes. (2) Areas in the smaller scale need to have a geometrically simple, compact shape. For the first time, this task is consequently formulated as an optimization problem and solved by applying combinatorial optimization techniques. In a simplified form, the problem can be stated as follows: Given a planar map with areas of different classes and a minimal allowed area size theta for the target scale, combine the areas into contiguous regions and define a new class for each region, such that each region has size at least theta and the area covered by objects whose classes change is minimized. It will be proven that this simplified problem is already NP-hard. Therefore, it is unlikely that an exact polynomial-time algorithm exists for its solution. This motivates an approach to the problem that is based on mixed-integer linear programming and heuristics. The proposed methods allow semantic class distances and different compactness measures to be considered. These criteria are incorporated into the cost function that is minimized. Furthermore, it is possible to define size thresholds for different classes, in order to preserve objects of high priority. Due to the high complexity of the problem, the exact solution cannot be obtained for large problem instances. Nevertheless, for small instances, the approach allows the results of heuristics to be compared with optimal solutions. This enables the performance of heuristic methods to be assessed with respect to the quality of the result. The development of the presented heuristics is motivated by two aims: Firstly, large problem instances, for example, national topographic databases, need to be generalized. Secondly, local updates need to be propagated into a previously derived small-scale map without processing the complete dataset again. In addition to heuristics that eliminate certain variables in the mixed-integer programs, a heuristic is proposed that decomposes a problem instance into smaller, independent instances. With this approach both aims are achieved. Furthermore, a generalization workflow is presented that, in addition to the aggregation method, comprises methods for area collapse and line simplification. In order to prove the applicability of the proposed method in practice, it was applied to a dataset of the official German topographic database ATKIS. A dataset of the ATKIS DLM 50 was processed, which contains similar amounts of detail as the digital topographic map at scale 1:50 000 (DTK 50). The minimal allowed size theta was defined according to existing specifications of the ATKIS DLM 250. A dataset of 22 km times 22 km with 5537 areas (a map sheet of the DTK 50) was aggregated in 82 minutes. Compared to an existing iterative approach (the so-called region-growing), the new method resulted in 20% less class change and 2% less cost for non-compact shapes. The developed method has several advantages, in particular, it offers results of high semantic accuracy. Furthermore, the proposed optimization method is deterministic and allows (hard) constraints to be handled. These are advantages compared to existing optimization methods for map generalization, which are often based on iterative meta-heuristics like simulated annealing. How to adapt the developed approach to other generalization tasks - in particular to building simplification - is discussed as a question for future research.