| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Comparative Evaluation of Length Estimators of Digital Curves
February 2004 (vol. 26 no. 2)
pp. 252-257
Abstract—This paper compares previously published length estimators in image analysis having digitized curves as input. The evaluation uses multigrid convergence (theoretical results and measured speed of convergence) and further measures as criteria. This paper also suggests a new gradient-based method for length estimation, and combines a previously proposed length estimator for straight segments with a polygonalization method.
[1] H. Freeman, Techniques for the Digital Computer Analysis of Chain-Encoded Arbitrary Plane Curves Proc. Nat'l Electronics Conf., vol. 17, pp. 421-432, 1961.
[2] A. Rosenfeld, Digital Straight Line Segments IEEE Trans. Computers, vol. 23, pp. 1264-1269, 1974.
[3] J. Sklansky and D.F. Kibler, A Theory of Nonuniformly Digitized Binary Pictures IEEE Trans. Systems, Man, and Cybernetics, vol. 6, pp. 637-647, 1976.
[4] T.J. Ellis, D. Proffitt, D. Rosen, and W. Rutkowski, Measurement of the Lengths of Digitized Curved Lines Computer Graphics and Image Processing, vol. 10, pp. 333-347, 1979.
[5] A. Hübler, R. Klette, and K. Voss, Determination of the Convex Hull of a Finite Set of Planar Points within Linear Time EIK (Elektronische Informationsverarb. Kybernetik), vol. 17, pp. 121-140, 1981.
[6] E. Creutzburg, A. Hübler, and V. Wedler, On-Line Erkennung Digitaler Geradensegmente in Linearer Zeit Proc. GEOBILD '82, pp. 48-65, 1982.
[7] C.E. Kim, On Cellular Straight Line Segments Computer Graphics and Image Processing, vol. 18, pp. 369-391, 1982.
[8] L.D. Wu, On the Chain Code of a Line IEEE Trans. Pattern Analysis Machine Intelligence, vol. 4, pp. 347-353, 1982.
[9] A.M. Vossepoel and A.W.M. Smeulders, Vector Code Probabilities and Metrication Error in the Representation of Straight Lines of Finite Length Computer Graphics and Image Processing, vol. 20, pp. 347-364, 1982.
[10] B.L. van der Waerden, Geometry and Algebra in Ancient Civilizations. Berlin: Springer, 1983.
[11] T.A. Anderson and C.E. Kim, Representation of Digital Line Segments and Their preimages Computer Vision, Graphics, Image Processing, vol. 30, pp. 279-288, 1985.
[12] G. Borgefors, Distance Transformations in Digital Images Computer Vision, Graphics, and Image Processing, vol. 34, pp. 344-371, 1986.
[13] L. Dorst and A.W.M. Smeulders, Length Estimators for Digitized Contours Computer Vision, Graphics, and Image Processing, vol. 40, pp. 311-333, 1987.
[14] J. Koplowitz and A.M. Bruckstein,“Design of perimeter estimators for digitized planar shapes,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 611-622, 1989.
[15] V.A. Kovalevsky, New Definition and Fast Recognition of Digital Straight Segments and Arcs Proc. 10th Int'l Conf. Pattern Recognition (ICPR '90), vol. 2, pp. 31-34, 1990.
[16] L. Dorst and A.W.M. Smeulders, Discrete Straight Line Segments: Parameters, Primitives, and Properties Contemporary Math., R. Melter, P. Bhattacharya, and A. Rosenfeld, eds., vol. 119, pp. 45-62, 1991.
[17] J.-P. Reveillès, Géométrie Discrète, Calcul en Nombres Entiers et Algorithmique Thèse d'état, Univ. Louis Pasteur, Strasbourg, 1991.
[18] B. Verwer, Local Distances for Distance Transformations in Two and Three Dimensions Pattern Recognition Letters, vol. 12, pp. 671-682, 1991.
[19] V. Kovalevsky and S. Fuchs, Theoretical and Experimental Analysis of the Accuracy of Perimeter Estimates Robust Computer Vision, Wichmann, Karlsruhe, pp. 218-242, 1992.
[20] I. Debled-Rennesson and J. Reveillès, A Linear Algorithm for Segmentation of Digital Curves Int'l J. Pattern Recognition and Artificial Intelligence, vol. 9, pp. 635-662, 1995.
[21] J. Françon, J.-M. Schramm, and M. Tajine, Recognizing Arithmetic Straight Lines and Planes Proc. Sixth Int'l Workshop Discrete Geometry for Computer Imagery, pp. 141-150, 1996.
[22] F. Sloboda and B. Zatko, On One-Dimensional Grid Continua in$R^2$ technical report, Inst. of Control Theory and Robotics, Bratislava, 1996.
[23] A. Vialard, Geometrical Parameters Extraction from Discrete Paths Discrete Geometry for Computer Imagery, pp. 24-35, 1996.
[24] A. Jonas and N. Kiryati, Length Estimation in 3-D Using Cube Quantization J. Math. Imaging and Vision, vol. 8, pp. 215-238, 1998.
[25] F. Sloboda, B. Zatko, and J. Stoer, On Approximation of Planar One-Dimensional Continua Advances in Digital and Computational Geometry, R. Klette, A. Rosenfeld, and F. Sloboda, eds., pp. 113-160, 1998.
[26] F. Feschet and L. Tougne, Optimal Time Computation of the Tangent of a Discrete Curve: Application to the Curvature Discrete Geometry for Computer Imagery, pp. 31-40, 1999.
[27] R. Klette, V. Kovalevsky, and B. Yip, Length Estimation of Digital Curves SPIE Proc. Vision Geometry VIII, pp. 117-129, July 1999. (expanded version available: Machine Graphics&Vision, vol. 9, pp. 673-703, 2000.)
[28] T. Asano, Y. Kawamura, R. Klette, and K. Obokata, A New Approximation Scheme for Digital Objects and Curve Length Estimations Proc. Image and Vision Computing, pp. 26-31, 2000.
[29] R. Klette and T. Bülow, Minimum-Length Polygons in Simple Cube-Curves Discrete Geometry for Computer Imagery, pp. 467-478, 2000.
[30] R. Klette and J. Zunic, Multigrid Convergence of Calculated Features in Image Analysis J. Math. Imaging Vision, vol. 13, pp. 173-191, 2000.
[31] T. Asano, Y. Kawamura, R. Klette, and K. Obokata, Minimum-Length Polygons in ApproximationSausages Proc. Fourth Int'l Workshop Visual Form, pp. 103-112, 2001.
[32] D. Coeurjolly, I. Debled-Rennesson, and O. Teytaud, Segmentation and Length Estimation of 3D Discrete Curves Proc. Digital and Image Geometry, pp. 299-317, 2001.
[33] D. Coeurjolly and O. Teytaud, Multigrid Convergence of Discrete Differential Estimators: Discrete Tangent and Length Estimation Research Report Laboratoire ERIC, Universite Lumiere Lyon, France, RR-0101,http://eric.univ-lyon2.fr/RRRR-0101.ps.gz , 2001.
[34] R. Klette, Multigrid Convergence of Geometric Features Proc. Digital and Image Geometry, pp. 318-338, 2001.
Index Terms:
Length estimator, digital geometry, curve length, multigrid convergence.
Citation:
David Coeurjolly, Reinhard Klette, "A Comparative Evaluation of Length Estimators of Digital Curves," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 252-257, Jan. 2004, doi:10.1109/TPAMI.2004.1262194
