数字曲线的多边形模拟算法研究

摘要

用多边形模拟数字曲线往往转化为数学上的优化问题，这一研究在计算机视觉与模式识别等学科领域中也有着重要的意义与广泛的应用，因此受到人们的普遍关注。特别地，近几年来用多边形模拟数字曲线的各种算法先后被提出和研究。本文对现有经典算法做了分析并探讨了其中所存在的问题，在此基础上提出两种多边形模拟数字曲线的新算法：矩形框算法和斜率算法。
　　 矩形框算法利用迭代的步骤逐步达到逼近数字曲线的要求。首先，确定初始点。这一步没有利用常规的Freeman链锁代码的方法，而是采用一种简单的矩形框方法，从而保证了算法的简单性和稳定性。然后，利用迭代逐次添加主要信息点直到满足设定的精度要求。数值实验中给出了本算法和几种现有算法的效果比对，表明该算法的时间复杂度较低。
　　 斜率算法是以斜率为基础探讨的。给定了阈值，通过改变它的大小控制曲线模拟所要求的点数或误差。和矩形框算法一样，首先提取非共线点作为拟有效点。在此基础上通过两组斜率的差值与事先给定的阈值比较大小来决定保留还是删除某些像素点，直到满足设定的精度要求。由于在提取有效点时没有采用常规的迭代方法，从而减少了计算量，保证了较快的运行速度。最后给出了数值实验，结果表明该算法有效。