Efficient Polygonal Approximation of Digital Curves via Monte Carlo Optimization

A novel stochastic searching scheme based on the Monte Carlo optimization is presented for polygonal approximation (PA) problem. We propose to combine the split-and-merge based local optimization and the Monte Carlo sampling, to give an efficient stochastic optimization scheme. Our approach, in essence, is a well-designed Basin-Hopping scheme, which performs stochastic hopping among the reduced energy peaks. Experiment results on various benchmarks show that our method achieves high-quality solutions with lower computational costs, and outperforms most of state-of-the-art algorithms for PA problem.