Analysis of total variation flow and its finite element approximations

Feng, Xiaobing; Prohl, Andreas

ESAIM: Modélisation mathématique et analyse numérique, Tome 37 (2003) no. 3, pp. 533-556.

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 $\epsilon$, 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\to 0$, and to the total variation gradient flow problem as $h,k,\epsilon \to 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 $\epsilon$. Optimal order error bounds are derived for the numerical solution under the mesh relation $k=O\left(h^2\right)$. In particular, it is shown that all error bounds depend on $\frac{1}{\epsilon }$ only in some lower polynomial order for small $\epsilon$.

[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). | MR | Zbl

[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. | Zbl

[3] F. Andreu, C. Ballester, V. Caselles and J.M. Mazón, Minimizing total variation flow. Differential Integral Equations 14 (2001) 321-360. | Zbl

[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. | Zbl

[5] G. Bellettini and V. Caselles, The total variation flow in ${𝐑}^N$. J. Differential Equations (accepted). | Zbl

[6] S.C. Brenner and L.R. Scott, The mathematical theory of finite element methods. Springer-Verlag, New York, 2nd ed. (2002). | MR | Zbl

[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). | MR | Zbl

[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. | Zbl

[9] A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems. Numer. Math. 76 (1997) 167-188. | Zbl

[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). | MR | Zbl

[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). | Zbl

[12] P.G. Ciarlet, The finite element method for elliptic problems. North-Holland Publishing Co., Amsterdam, Stud. Math. Appl. 4 (1978). | MR | Zbl

[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. | Zbl

[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. | Zbl

[15] C. Gerhardt, Boundary value problems for surfaces of prescribed mean curvature. J. Math. Pures Appl. 58 (1979) 75-109. | Zbl

[16] C. Gerhardt, Evolutionary surfaces of prescribed mean curvature. J. Differential Equations 36 (1980) 139-172. | Zbl

[17] D. Gilbarg and N.S. Trudinger, Elliptic partial differential equations of second order. Springer-Verlag, Berlin (2001). Reprint of the 1998 ed. | MR | Zbl

[18] E. Giusti, Minimal surfaces and functions of bounded variation. Birkhäuser Verlag, Basel (1984). | MR | Zbl

[19] R. Hardt and X. Zhou, An evolution problem for linear growth functionals. Comm. Partial Differential Equations 19 (1994) 1879-1907. | Zbl

[20] C. Johnson and V. Thomée, Error estimates for a finite element approximation of a minimal surface. Math. Comp. 29 (1975) 343-349. | Zbl

[21] A. Lichnewsky and R. Temam, Pseudosolutions of the time-dependent minimal surface problem. J. Differential Equations 30 (1978) 340-364. | Zbl

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

[23] R. Rannacher, Some asymptotic error estimates for finite element approximation of minimal surfaces. RAIRO Anal. Numér. 11 (1977) 181-196. | Numdam | Zbl

[24] L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms. Phys. D 60 (1992) 259-268. | Zbl

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

[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). | MR | Zbl