A TECHNIQUE FOR PIECEWISE LINEAR APPROXIMATION OF 2D DIGITAL CURVE
Authors:
Bimal Kumar Ray, School of Information Technology & Engineering, VIT University, Vellore – 632014, India
Abstract:
This paper introduces the concept of curve segment after relaxing the definition of digital straight segment and uses this concept to decompose a digital curve into a sequence of curve segments. For each curve segment, the maximum deviation of it from its approximating line segment is computed and the segment with the highest maximum deviation is split into two at a point most distant from the line segment, if the deviation exceeds a threshold. Only one vertex is added to the existing set of vertices in iteration until no more vertices can be added to the approximation. Experiments show improvement over a similar work.
Keywords:
Curve Segment, Incremental Splitting, Iteration
References:
[1] Y. Kurozumi, W.A. Davis, Polygonal approximation by the minimax method, Computer Graphics and Image Processing 19 (1982) 248 – 264.
[2] J. G. Dunham, Optimum piecewise linear approximation of planar curves, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8 (1986) 67 – 75.
[3] J. C. Perez, E. Vidal, Optimum polygonal approximation of digitized curves, Pattern Recognition Letters 15 (1994) 743 – 750.
[4] M. Salotti, Optimal polygonal approximation of digitized curves using the sum of square deviations criterion, Pattern Recognition 35 (2002) 435 – 443.
[5] P. Y. Yin, Genetic particle swarm optimization for polygonal approximation of digital curves, Pattern Recognition and Image Analysis 16 (2006) 223 – 233.
[6] B. Wang , H. Shu, L. Luo, A genetic algorithm with chromosome-repairing for min - # and min - ε polygonal approximation of digital curves, Journal of Visual Communication and Image Representation 20 (2009) 45 – 56.
[7] C. Williams, An efficient algorithm for piecewise linear approximation of planar curves, Computer Graphics and Image Processing 8 (1978) 286 – 293.
[8] J. Sklansky, V. Gonzalez, Fast Polygonal Approximation of Digitized Curves, Pattern Recognition 12 (1980) 327 – 331.
[9] K. Wall, P.-E. Danielsson, A fast sequential method for polygonal approximation of digitized curves, Computer Vision, Graphics and Image Processing 28 (1984) 220-227.
[10] T. Pavlidis, S. L. Horowitz, Segmentation of plane curves, IEEE Transactions on Computer 23 (1974) 860 – 870.
[11] U. E. Ramer, An iterative procedure for polygonal approximation of plane curves, Computer Graphics and Image Processing 1 (1972) 244 – 256.
[12] M. Visvalingam, J. D. Whyatt, Line generalization by repeated elimination of points, Cartographic Journal 30 (1993) 46 – 51.
[13] P. Zhu, P.M. Chirlian, On critical point detection of digital shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI – 17 (1995) 737 – 748.
[14] A. Pikaz, I. Dinstein, An algorithm for polygonal approximation based on iterative point elimination, Pattern Recognition Letters 16 (1995) 557 – 563.
[15] P. Bhowmick, B. Bhattacharya, Fast Polygonal Approximation of Digital Curves Using Relaxed Straightness Properties, IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI – 29 (2007) 1590 – 1602.
[16] H. Freeman, Techniques for the Digital Computer Analysis of Chain-Encoded Arbitrary Plane Curves, Proceedings of the National Electronics Conference 7 (1961) 421 – 432.
[17] A. Rosenfeld, Digital Straight Line Segments, IEEE Transactions on Computers 23 (1974) 1264 – 1268.
[18] H. Freeman, On the Encoding of Arbitrary Geometric Configurations, IRE Transactions on Electronic Computers 10 (1961) 260 – 268.
[19] D. Sarkar, A simple algorithm for detection of significant vertices for polygonal approximation of chain-coded curves, Pattern Recognition Letters 14 (1993) 959 – 964.
[20] http://www.dabi.temple.edu/~shape/MPEG7/dataset.html.
Citations:
APA:
Ray, B. K. (2021). A Technique for Piecewise Linear Approximation of 2D Digital Curve. International Journal of Advanced Science and Technology (IJAST), ISSN: 2005-4238(Print); 2207-6360 (Online), NADIA, 147, 9-24. doi: 10.33832/ijast.2021.147.02.
MLA:
Ray, Bimal Kumar, “A Technique for Piecewise Linear Approximation of 2D Digital Curve.” International Journal of Advanced Science and Technology, ISSN: 2005-4238(Print); 2207-6360 (Online), NADIA, vol. 147, 2021, pp. 9-24. IJAST, http://article.nadiapub.com/IJAST/Vol147/2.html.
IEEE:
[1] B. K. Ray, "A Technique for Piecewise Linear Approximation of 2D Digital Curve." International Journal of Advanced Science and Technology (IJAST), ISSN: 2005-4238(Print); 2207-6360 (Online), NADIA, vol. 147, pp. 9-24, April 2021.
