Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach

An important task of pattern recognition and map generalization is to partition a set of disjoint polygons into groups and to aggregate the polygons within each group to a representative output polygon. We introduce a new method for this task called bicriteria shapes. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a conforming Delaunay triangulation of the input polygons’ exterior. The innovation is that we control the selection of triangles with a bicriteria optimization model that is efficiently solved via graph cuts. In particular, we minimize a weighted sum that combines the total area of the output polygons and their total perimeter. In a basic problem, we ask for a single solution that is optimal for a preset parameter value. In a second problem, we ask for a set containing an optimal solution for every possible value of the parameter. We discuss how this set can be approximated with few solutions and show that it is hierarchically nested. Hence, the output is a hierarchical clustering that corresponds to multiple levels of detail. An evaluation with building footprints as input and a comparison with α-shapes that are based on the same underlying triangulation conclude the article. An advantage of bicriteria shapes compared to α-shapes is that the sequence of solutions for decreasing values of the parameter is monotone with respect to the total perimeter of the output polygons, resulting in a monotonically decreasing visual complexity.