Effective Data Reduction by the Curvature-Based Polygonal Approximation

Kento MIYAOKU  Koichi HARADA  

IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.2   pp.250-258
Publication Date: 1997/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Image Processing,Computer Graphics and Pattern Recognition
polygonal approximation,  weighted minimum number problem,  curvature information,  

Full Text: PDF>>
Buy this Article

For object analysis and recognition, an original shape often needs to be described by using a small number of vertices. Polygonal approximation is one of the useful methods for the description. In this paper, we propose the curvature-based polygonal approximation (CBPA) method that is an application of the weighted polygonal approximation problem which minimizes the number of vertices of an approximate curve for a given error tolerance (the weighted minimum number problem). The CBPA method considers the curvature information of each vertex of an input curve as the weight of the vertex, and it can be executed in O(n2) time where n is the number of vertices of the input curve. Experimental results show that this method is effective even in the case when relatively few vertices are given as an original shape of a planar object, such as handwritten letters, figures (freehand curves) and wave-form data.