×

Regularization of discrete contour by Willmore energy. (English) Zbl 1255.68212

Summary: We propose a novel approach to reconstruct shapes from digital data. Contrarily to most methods, reconstructed shapes are smooth with a well-defined curvature field and have the same digitization as the input data: the range of application we have in mind is especially post-processing to image segmentation where labelled regions are digital objects. For this purpose, we introduce three new algorithms to regularize digital contours based on the minimization of Willmore energy: our first algorithm is based on tools coming from discrete geometry, the second is related to convex geometry while the third approach is a constrained phase field minimization. The three algorithms are described in details and the convergence of the phase field approach is investigated. We present a comparative evaluation of all three methods, in terms of the accuracy of curvature estimators and computation time.

MSC:

68U10 Computing methodologies for image processing
49Q10 Optimization of shapes other than minimal surfaces
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

KNITRO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alberti, G.: Variational models for phase transitions, an approach via {\(\gamma\)}-convergence. In: Calculus of Variations and Partial Differential Equations, Pisa, 1996, pp. 95–114. Springer, Berlin (2000) · Zbl 0957.35017
[2] Ambrosio, L.: Geometric evolution problems, distance function and viscosity solutions. In: Calculus of Variations and Partial Differential Equations, Pisa, 1996, pp. 5–93. Springer, Berlin (2000) · Zbl 0956.35002
[3] Amenta, N., Bern, M., Eppstein, D.: The crust and the [beta]-skeleton: Combinatorial curve reconstruction. Graph. Models Image Process. 60(2), 125–135 (1998) · doi:10.1006/gmip.1998.0465
[4] Bellettini, G.: Variational approximation of functionals with curvatures and related properties. J. Convex Anal. 4(1), 91–108 (1997) · Zbl 0882.49013
[5] Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C., Taubin, G.: The ball-pivoting algorithm for surface reconstruction. IEEE Trans. Vis. Comput. Graph. 5(4), 349–359 (1999) · Zbl 05108510 · doi:10.1109/2945.817351
[6] Bretin, E.: Mouvement par courbure moyenne et méthode de champ de phase. PhD thesis, Institut polytechnique de Grenoble (2009)
[7] Byrd, R.H., Nocedal, J., Waltz, R.A.: KNITRO: An integrated package for nonlinear optimization. In: Large-Scale Nonlinear Optimization. Nonconvex Optim. Appl., vol. 83, pp. 35–59. Springer, New York (2006) · Zbl 1108.90004
[8] Chan, T.F., Kang, S.H., Shen, J.: Euler’s elastica and curvature-based inpainting. SIAM J. Appl. Math. 63(2), 564–592 (2002) (electronic) · Zbl 1028.68185
[9] Chen, X.: Generation and propagation of interfaces for reaction-diffusion equations. J. Differ. Equ. 96(1), 116–141 (1992) · Zbl 0765.35024 · doi:10.1016/0022-0396(92)90146-E
[10] Chen, X.: Global asymptotic limit of solutions of the Cahn-Hilliard equation. J. Differ. Geom. 44, 262–311 (1996) · Zbl 0874.35045
[11] Chen, L.Q., Shen, J.: Applications of semi-implicit Fourier-spectral method to phase field equations. Comput. Phys. Commun. 108, 147–158 (1998) · Zbl 1017.65533 · doi:10.1016/S0010-4655(97)00115-X
[12] Chen, X., Elliott, C.M., Gardiner, A., Zhao, J.J.: Convergence of numerical solutions to the Allen-Cahn equation. Appl. Anal. 69(1–2), 47–56 (1998) · Zbl 0992.65096
[13] Ciarlet, P.-G.: Introduction à l’Analyse Numérique et à l’Optimisation. Dunod, Paris (1998)
[14] de Vieilleville, F., Lachaud, J.-O., Feschet, F.: Maximal digital straight segments and convergence of discrete geometric estimators. J. Math. Imaging Vis. 27(2), 471–502 (2007)
[15] Du, Q., Liu, C., Ryham, R., Wang, X.: A phase field formulation of the Willmore problem. Nonlinearity 18(3), 1249–1267 (2005) · Zbl 1125.35366 · doi:10.1088/0951-7715/18/3/016
[16] Du, Q., Liu, C., Wang, X.: A phase field approach in the numerical study of the elastic bending energy for vesicle membranes. J. Comput. Phys. 198(2), 450–468 (2004) · Zbl 1116.74384 · doi:10.1016/j.jcp.2004.01.029
[17] Edelsbrunner, H., Mücke, E.P.: Three-dimensional alpha shapes. ACM Trans. Graph. 13, 43–72 (1994) · Zbl 0806.68107 · doi:10.1145/174462.156635
[18] Elliott, C.M.: Approximation of curvature dependent interface motion. In: The State of the Art in Numerical Analysis, York, 1996. Inst. Math. Appl. Conf. Ser. New Ser, vol. 63, pp. 407–440. Oxford Univ. Press, New York (1997)
[19] Evans, L.C., Soner, H.M., Souganidis, P.E.: Phase transitions and generalized motion by mean curvature. Commun. Pure Appl. Math. 45(9), 1097–1123 (1992) · Zbl 0801.35045 · doi:10.1002/cpa.3160450903
[20] Feschet, F., Tougne, L.: Optimal time computation of the tangent of a discrete curve: Application to the curvature. In: Proc. 8th Int. Conf. Discrete Geometry for Computer Imagery (DGCI’99). LNCS, vol. 1568, pp. 31–40. Springer, Berlin (1999)
[21] Fraser, C.G.: Mathematical technique and physical conception in Euler’s investigation of the elastica. Centaurus 34(3), 211–246 (1991) · Zbl 0752.01005 · doi:10.1111/j.1600-0498.1991.tb00695.x
[22] Gaffney, P.W., Powell, M.J.D.: Optimal interpolation. In: Numerical Analysis, Proc. 6th Biennial Dundee Conf., Univ. Dundee, Dundee, 1975. Lecture Notes in Math., vol. 506, pp. 90–99. Springer, Berlin (1976)
[23] Kass, M., Witkin, A., Terzopoulos, D.: Snakes: Active contour models. Int. J. Comput. Vis. 1(4), 321–331 (1988) · Zbl 0646.68105 · doi:10.1007/BF00133570
[24] Kazhdan, M., Bolitho, M., Hoppe, H.: Poisson surface reconstruction. In: Proceedings of the Fourth Eurographics Symposium on Geometry Processing, pp. 61–70 (2006)
[25] Kerautret, B., Lachaud, J.-O.: Robust estimation of curvature along digital contours with global optimization. In: Coeurjolly, D., Sivignon, I., Tougne, L., Dupont, F. (eds.) Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI’2008), Lyon, France. LNCS, vol. 4992, pp. 334–345. Springer, Berlin (2008) · Zbl 1138.68600
[26] Kerautret, B., Lachaud, J.-O.: Curvature estimation along noisy digital contours by approximate global optimization. Pattern Recognit. 42(10), 2265–2278 (2009) · Zbl 1192.68581 · doi:10.1016/j.patcog.2008.11.013
[27] Lachaud, J.-O.: Espaces non-euclidiens et analyse d’image: modèles déformables riemanniens et discrets, topologie et géométrie discrète. Habilitation à diriger des recherches, Université Bordeaux 1, Talence, France (2006). In french
[28] Lachaud, J.-O., Vialard, A., de Vieilleville, F.: Fast, accurate and convergent tangent estimation on digital contours. Image Vis. Comput. 25(10), 1572–1587 (2007) · doi:10.1016/j.imavis.2006.06.019
[29] Lawson, C.L., Hanson, R.J.: Solving Least Squares Problems. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Englewood Cliffs (1974)
[30] Lorensen, W.E., Cline, H.E.: Marching cubes: A high resolution 3d surface construction algorithm. In: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’87, pp. 163–169 (1987)
[31] Modica, L., Mortola, S.: Il limite nella {\(\Gamma\)}-convergenza di una famiglia di funzionali ellittici. Boll. Unione Mat. Ital., A (5) 14(3), 526–529 (1977)
[32] Modica, L., Mortola, S.: Un esempio di {\(\Gamma\)}convergenza. Boll. Unione Mat. Ital. B (5) 14(1), 285–299 (1977) · Zbl 0356.49008
[33] Röger, M., Schätzle, R.: On a modified conjecture of De Giorgi. Math. Z. 254(4), 675–714 (2006) · Zbl 1126.49010 · doi:10.1007/s00209-006-0002-6
[34] Schätzle, R.: Lower semicontinuity of the Willmore functional for currents. J. Differ. Geom. 81(2), 437–456 (2009) · Zbl 1214.53011
[35] Schätzle, R.: The Willmore boundary problem. Calc. Var. Partial Differ. Equ. 37(3–4), 275–302 (2010) · Zbl 1188.53006 · doi:10.1007/s00526-009-0244-3
[36] Schneider, R.: Convex Bodies: the Brunn-Minkowski Theory. Encyclopedia of Mathematics and its Applications, vol. 44. Cambridge University Press, Cambridge (1993) · Zbl 0798.52001
[37] Willmore, T.J.: Riemannian Geometry. Oxford Science Publications. The Clarendon Press, New York (1993) · Zbl 0797.53002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.