Polygonal approximation of digital planar curves through vertex betweenness

Andre Ricardo Backes and Odemir Martinez Bruno

INFORMATION SCIENCES, 222():795-804, 2013

Contour polygonal approximation is usually defined as a set of selected points, which describes a polygon and best represents the original contour. This paper presents a novel graph based approach to compute a polygonal approximation of a shape contour. In a graph, such points correspond to a high transitivity region of the graph. We use the vertex betweenness to measure the importance of each vertice in a graph according to the number of shortest paths where each vertice occurs. By selecting the vertices with higher vertex betweenness, a polygon which retains the main characteristics of the contour is achieved. By using benchmark curves, a comparative experiment with other commonly used algorithms is presented. Results indicate that the proposed approach produced efficient and effective polygonal approximations for digital planar curves. (C) 2012 Published by Elsevier Inc.