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

Xiaobing Feng; Andreas Prohl

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2004)

  • Volume: 38, Issue: 2, page 291-320
  • ISSN: 0764-583X

Abstract

top
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 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 . 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 and only in low polynomial order, are derived for the proposed fully discrete schemes under the mesh relation . Numerical experiments are also presented to show effectiveness of the proposed numerical methods and to validate the theoretical analysis.

How to cite

top

Feng, Xiaobing, and Prohl, Andreas. "Analysis of gradient flow of a regularized Mumford-Shah functional for image segmentation and image inpainting." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 38.2 (2004): 291-320. <http://eudml.org/doc/244655>.

@article{Feng2004,
abstract = {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\}\{\{\varepsilon \}\}$ and $\frac\{1\}\{k_\{\varepsilon \}\}$ only in low polynomial order, are derived for the proposed fully discrete schemes under the mesh relation $k=o(h^\{\frac\{1\}\{2\}\})$. Numerical experiments are also presented to show effectiveness of the proposed numerical methods and to validate the theoretical analysis.},
author = {Feng, Xiaobing, Prohl, Andreas},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {image segmentation and inpainting; Mumford-Shah model; elliptic approximation; gradient flow; a priori estimates; finite element method; error analysis; image segmentation; ellpitic approximation; apriori estimates; convergence},
language = {eng},
number = {2},
pages = {291-320},
publisher = {EDP-Sciences},
title = {Analysis of gradient flow of a regularized Mumford-Shah functional for image segmentation and image inpainting},
url = {http://eudml.org/doc/244655},
volume = {38},
year = {2004},
}

TY - JOUR
AU - Feng, Xiaobing
AU - Prohl, Andreas
TI - Analysis of gradient flow of a regularized Mumford-Shah functional for image segmentation and image inpainting
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2004
PB - EDP-Sciences
VL - 38
IS - 2
SP - 291
EP - 320
AB - 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}{{\varepsilon }}$ and $\frac{1}{k_{\varepsilon }}$ only in low polynomial order, are derived for the proposed fully discrete schemes under the mesh relation $k=o(h^{\frac{1}{2}})$. Numerical experiments are also presented to show effectiveness of the proposed numerical methods and to validate the theoretical analysis.
LA - eng
KW - image segmentation and inpainting; Mumford-Shah model; elliptic approximation; gradient flow; a priori estimates; finite element method; error analysis; image segmentation; ellpitic approximation; apriori estimates; convergence
UR - http://eudml.org/doc/244655
ER -

References

top
  1. [1] R.A. Adams, Sobolev Spaces. Academic Press, New York (1975). Zbl0314.46030MR450957
  2. [2] L. Ambrosio and V.M. Tortorelli, Approximation of functionals depending on jumps by elliptic functionals via -convergence. Comm. Pure Appl. Math. 43 (1990) 999–1036. Zbl0722.49020
  3. [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. Zbl0776.49029
  4. [4] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems. Oxford University Press (2000). Zbl0957.49001MR1857292
  5. [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. Zbl1097.35082MR2223509
  6. [6] G. Bellettini and A. Coscia, Discrete approximation of a free discontinuity problem. Numer. Funct. Anal. Optimiz. 15 (1994) 201–224. Zbl0806.49002
  7. [7] A. Blake and A. Zisserman, Visual reconstruction. MIT Press, Cambridge, MA (1987). MR919733
  8. [8] B. Bourdin, Image segmentation with a finite element method. ESAIM: M2AN 33 (1999) 229–244. Zbl0947.65075
  9. [9] A. Braides, Approximation of free-discontinuity problems. Lect. Notes Math. 1694, Springer-Verlag (1998). Zbl0909.49001MR1651773
  10. [10] A. Braides and G. Dal Maso, Nonlocal approximation of the Mumford-Shah functional. Calc. Var. Partial Differential Equations 5 (1997) 293–322. Zbl0873.49009
  11. [11] S.C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods, Second Edition, Springer-Verlag, New York (2001). Zbl0804.65101MR1894376
  12. [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. [13] A. Chambolle, Image segmentation by variational methods: Mumford-Shah functional and the discrete approximation. SIAM J. Appl. Math. 55 (1995) 827–863. Zbl0830.49015
  14. [14] A. Chambolle and G. Dal Maso, Discrete approximation of the Mumford-Shah functional in dimension two. ESAIM: M2AN 33 (1999) 651–672. Zbl0943.49011
  15. [15] P.G. Ciarlet, Basic error estimates for elliptic problems, in Handbook of Numer. Anal. II, Elsevier Sciences Publishers (1991). Zbl0875.65086MR1115237
  16. [16] G. Dal Maso, An introduction to -convergence, Birkhäuser Boston, Boston, MA (1993). Zbl0816.49001MR1201152
  17. [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. Zbl0682.49002
  18. [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. Zbl0339.49005
  19. [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). Zbl0873.49008MR1438364
  20. [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. Zbl0668.65097
  21. [21] S. Esedoglu and J. Shen, Digital inpainting based on the Mumford-Shah-Euler image model. European J. Appl. Math. 13 (2002) 353–370. Zbl1017.94505
  22. [22] X. Feng and A. Prohl, Analysis of total variation flow and its finite element approximations. ESAIM: M2AN 37 (2003) 533–556. Zbl1050.35004
  23. [23] X. Feng and A. Prohl, On gradient flow of the Mumford-Shah functional. (in preparation). 
  24. [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. Zbl0573.62030
  25. [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). Zbl0463.65046MR635927
  26. [26] M. Gobbino, Gradient flow for the one-dimensional Mumford-Shah strategies. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 27 (1998) 145–193. Zbl0931.49010
  27. [27] J.L. Lions, Quelques méthodes de résolution des problèmes aux limites non linéaires, Dunod (1969). Zbl0189.40603MR259693
  28. [28] R. March and M. Dozio, A variational method for the recovery of smooth boundaries. Im. Vis. Comp. 15 (1997) 705–712. 
  29. [29] L. Modica, The gradient theory of phase transitions and the minimal interface criterion. Arch. Rational Mech. Anal. 98 (1987) 123–142. Zbl0616.76004
  30. [30] L. Modica and S. Mortola, Un esempio di -convergenza. Boll. Un. Mat. Ital. B 14 (1977) 285–299. Zbl0356.49008
  31. [31] J.-M. Morel and S. Solimini, Variational Methods in Image Segmentation, Birkhäuser (1995). MR1321598
  32. [32] D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42 (1989) 577–685. Zbl0691.49036
  33. [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. Zbl0876.35053
  34. [34] J. Simon, Compact sets in the space . Ann. Mat. Pura Appl. 146 (1987) 65–96. Zbl0629.46031
  35. [35] M. Struwe, Geometric evolution problems. IAS/Park City Math. Series 2 (1996) 259–339. Zbl0847.58012

NotesEmbed ?

top

You must be logged in to post comments.