# Particle Swarm Optimization-Based Unconstrained Polygonal Fitting of 2D Shapes
## 1 Introduction  
Polygonal shape fitting is a key problem in computer vision and computer graphics with several applications, including object recognition, computational cartography, signal summarization, and compression [1; 2; 3]. When curves are modeled, straight-line segments are usually preferred due to their simplicity. The polygonal fitting process saves memory space, reduces rendering time on graphics applications, and gives a more compact representation of the original shape. According to the classical polygonal approximation problem of a 2D shape, the goal is to compute an N-vertex polygonal curve \(P\) that approximates the boundary \(B\) of the original shape \(S\) according to a predefined error criterion. In the classical polygonal approximation, the vertices of \(P\) are an ordered sub-sequence of the boundary points \(B\)[1]. The classical polygonal shape fitting provides poor results, especially when the number of vertices is low and the shape complexity is high. In this work, we study a general version of polygonal fitting, called the Unconstrained Polygonal Fitting (UPF) problem, to provide better solutions with the same number of vertices. According to UPF, the N-vertices of \(P\) can be placed anywhere in the 2D space. Therefore, the search space of UPF problem is a superset of the classical polygonal approximation (PA) problem, where the vertices are constrained to belong in the boundary of the given 2D shape. This means that the resulting solutions of UPF may better approximate the given curve than the PA problem solutions. This theoretically interesting computer vision problem has a compact and easy-to-grasp description, but a very high algorithmic complexity due to the large search space. Even if just a triangle (\(N=3\)) is used, there does not exist any trivial method to compute the optimal solution of UPF problem. Different error criteria have been proposed for shape fitting/polygonal approximation problems. In this research, the Intersection over Union (IoU) metric between \(S\) and \(P\) is maximized given a fixed number of polygonal vertices \(N\), without any assumption or prior knowledge of the object structure. IoU metric can be easily replaced by any other segmentation metric, for example accuracy and dice coefficient (\(DICE\)), without any change in the proposed methodology. Another problem instance that we experimentally study is to define the problem under the Equal Area constraint, which states that the area covered by the polygonal curve \(P\) should be equal to the area of the given shape \(S\). Figure 1 shows two example outputs of the classical polygonal approximation using the Douglas-Peucker algorithm [4] (left) and the unconstrained polygonal fitting using the proposed method (right) for \(N=4\) vertices. In both cases, it holds that the solution of the UPF problem provides higher IoU, DICE values compared with the results of Douglas-Peucker algorithm. In the first example with an apple, the Douglas-Peucker algorithm yields \(DICE=79.6\%\), \(IoU=66.1\%\) (Figure 1a), while the proposed method yields \(DICE=90.8\%\), \(IoU=83.2\%\) (Figure 1b). In the second example we with a building, the Douglas-Peucker algorithm yields \(DICE=88.9\%\), \(IoU=80.1\%\) (Figure 1c), while the proposed method yields \(DICE=97.5\%\), \(IoU=95.1\%\) (Figure 1d). There exist several examples where there exist significant differences in performance between the optimal solutions of the two problems, especially for lower values of \(N\), where the optimal solutions of UPF space may be far from the shape boundary. In summary, the main contributions of our work are the following: To the best of our knowledge, this is the first work to define and solve the UPF problem. The proposed method solves the UPF problem via Particle Swarm Optimization (PSO) [5] that quickly  
Figure 1: Example outputs of the classical polygonal approximation (PA) (**left**) and the proposed unconstrained polygonal fitting (UPF) (**right**) for \(N=4\) vertices.