Maximal digital straight segments and convergence of discrete geometric estimators

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 curvature estimator. The proof involves results from arithmetic properties of digital lines, digital convexity, combinatorics, continued fractions and random polytopes.

Publication
Proc. 14th Scandinavian Conference on Image Analysis (SCIA'2005), Joensuu, Finland, volume 3540 of Lecture Notes in Computer Science, pp 988–1003, 2005. Springer
Jacques-Olivier Lachaud
Jacques-Olivier Lachaud
Professor of Computer Science

My research interests include digital geometry, geometry processing, image analysis, variational models and discrete calculus.