# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 2 Related Work  
The problem of image segmentation has been studied extensively during the last decades. In the literature, a variety of image segmentation techniques have been proposed, each utilizing different principles and methodologies. Traditional approaches include thresholding methods [8; 9], region-growing techniques, and region-merging strategies [10; 11]. Other widely used techniques involve clustering algorithms, such as k-means [12], and edge-based methods such as watershed segmentation [13; 14]. Furthermore, contour-based techniques, such as active contours [15], and graph-based methods, including graph cuts [16], have demonstrated effectiveness in various applications. Probabilistic approaches, such as conditional and Markov random fields, as well as sparsity-based methods [17], have been explored for robust segmentation under challenging conditions. In recent years, the advent of deep learning (DL) has revolutionized the field of image segmentation, leading to significant improvements in accuracy and generalization. Deep learning models leverage hierarchical feature extraction and end-to-end learning capabilities to surpass traditional methods in performance. Convolutional neural networks (CNNs)  
Figure 3: Instances of the proposed 2D Shape Equipartition problem. In the first and second rows, the results come from the _SEP-ILS_ and _SEP-RG_ methods [7] from literature, respectively. In the third row, the corresponding results come from the proposed _SEP-FBC_ method. The number of regions (\(N\)) and the intrinsic boundary length (\(L\)) are reported in the caption of each shape. and their advanced architectures, including fully convolutional networks (FCNs), U-Net, DeepLab, and Mask R-CNN, have established new benchmarks in image segmentation tasks in multiple domains [18]. These advances have enabled the development of highly accurate automated segmentation systems, facilitating progress in medical diagnostics, autonomous driving, and many other critical applications. Different error criteria have been proposed for image segmentation problems. The Intersection Over Union (_IoU_) and the F-measure are two of the most popular supervised methods to evaluate image segmentation quality but require the ground truth [19]. Under unsupervised image (color or grayscale) segmentation methods, where the ground truth is completely unknown, clustering-based criteria such as the heterogeneity of pixels between regions and the homogeneity within the region objectively can be used to evaluate the segmentation [20]. Under the 2D-SEP problem, no ground truth is given. So, we have to select an unsupervised criterion. Additionally, the given image is binary, so no color-grayscale information is given. Similar to the polygonal approximation [21] problem, the 2D-SEP problem can be formulated in two ways:  
* The problem of minimum error, where the error (e.g., boundary length) is minimized given the number of segments \(N\). * The problem of the minimum number of segments, where the approximation error is bounded, and the goal is to find the minimum number of segments (\(N\)) that gives an error lower than the given error. In this work, according to the proposed problem formulation, we select the first problem formulation of error minimization given the number of segments \(N\), under the error criterion of minimum intrinsic boundary length that may better divide the shape into \(N\) equal-area segments. The intrinsic boundary length criterion is selected since, in the given shape \(S\), there does not exist color information, model error, or weights for the boundaries to use a more complicated criterion. Additionally, the same idea called a minimum cut has also been used in image segmentation [22]. Apart from image segmentation, the 2D-SEP problem is related to the balanced clustering problem in the sense that the goal of 2D-SEP is to group the pixels into balanced in-area regions.