Figure 1:Instances of the proposed 2D Shape Equipartition problem using line segments boundaries (first row) and without this assumption (second row) for different number of segments. In the first row, the results come from the proposed sequential selection method. In the second row, the corresponding results come from the proposed fast region growing based method. The number of segments (N) and the intrinsic boundary length (L) are reported in the caption of each shape.

This work [1] presents a general version 2D Shape Equipartition Problem  (2D-SEP) under minimum boundary length. The goal of this problem is to obtain a segmentation into N equal area segments (regions), where the number of segments N is given by the user, under the constraint that the boundaries between the segments have a minimum length.  2D-SEP is defined without any assumption or prior knowledge of the object structure and the location of the segments. In this work, we define the 2D-SEP and we propose a fast region growing based method that solves the general version of 2D-SEP problem.  Additionally, we study the special case of the 2D-SEP in which the intrinsic boundaries are line segments, proving that it has at least one solution in convex shapes and presenting a sequential selection method that efficiently solves the problem. The quantitative results obtained on more than 2,800 2D shapes included in two standard datasets quantify the performance of the proposed methods.

Related Publications

[1]  C. Panagiotakis, The 2D Shape Equipartition Problem under Minimum Boundary Length, submitted to ICPR, 2024. 

[2]  C. Panagiotakis, Particle Swarm Optimization-Based Unconstrained Polygonal Fitting of 2D Shapes, Algorithms, 17(1), 2024.