# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 5 Methodology
### SEP-PSO Fast Balanced Clustering  
This Section presents the proposed Particle Swarm Optimization (PSO)-based fast balanced clustering method (_SEP-PSO FBC_), which combines the PSO framework with the proposed _SEP-FBC_ method to improve its results.  
PSO is a derivative-free optimization method designed to handle complex, multi-modal, and discontinuous objective functions with multiple local minima. The optimization process is driven by the evolution of a population (swarm) of candidate solutions (particles). These particles explore the parameter space of the objective function, adapting over a finite number of generations (iterations) based on a strategy that emulates \"social interaction\". The key parameters of PSO are the number of particles and generations, whose product defines the computational budget--that is, the total number of objective function evaluations. PSO is capable of achieving near-optimal solutions and has been successfully applied to various challenging optimization problems in computer vision and pattern recognition, including classification, clustering, prediction, simplification, image segmentation, video co-segmentation, and object tracking [21; 31; 32; 33].  
According to the 2D-SEP problem definition, the proposed _SEP-PSO FBC_ method optimizes the \(L(R)\) metric (see Equation (3)) for initial centroids, which initialize _SEP-FBC_ method (instead of k-means initialization), that are directly represented by PSO particles. Similar to _SEP-FBC_, the input of _SEP-PSO FBC_ is the shape \(S\) and the number of the desired regions \(N\) of equipartition, and the output is the segmentation \(R\) according to the constraints of the problem, as defined in Section 3.  
Iteratively, PSO searches for the best combination of \(N\) initial centroids that minimize the \(L(R)\) metric. We represent each particle by a \(2\cdot N\) vector with the 2D coordinates of the \(N\)-initial centroids of the regions. In order to reduce the search space, we assume that the vertices are sorted in ascending order concerning their distance from the top-left image corner; otherwise, in the evolution process, we correct the order of vertices of each particle  
Figure 9: Segmentation results of the two stages of the proposed _SEP-FBC_ method for \(N=5\).  
according to this hypothesis. The fitness (objective function) of the particle is directly given by the \(L(R)\) metric of the particle (see Equation (3)). The _SEP-PSO FBC_ algorithm is analytically described hereafter.  
Initially, we create a population of \(M\) particles (e.g., \(M=10\)) that are located in random positions in shape \(S\), while the first particle is given by the k-means++ algorithm (see Section 5.1). In the evolution process, PSO finds the current optimal solution in order to update the best global solution. Furthermore, the best local solution for each particle is also updated, where the \(L(R)\) of the particle reaches a better solution. The method ends when the number of iterations of the evolution process exceeds the given number of generations. In this work, we use the upper limit of 50 generations.