Abstract
With the definition of discrete lines introduced by Réveillès [REV91], there has been a wide range of research in discrete geometry and more precisely on the study of discrete lines. By the use of the linear time segment recognition algorithm of Debled and Réveillès [DR94], Vialard [VIA96a] has proposed a O(l) algorithm for computing the tangent in one point of a discrete curve where l is the average length of the tangent. By applying her algorithm to n points of a discrete curve, the complexity becomes O(n.l). This paper proposes a new approach for computing the tangent. It is based on a precise study of the tangent evolution along a discrete curve. The resulting algorithm has a O(n) complexity and is thus optimal. Some applications in curvature computation and a tombstones contours study are also presented.
Chapter PDF
Similar content being viewed by others
References
I. DEBLED and J.P. REVEILLES. A linear algorithm for segmentation of digital curves. In Third International Workshop on parallel Image Analysis, June 1994.
I. DEBLED-RENNESSON. Étude et reconnaissance de droites et de plans discrets. PhD thesis, Université Louis Pasteur, 1995.
Jean-Marc Chassery et Annick Montanvert. Géométrie discréte en analyse d’images. Editions Hermés, 1991.
J.P. REVEILLES. Géométrie discréte, calcul en nombres entiers et algorithmique. PhD thesis, Université Louis Pasteur, 1991.
A.W.M. SMEULDERS and L. DORST. Decomposition of discrete curves into piecewise straight segments in linear time. Contemporary Mathematics, 119:169–195, 1991.
CHO-HUAK TEH and ROLAND T. CHIN. On the detection of dominant points on digital curves. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(8):859–872, August 1989.
ANNE VIALARD. Chemins Euclidiens: un modèle de représentation des contours discrets. PhD thesis, Université Bordeaux I, 1996.
ANNE VIALARD. Geometrical parameters extraction from discrete paths. In 6th International workshop DGCI. Springer, 1996.
MARCEL WORRING and ARNOLD W.M. SMEULDERS. Digital curve estimation. CVGIP: Image Understanding, 58(3):366–382, 1993.
MARCEL WORRING and ARNOLD W.M. SMEULDERS. Digitized circular arcs: Characterization and parameter estimation. IEEE PAMI, 17(6):587–598, jun 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feschet, F., Tougne, L. (1999). Optimal Time Computation of the Tangent of a Discrete Curve: Application to the Curvature. In: Bertrand, G., Couprie, M., Perroton, L. (eds) Discrete Geometry for Computer Imagery. DGCI 1999. Lecture Notes in Computer Science, vol 1568. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49126-0_3
Download citation
DOI: https://doi.org/10.1007/3-540-49126-0_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65685-2
Online ISBN: 978-3-540-49126-2
eBook Packages: Springer Book Archive