Multigrid-convergence of digital curvature estimators

Lachaud, Jacques-Olivier

Actes des rencontres du CIRM, Tome 3 (2013) no. 1, pp. 171-181.

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.

Classification : 52Cxx
Mots clés : Discrete geometry, digital curvature, geometric estimation

[1] Alliez, P.; Cohen-Steiner, D.; Tong, Y.; Desbrun, M. Voronoi-based variational reconstruction of unoriented point sets, Symposium on Geometry processing, Volume 7 (2007), pp. 39-48

[2] Amenta, N.; Bern, M.; Kamvysselis, M. A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM (1998), pp. 415-421

[3] Bobenko, A. I.; Suris, Y. B. Discrete differential geometry: Integrable structure, 98, AMS Bookstore, 2008 | Zbl

[4] Bretin, E.; Lachaud, J.-O.; Oudet, É. Regularization of Discrete Contour by Willmore Energy, Journal of Mathematical Imaging and Vision, Volume 40 (2011), pp. 214-229 | DOI | MR | Zbl

[5] Cazals, F.; Pouget, M. 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] Clarenz, U.; Rumpf, M.; Telea, A. 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] Coeurjolly, D.; Lachaud, J.-O.; Levallois, J. Integral based Curvature Estimators in Digital Geometry, Discrete Geometry for Computer Imagery (LNCS), Springer (2013) no. 7749, pp. 215-227 | DOI | Zbl

[8] Coeurjolly, D.; Lachaud, J.-O.; Levallois, J. Multigrid Convergent Principal Curvature Estimators in Digital Geometry, Computer Vision and Image Understanding (2014) (Submitted, minor revision.) | DOI

[9] Coeurjolly, D.; Lachaud, J.-O.; Roussillon, T. Multigrid convergence of discrete geometric estimators, Digital Geometry Algorithms, Theoretical Foundations and Applications of Computational Imaging (Brimkov, V.; Barneva, R., eds.) (Lecture Notes in Computational Vision and Biomechanics), Volume 2, Springer, 2012, pp. 395-424 | MR | Zbl

[10] Cohen-Steiner, D.; Morvan, J.-M. Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry (SCG’03), ACM, New York, NY, USA (2003), pp. 312-321 http://doi.acm.org/10.1145/777792.777839 | DOI | Zbl

[11] Cohen-Steiner, D.; Morvan, J.-M. 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] de Vieilleville, F.; Lachaud, J.-O.; Feschet, F. 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] Desbrun, M.; Hirani, A. N.; Leok, M.; Marsden, J. E. Discrete exterior calculus, arXiv preprint math/0508341 (2005)

[14] DGtal: Digital Geometry tools and algorithms library (http://libdgtal.org)

[15] Esbelin, H.-A.; Malgouyres, R.; Cartade, C. 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] Federer, H. Curvature measures, Trans. Amer. Math. Soc, Volume 93 (1959) no. 3, pp. 418-491 | DOI | MR | Zbl

[17] Fourey, S.; Malgouyres, R. Normals and Curvature Estimation for Digital Surfaces Based on Convolutions, Discrete Geometry for Computer Imagery (LNCS), Springer (2008), pp. 287-298 | DOI | Zbl

[18] Gatzke, T. D.; Grimm, C. M. 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] Kerautret, B.; Lachaud, J.-O. Robust estimation of curvature along digital contours with global optimization, Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI’2008), Lyon, France (Coeurjolly, D.; Sivignon, I.; Tougne, L.; Dupont, F., eds.) (LNCS), Volume 4992, Springer (2008), pp. 334-345 http://www.lama.univ-savoie.fr/~lachaud/Publications/LACHAUD-JO/publications.html#Kerautret08a | DOI | Zbl

[20] Kerautret, B.; Lachaud, J.-O. 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] Kerautret, B.; Lachaud, J.-O.; Naegel, B. 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] Klette, R.; Rosenfeld, A. Digital Geometry: Geometric Methods for Digital Picture Analysis, Series in Computer Graphics and Geometric Modelin, Morgan Kaufmann, 2004 | Zbl

[23] Klette, R.; Žunić, J. 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] Lachaud, J.-O. 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] Lachaud, J-O; Taton, Benjamin Deformable model with a complexity independent from image resolution, Computer Vision and Image Understanding, Volume 99 (2005) no. 3, pp. 453-475 | DOI

[26] Lachaud, J.-O.; Vialard, A.; de Vieilleville, F. 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] Lenoir, A. Fast estimation of mean curvature on the surface of a 3D discrete object, Proc. Discrete Geometry for Computer Imagery (DGCI’97) (Ahronovitz, E.; Fiorio, C., eds.) (Lecture Notes in Computer Science), Volume 1347, Springer Berlin Heidelberg, 1997, pp. 175-186 | DOI

[28] Levallois, J.; Coeurjolly, D.; Lachaud, J.-O. Parameter-free and Multigrid Convergent Digital Curvature Estimators, Discrete Geometry for Computer Imagery (2014) (Submitted.) | Zbl

[29] Malgouyres, R.; Brunet, F.; Fourey, S. Binomial Convolutions and Derivatives Estimation from Noisy Discretizations, Discrete Geometry for Computer Imagery (LNCS), Volume 4992, Springer (2008), pp. 370-379 | DOI | MR | Zbl

[30] Mérigot, Q.; Ovsjanikov, M.; Guibas, L. Robust Voronoi-based curvature and feature estimation, 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling (SPM’09), ACM, New York, NY, USA (2009), pp. 1-12 http://doi.acm.org/10.1145/1629255.1629257

[31] Mérigot, Q.; Ovsjanikov, M.; Guibas, L. 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] Monga, O.; Benayoun, S. 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] Osher, S.; Paragios, N. Geometric level set methods in imaging, vision, and graphics, Springer, 2003 | Zbl

[34] Pottmann, H.; Wallner, J.; Huang, Q.; Yang, Y. Integral invariants for robust geometry processing, Computer Aided Geometric Design, Volume 26 (2009) no. 1, pp. 37-60 | DOI | MR | Zbl

[35] Pottmann, H.; Wallner, J.; Yang, Y.; Lai, Y.; Hu, S. Principal curvatures from the integral invariant viewpoint, Computer Aided Geometric Design, Volume 24 (2007) no. 8-9, pp. 428-442 | DOI | MR | Zbl

[36] Provot, L.; Gérard, Y. Estimation of the Derivatives of a Digital Function with a Convergent Bounded Error, Discrete Geometry for Computer Imagery (LNCS), Springer (2011), pp. 284-295 | DOI | Zbl

[37] Rieger, B.; Timmermans, F. J.; Van Vliet, L. J.; Verbeek, P. W. 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] Roussillon, T.; Lachaud, J.-O. Accurate Curvature Estimation along Digital Contours with Maximal Digital Circular Arcs, Combinatorial Image Analysis, Volume 6636, Springer (2011), pp. 43-55 | DOI | MR | Zbl

[39] Sethian, James Albert 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] Sloboda, F.; Stoer, J. On piecewise linear approximation of planar Jordan curves, J. Comput. Appl. Math., Volume 55 (1994) no. 3, pp. 369-383 | DOI | MR | Zbl

[41] Surazhsky, T.; Magid, E.; Soldea, O.; Elber, G.; Rivlin, E. 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] Xu, G. 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