Analysis of total variation flow and its finite element approximations

Xiaobing Feng; Andreas Prohl

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

  • Volume: 37, Issue: 3, page 533-556
  • ISSN: 0764-583X

Abstract

top
We study the gradient flow for the total variation functional, which arises in image processing and geometric applications. We propose a variational inequality weak formulation for the gradient flow, and establish well-posedness of the problem by the energy method. The main idea of our approach is to exploit the relationship between the regularized gradient flow (characterized by a small positive parameter ε , and the minimal surface flow [21] and the prescribed mean curvature flow [16]. Since our approach is constructive and variational, finite element methods can be naturally applied to approximate weak solutions of the limiting gradient flow problem. We propose a fully discrete finite element method and establish convergence to the regularized gradient flow problem as h , k → 0 , and to the total variation gradient flow problem as h , k , ε → 0 in general cases. Provided that the regularized gradient flow problem possesses strong solutions, which is proved possible if the datum functions are regular enough, we establish practical a priori error estimates for the fully discrete finite element solution, in particular, by focusing on the dependence of the error bounds on the regularization parameter ε . Optimal order error bounds are derived for the numerical solution under the mesh relation k = O ( h 2 ) . In particular, it is shown that all error bounds depend on 1 ε only in some lower polynomial order for small ε .

How to cite

top

Feng, Xiaobing, and Prohl, Andreas. "Analysis of total variation flow and its finite element approximations." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 37.3 (2003): 533-556. <http://eudml.org/doc/245487>.

@article{Feng2003,
abstract = {We study the gradient flow for the total variation functional, which arises in image processing and geometric applications. We propose a variational inequality weak formulation for the gradient flow, and establish well-posedness of the problem by the energy method. The main idea of our approach is to exploit the relationship between the regularized gradient flow (characterized by a small positive parameter $\{\varepsilon \}$, and the minimal surface flow [21] and the prescribed mean curvature flow [16]. Since our approach is constructive and variational, finite element methods can be naturally applied to approximate weak solutions of the limiting gradient flow problem. We propose a fully discrete finite element method and establish convergence to the regularized gradient flow problem as $h,k\rightarrow 0$, and to the total variation gradient flow problem as $h,k,\{\varepsilon \}\rightarrow 0$ in general cases. Provided that the regularized gradient flow problem possesses strong solutions, which is proved possible if the datum functions are regular enough, we establish practical a priori error estimates for the fully discrete finite element solution, in particular, by focusing on the dependence of the error bounds on the regularization parameter $\varepsilon $. Optimal order error bounds are derived for the numerical solution under the mesh relation $k=O(h^2)$. In particular, it is shown that all error bounds depend on $\frac\{1\}\{\varepsilon \}$ only in some lower polynomial order for small $\varepsilon $.},
author = {Feng, Xiaobing, Prohl, Andreas},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {bounded variation; gradient flow; variational inequality; equations of prescribed mean curvature and minimal surface; fully discrete scheme; finite element method},
language = {eng},
number = {3},
pages = {533-556},
publisher = {EDP-Sciences},
title = {Analysis of total variation flow and its finite element approximations},
url = {http://eudml.org/doc/245487},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Feng, Xiaobing
AU - Prohl, Andreas
TI - Analysis of total variation flow and its finite element approximations
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2003
PB - EDP-Sciences
VL - 37
IS - 3
SP - 533
EP - 556
AB - We study the gradient flow for the total variation functional, which arises in image processing and geometric applications. We propose a variational inequality weak formulation for the gradient flow, and establish well-posedness of the problem by the energy method. The main idea of our approach is to exploit the relationship between the regularized gradient flow (characterized by a small positive parameter ${\varepsilon }$, and the minimal surface flow [21] and the prescribed mean curvature flow [16]. Since our approach is constructive and variational, finite element methods can be naturally applied to approximate weak solutions of the limiting gradient flow problem. We propose a fully discrete finite element method and establish convergence to the regularized gradient flow problem as $h,k\rightarrow 0$, and to the total variation gradient flow problem as $h,k,{\varepsilon }\rightarrow 0$ in general cases. Provided that the regularized gradient flow problem possesses strong solutions, which is proved possible if the datum functions are regular enough, we establish practical a priori error estimates for the fully discrete finite element solution, in particular, by focusing on the dependence of the error bounds on the regularization parameter $\varepsilon $. Optimal order error bounds are derived for the numerical solution under the mesh relation $k=O(h^2)$. In particular, it is shown that all error bounds depend on $\frac{1}{\varepsilon }$ only in some lower polynomial order for small $\varepsilon $.
LA - eng
KW - bounded variation; gradient flow; variational inequality; equations of prescribed mean curvature and minimal surface; fully discrete scheme; finite element method
UR - http://eudml.org/doc/245487
ER -

References

top
  1. [1] L. Ambrosio, N. Fusco and D. Pallara, Functions of bounded variation and free discontinuity problems. The Clarendon Press Oxford University Press, New York (2000). Zbl0957.49001MR1857292
  2. [2] F. Andreu, C. Ballester, V. Caselles and J.M. Mazón, The Dirichlet problem for the total variation flow. J. Funct. Anal. 180 (2001) 347–403. Zbl0973.35109
  3. [3] F. Andreu, C. Ballester, V. Caselles and J.M. Mazón, Minimizing total variation flow. Differential Integral Equations 14 (2001) 321–360. Zbl1020.35037
  4. [4] F. Andreu, V. Caselles, J.I. Díaz and J.M. Mazón, Some qualitative properties for the total variation flow. J. Funct. Anal. 188 (2002) 516–547. Zbl1042.35018
  5. [5] G. Bellettini and V. Caselles, The total variation flow in 𝐑 N . J. Differential Equations (accepted). Zbl1036.35099
  6. [6] S.C. Brenner and L.R. Scott, The mathematical theory of finite element methods. Springer-Verlag, New York, 2nd ed. (2002). Zbl0804.65101MR1894376
  7. [7] H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. North-Holland Publishing Co., Amsterdam, North-Holland Math. Stud., No. 5. Notas de Matemática (50) (1973). Zbl0252.47055MR348562
  8. [8] E. Casas, K. Kunisch and C. Pola, Regularization by functions of bounded variation and applications to image enhancement. Appl. Math. Optim. 40 (1999) 229–257. Zbl0942.49014
  9. [9] A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems. Numer. Math. 76 (1997) 167–188. Zbl0874.68299
  10. [10] T. Chan and J. Shen, On the role of the BV image model in image restoration. Tech. Report CAM 02-14, Department of Mathematics, UCLA (2002). Zbl1035.94501MR2011710
  11. [11] T.F. Chan, G.H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20 (1999) 1964–1977 (electronic). Zbl0929.68118
  12. [12] P.G. Ciarlet, The finite element method for elliptic problems. North-Holland Publishing Co., Amsterdam, Stud. Math. Appl. 4 (1978). Zbl0383.65058MR520174
  13. [13] M.G. Crandall and T.M. Liggett, Generation of semi-groups of nonlinear transformations on general Banach spaces. Amer. J. Math. 93 (1971) 265–298. Zbl0226.47038
  14. [14] D.C. Dobson and C.R. Vogel, Convergence of an iterative method for total variation denoising. SIAM J. Numer. Anal. 34 (1997) 1779–1791. Zbl0898.65034
  15. [15] C. Gerhardt, Boundary value problems for surfaces of prescribed mean curvature. J. Math. Pures Appl. 58 (1979) 75–109. Zbl0413.35024
  16. [16] C. Gerhardt, Evolutionary surfaces of prescribed mean curvature. J. Differential Equations 36 (1980) 139–172. Zbl0485.35053
  17. [17] D. Gilbarg and N.S. Trudinger, Elliptic partial differential equations of second order. Springer-Verlag, Berlin (2001). Reprint of the 1998 ed. Zbl1042.35002MR1814364
  18. [18] E. Giusti, Minimal surfaces and functions of bounded variation. Birkhäuser Verlag, Basel (1984). Zbl0545.49018MR775682
  19. [19] R. Hardt and X. Zhou, An evolution problem for linear growth functionals. Comm. Partial Differential Equations 19 (1994) 1879–1907. Zbl0811.35061
  20. [20] C. Johnson and V. Thomée, Error estimates for a finite element approximation of a minimal surface. Math. Comp. 29 (1975) 343–349. Zbl0302.65086
  21. [21] A. Lichnewsky and R. Temam, Pseudosolutions of the time-dependent minimal surface problem. J. Differential Equations 30 (1978) 340–364. Zbl0368.49016
  22. [22] J.-L. Lions, Quelques méthodes de résolution des problèmes aux limites non linéaires. Dunod (1969). Zbl0189.40603MR259693
  23. [23] R. Rannacher, Some asymptotic error estimates for finite element approximation of minimal surfaces. RAIRO Anal. Numér. 11 (1977) 181–196. Zbl0356.35034
  24. [24] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms. Phys. D 60 (1992) 259–268. Zbl0780.49028
  25. [25] J. Simon, Compact sets in the space L p ( 0 , T ; B ) . Ann. Mat. Pura Appl. 146 (1987) 65–96. Zbl0629.46031
  26. [26] M. Struwe, Applications to nonlinear partial differential equations and Hamiltonian systems, in Variational methods. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics (Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics), Vol. 34. Springer-Verlag, Berlin, 3rd ed. (2000). Zbl0939.49001MR1736116

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.