Polygonal Approximation of Digital Planar Curves via Hybrid Monte Carlo Optimization

This letter presents a novel computing paradigm for polygonal approximation of digital planar curves. While the existing heuristic algorithms, such as genetic algorithm (GA) and particle swarm optimization (PSO), have achieved considerable success in solving the two types of polygonal approximation problems, more efficient optimization schemes are still desirable for practical applications. We propose to embed the split-and-merge local search in the Monte Carlo sampling framework, to combine strength of the local optimization and the global sampling. The proposed algorithm is essentially a well-designed basin hopping scheme that performs stochastic exploration in the reduced potential energy space. Experimental results on several benchmarks indicate that the proposed algorithm can achieve high approximation accuracy and is highly competitive to the state-of-the-art alternative algorithms with less computational cost.