# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 5 Methodology
### SEP-Fast Balanced Clustering
The sum of the boundaries' lengths of the resulting segmentation is low due to the distance-based clustering procedure, but the clusters' sizes may not be equal. In the second stage, the resulting clustering is balanced (lines 17-23 of Algorithm 1). * Initially, we ensure that all the clusters (regions) consist of connected pixels by assigning non-connected pixels to the smallest neighbor region. This is performed by the procedure _correctConnectedComponets(R)_ (in line 17 of Algorithm 1). Additionally, we smooth the region boundaries by reassigning the pixels of each region boundary to the region that has the most neighbors which is carried out by the procedure _smoothBoundaries(R)_ of line 18 of Algorithm 1. * Finally, we perform an iterative process that in each iteration grows the smallest region (_areaGrow_ procedure) until the inequality (4) is satisfied (see lines 20-23 of Algorithm 1). The \(N\times N\) symmetric matrix \(RR\) that counts the number of pixel reassignments between two regions is initialized to zero. The _areaGrow_ procedure uniformly grows the smallest region \(c\) by applying the dilation operation with an open disk of radius one. The procedure prevents infinite loops by adding the extra pixels \(p\) in a descending way according to expression \(|R(p)|-RR(c,R(p))\), where \(|R(p)|\) denotes the area of the region to which \(p\) belonged, and \(RR(c,R(p))\) is the number of reassignments between the regions \(c\) and the region that \(p\) belonged (\(R(p)\)). The procedure can stop before growth has finished only if the current area of the region \(|R_{c}|\) is at least \(\frac{|S|}{N}-1\). The computational cost of this stage is \(O(|S|+|S|+N^{2})\) according to the procedures of lines 17-19 of Algorithm 1. The iterative step of lines 20-23 of Algorithm 1 has a computational cost of \(O(N^{2}+N\cdot|S|)\). Taking into account all the steps of the method, we obtain a total computation complexity equal to \(O(N\cdot|S|\cdot log|S|+N^{2})\) that is simplified to \(O(N\cdot|S|\cdot log|S|)\) since \(N<<|S|\). This computational complexity is lower compared with the computational complexity \(O(N^{2}\cdot|S|+|S|^{2})\) of the most computational efficient method from the literature _SEP-RG_. In our experimental results, we also verify the computational efficiency of the proposed method by comparing the execution times of the proposed method and baselines from the literature. Both important differences in computational complexity and execution times compared with other state-of-the-art methods provide a justification for the Fast \"fast\" in the name of the method. Additionally, the most computationally efficient method for the simpler clustering problem is k-means with a \(O(N\cdot|S|)\) computational cost. The proposed method that provides a solution to the more complex 2D-SEP problem with a slightly higher computational cost can also be considered as a fast method. Figure 9 shows some segmentation results of the two stages of the proposed _SEP-FBC_ method for \(N=5\). Figure 8(a) shows the result of the first stage of the method with a total intrinsic boundary length equal to 106.6, which produces regions of varying areas in the range \([583,1132]\). The execution of the second stage (see Figure 8(b)) yields equal-area segments with a total intrinsic boundary length equal to 121.6. In another example of Figure 8(c), the result of the first stage has the total intrinsic boundary length 116.9 with regions of varying areas in the range \([918,2082]\). The execution of the second stage (see Figure 8(d)) results in equal-area segments with a total intrinsic boundary length 162.6.