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 (2010)

  • 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 L2 x L∞ 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 H1 x H1 ∩ L∞. 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 1 ε and 1 k ε only in low polynomial order, are derived for the proposed fully discrete schemes under the mesh relation k = o ( h 1 2 ) . 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 38.2 (2010): 291-320. <http://eudml.org/doc/194215>.

@article{Feng2010,
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 L2 x L∞ 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 H1 x H1 ∩ L∞. 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^\{\frac12\})$. 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},
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; finite element method; error analysis},
language = {eng},
month = {3},
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/194215},
volume = {38},
year = {2010},
}

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
DA - 2010/3//
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 L2 x L∞ 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 H1 x H1 ∩ L∞. 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^{\frac12})$. 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; finite element method; error analysis
UR - http://eudml.org/doc/194215
ER -

References

top
  1. R.A. Adams, Sobolev Spaces. Academic Press, New York (1975).  
  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.  
  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.  
  4. L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems. Oxford University Press (2000).  
  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.  
  6. G. Bellettini and A. Coscia, Discrete approximation of a free discontinuity problem. Numer. Funct. Anal. Optimiz.15 (1994) 201–224.  
  7. A. Blake and A. Zisserman, Visual reconstruction. MIT Press, Cambridge, MA (1987).  
  8. B. Bourdin, Image segmentation with a finite element method. ESAIM: M2AN33 (1999) 229–244.  
  9. A. Braides, Approximation of free-discontinuity problems. Lect. Notes Math.1694, Springer-Verlag (1998).  
  10. A. Braides and G. Dal Maso, Nonlocal approximation of the Mumford-Shah functional. Calc. Var. Partial Differential Equations5 (1997) 293–322.  
  11. S.C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods, Second Edition, Springer-Verlag, New York (2001).  
  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.  
  14. A. Chambolle and G. Dal Maso, Discrete approximation of the Mumford-Shah functional in dimension two. ESAIM: M2AN33 (1999) 651–672.  
  15. P.G. Ciarlet, Basic error estimates for elliptic problems, in Handbook of Numer. Anal.II, Elsevier Sciences Publishers (1991).  
  16. G. Dal Maso, An introduction to Γ-convergence, Birkhäuser Boston, Boston, MA (1993).  
  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.  
  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.  
  19. F. Dibos and E. Séré, An approximation result for the minimizers of the Mumford-Shah functional. Boll. Un. Mat. Ital. A11 (1997).  
  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.  
  21. S. Esedoglu and J. Shen, Digital inpainting based on the Mumford-Shah-Euler image model. European J. Appl. Math.13 (2002) 353–370.  
  22. X. Feng and A. Prohl, Analysis of total variation flow and its finite element approximations. ESAIM: M2AN37 (2003) 533–556.  
  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.  
  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).  
  26. M. Gobbino, Gradient flow for the one-dimensional Mumford-Shah strategies. Ann. Scuola Norm. Sup. Pisa Cl. Sci.27 (1998) 145–193.  
  27. J.L. Lions, Quelques méthodes de résolution des problèmes aux limites non linéaires, Dunod (1969).  
  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.  
  30. L. Modica and S. Mortola, Un esempio di Γ-convergenza. Boll. Un. Mat. Ital. B14 (1977) 285–299.  
  31. J.-M. Morel and S. Solimini, Variational Methods in Image Segmentation, Birkhäuser (1995).  
  32. D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math.42 (1989) 577–685.  
  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.  
  34. J. Simon, Compact sets in the space Lp(0,T;B). Ann. Mat. Pura Appl.146 (1987) 65–96.  
  35. M. Struwe, Geometric evolution problems. IAS/Park City Math. Series2 (1996) 259–339.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.