王 斌. 一种基于离散微粒群优化的数字曲线的多边形近似算法[J]. 计算机研究与发展, 2010, 47(11): 1886-1892.
 引用本文: 王 斌. 一种基于离散微粒群优化的数字曲线的多边形近似算法[J]. 计算机研究与发展, 2010, 47(11): 1886-1892.
Wang Bin. A Discrete Particle Swarm Optimization-based Algorithm for Polygonal Approximation of Digital Curves[J]. Journal of Computer Research and Development, 2010, 47(11): 1886-1892.
 Citation: Wang Bin. A Discrete Particle Swarm Optimization-based Algorithm for Polygonal Approximation of Digital Curves[J]. Journal of Computer Research and Development, 2010, 47(11): 1886-1892.

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

• 摘要: 数字曲线的多边形近似是图像分析研究领域的一个热点问题.获取数字曲线的优化多边形近似是一个复杂的问题，其计算复杂度非常高.微粒群算法是近些年来提出的一种新的优化方法，已经被广泛应用于各种优化问题的求解.提出了一种求解数字曲线的多边形近似问题的基于整数编码的离散微粒群算法(IPSO).IPSO通过重新定义标准微粒群算法的速度和位置更新公式中的加法、乘法和减法运算，使得算法能运行在离散的解空间.IPSO的位置向量修复机制保证了解的可行性，而局部优化器提高了算法的搜索精度.实验结果表明，IPSO求解的质量和求解的效率均优于遗传算法和0-1编码的微粒群算法.

Abstract: 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.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈