# Particle Swarm Optimization-Based Unconstrained Polygonal Fitting of 2D Shapes
## 2 Related Work  
The problem of shape fitting/polygonal approximation has been studied extensively during the last five decades [1; 3; 4; 6]. The methods that have been developed solve the problem by approximating the original shape \(\mathcal{S}\) by a polygonal curve \(P\) under the constraint that the \(P\) vertex sequence is an ordered sub-sequence of the vertices along shape boundary. The polygonal approximation problem can be formulated in two ways [1; 6]:  
* The problem of better fitting, where the approximation error is minimized or the fitting accuracy is maximized given the number of vertices \(N\). * The problem of minimum number of vertices, where the approximation error or the fitting accuracy is bounded and the goal is to find the minimum number of vertices that satisfy the given bound. The polygonal approximations algorithms can be classified as (1) optimal or non-optimal and (2) supervised or unsupervised algorithms [6]. The non-optimal algorithms do not guarantee any kind of optimum as optimal algorithms, but can find reasonable polygonal approximations faster than the optimal ones. The supervised algorithms take into account parameters to generate polygonal approximations, while the unsupervised algorithms generate the polygonal approximations without parameters. The Douglas-Peucker algorithm [4] is one of the first successful algorithms developed for polygonal approximation and cartographic generalization [7]. The algorithm is also widely used in robotics to perform simplification [8]. The purpose of the algorithm is, given a curve composed of line segments, to find a similar polygonal curve with fewer points so that the simplified curve consists of a subset of the points that defined the original curve. [PERSON] [9] presents a polygonal approximation approach based on the discrete particle swarm optimization (PSO) algorithm. Each particle represented as a binary vector corresponds to a candidate solution to the polygonal approximation problem. A swarm of particles is initiated and flies through the solution space for targeting the optimal solution. In [10], the authors proposes a non-optimal and unsupervised algorithm for generation of polygonal approximations based on the convex hull of the 2D closed curves or contours. The significance levels of the contour points are computed using a symmetric version of the well-known Douglas-Peucker algorithm and, finally, a thresholding process is applied to obtain the vertices or dominant points of the polygonal approximation. In the case of 2D shape fitting, a 2D binary image is given with foreground points representing the shape to be modeled. This image can be the result of any object detection or image segmentation method (e.g., [11; 12; 13]). Several models can be used to solve the 2D shape fitting problem. In the literature, there exists several approaches that fit a set of ellipses to the given 2D shape based on (a) the Hough Transform, (b) Genetic and Optimization Algorithms, and (c) edge-following [13; 14]. In [13], a framework has been proposed to represent a given 2D shape with an automatically determined number of ellipses based on expectation maximization criterion, so that the total area covered by the ellipses is equal to the area of the original shape. In [3], an algorithm is proposed to extract and vectorize objects in images with low-complexity polygons based on local merging and splitting of cells. Departing from a polygonal partition that oversegments an image into convex cells, the algorithm refines the geometry of the partition while labeling its cells by a semantic class. The authors applied their method to a variety of scenes, from organic shapes to human-made objects through floor maps and line-drawing sketches. Concerning the metrics that have been used to measure the performance on shape fitting problem, they can be classified into:* Boundary-based metrics that compare the distance between the boundary of given shape and the approximated curve.