Abstract
Discrete geometric estimators approach geometric quantities on digitized shapes without any knowledge of the continuous shape. A classical yet difficult problem is to show that an estimator asymptotically converges toward the true geometric quantity as the resolution increases. We study here the convergence of local estimators based on Digital Straight Segment (DSS) recognition. It is closely linked to the asymptotic growth of maximal DSS, for which we show bounds both about their number and sizes. These results not only give better insights about digitized curves but indicate that curvature estimators based on local DSS recognition are not likely to converge. We indeed invalidate an hypothesis which was essential in the only known convergence theorem of a discrete curvature estimator. The proof involves results from arithmetic properties of digital lines, digital convexity, combinatorics, continued fractions and random polytopes.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Balog, A., Bárány, I.: On the convex hull of the integer points in a disc. In: SCG 1991: Proceedings of the seventh annual symposium on Computational geometry, pp. 162–165. ACM Press, New York (1991)
Berstel, J., De Luca, A.: Sturmian words, lyndon words and trees. Theoret. Comput. Sci. 178(1-2), 171–203 (1997)
Coeurjolly, D.: Algorithmique et géométrie pour la caractérisation des courbes et des surfaces. PhD thesis, Universit’́e Lyon 2, Décembre (2002)
Coeurjolly, D., Klette, R.: A comparative evaluation of length estimators of digital curves. IEEE Trans. on Pattern Anal. and Machine Intell. 26(2), 252–257 (2004)
Kim, C.E.: Digital convexity, straightness, and convex polygons. IEEE Trans. on Pattern Anal. and Machine Intell. 6(6), 618–626 (1982)
Lachaud, J.-O., de Vieilleville, F., Feschet, F.: Maximal digital straight segments and convergence of discrete geometric estimators. Research Report 1350-05, LaBRI, University Bordeaux 1, Talence, France (2005)
Feschet, F., Tougne, L.: Optimal time computation of the tangent of a discrete curve: application to the curvature. In: Bertrand, G., Couprie, M., Perroton, L. (eds.) DGCI 1999. LNCS, vol. 1568, pp. 31–40. Springer, Heidelberg (1999)
Feschet, F., Tougne, L.: On the Min DSS Problem of Closed Discrete Curves. In: Del Lungo, A., Di Gesù, V., Kuba, A. (eds.) IWCIA. Electonic Notes in Discrete Math., vol. 12. Elsevier, Amsterdam (2003)
Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers, 4th edn. Oxford University Press, Oxford (1960)
Hayes, A.S., Larman, D.C.: The vertices of the knapsack polytope. Discrete Applied Mathematics 6, 135–138 (1983)
Klette, R., Žunić, J.: Multigrid convergence of calculated features in image analysis. Journal of Mathematical Imaging and Vision 13, 173–191 (2000)
Kovalevsky, V., Fuchs, S.: Theoretical and experimental analysis of the accuracy of perimeter estimates. In: Förster, R. (ed.) Proc. Robust Computer Vision, pp. 218–242 (1992)
Lachaud, J.-O.: On the convergence of some local geometric estimators on digitized curves. Research Report 1347-05, LaBRI, University Bordeaux 1, Talence, France (2005)
Lachaud, J.-O., Vialard, A., de Vieilleville, F.: Analysis and comparative evaluation of discrete tangent estimators (To appear). In: Andrès, É., Damiand, G., Lienhardt, P. (eds.) DGCI 2005. LNCS, vol. 3429, pp. 240–251. Springer, Heidelberg (2005)
Réveillès, J.-P.: Géométrie discrète, calcul en nombres entiers et algorithmique. Thèse d’etat, Université Louis Pasteur, Strasbourg (1991)
Shevchenko, V.N.: On the number of extreme points in linear programming. Kibernetika 2, 133–134 (1981) (In russian)
Voss, K.: Discrete Images, Objects, and Functions in ℤn. Springer, Heidelberg (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Vieilleville, F., Lachaud, JO., Feschet, F. (2005). Maximal Digital Straight Segments and Convergence of Discrete Geometric Estimators. In: Kalviainen, H., Parkkinen, J., Kaarna, A. (eds) Image Analysis. SCIA 2005. Lecture Notes in Computer Science, vol 3540. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11499145_100
Download citation
DOI: https://doi.org/10.1007/11499145_100
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26320-3
Online ISBN: 978-3-540-31566-7
eBook Packages: Computer ScienceComputer Science (R0)