Fast Equipartition of Complex 2D Shapes with Minimal Boundaries

In this paper, we study the 2D Shape Equipartition Problem (2D-SEP) with minimal boundaries, and we propose an efficient method that solves the problem with a low computational cost. The goal of 2D-SEP 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 length of boundaries between the segments is minimized. We define the 2D-SEP, and we study problem solutions using basic geometric shapes. We propose a 2D Shape Equipartition algorithm based on a fast balanced clustering method (SEP-FBC) that efficiently solves the 2D-SEP problem under complex 2D shapes in O(N·|S|·log(|S|)), where |S| denotes the number of image pixels. The proposed SEP-FBC method initializes clustering using centroids provided by the k-means algorithm, which is executed first. During each iteration of the main SEP-FBC process, a region-growing procedure is applied, starting from the smallest region and expanding until regions of equal area are achieved. Additionally, a Particle Swarm Optimization (PSO) method that uses the SEP-FBC method under different initial centroids has also been proposed to explore better 2D-SEP solutions and to show how the selection of the initial centroids affect the performance of the proposed method. Finally, we present experimental results on more than 2800 2D shapes to evaluate the performance of the proposed methods and illustrate that their solutions outperform other methods from the literature.