Analysis of gradient flow of a regularized Mumford-Shah functional for image segmentation and image inpainting

Feng, Xiaobing; Prohl, Andreas

ESAIM: Modélisation mathématique et analyse numérique, Tome 38 (2004) no. 2, pp. 291-320.

This paper studies the gradient flow of a regularized Mumford-Shah functional proposed by Ambrosio and Tortorelli (1990, 1992) for image segmentation, and adopted by Esedoglu and Shen (2002) for image inpainting. It is shown that the gradient flow with $L^2\times L^{\infty }$ initial data possesses a global weak solution, and it has a unique global in time strong solution, which has at most finite number of point singularities in the space-time, when the initial data are in $H^1\times H^1\cap L^{\infty }$. A family of fully discrete approximation schemes using low order finite elements is proposed for the gradient flow. Convergence of a subsequence (resp. the whole sequence) of the numerical solutions to a weak solution (resp. the strong solution) of the gradient flow is established as the mesh sizes tend to zero, and optimal and suboptimal order error estimates, which depend on $\frac{1}{\epsilon }$ and $\frac{1}{k_{\epsilon }}$ only in low polynomial order, are derived for the proposed fully discrete schemes under the mesh relation $k=o\left(h^{\frac{1}{2}}\right)$. Numerical experiments are also presented to show effectiveness of the proposed numerical methods and to validate the theoretical analysis.

[1] R.A. Adams, Sobolev Spaces. Academic Press, New York (1975). | MR | Zbl

[2] L. Ambrosio and V.M. Tortorelli, Approximation of functionals depending on jumps by elliptic functionals via $\Gamma$-convergence. Comm. Pure Appl. Math. 43 (1990) 999-1036. | MR | Zbl

[3] L. Ambrosio and V.M. Tortorelli, On the approximation of functionals depending on jumps by quadratic, elliptic functionals. Boll. Un. Mat. Ital. 6-B (1992) 105-123. | MR | Zbl

[4] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems. Oxford University Press (2000). | MR | Zbl

[5] J.W. Barrett, X. Feng and A. Prohl, Convergence of a fully discrete finite element method for a degenerate parabolic system modeling nematic liquid crystals with variable degree of orientation, preprint. | Numdam | MR | Zbl

[6] G. Bellettini and A. Coscia, Discrete approximation of a free discontinuity problem. Numer. Funct. Anal. Optimiz. 15 (1994) 201-224. | MR | Zbl

[7] A. Blake and A. Zisserman, Visual reconstruction. MIT Press, Cambridge, MA (1987). | MR

[8] B. Bourdin, Image segmentation with a finite element method. ESAIM: M2AN 33 (1999) 229-244. | Numdam | MR | Zbl

[9] A. Braides, Approximation of free-discontinuity problems. Lect. Notes Math. 1694, Springer-Verlag (1998). | MR | Zbl

[10] A. Braides and G. Dal Maso, Nonlocal approximation of the Mumford-Shah functional. Calc. Var. Partial Differential Equations 5 (1997) 293-322. | Zbl

[11] S.C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods, Second Edition, Springer-Verlag, New York (2001). | MR | Zbl

[12] J.W. Cahn and J.E. Hilliard, Free energy of a nonuniform system I, Interfacial free energy. J. Chem. Phys. 28 (1958) 258-267.

[13] A. Chambolle, Image segmentation by variational methods: Mumford-Shah functional and the discrete approximation. SIAM J. Appl. Math. 55 (1995) 827-863. | Zbl

[14] A. Chambolle and G. Dal Maso, Discrete approximation of the Mumford-Shah functional in dimension two. ESAIM: M2AN 33 (1999) 651-672. | Numdam | Zbl

[15] P.G. Ciarlet, Basic error estimates for elliptic problems, in Handbook of Numer. Anal. II, Elsevier Sciences Publishers (1991). | MR | Zbl

[16] G. Dal Maso, An introduction to $\Gamma$-convergence, Birkhäuser Boston, Boston, MA (1993). | MR | Zbl

[17] E. De Giorgi, M. Carriero and A. Leaci, Existence theorem for a minimum problem with discontinuity set. Arch. Rat. Mech. Anal. 108 (1989) 195-218. | Zbl

[18] E. De Giorgi and T. Franzoni, Su un tipo di convergenza variazionale. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. 58 (1975) 842-850. | Zbl

[19] F. Dibos and E. Séré, An approximation result for the minimizers of the Mumford-Shah functional. Boll. Un. Mat. Ital. A 11 (1997). | MR | Zbl

[20] C.M. Elliott, D.A. French and F.A. Milner, A second order splitting method for the Cahn-Hilliard equation. Numer. Math. 54 (1989) 575-590. | Zbl

[21] S. Esedoglu and J. Shen, Digital inpainting based on the Mumford-Shah-Euler image model. European J. Appl. Math. 13 (2002) 353-370. | Zbl

[22] X. Feng and A. Prohl, Analysis of total variation flow and its finite element approximations. ESAIM: M2AN 37 (2003) 533-556. | Numdam | Zbl

[23] X. Feng and A. Prohl, On gradient flow of the Mumford-Shah functional. (in preparation).

[24] D. Geman and S. Geman, Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Trans. Patten Anal. Mach. Intell. 6 (1984) 721-741. | Zbl

[25] R. Glowinski, J.L. Lions and R. Trémoliéres, Numerical analysis of variational inequalities. North-Holland, New York. Stud. Math. Appl. 8 (1981). | MR | Zbl

[26] M. Gobbino, Gradient flow for the one-dimensional Mumford-Shah strategies. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 27 (1998) 145-193. | Numdam | Zbl

[27] J.L. Lions, Quelques méthodes de résolution des problèmes aux limites non linéaires, Dunod (1969). | MR | Zbl

[28] R. March and M. Dozio, A variational method for the recovery of smooth boundaries. Im. Vis. Comp. 15 (1997) 705-712.

[29] L. Modica, The gradient theory of phase transitions and the minimal interface criterion. Arch. Rational Mech. Anal. 98 (1987) 123-142. | Zbl

[30] L. Modica and S. Mortola, Un esempio di $\Gamma$-convergenza. Boll. Un. Mat. Ital. B 14 (1977) 285-299. | Zbl

[31] J.-M. Morel and S. Solimini, Variational Methods in Image Segmentation, Birkhäuser (1995). | MR

[32] D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42 (1989) 577-685. | Zbl

[33] R.H. Nochetto and C. Verdi, Convergence past singularities for a fully discrete approximation of curvature-driven interfaces. SIAM J. Numer. Anal. 34 (1997) 490-512. | Zbl

[34] J. Simon, Compact sets in the space $L^p(0,T;B)$. Ann. Mat. Pura Appl. 146 (1987) 65-96. | Zbl

[35] M. Struwe, Geometric evolution problems. IAS/Park City Math. Series 2 (1996) 259-339. | Zbl