# Particle Swarm Optimization-Based Unconstrained Polygonal Fitting of 2D Shapes
## 3 Unconstrained Polygonal Fitting
### UPF-PSO and UPF-PSO-EA Algorithms  
In this work, we cast the search for a single polygonal curve as a stochastic optimization problem that is solved based on Particle Swarm Optimization (PSO) [5; 16; 17]. PSO is a derivative-free optimization method that handles multi-modal, discontinuous objective functions with several local minima. Optimization is performed through the evolution of particles (candidate solutions) of a population (swarm). Particles lie in the parameter space of the objective function to be optimized, and evolve through a limited number of generations (iterations) according to a policy which emulates \"social interaction\". The main parameters of PSO are the number of particles and generations, the product of which determines its computational budget (i.e., the number of objective function evaluations). PSO achieves near-optimal solutions, and has been successfully applied in several challenging optimization problems in computer vision and pattern recognition such as classification, clustering, prediction, image segmentation, video co-segmentation, object tracking [16; 18; 19; 20].  
The proposed Unconstrained Polygonal Fitting based on Particle Swarm Optimization Algorithm (UPF-PSO) optimizes the IoU metric (see Equation (3)) for different polygonal curves that are directly represented by PSO particles. The input to UPF-PSO is the binary image \(I\), representing the given shape \(S\) and the number of vertices \(N\) of the polygonal closed curve that will be fitted to \(S\). The UPF-PSO method quickly explores the search space starting from random solutions. Iteratively, PSO searches for a polygonal curve that maximizes the IoU metric.  
We represent each particle by a \(2\cdot N\) vector with the 2D coordinates of the \(N\) points of the polygonal curve. In order to simplify the search space, we assume that the vertices are in clockwise order; otherwise, in the evolution process, we correct the order of vertices of each particle according to this hypothesis. The fitness (objective function) of the particle is directly given by the IoU metric of the particle (see Equation (2)). The UPF-PSO Algorithm is analytically described hereafter.  
Initially, we create a population of \(M\) (e.g., \(M=20\)) particles that are located in random positions around the centroid of the shape \(S\) under the Equal Area Principle (see Section 3.2) to be in valid positions of the search space. In the evolution process, PSO finds the current optimal solution in order to update the best global solution. Additionally, the best local solution of each particle is also updated, where the IoU of the particle reaches a better solution. The method terminates when the number of iterations of the evolution process exceeds the given number of generations. In this work, we use the upper limit of 100 generations.  
The proposed Unconstrained Polygonal Fitting based on Particle Swarm Optimization Algorithm under equal area principle (UPF-PSO-EA) is the UPF-PSO algorithm with the extra modification of applying the transform of Equation (6) at each iteration of PSO. This means that in each step of the method, the area of \(P\) is equal with the area of the given shape. Therefore, the solutions of UPF-PSO-EA can be completely different from the original UPF-PSO.