A segmentation of an image is “close” to the original one but also “homogeneous” far from some edges. Some compare this work to that of a cartoonist who would first sketch a set of contour lines and fill them with flat greys.
Of course, there are several way to achieve a segmentation and D. Mumford and J. Shah (Mumford & Shah, 1989) that for any given image whose grey level correspond to a function , one can compute a segmentation by minimizing amongst every edge set and every segmented image the energy functional:
where, and are two strictly positive parameters and denotes the -dimensional Hausdorff measure (i.e. length in 2D or surface area in 3D).
The analysis and the numerical implementation of the Mumford-Shah problem are very challenging, mostly due to the nature of the unknowns: a function and a curve. Typically, the first step is to propose a weak formulation by identifying the edges and the discontinuities of the function and defining the functional
where now belongs to the space of functions with bounded variations and denotes its jump set.
Unfortunately, the numerical implementation of is still challenging. Most classical numerical methods will not allow the direct approximation of arguments in , and one still has to approximate surface and bulk energies. There are many way to deal with this issue, two of which are presented below.
Approximation by the Ambrosio-Tortorelli functional
L. Ambrosio and V.M. Tortorelli suggested to approximate the Mumford-Shah energy by sequences of elliptic functionals, in the sense of the -convergence (Ambrosio & Tortorelli, 1990), (Ambrosio & Tortorelli, 1992). Introducing a secondary variable v and a small parameter , they showed that the functional
-converges to the Mumford-Shah weak energy . In particular, this implies that the minimizers of the regularized functional converge in some sense to that of the original problem. This result can be further extended to the case of a finite element approximation of the original energy, provided that the mesh size goes to 0 faster than the regularization parameter (Bellettini & Coscia, 1994), (Bourdin, 1999). This is the base of the numerical experiment presented below. From left to right, the figures represent the original image , the regularized edge set , and the segmented image .
Image segmentation using the Ambrosio-Tortorelli approximation of the Mumford-Shah functional, from (Bourdin, 1999).
###Adaptive Finite Element approximation
Another approach was first presented in (Chambolle & Dal Maso, 1999) then extended and implemented in (Bourdin & Chambolle, 2000). It relies again on finite elements, but requires the construction of an adapted mesh, in order to build a proper approximation of the discontinuous function (u). The following set of figure illustrate the construction of the adapted triangulation and the segmentation on the constructed mesh. The first row of figure correspond to a first segmentation and edge set on a background triangulation, and the second one present the same fields, and the final triangulation.
Image segmentation using an adaptive finite element approximation of the Mumford-Shah functional, from (Bourdin & Chambolle, 2000). Background mesh and segmentation
Image segmentation using an adaptive finite element approximation of the Mumford-Shah functional, from (Bourdin & Chambolle, 2000). Adapted mesh and segmentation
- Mumford, D., & Shah, J. (1989). Optimal approximation by piecewise smooth functions and associated variational problem. Comm. Pure. Appl. Math., 42, 577–685.
- Ambrosio, L., & Tortorelli, V. M. (1990). Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence. Comm. Pure Appl. Math., 43(8), 999–1036.
- Ambrosio, L., & Tortorelli, V. M. (1992). On the approximation of free discontinuity problems. Boll. Un. Mat. Ital. B (7), 6(1), 105–123.
- Bellettini, G., & Coscia, A. (1994). Discrete approximation of a free discontinuity problem. Numer. Funct. Anal. Optim., 15(3-4), 201–224.
- Bourdin, B. (1999). Image segmentation with a finite element method. M2AN Math. Model. Numer. Anal., 33(2), 229–244. Download
- Chambolle, A., & Dal Maso, G. (1999). Discrete approximations of the Mumford-Shah functional in dimension two. M2AN Math. Model. Num. Ana., 33(4), 651–672.
- Bourdin, B., & Chambolle, A. (2000). Implementation of an adaptive finite-element approximation of the Mumford-Shah functional. Numer. Math., 85(4), 609–646. DOI:10.1007/s002110000099 Download