OPTIMAL POLYGONAL-APPROXIMATION OF DIGITAL CURVES

Authors
PIKAZ A DINSTEIN I
Citation
A. Pikaz et I. Dinstein, OPTIMAL POLYGONAL-APPROXIMATION OF DIGITAL CURVES, Pattern recognition, 28(3), 1995, pp. 373-379
Citations number
25
Categorie Soggetti
Computer Sciences, Special Topics","Engineering, Eletrical & Electronic","Computer Science Artificial Intelligence
Journal title
Pattern recognition → ACNP
ISSN journal
00313203
Volume
28
Issue
3
Year of publication
1995
Pages
373 - 379
Database
ISI
SICI code
0031-3203(1995)28:3<373:OPODC>2.0.ZU;2-7
Abstract
An algorithm for optimal polygonal approximation is presented. Given a value for the maximal allowed distance between the approximation and the curve, the algorithm finds an approximation with the minimal numbe r of vertices. The city-block metric is used to measure the distance b etween the approximation and the curve. The algorithm worst case compl exity is O(n(2)), where n is the number of points in the curve. An eff icient and optimal solution for the case of closed curves where no ini tial point is given, is also presented.