Computer Engineering and Applications ›› 2006, Vol. 42 ›› Issue (25): 12-.

• 博士论坛 • Previous Articles     Next Articles

An improved approach to polygonal approximation of digital curves based on genetic algorithm


  1. 华中科技大学CAD中心
  • Received:2006-06-07 Revised:1900-01-01 Online:2006-09-01 Published:2006-09-01



  1. 华中科技大学CAD中心
  • 通讯作者: 董方敏 ctgudfm

Abstract: An improved approach to polygonal approximation of regular digital curves based on GA algorithm is presented. In this paper, each chromosome corresponds to a candidate solution to the polygonal approximation problem which is represented as a binary vector. The position error of centroid between the original curve and the approximation polygon, and the variance of distance error for each approximation segment are adopted in the fitness functon to evaluate the feasibility degree of the candidate solutions. The sigmoid function of iteration times is used as the mutation probability instead of the constant ones to improve the global and local searching characteristics. Experimental results show that the proposed approach can get suitable approximation results for preserving the features of original curves.

Key words: polygonal approximation, generic algorithm, centroid, sigmoid function

摘要: 提出了一种基于遗传算法的数字曲线多边形改进逼近方法。该方法针对规则形状数字曲线的多边形逼近问题,以二进制向量序列表示的染色体作为每一个对应的逼近多边形候选解,将简化前后多边形质心偏移误差以及各被替换线段欧氏距离的方差引入到适应函数中,用迭代次数的sigmoid函数作为变异概率来控制遗传算法优化求解过程中的全局和局部搜索特性。实验结果表明,该方法对于保持曲线多边形简化逼近后的形状特征具有较好的效果。

关键词: 多边形逼近, 遗传算法, 质心, Sigmoid函数