Calculus of Variations and Geometric Measure Theory

A. Chambolle - A. Giacomini - L. Lussardi

Continuous limits of discrete perimeters

created by lussardi on 01 Mar 2009
modified on 03 Apr 2010


Published Paper

Inserted: 1 mar 2009
Last Updated: 3 apr 2010

Journal: ESAIM Math. Model. Numer. Anal.
Volume: 44
Number: 2
Pages: 207-230
Year: 2010


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 comunity. We study the limit in the continuum of these functionals, show that they always converge to some "crystalline" perimetertotal variation, and provide an almost explicit formula for the limiting functional.

Keywords: Total variation, generalized coarea formula, anisotropic perimeter