# Multigrid-convergence of digital curvature estimators

Jacques-Olivier Lachaud^{[1]}

- [1] Univ. Savoie, LAMA, F-73000 Chambéry, France — CNRS, LAMA, F-73000 Chambéry, France

Actes des rencontres du CIRM (2013)

- Volume: 3, Issue: 1, page 171-181
- ISSN: 2105-0597

## Access Full Article

top## Abstract

top## How to cite

topLachaud, Jacques-Olivier. "Multigrid-convergence of digital curvature estimators." Actes des rencontres du CIRM 3.1 (2013): 171-181. <http://eudml.org/doc/275410>.

@article{Lachaud2013,

abstract = {Many methods have been proposed to estimate differential geometric quantities like curvature(s) on discrete data. A common characteristics is that they require (at least) one user-given scale or window parameter, which smoothes data to take care of both the sampling rate and possible perturbations. Digital shapes are specific discrete approximation of Euclidean shapes, which come from their digitization at a given grid step. They are thus subsets of the digital plane $\{\mathbb\{Z\}\}^d$. A digital geometric estimator is called multigrid convergent whenever the estimated quantity tends towards the expected geometric quantity as the grid step gets finer and finer. The problem is then: can we define curvature estimators that are multigrid convergent without such user-given parameter ? If so, what speed of convergence can we achieve ? We review here three digital curvature estimators that aim at this objective: a first one based on maximal digital circular arc, a second one using a global optimization procedure, a third one that is a digital counterpart to integral invariants and that works on 2D and 3D shapes. We close the exposition by a discussion about their respective properties and their ability to measure curvatures on gray-level images.},

affiliation = {Univ. Savoie, LAMA, F-73000 Chambéry, France — CNRS, LAMA, F-73000 Chambéry, France},

author = {Lachaud, Jacques-Olivier},

journal = {Actes des rencontres du CIRM},

keywords = {Discrete geometry; digital curvature; geometric estimation},

language = {eng},

month = {11},

number = {1},

pages = {171-181},

publisher = {CIRM},

title = {Multigrid-convergence of digital curvature estimators},

url = {http://eudml.org/doc/275410},

volume = {3},

year = {2013},

}

TY - JOUR

AU - Lachaud, Jacques-Olivier

TI - Multigrid-convergence of digital curvature estimators

JO - Actes des rencontres du CIRM

DA - 2013/11//

PB - CIRM

VL - 3

IS - 1

SP - 171

EP - 181

AB - Many methods have been proposed to estimate differential geometric quantities like curvature(s) on discrete data. A common characteristics is that they require (at least) one user-given scale or window parameter, which smoothes data to take care of both the sampling rate and possible perturbations. Digital shapes are specific discrete approximation of Euclidean shapes, which come from their digitization at a given grid step. They are thus subsets of the digital plane ${\mathbb{Z}}^d$. A digital geometric estimator is called multigrid convergent whenever the estimated quantity tends towards the expected geometric quantity as the grid step gets finer and finer. The problem is then: can we define curvature estimators that are multigrid convergent without such user-given parameter ? If so, what speed of convergence can we achieve ? We review here three digital curvature estimators that aim at this objective: a first one based on maximal digital circular arc, a second one using a global optimization procedure, a third one that is a digital counterpart to integral invariants and that works on 2D and 3D shapes. We close the exposition by a discussion about their respective properties and their ability to measure curvatures on gray-level images.

LA - eng

KW - Discrete geometry; digital curvature; geometric estimation

UR - http://eudml.org/doc/275410

ER -

## References

top- P. Alliez, D. Cohen-Steiner, Y. Tong, M. Desbrun, Voronoi-based variational reconstruction of unoriented point sets, Symposium on Geometry processing 7 (2007), 39-48
- N. Amenta, M. Bern, M. Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques (1998), 415-421
- A. I. Bobenko, Y. B. Suris, Discrete differential geometry: Integrable structure, 98 (2008), AMS Bookstore Zbl1158.53001
- E. Bretin, J.-O. Lachaud, É. Oudet, Regularization of Discrete Contour by Willmore Energy, Journal of Mathematical Imaging and Vision 40 (2011), 214-229 Zbl1255.68212
- F. Cazals, M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Computer Aided Geometric Design 22 (2005), 121-146 Zbl1084.65017
- U. Clarenz, M. Rumpf, A. Telea, Robust feature detection and local classification for surfaces based on moment analysis, Visualization and Computer Graphics, IEEE Transactions on 10 (2004), 516-524
- D. Coeurjolly, J.-O. Lachaud, J. Levallois, Integral based Curvature Estimators in Digital Geometry, Discrete Geometry for Computer Imagery (2013), 215-227, Springer Zbl06169461
- D. Coeurjolly, J.-O. Lachaud, J. Levallois, Multigrid Convergent Principal Curvature Estimators in Digital Geometry, Computer Vision and Image Understanding (2014) Zbl06344589
- D. Coeurjolly, J.-O. Lachaud, T. Roussillon, Multigrid convergence of discrete geometric estimators, Digital Geometry Algorithms, Theoretical Foundations and Applications of Computational Imaging 2 (2012), 395-424, BrimkovV.V. Zbl1251.68294
- D. Cohen-Steiner, J.-M. Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry (2003), 312-321, ACM, New York, NY, USA
- D. Cohen-Steiner, J.-M. Morvan, Second fundamental measure of geometric sets and local approximation of curvatures, Journal of Differential Geometry 74 (2006), 363-394 Zbl1107.49029
- F. de Vieilleville, J.-O. Lachaud, F. Feschet, Maximal digital straight segments and convergence of discrete geometric estimators, Journal of Mathematical Image and Vision 27 (2007), 471-502
- M. Desbrun, A. N. Hirani, M. Leok, J. E. Marsden, Discrete exterior calculus, arXiv preprint math/0508341 (2005) Zbl1080.39021
- DGtal: Digital Geometry tools and algorithms library
- H.-A. Esbelin, R. Malgouyres, C. Cartade, Convergence of binomial-based derivative estimation for 2 noisy discretized curves, Theoretical Computer Science 412 (2011), 4805-4813 Zbl1234.68449
- H. Federer, Curvature measures, Trans. Amer. Math. Soc 93 (1959), 418-491 Zbl0089.38402
- S. Fourey, R. Malgouyres, Normals and Curvature Estimation for Digital Surfaces Based on Convolutions, Discrete Geometry for Computer Imagery (2008), 287-298, Springer Zbl1138.68593
- T. D. Gatzke, C. M. Grimm, Estimating curvature on triangular meshes, International Journal of Shape Modeling 12 (2006), 1-28 Zbl1095.53004
- B. Kerautret, J.-O. Lachaud, Robust estimation of curvature along digital contours with global optimization, Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI’2008), Lyon, France 4992 (2008), 334-345, Springer Zbl1138.68600
- B. Kerautret, J.-O. Lachaud, Curvature estimation along noisy digital contours by approximate global optimization, Pattern Recognition 42 (2009), 2265-2278 Zbl1192.68581
- B. Kerautret, J.-O. Lachaud, B. Naegel, Curvature based corner detector for discrete, noisy and multi-scale contours, International Journal of Shape Modeling 14 (2008), 127-145 Zbl1189.68159
- R. Klette, A. Rosenfeld, Digital Geometry: Geometric Methods for Digital Picture Analysis, (2004), Morgan Kaufmann Zbl1064.68090
- R. Klette, J. Žunić, Multigrid convergence of calculated features in image analysis, Journal of Mathematical Imaging and Vision 13 (2000), 173-191 Zbl0969.68167
- J.-O. Lachaud, Espaces non-euclidiens et analyse d’image : modèles déformables riemanniens et discrets, topologie et géométrie discrète, (2006)
- J-O Lachaud, Benjamin Taton, Deformable model with a complexity independent from image resolution, Computer Vision and Image Understanding 99 (2005), 453-475
- J.-O. Lachaud, A. Vialard, F. de Vieilleville, Fast, Accurate and Convergent Tangent Estimation on Digital Contours, Image and Vision Computing 25 (2007), 1572-1587
- A. Lenoir, Fast estimation of mean curvature on the surface of a 3D discrete object, Proc. Discrete Geometry for Computer Imagery (DGCI’97) 1347 (1997), 175-186, AhronovitzE.E.
- J. Levallois, D. Coeurjolly, J.-O. Lachaud, Parameter-free and Multigrid Convergent Digital Curvature Estimators, Discrete Geometry for Computer Imagery (2014) Zbl06344589
- R. Malgouyres, F. Brunet, S. Fourey, Binomial Convolutions and Derivatives Estimation from Noisy Discretizations, Discrete Geometry for Computer Imagery 4992 (2008), 370-379, Springer Zbl1138.68603
- Q. Mérigot, M. Ovsjanikov, L. Guibas, Robust Voronoi-based curvature and feature estimation, 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling (2009), 1-12, ACM, New York, NY, USA
- Q. Mérigot, M. Ovsjanikov, L. Guibas, Voronoi-Based Curvature and Feature Estimation from Point Clouds, Visualization and Computer Graphics, IEEE Transactions on 17 (2011), 743-756
- O. Monga, S. Benayoun, Using partial derivatives of 3D images to extract typical surface features, Computer vision and image understanding 61 (1995), 171-189
- S. Osher, N. Paragios, Geometric level set methods in imaging, vision, and graphics, (2003), Springer Zbl1027.68137
- H. Pottmann, J. Wallner, Q. Huang, Y. Yang, Integral invariants for robust geometry processing, Computer Aided Geometric Design 26 (2009), 37-60 Zbl1205.53012
- H. Pottmann, J. Wallner, Y. Yang, Y. Lai, S. Hu, Principal curvatures from the integral invariant viewpoint, Computer Aided Geometric Design 24 (2007), 428-442 Zbl1171.65350
- L. Provot, Y. Gérard, Estimation of the Derivatives of a Digital Function with a Convergent Bounded Error, Discrete Geometry for Computer Imagery (2011), 284-295, Springer Zbl1272.90028
- B. Rieger, F. J. Timmermans, L. J. Van Vliet, P. W. Verbeek, On curvature estimation of ISO surfaces in 3D gray-value images and the computation of shape descriptors, Pattern Analysis and Machine Intelligence, IEEE Transactions on 26 (2004), 1088-1094
- T. Roussillon, J.-O. Lachaud, Accurate Curvature Estimation along Digital Contours with Maximal Digital Circular Arcs, Combinatorial Image Analysis 6636 (2011), 43-55, Springer Zbl1330.68314
- James Albert Sethian, Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science, 3 (1999), Cambridge university press Zbl0973.76003
- F. Sloboda, J. Stoer, On piecewise linear approximation of planar Jordan curves, J. Comput. Appl. Math. 55 (1994), 369-383 Zbl0823.65017
- T. Surazhsky, E. Magid, O. Soldea, G. Elber, E. Rivlin, A comparison of Gaussian and mean curvatures estimation methods on triangular meshes, Robotics and Automation, 2003. Proceedings. ICRA ’03. IEEE International Conference on 1 (2003), 1021-1026
- G. Xu, Convergence analysis of a discretization scheme for Gaussian curvature over triangular surfaces, Computer Aided Geometric Design 23 (2006), 193-207 Zbl1083.65024

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.