Bicriteria Aggregation of Polygons via Graph Cuts

Peter Rottmann, Anne Driemel, Herman J. Haverkort, Heiko Röglin, Jan-Henrik HaunertGIScience (II) 2021 · DOI · OpenReview

TL;DR

This paper introduces a novel method for polygon aggregation in map generalization, aiming to create simplified maps by merging input polygons. The core innovation is a bicriteria optimization approach that balances minimizing the total area and total perimeter of the resulting polygons. This is efficiently solved using graph cuts, and the authors provide algorithms to find optimal solutions for all possible trade-offs between area and perimeter.

What Problem Does This Paper Address?

Map generalization is the process of creating a less detailed map from a more detailed one. A key sub-task is "aggregation," where groups of input polygons (like individual buildings) are merged into a single representative polygon (like a settlement area). Existing methods often rely on threshold-based rules, which can be cumbersome to tune and may produce undesirable results like narrow bridges between aggregated areas. This paper addresses the challenge of finding an optimal way to select which "connecting" elements (triangles in a triangulation) to use for aggregation, and how to balance two crucial, often conflicting, objectives: preserving information (minimizing added area) and ensuring legibility (minimizing the total boundary length of the output polygons).

Methods

The authors propose a method that leverages graph cuts, a powerful technique from computer vision, to solve the polygon aggregation problem.

  • Bicriteria Optimization: Instead of a single objective, they optimize for two: minimizing the total area of the output polygons and minimizing their total perimeter. These are combined into a weighted sum, controlled by a "balance factor" $\alpha \in [0,1]$.
  • Problem Formulation:
    • Problem 1: Given a set of input polygons and a balance factor $\alpha$, find a subset of polygons (including the input ones) and connecting triangles that minimizes the weighted sum of area and perimeter.
  • Problem 2: Find a set of solutions that collectively covers all possible values of $\alpha$, ensuring an optimal solution for every trade-off.
  • Graph Cut Formulation: They construct a graph where nodes represent input polygons and edges represent adjacency or potential connections. A minimum s-t cut in this graph corresponds to an optimal selection of polygons and triangles for a given $\alpha$.
  • Algorithm for Problem 1: An efficient algorithm based on computing a minimum s-t cut in the constructed graph is presented, achieving a time complexity of $O(n^2/\log n)$.
  • Algorithm for Problem 2: To address the challenge of finding solutions for all $\alpha$, they develop a recursive algorithm that efficiently computes a set of solutions. This algorithm leverages the fact that the set of optimal solutions for all $\alpha$ has a linear size ($O(n)$). They also provide an approximation version of this algorithm for cases where a perfect set is not required.

Datasets

The authors evaluated their method using:

  • Building footprints from OpenStreetMap: This data was used to test the aggregation of individual buildings into settlement areas.
  • German "Authoritative Topographic-Cartographic Information System" (ATKIS) DLM250 data: This dataset, at a scale of 1:250000, was used to compare the aggregated polygons against official settlement area polygons. Two instances were used: one with 44 buildings and larger instances corresponding to the towns of Euskirchen (16881 buildings) and the village of Ahrem (853 buildings).

Key Insights and Ideas

  • Graph Cuts for Geometric Problems: The paper demonstrates the effectiveness of graph cuts, a technique traditionally used for image segmentation, in solving complex geometric problems like polygon aggregation. This opens doors for applying similar methods to other spatial data processing tasks.
  • Balancing Area and Perimeter: The bicriteria optimization approach is crucial. Simply minimizing area can lead to overly complex shapes, while minimizing perimeter might result in too much generalization. Finding the right balance is key for creating useful maps.
  • The Pareto Frontier of Solutions: The problem of finding solutions for all $\alpha$ naturally leads to the concept of a Pareto frontier. The authors show that this frontier can be efficiently represented by a linear number of solutions, making it computationally tractable.
  • Approximation is Often Sufficient: For practical applications, an exact set of all optimal solutions might be overkill. The authors show that a small set of approximated solutions can be generated efficiently, offering a good trade-off between accuracy and computational cost.
  • Geometric Nesting of Solutions: A key theoretical insight is that as the balance factor $\alpha$ changes, the optimal solutions exhibit a "geometrically nested" structure, meaning solutions for different $\alpha$ values are related in a predictable way. This property is fundamental to their efficient recursive algorithm.

Key Results

  • Efficient Solution for Problem 1: The graph-cut based algorithm solves Problem 1 in $O(n^2/\log n)$ time.
  • Linear Number of Solutions for Problem 2: A set containing an optimal solution for every $\alpha \in [0,1]$ can be represented by $O(n)$ solutions.
  • Efficient Approximation: The recursive approximation algorithm can generate a small set of solutions (e.g., 5-6 solutions for a large instance) that are close to optimal, even for a small error tolerance ($\epsilon = 0.05$ or $\epsilon = 0.1$).
  • Practical Performance: The implemented algorithms were able to process realistic datasets, including one with 16881 buildings, within reasonable timeframes (e.g., 20.3 seconds for approximation).
  • Qualitative Similarity to Reference Data: The aggregated settlement areas produced by the method showed significant similarity to official settlement polygons, particularly in terms of area and overall shape, as assessed by metrics like IoU, Area Similarity, and Perimeter Similarity. The Hausdorff distance also indicated good agreement.

Limitations and Future Work

  • Implementation of Graph Cut Algorithm: The authors note that their implementation used a standard Push Relabel algorithm for graph cuts, resulting in an $O(n^3)$ runtime for Problem 1. They acknowledge that faster sub-quadratic algorithms exist and could improve performance.
  • Post-processing for Shape Regularity: While the aggregated shapes were similar to reference data, the reference solutions sometimes had more 90-degree angles. The authors suggest that a post-processing step using a schematization algorithm could further improve similarity.
  • Exploring More Criteria: The current work focuses on two criteria (area and perimeter). Future work could explore multi-criteria optimization with more than two objectives.
  • Relaxed Aggregation Requirements: The current method requires all input polygons to be included in the output. Future research could explore relaxing this constraint or introducing hard size constraints for output polygons.
  • Alternative Partitions: The method currently uses Delaunay triangulations. Investigating other partitions of the plane, such as those based on linear extensions of polygon edges, could preserve input polygon regularities.
  • Pareto-optimal Solutions vs. Extreme Nondominated: The paper focuses on $\alpha$-optimal solutions, which correspond to extreme nondominated points. Exploring the full set of Pareto-optimal solutions might offer more flexibility.

Summary updated

Abstract

We present a new method for the task of detecting groups of polygons in a given geographic data set and computing a representative polygon for each group. This task is relevant in map generalization where the aim is to derive a less detailed map from a given map. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a constrained Delaunay triangulation of the input polygons' exterior. The innovation of our method is to compute the selection of triangles by solving a bicriteria optimization problem. While on the one hand we aim at minimizing the total area of the outputs polygons, we aim on the other hand at minimizing their total perimeter. We combine these two objectives in a weighted sum and study two computational problems that naturally arise. In the first problem, the parameter that balances the two objectives is fixed and the aim is to compute a single optimal solution. In the second problem, the aim is to compute a set containing an optimal solution for every possible value of the parameter. We present efficient algorithms for these problems based on computing a minimum cut in an appropriately defined graph. Moreover, we show how the result set of the second problem can be approximated with few solutions. In an experimental evaluation, we finally show that the method is able to derive settlement areas from building footprints that are similar to reference solutions.
BibTeX
@inproceedings{rottmann2021bicriteria,
  author = {Peter Rottmann and Anne Driemel and Herman J. Haverkort and Heiko Röglin and Jan-Henrik Haunert},
  title = {{Bicriteria Aggregation of Polygons via Graph Cuts}},
  booktitle = {GIScience (II)},
  year = {2021},
  doi = {10.4230/lipics.giscience.2021.ii.6},
}
Figure