OPTIMUM POLYGONAL APPROXIMATION OF DIGITAL CURVES USING GENETIC ALGORITHM

Polygonal approximation methods based on local property of a curve generally suffer from lacking global information. This paper presents an algorithm for polygonal approximation of digital curves. It takes the polygonal approximation as an optimization problem of finding a polygon whose vertex number is minimal for a given maximal allowed error,or both vertex number and approximation error are as minimal as possible. In the case of long curves, the authors use genetic algorithm (GA) and improved GA based on Pareto optimal solution to obtain a near optimal polygonal approximation. Compared to the famous Teh Chin algorithm, the algorithm proposed in the paper has obtained the approximated polygon with less number of vertices and less error. Compared to the dynamic programming algorithm, the processing time of the algorithms are much less expensive.