A Discrete Particle Swarm Optimization-based Algorithm for Polygonal Approximation of Digital Curves

The shape contour of objects can be regarded as a closed digital curve. How to find the optimal polygonal approximation of the digital curve is a very difficult problem. In recent years, many bio-inspired algorithms, including genetic algorithms (GA), ant colony optimization (ACO) and particle swarm optimization (PSO), have been applied to solve polygonal approximation problem. The existing PSO-based methods adopt binary particle swarm optimization (BPSO) which requires developing a constraint function to deal with velocity and position updates. However, it is very difficult to develop a proper constraint function. In addition, the computational cost of constraint function is expensive. To overcome these problems, an integer-coding particle swarm optimization (IPSO) is proposed for polygonal approximation. As a modified version of standard particle swarm optimization，IPSO can be performed to search the optimal solutions in the discrete solution space，by redefining the addition, multiplication and subtraction for the updating formulas of the velocity and position. A position-vector repairing scheme is developed to maintain the feasibility of the solutions, and a local optimizer is embedded to the IPSO to improve the quality of the solutions. The experimental results manifest that IPSO outperforms the GA and binary-coding PSO on the quality of solutions and computational speed.