Total roto-translational variation. (English) Zbl 1418.53004
Summary: We consider curvature depending variational models for image regularization, such as Euler’s elastica. These models are known to provide strong priors for the continuity of edges and hence have important applications in shape- and image processing. We consider a lifted convex representation of these models in the roto-translation space: in this space, curvature depending variational energies are represented by means of a convex functional defined on divergence free vector fields. The line energies are then easily extended to any scalar function. It yields a natural generalization of the total variation to curvature-dependent energies. As our main result, we show that the proposed convex representation is tight for characteristic functions of smooth shapes. We also discuss cases where this representation fails. For numerical solution, we propose a staggered grid discretization based on an averaged Raviart-Thomas finite elements approximation. This discretization is consistent, up to minor details, with the underlying continuous model. The resulting non-smooth convex optimization problem is solved using a first-order primal-dual algorithm. We illustrate the results of our numerical algorithm on various problems from shape- and image processing.
MSC:
| 53A04 | Curves in Euclidean and related spaces |
| 49Q20 | Variational problems in a geometric measure-theoretic setting |
| 26A45 | Functions of bounded variation, generalizations |
| 35J35 | Variational methods for higher-order elliptic equations |
| 53A40 | Other special differential geometries |
| 65K10 | Numerical optimization and variational techniques |
Keywords:
Euler’s elastica; image processing; roto-translation space; finite elements approximation; primal-dual algorithmReferences:
| [1] | Acerbi, E., Mucci, D.: Curvature-dependent energies. Milan J. Math. 85(1), 41-69 (2017) · Zbl 1375.49013 |
| [2] | Acerbi, E., Mucci, D.: Curvature-dependent energies: the elastic case. Nonlinear Anal. 153, 7-34 (2017) · Zbl 1361.53007 |
| [3] | Ambrosio, L., Fusco, N., Pallara, D.: Functions of Bounded Variation and Free Discontinuity Problems. The Clarendon Press/Oxford University Press, New York (2000) · Zbl 0957.49001 |
| [4] | Ambrosio, L., Masnou, S.: A direct variational approach to a problem arising in image reconstruction. Interfaces Free Bound. 5(1), 63-81 (2003) · Zbl 1029.49037 |
| [5] | Anzellotti, G.: Functionals depending on curvatures. Rend. Sem. Mat. Univ. Politec. Torino (Special Issue):47-62 (1990), 1989. Conference on Partial Differential Equations and Geometry (Torino, 1988) · Zbl 0738.49021 |
| [6] | Anzellotti, G., Serapioni, R., Tamanini, I.: Curvatures, functionals, currents. Indiana Univ. Math. J. 39(3), 617-669 (1990) · Zbl 0718.49030 |
| [7] | Anzellotti, G., Delladio, S.: Minimization of functionals of curvatures and the Willmore problem. In: Advances in Geometric Analysis and Continuum Mechanics (Stanford, CA, 1993), pp. 33-43. International Press Press, Cambridge (1995) · Zbl 0840.49008 |
| [8] | Bae, E., Tai, X.-C., Zhu, W.: Augmented Lagrangian method for an Euler’s elastica based segmentation model that promotes convex contours. Inverse Probl. Imaging 11(1), 1-23 (2017) · Zbl 1416.94013 |
| [9] | Ballester, C., Bertalmio, M., Caselles, V., Sapiro, G., Verdera, J.: Filling-in by joint interpolation of vector fields and gray levels. IEEE Trans. Image Process. 10(8), 1200-1211 (2001) · Zbl 1037.68771 |
| [10] | Ballester, C., Caselles, V., Verdera, J.: Disocclusion by joint interpolation of vector fields and gray levels. Multiscale Model. Simul. 2(1), 80-123 (2003) · Zbl 1079.68634 |
| [11] | Bekkers, E.J., Duits, R., Mashtakov, A., Sanguinetti, G.R.: A PDE approach to data-driven sub-Riemannian geodesics in \[SE(2)\] SE(2). SIAM J. Imaging Sci. 8(4), 2740-2770 (2015) · Zbl 1336.58014 |
| [12] | Bellettini, G., Dal Maso, G., Paolini, M.: Semicontinuity and relaxation properties of a curvature depending functional in 2D. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 20(2), 247-297 (1993) · Zbl 0797.49013 |
| [13] | Bellettini, G., Mugnai, L.: Characterization and representation of the lower semicontinuous envelope of the elastica functional. Ann. Inst. H. Poincaré Anal. Non Linéaire 21(6), 839-880 (2004) · Zbl 1110.49014 |
| [14] | Bellettini, G., Mugnai, L.: On the approximation of the elastica functional in radial symmetry. Calc. Var. Partial Differ. Equ. 24(1), 1-20 (2005) · Zbl 1086.49009 |
| [15] | Bellettini, G., Mugnai, L.: A varifolds representation of the relaxed elastica functional. J. Convex Anal. 14(3), 543-564 (2007) · Zbl 1127.49032 |
| [16] | Bellettini, G., March, R.: An image segmentation variational model with free discontinuities and contour curvature. Math. Models Methods Appl. Sci. 14(1), 1-45 (2004) · Zbl 1044.49009 |
| [17] | Bellettini, G., March, R.: Asymptotic properties of the Nitzberg-Mumford variational model for segmentation with depth. In: Free Boundary Problems. Volume 154 of International Series of Numerical Mathematics, pp. 75-84. Birkhäuser, Basel (2007) · Zbl 1112.49037 |
| [18] | Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, pp. 417-424. ACM Press/Addison-Wesley Publishing Co. (2000) |
| [19] | Boscain, U., Chertovskih, R.A., Gauthier, J.P., Remizov, A.O.: Hypoelliptic diffusion and human vision: a semidiscrete new twist. SIAM J. Imaging Sci. 7(2), 669-695 (2014) · Zbl 1343.94002 |
| [20] | Boscain, U., Duits, R., Rossi, F., Sachkov, Y.: Curve cuspless reconstruction via sub-Riemannian geometry. ESAIM Control Optim. Calc. Var. 20(3), 748-770 (2014) · Zbl 1381.49003 |
| [21] | Bouchitté, G., Valadier, M.: Integral representation of convex functionals on a space of measures. J. Funct. Anal. 80(2), 398-420 (1988) · Zbl 0662.46009 |
| [22] | Bredies, K., Pock, T., Wirth, B.: Convex relaxation of a class of vertex penalizing functionals. J. Math. Imaging Vis. 47(3), 278-302 (2013) · Zbl 1293.49063 |
| [23] | Bredies, K., Pock, T., Wirth, B.: A convex, lower semicontinuous approximation of Euler’s elastica energy. SIAM J. Math. Anal. 47(1), 566-613 (2015) · Zbl 1319.49018 |
| [24] | Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145 (2011) · Zbl 1255.68217 |
| [25] | Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159(1-2, Ser. A), 253-287 (2016) · Zbl 1350.49035 |
| [26] | Chan, T.F., Kang, S.H., Shen, J.: Euler’s elastica and curvature-based inpainting. SIAM J. Appl. Math. 63(2), 564-592 (2002) · Zbl 1028.68185 |
| [27] | Chan, T.F., Shen, J.: Mathematical models for local nontexture inpaintings. SIAM J. Appl. Math. 62(3), 1019-1043 (2001/2002) · Zbl 1050.68157 |
| [28] | Chen, D., Mirebeau, J.-M., Cohen, L.D.: Global minimum for a Finsler elastica minimal path approach. Int. J. Comput. Vis. 122(3), 458-483 (2017) · Zbl 1477.68341 |
| [29] | Citti, G., Franceschiello, B., Sanguinetti, G., Sarti, A.: Sub-Riemannian mean curvature flow for image processing. SIAM J. Imaging Sci. 9(1), 212-237 (2016) · Zbl 1352.68272 |
| [30] | Dayrens, F., Masnou, S., Novaga, M.: Existence, regularity and structure of confined elasticæ. In: ESAIM:COCV, 2017 (to appear) · Zbl 1397.49020 |
| [31] | Delladio, S.: Minimizing functionals depending on surfaces and their curvatures: a class of variational problems in the setting of generalized Gauss graphs. Pac. J. Math. 179(2), 301-323 (1997) · Zbl 0886.49032 |
| [32] | Delladio, S.: Special generalized Gauss graphs and their application to minimization of functionals involving curvatures. J. Reine Angew. Math. 486, 17-43 (1997) · Zbl 0871.49034 |
| [33] | Duits, R., Boscain, U., Rossi, F., Sachkov, Y.: Association fields via cuspless sub-Riemannian geodesics in SE(2). J. Math. Imaging Vis. 49(2), 384-417 (2014) · Zbl 1296.49040 |
| [34] | Duits, R., Meesters, S.P.L., Mirebeau, J.-M., Portegies, J. M.: Optimal Paths for Variants of the 2D and 3D Reeds-Shepp Car with Applications in Image Analysis. ArXiv e-prints (2016) · Zbl 1398.65135 |
| [35] | Ekeland, I., Témam, R.: Convex Analysis and Variational Problems, Volume 28 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, english edition (1999). Translated from the French · Zbl 0939.49002 |
| [36] | El-Zehiry, N., Grady, L.: Optimization of weighted curvature for image segmentation. arXiv preprint arXiv:1006.4175 (2010) · Zbl 1408.94163 |
| [37] | El-Zehiry, N.Y., Grady, L.: Fast global optimization of curvature. In: 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3257-3264. IEEE (2010) |
| [38] | El-Zehiry, N.Y., Grady, L.: Contrast driven elastica for image segmentation. IEEE Trans. Image Process. 25(6), 2508-2518 (2016) · Zbl 1408.94163 |
| [39] | Esedoglu, S., March, R.: Segmentation with depth but without detecting junctions. J. Math. Imaging Vis. 18(1), 7-15 (2003). Special issue on imaging science (Boston, MA, 2002) · Zbl 1033.68132 |
| [40] | Esedoglu, S., Shen, J.: Digital inpainting based on the Mumford-Shah-Euler image model. Eur. J. Appl. Math. 13(4), 353-370 (2002) · Zbl 1017.94505 |
| [41] | Franken, E., Duits, R.: Crossing-preserving coherence-enhancing diffusion on invertible orientation scores. Int. J. Comput. Vis. 85(3), 253 (2009) |
| [42] | Glowinski, R.: ADMM and non-convex variational problems. In: Splitting Methods in Communication, Imaging, Science, and Engineering, Science, and Engineering, pp. 251-299. Springer, Cham (2016) · Zbl 1372.65192 |
| [43] | Glowinski, R., Pan, T.-W., Tai, X.-C.: Some facts about operator-splitting and alternating direction methods. In: Splitting Methods in Communication, Imaging, Science, and Engineering. Sci. Comput., pp. 19-94. Springer, Cham (2016) · Zbl 1372.65205 |
| [44] | Hubel, D.H., Wiesel, T.N.: Receptive fields of single neurones in the cat’s striate cortex. J. Physiol. 148(3), 574-591 (1959) |
| [45] | Hutchinson, J.E.: Second fundamental form for varifolds and the existence of surfaces minimising curvature. Indiana Univ. Math. J. 35(1), 45-71 (1986) · Zbl 0561.53008 |
| [46] | Kanizsa, G.: Grammatica del vedere: saggi su percezione e gestalt. Biblioteca: Mulino. Il Mulino (1980), 2nd edition 1997 |
| [47] | Kanizsa, G.: Organization in Vision : Essays on Gestalt Perception. Praeger, New York (1979). Foreword by Paolo Legrenzi and Paolo Bozzi |
| [48] | Koenderink, J.J., van Doorn, A.J.: Representation of local geometry in the visual system. Biol. Cybernet. 55(6), 367-375 (1987) · Zbl 0617.92024 |
| [49] | Krueger, M., Delmas, P., Gimel’farb, G.: Efficient Image Segmentation Using Weighted Pseudo-Elastica, pp. 59-67. Springer, Berlin (2011) |
| [50] | Mantegazza, C.: Curvature varifolds with boundary. J. Differ. Geom. 43(4), 807-843 (1996) · Zbl 0865.49030 |
| [51] | Masnou, S., Nardi, G.: A coarea-type formula for the relaxation of a generalized elastica functional. J. Convex Anal. 20(3), 617-653 (2013) · Zbl 1278.49015 |
| [52] | Masnou, S., Morel, J.-M.: Level lines based disocclusion. In: International Conference on Image Processing, 1998. ICIP 98. Proceedings, pp. 259-263. IEEE (1998) |
| [53] | Masnou, S., Morel, J.-M.: On a variational theory of image amodal completion. Rend. Sem. Mat. Univ. Padova 116, 211-252 (2006) · Zbl 1150.49023 |
| [54] | Mercier, G.: Continuity results for TV-minimizers. Indiana Univ. Math. J. 67(4), 1499-1545 (2018) · Zbl 1408.49038 |
| [55] | Mirebeau, J.-M.: Anisotropic fast-marching on Cartesian grids using lattice basis reduction. SIAM J. Numer. Anal. 52(4), 1573-1599 (2014) · Zbl 1312.65172 |
| [56] | Mirebeau, J.-M.: Fast Marching Methods for Curvature Penalized Shortest Paths, preprint (2017) |
| [57] | Moiseev, I., Sachkov, Y.L.: Maxwell strata in sub-Riemannian problem on the group of motions of a plane. ESAIM Control Optim. Calc. Var. 16(2), 380-399 (2010) · Zbl 1217.49037 |
| [58] | Nitzberg, M., Mumford, D., Shiota, T.: Filtering, segmentation and depth. Lecture Notes in Computer Science, vol. 662. Springer, Berlin (1993) · Zbl 0801.68171 |
| [59] | Petitot, J., Tondut, Y.: Vers une neurogéométrie. Fibrations corticales, structures de contact et contours subjectifs modaux. Math. Inform. Sci. Hum. 145, 5-101 (1999) |
| [60] | Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: Proceedings of the 2011 International Conference on Computer Vision, ICCV’11, pp. 1762-1769, Washington, DC, USA, IEEE Computer Society (2011) |
| [61] | Prandi, D., Boscain, U., Gauthier, J.-P.: Image processing in the semidiscrete group of rototranslations. In: Geometric science of information. Volume 9389 of Lecture Notes in Computer Science, pp. 627-634. Springer, Cham (2015) · Zbl 1406.94005 |
| [62] | Raviart, P.-A., Thomas, J.M.: A mixed finite element method for 2nd order elliptic problems. In: Mathematical Aspects of Finite Element Methods (Proceedings of the International Conference on Consiglio Nazionale delle Ricerche (C.N.R.), Rome, 1975). Lecture Notes in Mathematics, Vol. 606, pp. 292-315. Springer, Berlin (1977) · Zbl 0362.65089 |
| [63] | Rockafellar, R.T.: Integrals which are convex functionals. II. Pac. J. Math. 39, 439-469 (1971) · Zbl 0236.46031 |
| [64] | Rockafellar R.T.: Convex analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1997). Reprint of the 1970 original, Princeton paperbacks · Zbl 0932.90001 |
| [65] | Sarti, A., Citti, G.: Subjective surfaces and Riemannian mean curvature flow of graphs. Acta Math. Univ. Comen. (N.S.) 70(1), 85-103 (2000) · Zbl 0995.65100 |
| [66] | Sarti, A., Citti, G., Petitot, J.: The symplectic structure of the primary visual cortex. Biol. Cybernet. 98(1), 33-48 (2008) · Zbl 1148.92012 |
| [67] | Schmaltz, C., Peter, P., Mainberger, M., Ebel, F., Weickert, J., Bruhn, A.: Understanding, optimising, and extending data compression with anisotropic diffusion. Int. J. Comput. Vis. 108(3), 222-240 (2014) |
| [68] | Schoenemann, T., Cremers, D.: Introducing curvature into globally optimal image segmentation: minimum ratio cycles on product graphs. In: IEEE 11th International Conference on Computer Vision, 2007. ICCV 2007, pp. 1-6. IEEE (2007) |
| [69] | Schoenemann, T., Kahl, F., Masnou, S., Cremers, D.: A linear framework for region-based image segmentation and inpainting involving curvature penalization. Int. J. Comput. Vis. 99(1), 53-68 (2012) · Zbl 1254.68282 |
| [70] | Schoenemann, T., Masnou, S., Cremers, D.: The elastic ratio: introducing curvature into ratio-based image segmentation. IEEE Trans. Image Process. 20(9), 2565-2581 (2011) · Zbl 1372.94227 |
| [71] | Schoenemann, T., Masnou, S., Cremers, D.: On a linear programming approach to the discrete Willmore boundary value problem and generalizations. In: Curves and Surfaces. Volume 6920 of Lecture Notes in Computer Science, pp. 629-646. Springer, Heidelberg (2012) · Zbl 1351.49055 |
| [72] | Sharma, U., Duits, R.: Left-invariant evolutions of wavelet transforms on the similitude group. Appl. Comput. Harmon. Anal. 39(1), 110-137 (2015) · Zbl 1345.94009 |
| [73] | Smirnov, S.K.: Decomposition of solenoidal vector charges into elementary solenoids, and the structure of normal one-dimensional flows. Algebra i Analiz 5(4), 206-238 (1993) · Zbl 0832.49024 |
| [74] | Tai, X.-C., Hahn, J., Chung, G.J.: A fast algorithm for Euler’s elastica model using augmented Lagrangian method. SIAM J. Imaging Sci. 4(1), 313-344 (2011) · Zbl 1215.68262 |
| [75] | Weickert, J.: Theoretical Foundations of Anisotropic Diffusion in Image Processing, pp. 221-236. Springer, Vienna (1996) |
| [76] | Weickert, J.: Mathematische Bildverarbeitung mit Ideen aus der Natur. Mitt. Dtsch. Math.-Ver. 20(2), 82-90 (2012) · Zbl 1260.94022 |
| [77] | Willmore, T.J.: A survey on Willmore immersions. In: Geometry and Topology of Submanifolds, IV (Leuven, 1991), pp. 11-16. World Science Publishing, River Edge (1992) · Zbl 0841.53051 |
| [78] | Yashtini, M., Kang, S.H.: Alternating direction method of multiplier for Euler’s elastica-based denoising. In: Aujol, J.-F., Nikolova, M., Papadakis, N. (eds.) Scale Space and Variational Methods in Computer Vision: 5th International Conference, SSVM 2015, Lège-Cap Ferret, France, May 31-June 4, 2015, Proceedings, pp. 690-701. Springer International Publishing, Cham (2015) · Zbl 1444.94026 |
| [79] | Yashtini, M., Kang, S.H.: A fast relaxed normal two split method and an effective weighted TV approach for Euler’s elastica image inpainting. SIAM J. Imaging Sci. 9(4), 1552-1581 (2016) · Zbl 1366.94075 |
| [80] | Zhu, W., Tai, X.-C., Chan, T.: Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Probl. Imaging 7(4), 1409-1432 (2013) · Zbl 1311.94015 |
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.
