A Fast Near-optimal min-# Polygonal Approximation of Digitized Curves

A. Kolesnikov (Russia) and P. Fränti (Finland)


: vectorization, polygonal approximation, min-# problem, shortest path, dynamic programming


We propose a fast near-optimal algorithm for solving the problem of min-# polygonal approximation of digitized curves. The algorithm consists of two steps. It first finds a reference approximation with minimum number of segments for a given error tolerance by using L∞ error metrics. It then improves the quality of the approximation by a reduced-search dynamic programming with additive L2 error measure. The algorithm is tailored for high quality vectorization of digitized curves.

Important Links:

Go Back