Continuous limits of discrete perimeters

Antonin Chambolle; Alessandro Giacomini; Luca Lussardi

ESAIM: Mathematical Modelling and Numerical Analysis (2010)

  • Volume: 44, Issue: 2, page 207-230
  • ISSN: 0764-583X

Abstract

top
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.

How to cite

top

Chambolle, Antonin, Giacomini, Alessandro, and Lussardi, Luca. "Continuous limits of discrete perimeters." ESAIM: Mathematical Modelling and Numerical Analysis 44.2 (2010): 207-230. <http://eudml.org/doc/250806>.

@article{Chambolle2010,
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. },
author = {Chambolle, Antonin, Giacomini, Alessandro, Lussardi, Luca},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Generalized coarea formula; total variation; anisotropic perimeter; generalized coarea formula},
language = {eng},
month = {3},
number = {2},
pages = {207-230},
publisher = {EDP Sciences},
title = {Continuous limits of discrete perimeters},
url = {http://eudml.org/doc/250806},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Chambolle, Antonin
AU - Giacomini, Alessandro
AU - Lussardi, Luca
TI - Continuous limits of discrete perimeters
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2010/3//
PB - EDP Sciences
VL - 44
IS - 2
SP - 207
EP - 230
AB - 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.
LA - eng
KW - Generalized coarea formula; total variation; anisotropic perimeter; generalized coarea formula
UR - http://eudml.org/doc/250806
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.