A Genetic Algorithm for Error-Bounded Polygonal Approximation of Curves

Polygonal approximation of digital curve is a hot topic in image processing and pattern recognition and has found wide applications. Genetic algorithms (GA) have been used to solve polygonal approximation problems recently. However, the existing GA-based methods have the following disadvantages which limit their performance. Firstly, the length of chromosome is very long because of adopting fixed-length chromosome encoding; secondly, the local search ability of the traditional genetic operator is poor; finally, the penalty function method is adopted to cope with infeasible solution, and however, an appropriate penalty function is very difficult to determine. To overcome these problems, a novel GA-based method is proposed for error-bounded polygonal approximation. Its main ideas are: 1) a variable-length chromosome encoding scheme is adopted to reduce the memory storage and computational time; 2) a novel genetic operator named gene-removing crossover is developed for removing the redundant genes; 3) a chromosome-repairing scheme is proposed to cope with the infeasible solutions by iteratively adding the valuable candidate genes to the chromosome and an gene evaluating scheme is developed for this task. The experimental results demonstrate that the proposed method outperforms the existing GA-based method. The proposed method is also applied to the polygonal approximation of the satellite image of lake and obtains a better approximation result.