Convex Digital Polygons, Maximal Digital Straight Segments and Convergence of Discrete Geometric Estimators

Authors: De Vieilleville, François¹; Lachaud, Jacques-Olivier²; Feschet, Fabien³

Source: Journal of Mathematical Imaging and Vision, Volume 27, Number 2, February 2007 , pp. 139-156(18)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

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. For estimators of local geometric quantities based on Digital Straight Segment (DSS) recognition this problem is closely linked to the asymptotic growth of maximal DSS for which we show bounds both about their number and sizes on Convex Digital Polygons. 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 a conjecture 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 and continued fractions.

Keywords: digital straightness; discrete geometric estimator; convex digital polygon; digital curvature; multigrid convergence

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10851-007-0779-x

Affiliations: 1: Email: devieill@labri.fr 2: Email: lachaud@labri.fr 3: Email: feschet@laic.u-clermont1.fr

Publication date: 2007-02-01