摘要
为在平面数字曲线的多边近似中克服顶点的检测只依靠局部区域、缺乏全局信息的弱点， 把多边形近似问题作为在一定的允许误差下寻找最少顶点数的最优化问题来处理。为能够处理点数较多的曲线， 采用Ｔａｂｕ 搜索来求近似最优解。和一些经典算法的实验比较表明， 与只依靠曲线局部特性的一类算法相比， 该算法在近似的保真性和效率上有明显的改进， 同时又比准确寻优一类的算法如动态规划等有大幅度的时间节省。
This paper presents a Tabu search based algorithm for optimum polygoal approximation of digital curves. For a maximal tolerable error between the approximation and the curve, the Tabu search algorithm finds a near optimal polygonal approximation with a minimal number of vertices. Compared to the famous Teh Chin algorithm, the algorithm has obtained the approximated polygon with less number of vertices and less error. Compared to the dynamic programming algorithm, the processing time of the algorithm is much less expensive. Experimental results have shown that the Tabu search has good performance in both fidelity and efficiency.
出处
《高技术通讯》
EI
CAS
CSCD
1999年第10期30-34,共5页
Chinese High Technology Letters
基金
国家自然科学基金
北京市自然科学基金
