Optimized polygonal approximations through vertex relocations in contour neighborhoods

摘要

This paper presents yet another algorithm for finding polygonal approximations of digital planar curves; however, with a significant distinction: the vertices of an approximating polygon need not lie on the contour itself. This approach gives us more flexibility to reduce the approximation error of the polygon compared to the conventional way, where the vertices of the polygon are restricted to lie on the contour. To compute the approximation efficiently, we adaptively define a local neighborhood of each point on the contour. The vertices of the polygonal approximation are allowed to 'move around' in the neighborhoods. In addition, we demonstrate a general approach where the error measure of an already computed polygonal approximation can possibly be reduced further by vertex relocation, without increasing the number of dominant points. Moreover, the proposed method is non-parametric, requiring no parameter to set for any particular application. Suitability of the proposed algorithm is validated by testing on several databases and comparing with existing methods.