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