Asymptotic analysis of discrete normals and curvatures of polylines

ABSTRACT

Accurate estimations of geometric properties of a smooth curve from its discrete approximation are important for many computer graphics and computer vision applications. To assess and improve the quality of such an approximation, we assume that the curve is known in general form. Then we can represent the curve by a Taylor series expansion and compare its geometric properties with the corresponding discrete approximations. In turn we can either prove convergence of these approximations towards the true properties as the edge lengths tend to zero, or we can get hints on how to eliminate the error. In this paper, we propose and study discrete schemes for estimating tangent and normal vectors as well as for estimating curvature and torsion of a smooth 3D curve approximated by a polyline. Thereby we make some interesting findings about connections between (smooth) classical curves and certain estimation schemes for polylines.

REFERENCES

• 1: Anoshkina, E. V., Belyaev, A. G., and Seidel, H.-P. 2002. Asymptotic analysis of three-point approximations of vertex normals and curvatures. In Vision, Modeling, and Visualization 2002, 211--216.
• 2: Belyaev, A. G., Anoshkina, E. V., Yoshizawa, S., and Yano, M. 1999. Polygonal curve evolutions for planar shape modeling and analysis. International Journal of Shape Modeling 5, 2, 195--217.
• 3: Mireille Boutin, Numerically Invariant Signature Curves, International Journal of Computer Vision, v.40 n.3, p.235-248, Dec. 2000 [doi>10.1023/A:1008139427340]
• 4: Cerda, E., Mahadevan, L., and Pasini, J. M. 2004. The elements of draping. Proc. Natl. Acad. Sci. USA 101, 7 (February), 1806--1810.
• 5: Do Carmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall. 503 pages.
• 6: Euler, L. 1744. Additamentum 'De Curvis Elasticis'. In Methodus Inveniendi Lineas Curvas Maximi Minimive Probprietate Gaudentes.
• 7: B. K. P. Horn, The Curve of Least Energy, ACM Transactions on Mathematical Software (TOMS), v.9 n.4, p.441-460, Dec. 1983 [doi>10.1145/356056.356061]
• 8: Jan J. Koenderink, Solid shape, MIT Press, Cambridge, MA, 1990
• 9: Kreyszig, E. 1959. Differential Geometry. University of Toronto Press.
• 10: Mumford, D. 1994. Elastica and computer vision. In Algebraic Geometry and its Applications, C. L. Bajaj, Ed., 491--506.
• 11: Sauer, R. 1970. Differenzengeometrie. Springer, Berlin.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
curvature, discrete approximation, error analysis, frenet frame, normal vector, polyline, tangent vector, torsion