Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T14:01:25.209Z Has data issue: false hasContentIssue false
  • English
  • Français

Continuous limits of discrete perimeters

Published online by Cambridge University Press:  16 December 2009

Antonin Chambolle ,
Alessandro Giacomini  and
Luca Lussardi
Antonin Chambolle
Affiliation:
CMAP, École polytechnique, CNRS 91128, Palaiseau, France. [email protected]
Alessandro Giacomini
Affiliation:
Dipartimento di Matematica, Facoltà di Ingegneria, Università degli Studi di Brescia, Via Valotti 9, 25133 Brescia, Italy. [email protected]
Luca Lussardi
Affiliation:
Dipartimento di Matematica, I Facoltà di Ingegneria, Politecnico di Torino, c.so Duca degli Abruzzi 24, 10129 Torino, Italy. [email protected]
Get access

Abstract

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.

Keywords

Generalized coarea formulatotal variationanisotropic perimeter
Type
Research Article
Information
ESAIM: Mathematical Modelling and Numerical Analysis , Volume 44 , Issue 2 , March 2010 , pp. 207 - 230
Copyright
© EDP Sciences, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows, Theory, algorithms, and applications. Prentice Hall Inc., Englewood Cliffs, USA (1993).
L. Ambrosio, N. Fusco and D. Pallara, Functions of bounded variation and free discontinuity problems, Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, USA (2000).
Y. Boykov and V. Kolmogorov, Computing geodesics and minimal surfaces via graph cuts, in International Conference on Computer Vision (2003) 26–33.
Boykov, Y. and Kolmogorov, V., An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26 (2004) 1124–1137. CrossRef
A. Braides, Γ-convergence for beginners, Oxford Lecture Series in Mathematics and its Applications 22. Oxford University Press, Oxford, UK (2002).
Chambolle, A. and Darbon, J., On total variation minimization and surface evolution using parametric maximum flows. Int. J. Comput. Vis. 84 (2009) 288–307. CrossRef
Cunningham, W.H., On submodular function minimization. Combinatoria 5 (1985) 185–192. CrossRef
G. Dal Maso, An introduction to Γ-convergence, Progress in Nonlinear Differential Equations and their Applications 8. Birkhäuser Boston Inc., Boston, USA (1993).
H. Federer, Geometric measure theory. Springer-Verlag New York Inc., New York, USA (1969).
E. Giusti, Minimal surfaces and functions of bounded variation, Monographs in Mathematics 80. Birkhäuser Verlag, Basel, Switzerland (1984).
Greig, D.M., Porteous, B.T. and Seheult, A.H., Exact maximum a posteriori estimation for binary images. J. R. Statist. Soc. B 51 (1989) 271–279.
S. Iwata, L. Fleischer and S. Fujishige, 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.
L. Lovász, Submodular functions and convexity, in Mathematical programming: the state of the art (Bonn, 1982), Springer, Berlin, Germany (1983) 235–257.
Picard, J.C. and Ratliff, H.D., Minimum cuts and related problems. Networks 5 (1975) 357–370. CrossRef
Schrijver, A., A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory (B) 80 (2000) 436–355. CrossRef
Visintin, A., Nonconvex functionals related to multiphase systems. SIAM J. Math. Anal. 21 (1990) 1281–1304. CrossRef
Visintin, A., Generalized coarea formula and fractal sets. Japan J. Indust. Appl. Math. 8 (1991) 175–201. CrossRef