Mumford–Shah functional

Short description: Mathematics concept

The Mumford–Shah functional is a functional that is used to establish an optimality criterion for segmenting an image into sub-regions. An image is modeled as a piecewise-smooth function. The functional penalizes the distance between the model and the input image, the lack of smoothness of the model within the sub-regions, and the length of the boundaries of the sub-regions. By minimizing the functional one may compute the best image segmentation. The functional was proposed by mathematicians David Mumford and Jayant Shah in 1989.

Definition of the Mumford–Shah functional

Consider an image I with a domain of definition D, call J the image's model, and call B the boundaries that are associated with the model: the Mumford–Shah functional E[ J,B ] is defined as

[math]\displaystyle{ E[J,B] = \alpha \int_D (I(\vec x) - J(\vec x))^2 \,\mathrm{d}\vec x + \beta \int _{D/B} \vec \nabla J(\vec x) \cdot \vec \nabla J(\vec x) \,\mathrm{d} \vec x + \gamma \int _B ds }[/math]

Optimization of the functional may be achieved by approximating it with another functional, as proposed by Ambrosio and Tortorelli.

Minimization of the functional

Ambrosio–Tortorelli limit

Ambrosio and Tortorelli showed that Mumford–Shah functional E[ J,B ] can be obtained as the limit of a family of energy functionals E[ J,z,ε ] where the boundary B is replaced by continuous function z whose magnitude indicates the presence of a boundary. Their analysis show that the Mumford–Shah functional has a well-defined minimum. It also yields an algorithm for estimating the minimum.

The functionals they define have the following form:

[math]\displaystyle{ E[J,z;\varepsilon] = \alpha \int (I(\vec x) - J(\vec x))^2 \,\mathrm{d} \vec x + \beta \int z(\vec x) |\vec \nabla J(\vec x)|^2 \,\mathrm{d} \vec x + \gamma \int \{ \varepsilon |\vec \nabla z(\vec x)|^2 + \varepsilon ^{-1} \phi ^2(z(\vec x))\} \,\mathrm{d} \vec x }[/math]

where ε > 0 is a (small) parameter and ϕ(z) is a potential function. Two typical choices for ϕ(z) are

• [math]\displaystyle{ \phi _1(z) = (1-z^2)/2 \quad z \in [-1,1]. }[/math] This choice associates the edge set B with the set of points z such that ϕ₁(z) ≈ 0
• [math]\displaystyle{ \phi _2(z) = z(1-z) \quad z \in [0,1]. }[/math] This choice associates the edge set B with the set of points z such that ϕ₂(z) ≈ 1/4

The non-trivial step in their deduction is the proof that, as [math]\displaystyle{ \epsilon\to 0 }[/math], the last two terms of the energy function (i.e. the last integral term of the energy functional) converge to the edge set integral ∫_Bds.

The energy functional E[ J,z,ε ] can be minimized by gradient descent methods, assuring the convergence to a local minimum.

Ambrosio, Fusco, and Hutchinson, established a result to give an optimal estimate of the Hausdorff dimension of the singular set of minimizers of the Mumford-Shah energy.

Minimization by splitting into one-dimensional problems

The Mumford-Shah functional can be split into coupled one-dimensional subproblems. The subproblems are solved exactly by dynamic programming.

See also

• Bounded variation
• Caccioppoli set
• Digital image processing
• Luigi Ambrosio

References

• Camillo, De Lellis; Focardi, Matteo; Ruffini, Berardo (October 2013), "A note on the Hausdorff dimension of the singular set for minimizers of the Mumford–Shah energy", Advances in Calculus of Variations 7 (4): 539–545, doi:10.1515/acv-2013-0107, ISSN 1864-8258 
• Ambrosio, Luigi; Fusco, Nicola; Hutchinson, John E. (2003), "Higher integrability of the gradient and dimension of the singular set for minimisers of the Mumford-Shah functional", Calculus of Variations and Partial Differential Equations 16 (2): 187–215, doi:10.1007/s005260100148 
• Ambrosio, Luigi; Tortorelli, Vincenzo Maria (1990), "Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence", Communications on Pure and Applied Mathematics 43 (8): 999–1036, doi:10.1002/cpa.3160430805 
• Ambrosio, Luigi; Fusco, Nicola; Pallara, Diego (2000). Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. New York: The Clarendon Press, Oxford University Press. pp. 434. ISBN 9780198502456. https://archive.org/details/functionsbounded00ambr_983. 
• Mumford, David; Shah, Jayant (1989), "Optimal Approximations by Piecewise Smooth Functions and Associated Variational Problems", Communications on Pure and Applied Mathematics XLII (5): 577–685, doi:10.1002/cpa.3160420503, https://dash.harvard.edu/bitstream/handle/1/3637121/Mumford_OptimalApproxPiece.pdf?sequence=1 

• Hohm, Kilian; Storath, Martin; Weinmann, Andreas (2015), "An algorithmic framework for Mumford–Shah regularization of inverse problems in imaging", Inverse Problems 31 (11): 115011, doi:10.1088/0266-5611/31/11/115011, Bibcode: 2015InvPr..31k5011H, http://bigwww.epfl.ch/publications/hohm1501.pdf