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

Abstract

top
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 ℤ 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.

How to cite

top

Lachaud, 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
  1. 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 
  2. 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 
  3. A. I. Bobenko, Y. B. Suris, Discrete differential geometry: Integrable structure, 98 (2008), AMS Bookstore Zbl1158.53001
  4. 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
  5. F. Cazals, M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Computer Aided Geometric Design 22 (2005), 121-146 Zbl1084.65017
  6. 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 
  7. D. Coeurjolly, J.-O. Lachaud, J. Levallois, Integral based Curvature Estimators in Digital Geometry, Discrete Geometry for Computer Imagery (2013), 215-227, Springer Zbl06169461
  8. D. Coeurjolly, J.-O. Lachaud, J. Levallois, Multigrid Convergent Principal Curvature Estimators in Digital Geometry, Computer Vision and Image Understanding (2014) Zbl06344589
  9. 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
  10. 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 
  11. 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
  12. 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 
  13. M. Desbrun, A. N. Hirani, M. Leok, J. E. Marsden, Discrete exterior calculus, arXiv preprint math/0508341 (2005) Zbl1080.39021
  14. DGtal: Digital Geometry tools and algorithms library 
  15. 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
  16. H. Federer, Curvature measures, Trans. Amer. Math. Soc 93 (1959), 418-491 Zbl0089.38402
  17. 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
  18. T. D. Gatzke, C. M. Grimm, Estimating curvature on triangular meshes, International Journal of Shape Modeling 12 (2006), 1-28 Zbl1095.53004
  19. 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
  20. B. Kerautret, J.-O. Lachaud, Curvature estimation along noisy digital contours by approximate global optimization, Pattern Recognition 42 (2009), 2265-2278 Zbl1192.68581
  21. 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
  22. R. Klette, A. Rosenfeld, Digital Geometry: Geometric Methods for Digital Picture Analysis, (2004), Morgan Kaufmann Zbl1064.68090
  23. R. Klette, J. Žunić, Multigrid convergence of calculated features in image analysis, Journal of Mathematical Imaging and Vision 13 (2000), 173-191 Zbl0969.68167
  24. 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) 
  25. J-O Lachaud, Benjamin Taton, Deformable model with a complexity independent from image resolution, Computer Vision and Image Understanding 99 (2005), 453-475 
  26. 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 
  27. 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. 
  28. J. Levallois, D. Coeurjolly, J.-O. Lachaud, Parameter-free and Multigrid Convergent Digital Curvature Estimators, Discrete Geometry for Computer Imagery (2014) Zbl06344589
  29. 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
  30. 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 
  31. 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 
  32. O. Monga, S. Benayoun, Using partial derivatives of 3D images to extract typical surface features, Computer vision and image understanding 61 (1995), 171-189 
  33. S. Osher, N. Paragios, Geometric level set methods in imaging, vision, and graphics, (2003), Springer Zbl1027.68137
  34. H. Pottmann, J. Wallner, Q. Huang, Y. Yang, Integral invariants for robust geometry processing, Computer Aided Geometric Design 26 (2009), 37-60 Zbl1205.53012
  35. 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
  36. 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
  37. 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 
  38. 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
  39. 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
  40. F. Sloboda, J. Stoer, On piecewise linear approximation of planar Jordan curves, J. Comput. Appl. Math. 55 (1994), 369-383 Zbl0823.65017
  41. 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 
  42. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.