| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Techniques for Assessing Polygonal Approximations of Curves
June 1997 (vol. 19 no. 6)
pp. 659-666
Abstract—Given the enormous number of available methods for finding polygonal approximations to curves techniques are required to assess different algorithms. Some of the standard approaches are shown to be unsuitable if the approximations contain varying numbers of lines. Instead, we suggest assessing an algorithm's results relative to an optimal polygon, and describe a measure which combines the relative fidelity and efficiency of a curve segmentation. We use this measure to compare the application of 23 algorithms to a curve first used by Teh and Chin [[37]]; their ISEs are assessed relative to the optimal ISE. In addition, using an example of pose estimation, it is shown how goal-directed evaluation can be used to select an appropriate assessment criterion.
[1] 659 K. Abe, R. Morii, K. Nishida, and T. Kadonaga, "Comparison of Methods for Detecting Corner Points From Digital Curves—A Preliminary Report," Int'l Conf. Document Analysis and Recognition, pp. 954-857, 1993,[2] I.M. Anderson and J.C. Bezdek, "Curvature and Tangential Deflection of Discrete Arcs," Trans. Pattern Analysis and Machine Intelligence, vol. 6, pp. 27-40, 1984,[3] N. Ansari and K.W. Huang, "Non-Parametric Dominant Point Detection," Pattern Recognition, vol. 24, pp. 849-862, 1991.[4] H. Aoyama and M. Kawagoe, "A Piecewise Linear Approximation Method Preserving Visual Feature Points of Original Figures," CVGIP: Graphical Models and Image Processing, vol. 53, pp. 435-446, 1991.[5] C. Arcelli and G. Ramella, "Finding Contour-Based Abstractions of Planar Patterns," Pattern Recognition, vol. 26, pp. 1,563-1,577, 1993.[6] S. Banerjee, W. Niblack, and M. Flickner, "A Minimum Description Length Polygonal Approximation Method," Technical Report no. RJ 10007, IBM Research Division, 1996.[7] P.C. Chung, C.T. Tsai, and Y.N. Sun, "Polygonal Approximation Using a Competitive Hopfield Neural Network," Pattern Recognition, vol. 27, pp. 1,505-1,512, 1994.[8] A. Deguchi, "Regularized Polygonal Approximation for Analysis and Interpretation of Planar Contour Figures," Int'l Conf. Pattern Recognition, vol. 1, pp. 865-869, 1990.[9] D.H. Douglas and T.K. Peucker, "Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature," The Canadian Cartographer, vol. 10, pp. 111-122, 1973.[10] J.G. Dunham, "Optimum Uniform Piecewise Linear Approximation of Planar Curves," Trans. Pattern Analysis and Machine Intelligence, vol. 8, pp. 67-75, 1986.[11] M.A. Fischler and H.C. Wolf,“Locating perceptually salient points on planar curves,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 2, pp. 113-129, 1994.[12] H. Freeman and L.S. Davis, "A Corner-Finding Algorithm for Chain-Coded Curves," IEEE Trans. Computers, vol. 26, pp. 297-303, 1977.[13] F. Gritzali and G. Papakonstantinou, "A Fast Piecewise Linear Approximation Algorithm," Signal Processing, vol. 5, pp. 221-227, 1983.[14] R.M. Haralick, "Performance Characterization in Image Analysis: Thinning, a Case in Point," Pattern Recognition Letters, vol. 13, pp. 5-12, 1992.[15] A. Held, K. Abe, and C. Arcelli, "Towards a Hierarchical Contour Description via Dominant Point Detection," IEEE Trans. Sys., Man, and Cybernetics, vol. 24, pp. 942-949, 1994.[16] T. Kadonaga and K. Abe, "Comparison of Methods for Detecting Corner Points From Digital Curves," Int'l Workshop on Graphics Recognition, pp. 3-12, 1995.[17] T. Kanungo, M.Y. Jaisimha, and R.M. Haralick, "A Methodology for Quantitative Performance Evaluation of Detection Algorithms," IEEE Trans. Image Processing, vol. 4, pp. 1,667-1,674, Dec. 1995.[18] J. Koplowitz and S. Plante, "Corner Detection for Chain Coded Curves," Pattern Recognition, vol. 28, pp. 843-852, 1995.[19] D.G. Lowe, "Three-Dimensional Object Recognition From Single Two-Dimensional Images," Artificial Intelligence, vol. 31, pp. 355-395, 1987.[20] T. Melen and T. Ozanian, "A Fast Algorithm for Dominant Point Detection on Chain-Coded Contours," Proc. Fifth Int'l Conf. Computer Analysis of Images and Patterns, 1993.[21] U. Montanari, "A Note on Minimal Length Polygonal Approximation to a Digitized Curve," Comm. ACM, vol. 13, pp. 41-47, 1970.[22] H. Ogawa, "Corner Detection on Digital Curves Based on Local Symmetry of the Shape," Pattern Recognition, vol. 22, pp. 351-357, 1989.[23] J.C. Perez and E. Vidal, "Optimum Polygonal Approximation of Digitized Curves," Pattern Recognition Letters, vol. 15, pp. 743-750, 1994.[24] T.Y. Phillips and A. Rosenfeld, "A Method of Curve Partitioning Using Arc-Chord Distance," Pattern Recognition Letters, vol. 5, pp. 285-288, 1987.[25] U. Ramer, "An Iterative Procedure for the Polygonal Approximation of Plane Curves," Computer, Graphics and Image Processing, vol. 1, pp. 244-256, 1972.[26] A. Rattarangsi and R.T. Chin,“Scale-based detection of corners of planar curves,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 4, pp. 430-449, 1992.[27] B.K. Ray and K.S. Ray, "An Algorithm for Detection of Dominant Points and Polygonal Approximation of Digitized Curves," Pattern Recognition Letters, vol. 12, pp. 849-856, 1992.[28] B.K. Ray and K.S. Ray, "Detection of Significant Points and Polygonal Approximation of Digitized Curves," Pattern Recognition Letters, vol. 12, pp. 443-452, 1992.[29] A. Rosenfeld and E. Johnston, "Angle Detection on Digital Curves," IEEE Trans. Computers, vol. 22, pp. 875-878, 1973.[30] A. Rosenfeld and J.S. Weszka, "An Improved Method of Angle Detection on Digital Curves," IEEE Trans. Computers, vol. 24, pp. 940-941, 1975.[31] P.L. Rosin, "Techniques for Assessing Polygonal Approximations of Curves," Technical Report no. CSTR-96-3, Brunel University, 1996.[32] P.L. Rosin, "Representing Curves at Their Natural Scales," Pattern Recognition, vol. 25, pp. 1,315-1,325, 1992.[33] P.L. Rosin and G.A.W. West, “Nonparametric Segmentation of Curves into Various Representations,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 1,140-1,153, 1995.[34] P.V. Sankar and C.V. Sharma, "A Parallel Procedure for the Detection of Dominant Points on a Digital Curve," Computer, Graphics and Image Processing, vol. 7, pp. 403-412, 1978.[35] D. Sarkar, "A Simple Algorithm for Detection of Significant Vertices for Polygonal Approximation of Chain-Coded Curves," Pattern Recognition Letters, vol. 14, pp. 959-964, 1993.[36] Y. Sato, "Piecewise Linear Approximation of Plane Curves by Perimeter Optimization," Pattern Recognition, vol. 25, pp. 1,535-1,543, 1992.[37] C.H. Teh and R.T. Chin, “On the Detection of Dominant Points on Digital Curves,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 859-872, 1989.[38] O.D. Trier and A.K. Jain, "Goal-Directed Evaluation of Binarization Methods," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 1,191-1,201, 1995.[39] J.A. Ventura and J.M. Chen, "Segmentation of Two-Dimensional Curve Contours," Pattern Recognition, vol. 25, pp. 1,129-1,140, 1992.[40] K. Wall and P.E. Danielsson, "A Fast Sequential Method for Polygonal Approximation of Digitized Curves," Computer Vision, Graphics and Image Processing, vol. 28, pp. 220-227, 1984.[41] C.M. Williams, "An Efficient Algorithm for the Piecewise Linear Approximation of Planar Curves," Computer, Graphics and Image Processing, vol. 8, pp. 286-293, 1978.[42] X. Zhang, R.M. Haralick, and V. Ramesh, "Corner Detection Using the MAP Technique," Proc. 12th Int'l Conf. Pattern Recognition, pp. 549-551, 1994.
Index Terms:
Polygonal approximation, assessment, optimal breakpoints, dynamic programming.
Citation:
Paul L. Rosin, "Techniques for Assessing Polygonal Approximations of Curves," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 6, pp. 659-666, June 1997, doi:10.1109/34.601253
