Title :
Optimal polygonal approximation of digitised curves
Author :
Zhu, Y. ; Seneviratne, L.D.
Author_Institution :
Dept. of Mech. Eng., Loughborough Univ. of Technol., UK
fDate :
2/1/1997 12:00:00 AM
Abstract :
Piecewise linear approximation of thinned digitised curves is a popular technique when a large number of discrete points has to be represented in a compact way for shape analysis and pattern classification. Such representations reduce significantly the storage-memory space and facilitate the extraction of numerical features from waveform curves or images. Polygonal curve fitting involves approximating a discretised planar curve by a sequence of connected straight-line segments, with a certain error norm. The authors consider the case where the knots of the polygon are a subset of the points of the curve and the error norm is uniform. Several algorithms have been proposed for this problem, but the results are generally not optimal. An optimal polygonal-approximation algorithm is presented which gives the minimum number of sides for a uniform error norm. The algorithm employs the concept of an invalid point, leading to a new condition for terminating a segment. The algorithm is experimentally tested and its advantages demonstrated by comparing with Dunham´s (1986) and Sklansky and Gonzalez´s (1980) algorithms
Keywords :
curve fitting; image representation; image segmentation; image sequences; optimisation; piecewise polynomial techniques; connected straight-line segments; digitised curves; discretised planar curve; image representation; invalid point; numerical features extraction; optimal polygonal approximation; optimal polygonal-approximation algorithm; pattern classification; piecewise linear approximation; polygon knots; polygonal curve fitting; shape analysis; storage-memory space reduction; uniform error norm; waveform curve;
Journal_Title :
Vision, Image and Signal Processing, IEE Proceedings -
DOI :
10.1049/ip-vis:19970985