An adaptive reduction procedure for the piecewise linear approximation of digitized curves
- 1 January 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 11 (9) , 967-973
- https://doi.org/10.1109/34.35499
Abstract
A new algorithm is presented for the piecewise linear approximation of two-dimensional digitized curves against a square grid. The algorithm utilizes an adaptive reduction procedure in two approximation phases to select the critical points of a digitized curve such that the deviation, from the digitized curve to its final approximated curve, is bounded by a uniform error tolerance. The time complexity of this algorithm is O(m/sup 2/) rather than O(n/sup 2/) on the theoretical plane. In the experiments of fixing the initial and the final processing points, the performance of the algorithm has been compared to those of three prominent other algorithms regarding the required number of critical points and the total execution time of the program. Of the four algorithms compared, the present algorithm consistently has the shortest execution time of the program, and it tends most to require as few critical points as the optimum algorithm that was tested.Keywords
This publication has 11 references indexed in Scilit:
- Optimum Uniform Piecewise Linear Approximation of Planar CurvesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- A data reduction algorithm for planar curvesComputer Vision, Graphics, and Image Processing, 1985
- A fast sequential method for polygonal approximation of digitized curvesComputer Vision, Graphics, and Image Processing, 1984
- Algorithms for Graphics and Image ProcessingPublished by Springer Nature ,1982
- Algorithms for Shape Analysis of Contours and WaveformsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Fast polygonal approximation of digitized curvesPattern Recognition, 1980
- An efficient algorithm for the piecewise linear approximation of planar curvesComputer Graphics and Image Processing, 1978
- A review of algorithms for shape analysisComputer Graphics and Image Processing, 1978
- Segmentation of Plane CurvesIEEE Transactions on Computers, 1974
- An iterative procedure for the polygonal approximation of plane curvesComputer Graphics and Image Processing, 1972