We consider a class of discrete convex functionals which satisfy a (generalized) coarea formula. These functionals, based on submodular interactions, arise in discrete optimization and are known as a large class of problems which can be solved in polynomial time. In particular, some of them can be solved very efficiently by maximal flow algorithms and are quite popular in the image processing community. We study the limit in the continuum of these functionals, show that they always converge to some “crystalline” perimeter/total variation, and provide an almost explicit formula for the limiting functional.
@article{M2AN_2010__44_2_207_0,
author = {Chambolle, Antonin and Giacomini, Alessandro and Lussardi, Luca},
title = {Continuous limits of discrete perimeters},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
volume = {44},
year = {2010},
pages = {207-230},
doi = {10.1051/m2an/2009044},
mrnumber = {2655948},
zbl = {1185.94008},
language = {en},
url = {http://dml.mathdoc.fr/item/M2AN_2010__44_2_207_0}
}
Chambolle, Antonin; Giacomini, Alessandro; Lussardi, Luca. Continuous limits of discrete perimeters. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 44 (2010) pp. 207-230. doi : 10.1051/m2an/2009044. http://gdmltest.u-ga.fr/item/M2AN_2010__44_2_207_0/
[1] , and , Network flows, Theory, algorithms, and applications. Prentice Hall Inc., Englewood Cliffs, USA (1993). | Zbl 1201.90001
[2] , and , Functions of bounded variation and free discontinuity problems, Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, USA (2000). | Zbl 0957.49001
[3] and , Computing geodesics and minimal surfaces via graph cuts, in International Conference on Computer Vision (2003) 26-33.
[4] and , An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26 (2004) 1124-1137. | Zbl 1005.68964
[5] , Γ-convergence for beginners, Oxford Lecture Series in Mathematics and its Applications 22. Oxford University Press, Oxford, UK (2002). | Zbl 1198.49001
[6] and , On total variation minimization and surface evolution using parametric maximum flows. Int. J. Comput. Vis. 84 (2009) 288-307.
[7] , On submodular function minimization. Combinatoria 5 (1985) 185-192. | Zbl 0647.05018
[8] , An introduction to Γ-convergence, Progress in Nonlinear Differential Equations and their Applications 8. Birkhäuser Boston Inc., Boston, USA (1993). | Zbl 0816.49001
[9] , Geometric measure theory. Springer-Verlag New York Inc., New York, USA (1969). | Zbl 0874.49001
[10] , Minimal surfaces and functions of bounded variation, Monographs in Mathematics 80. Birkhäuser Verlag, Basel, Switzerland (1984). | Zbl 0545.49018
[11] , and , Exact maximum a posteriori estimation for binary images. J. R. Statist. Soc. B 51 (1989) 271-279.
[12] , and , A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, in Proceedings of the 32nd annual ACM symposium on Theory of computing, ACM (2000) 97-106. | Zbl 0957.90511
[13] , Submodular functions and convexity, in Mathematical programming: the state of the art (Bonn, 1982), Springer, Berlin, Germany (1983) 235-257. | Zbl 0566.90060
[14] and , Minimum cuts and related problems. Networks 5 (1975) 357-370. | Zbl 0325.90047
[15] , A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory (B) 80 (2000) 436-355. | Zbl 1052.90067
[16] , Nonconvex functionals related to multiphase systems. SIAM J. Math. Anal. 21 (1990) 1281-1304. | Zbl 0723.49006
[17] , Generalized coarea formula and fractal sets. Japan J. Indust. Appl. Math. 8 (1991) 175-201. | Zbl 0736.49030