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 . 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.
@article{ACIRM_2013__3_1_171_0, author = {Jacques-Olivier Lachaud}, title = {Multigrid-convergence of digital curvature estimators}, journal = {Actes des rencontres du CIRM}, pages = {171--181}, publisher = {CIRM}, volume = {3}, number = {1}, year = {2013}, doi = {10.5802/acirm.66}, zbl = {06938614}, language = {en}, url = {https://acirm.centre-mersenne.org/articles/10.5802/acirm.66/} }
TY - JOUR AU - Jacques-Olivier Lachaud TI - Multigrid-convergence of digital curvature estimators JO - Actes des rencontres du CIRM PY - 2013 SP - 171 EP - 181 VL - 3 IS - 1 PB - CIRM UR - https://acirm.centre-mersenne.org/articles/10.5802/acirm.66/ DO - 10.5802/acirm.66 LA - en ID - ACIRM_2013__3_1_171_0 ER -
Jacques-Olivier Lachaud. Multigrid-convergence of digital curvature estimators. Actes des rencontres du CIRM, Volume 3 (2013) no. 1, pp. 171-181. doi : 10.5802/acirm.66. https://acirm.centre-mersenne.org/articles/10.5802/acirm.66/
[1] P. Alliez; D. Cohen-Steiner; Y. Tong; M. Desbrun Voronoi-based variational reconstruction of unoriented point sets, Symposium on Geometry processing, Volume 7 (2007), pp. 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), pp. 415-421
[3] A. I. Bobenko; Y. B. Suris Discrete differential geometry: Integrable structure, 98, AMS Bookstore, 2008 | Zbl
[4] E. Bretin; J.-O. Lachaud; É. Oudet Regularization of Discrete Contour by Willmore Energy, Journal of Mathematical Imaging and Vision, Volume 40 (2011), pp. 214-229 | DOI | MR | Zbl
[5] F. Cazals; M. Pouget Estimating differential quantities using polynomial fitting of osculating jets, Computer Aided Geometric Design, Volume 22 (2005) no. 2, pp. 121-146 | DOI | MR | Zbl
[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, Volume 10 (2004) no. 5, pp. 516-524 | DOI
[7] D. Coeurjolly; J.-O. Lachaud; J. Levallois Integral based Curvature Estimators in Digital Geometry, Discrete Geometry for Computer Imagery (LNCS) (2013) no. 7749, pp. 215-227 | DOI | Zbl
[8] D. Coeurjolly; J.-O. Lachaud; J. Levallois Multigrid Convergent Principal Curvature Estimators in Digital Geometry, Computer Vision and Image Understanding (2014) (Submitted, minor revision.) | DOI
[9] D. Coeurjolly; J.-O. Lachaud; T. Roussillon Multigrid convergence of discrete geometric estimators, Digital Geometry Algorithms, Theoretical Foundations and Applications of Computational Imaging (V. Brimkov; R. Barneva, eds.) (Lecture Notes in Computational Vision and Biomechanics), Volume 2, Springer, 2012, pp. 395-424 | MR | Zbl
[10] D. Cohen-Steiner; J.-M. Morvan Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry (SCG’03) (2003), pp. 312-321 http://doi.acm.org/10.1145/777792.777839 | DOI | Zbl
[11] D. Cohen-Steiner; J.-M. Morvan Second fundamental measure of geometric sets and local approximation of curvatures, Journal of Differential Geometry, Volume 74 (2006) no. 3, pp. 363-394 | DOI | MR | Zbl
[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, Volume 27 (2007) no. 2, pp. 471-502
[13] M. Desbrun; A. N. Hirani; M. Leok; J. E. Marsden Discrete exterior calculus, arXiv preprint math/0508341 (2005)
[14] DGtal: Digital Geometry tools and algorithms library (http://libdgtal.org)
[15] H.-A. Esbelin; R. Malgouyres; C. Cartade Convergence of binomial-based derivative estimation for 2 noisy discretized curves, Theoretical Computer Science, Volume 412 (2011) no. 36, pp. 4805 -4813 | DOI | MR | Zbl
[16] H. Federer Curvature measures, Trans. Amer. Math. Soc, Volume 93 (1959) no. 3, pp. 418-491 | DOI | MR | Zbl
[17] S. Fourey; R. Malgouyres Normals and Curvature Estimation for Digital Surfaces Based on Convolutions, Discrete Geometry for Computer Imagery (LNCS) (2008), pp. 287-298 | DOI | Zbl
[18] T. D. Gatzke; C. M. Grimm Estimating curvature on triangular meshes, International Journal of Shape Modeling, Volume 12 (2006) no. 01, pp. 1-28 http://www.worldscientific.com/doi/abs/10.1142/S0218654306000810 | DOI | Zbl
[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 (LNCS), Volume 4992 (2008), pp. 334-345 http://www.lama.univ-savoie.fr/~lachaud/Publications/LACHAUD-JO/publications.html#Kerautret08a | DOI | Zbl
[20] B. Kerautret; J.-O. Lachaud Curvature estimation along noisy digital contours by approximate global optimization, Pattern Recognition, Volume 42 (2009) no. 10, pp. 2265 -2278 http://www.sciencedirect.com/science/article/B6V14-4V1662J-1/2/bf89b2c4f3cda797a94ad3724bc4ac17 | DOI | Zbl
[21] B. Kerautret; J.-O. Lachaud; B. Naegel Curvature based corner detector for discrete, noisy and multi-scale contours, International Journal of Shape Modeling, Volume 14 (2008) no. 2, pp. 127-145 | DOI | MR | Zbl
[22] R. Klette; A. Rosenfeld Digital Geometry: Geometric Methods for Digital Picture Analysis, Series in Computer Graphics and Geometric Modelin, Morgan Kaufmann, 2004 | Zbl
[23] R. Klette; J. Žunić Multigrid convergence of calculated features in image analysis, Journal of Mathematical Imaging and Vision, Volume 13 (2000) no. 3, pp. 173-191 | DOI | MR | Zbl
[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, Université Bordeaux 1, Talence, France (2006) (Habilitation à Diriger des Recherches)
[25] J-O Lachaud; Benjamin Taton Deformable model with a complexity independent from image resolution, Computer Vision and Image Understanding, Volume 99 (2005) no. 3, pp. 453-475 | DOI
[26] J.-O. Lachaud; A. Vialard; F. de Vieilleville Fast, Accurate and Convergent Tangent Estimation on Digital Contours, Image and Vision Computing, Volume 25 (2007) no. 10, pp. 1572-1587 http://www.lama.univ-savoie.fr/~lachaud/Publications/LACHAUD-JO/publications.html#Lachaud07a | DOI
[27] A. Lenoir Fast estimation of mean curvature on the surface of a 3D discrete object, Proc. Discrete Geometry for Computer Imagery (DGCI’97) (E. Ahronovitz; C. Fiorio, eds.) (Lecture Notes in Computer Science), Volume 1347, Springer Berlin Heidelberg, 1997, pp. 175-186 | DOI
[28] J. Levallois; D. Coeurjolly; J.-O. Lachaud Parameter-free and Multigrid Convergent Digital Curvature Estimators, Discrete Geometry for Computer Imagery (2014) (Submitted.) | Zbl
[29] R. Malgouyres; F. Brunet; S. Fourey Binomial Convolutions and Derivatives Estimation from Noisy Discretizations, Discrete Geometry for Computer Imagery (LNCS), Volume 4992 (2008), pp. 370-379 | DOI | MR | Zbl
[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 (SPM’09) (2009), pp. 1-12 http://doi.acm.org/10.1145/1629255.1629257
[31] Q. Mérigot; M. Ovsjanikov; L. Guibas Voronoi-Based Curvature and Feature Estimation from Point Clouds, Visualization and Computer Graphics, IEEE Transactions on, Volume 17 (2011) no. 6, pp. 743-756 | DOI
[32] O. Monga; S. Benayoun Using partial derivatives of 3D images to extract typical surface features, Computer vision and image understanding, Volume 61 (1995) no. 2, pp. 171-189 | DOI
[33] S. Osher; N. Paragios Geometric level set methods in imaging, vision, and graphics, Springer, 2003 | Zbl
[34] H. Pottmann; J. Wallner; Q. Huang; Y. Yang Integral invariants for robust geometry processing, Computer Aided Geometric Design, Volume 26 (2009) no. 1, pp. 37-60 | DOI | MR | Zbl
[35] H. Pottmann; J. Wallner; Y. Yang; Y. Lai; S. Hu Principal curvatures from the integral invariant viewpoint, Computer Aided Geometric Design, Volume 24 (2007) no. 8-9, pp. 428-442 | DOI | MR | Zbl
[36] L. Provot; Y. Gérard Estimation of the Derivatives of a Digital Function with a Convergent Bounded Error, Discrete Geometry for Computer Imagery (LNCS) (2011), pp. 284-295 | DOI | Zbl
[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, Volume 26 (2004) no. 8, pp. 1088-1094 | DOI
[38] T. Roussillon; J.-O. Lachaud Accurate Curvature Estimation along Digital Contours with Maximal Digital Circular Arcs, Combinatorial Image Analysis, Volume 6636 (2011), pp. 43-55 | DOI | MR | Zbl
[39] James Albert Sethian Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science, 3, Cambridge university press, 1999 | Zbl
[40] F. Sloboda; J. Stoer On piecewise linear approximation of planar Jordan curves, J. Comput. Appl. Math., Volume 55 (1994) no. 3, pp. 369-383 | DOI | MR | Zbl
[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, Volume 1 (2003), pp. 1021-1026 | DOI
[42] G. Xu Convergence analysis of a discretization scheme for Gaussian curvature over triangular surfaces, Computer Aided Geometric Design, Volume 23 (2006) no. 2, pp. 193-207 http://www.sciencedirect.com/science/article/pii/S0167839605000865 | DOI | MR | Zbl
Cited by Sources: