An adaptive finite element method in $L^2$-TV-based image denoising

Michael Hintermüller; Monserrat Rincon-Camacho

doi:10.3934/ipi.2014.8.685

Article Contents

2014, Volume 8, Issue 3: 685-711. Doi: 10.3934/ipi.2014.8.685

This issue Previous Article Resolution enhancement from scattering in passive sensor imaging with cross correlations Next Article Stability of the determination of a coefficient for wave equations in an infinite waveguide

An adaptive finite element method in $L^2$-TV-based image denoising

Michael Hintermüller^1, and
Monserrat Rincon-Camacho^2,

1.
Department of Mathematics, Humboldt-University of Berlin, Unter den Linden 6, 10099 Berlin
2.
START-Project "Interfaces and Free Boundaries" and SFB "Mathematical Optimization and Applications in Biomedical Science", Institute of Mathematics and Scientific Computing, University of Graz, Heinrichstrasse 36, A-8010 Graz

Received: September 30, 2012

Revised: May 31, 2013

Published: July 2014

Abstract Related Papers Cited by

Abstract

The first order optimality system of a total variation regularization based variational model with $L^2$-data-fitting in image denoising ($L^2$-TV problem) can be expressed as an elliptic variational inequality of the second kind. For a finite element discretization of the variational inequality problem, an a posteriori error residual based error estimator is derived and its reliability and (partial) efficiency are established. The results are applied to solve the $L^2$-TV problem by means of the adaptive finite element method. The adaptive mesh refinement relies on the newly derived a posteriori error estimator and on an additional heuristic providing a local variance estimator to cope with noisy data. The numerical solution of the discrete problem on each level of refinement is obtained by a superlinearly convergent algorithm based on Fenchel-duality and inexact semismooth Newton techniques and which is stable with respect to noise in the data. Numerical results justifying the advantage of adaptive finite elements solutions are presented.

Keywords:

A posteriori error estimation,
elliptic variational inequality of the second kind,
adaptive finite elements,
total variation,
primal-dual method,
semismooth Newton method.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	R. Acar and C. R. Vogel, Analysis of bounded variation penalty methods for ill-posed problems, Inverse Prolems, 10 (1994), 1217-1229.doi: 10.1088/0266-5611/10/6/003.
[2]	R. A. Adams and J. J. Fournier, Sobolev Spaces, volume 140. Academic Press, 2nd edition, 2003.
[3]	M. Ainsworth and J. T. Oden, A Posteriori Error Estimation in Finite Element Analysis, Wiley, New York, 2000.doi: 10.1002/9781118032824.
[4]	J. Alberty, C. Carstensen and S. Funken, Remarks around 50 lines of matlab: Short finite element implementation, Numerical Algorithms, 20 (1999), 117-137.doi: 10.1023/A:1019155918070.
[5]	A. Almansa, C. Ballester, V. Caselles and G. Haro, A TV based restoration model with local constraints, Journal Scientific Computing, 34 (2008), 209-236.doi: 10.1007/s10915-007-9160-x.
[6]	W. Bangerth and A. Joshi, Adaptive finite element methods for the solution of inverse problems in optical tomography, Inverse Problems, 24 (2008), 034011, 22 pp.doi: 10.1088/0266-5611/24/3/034011.
[7]	W. Bangerth and R. Rannacher, Adaptive Finite Element Methods for Differential Equations, Birkhäuser, 2003.doi: 10.1007/978-3-0348-7605-6.
[8]	E. Bänsch and K. Mikula, A coarsening finite element strategy in images selective smoothing, Computing and Visualization in Science, 1 (1997), 53-61.
[9]	C. Bazan and P. Blomgren, Adaptive finite element method for image processing, In Proceedings of the COMSOL Multiphysics Conference 2005 Boston, 2005.
[10]	E. C. Bingham, Fluidity and Plasticty, International chemical series. McGraw-Hill Book Company, inc., 1922.
[11]	V. Bostan, W. Han and B. D. Reddy, A posteriori error estimation and adaptive solution of elliptic variational inequalities of the second kind, Applied Numerical Mathematics, 52 (2005), 13-38.doi: 10.1016/j.apnum.2004.06.012.
[12]	D. Braess and R. Verfürth, A posteriori error estimators for the Raviart-Thomas element, SIAM J. Numer. Anal., 33 (1996), 2431-2444.doi: 10.1137/S0036142994264079.
[13]	F. Brezzi and M. Fortin, Mixed and Hybrid Finite Element Methods, Springer-Verlag, New York, 1991.doi: 10.1007/978-1-4612-3172-1.
[14]	A. Chambolle, An algorithm for total variation minimization and application, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.
[15]	A. Chambolle and P-L. Lions., Image recovery via total variation minimization and related problems, Numerische Mathematik, 76 (1997), 167-188.doi: 10.1007/s002110050258.
[16]	Q. Chang and I-L. Chern, Acceleration methods for total variation-based image denoising, SIAM J. Applied Mathematics, 25 (2003), 982-994.doi: 10.1137/S106482750241534X.
[17]	P. G. Ciarlet, The Finite Element Method for Elliptic Problems, North Holland, 1978.
[18]	P. Clément, Approximation by finite element functions using local regularization, RAIRO Analyse Numérique, 9 (1975), 77-84.
[19]	E. J. Dean, R. Glowinski and G. Guidoboni, On the numerical simulation of Bingham visco-plastic flow: Old and new results, Journal of Non-Newtonian Fluid Mechanics, 142 (2007), 36-62.doi: 10.1016/j.jnnfm.2006.09.002.
[20]	D. C. Dobson and C. R. Vogel, Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal., 34 (1997), 1779-1791.doi: 10.1137/S003614299528701X.
[21]	Y. Dong, M. Hintermüller and M. M. Rincon-Camacho, Automated regularization parameter selection in multi-scale total variation models for image restoration, Journal of Mathematical Imaging and Vision, 40 (2011), 82-104.doi: 10.1007/s10851-010-0248-9.
[22]	G. Duvaut and J. L. Lions, Inequalities in Mechanics and Physics, Springer-Verlag, Berlin, 1976.
[23]	I. Ekeland and R. Témam, Convex Analysis and Variational Problems, Classics Appl. Math. 28, SIAM, 1999.doi: 10.1137/1.9781611971088.
[24]	X. Feng and A. Prohl, Analysis of total variation flow and its finite element approximations, ESAIM: Mathematical Modelling and Numerical Analysis, 37 (2003), 533-556.doi: 10.1051/m2an:2003041.
[25]	K. Frick and P. Marnitz, Statistical multiresolution dantzig estimation in imaging: Fundamental concepts and algorithmic framework, Electronic Journal of Statistics, 6 (2012), 231-268.doi: 10.1214/12-EJS671.
[26]	K. Frick, P. Marnitz and A. Munk, Statistical multiresolution estimation for variational imaging: with an application in Poisson-biophotonics, J. Math. Imaging Vision, 46 (2013), 370-387.doi: 10.1007/s10851-012-0368-5.
[27]	M. Fried, Multichannel image segmentation using adaptive finite elements, Computing and Visualization in Science, 12 (2009), 125-135.doi: 10.1007/s00791-007-0082-9.
[28]	I. A. Frigaard and O. Scherzer, Uniaxial exchange flows of two Bingham fluids in a cylindrical duct, IMA journal of applied mathematics, 61 (1998), 237-266.doi: 10.1093/imamat/61.3.237.
[29]	I. A. Frigaard and O. Scherzer, The effects of yield stress variation on uniaxial exchange flows of two Bingham fluids in a pipe, SIAM J. Appl. Math., 60 (2000), 1950-1976.doi: 10.1137/S0036139998335165.
[30]	E. Giusti, Minimal Surfaces and Functions of Bounded Variation, Birkhäuser, 1984.doi: 10.1007/978-1-4684-9486-0.
[31]	R. Glowinski, J. L. Lions and R. Trémolières, Analyse Numérique des Inéquations Variationelles, Dunod, Paris, France, 1976.
[32]	E. J. Gumbel, Les valeurs extrêmes des distributions statistiques, Annales de l'institut Henri Poincaré, 5 (1935), 115-158.
[33]	M. Guven et al, Effect of discretization error analysis and adaptive mesh generation in diffuse optical absorption imaging: I, Inverse Problems, 23 (2007), 1115-1133.doi: 10.1088/0266-5611/23/3/017.
[34]	M. Guven et al, Discretization error analysis and adaptive meshing algorithms for fluorescence diffuse optical tomography: Part I, IEEE Trans. Med. Imag., 29 (2010), 217-229.
[35]	E. Haber, S. Heldmann and U. Ascher, Adaptive finite volume method for distributed non-smooth parameter identification, Inverse Problems, 23 (2007), 1659-1676.doi: 10.1088/0266-5611/23/4/017.
[36]	E. Haber, S. Heldmann and J. Modersitzki, An octree method for parametric image registration, SIAM J. on Scientific Computing, 29 (2007), 2008-2023.doi: 10.1137/060662605.
[37]	E. Haber, S. Heldmann and J. Modersitzki, Adaptive mesh refinement for non parametric image registration, SIAM J. on Scientific Computing, 30 (2008), 3012-3027.doi: 10.1137/070687724.
[38]	E. Hashrova, Z. Kabluchko and A. Wübker, Extremes of independent chi-square random vectors, Extremes, 15 (2012), 35-42.doi: 10.1007/s10687-010-0125-3.
[39]	M. Hintermüller, R. H. W. Hoppe, Y. Iliash and M. Kieweg, An a posteriori error analysis of adaptive finite element methods for distributed elliptic control problems with control constraints, ESAIM: COCV, 14 (2008), 540-560.doi: 10.1051/cocv:2007057.
[40]	M. Hintermüller, K. Ito and K. Kunisch, The primal-dual active set strategy as a semismooth newton method, SIAM Journal on Optimization, 13 (2002), 865-888.doi: 10.1137/S1052623401383558.
[41]	M. Hintermüller and K. Kunisch, Total bounded variation regularization as bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), 1311-1333.doi: 10.1137/S0036139903422784.
[42]	M. Hintermüller and G. Stadler, An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration, SIAM Journal on Scientific Computing, 28 (2006), 1-23.doi: 10.1137/040613263.
[43]	T. Hotz, P. Marnitz, R. Stichtenoth, L. Davies, Z. Kabluchko and A. Munk, Locally adaptive image denoising by a statistical multiresolution criterion, Comput. Stat. Data Anal., 56 (2012), 543-558.doi: 10.1016/j.csda.2011.08.018.
[44]	S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, SIAM Multiscale Model. and Simu., 4 (2005), 460-489.doi: 10.1137/040605412.
[45]	T. Preusser and M. Rumpf, An adaptive finite element method for large scale image processing, In Proceedings of the Second International Conference on Scale-Space Theories in Computer Vision, 223-234.
[46]	N. Roquet and P. Saramito, An adaptive finite element method for bingham fluid flows around a cylinder, Computer Methods in Applied Mechanics and Engineering, 192 (2003), 3317-3341.doi: 10.1016/S0045-7825(03)00262-7.
[47]	L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[48]	L. Rudin, MTV-multiscale Total Variation Principle for a Pde-based Solution to Nonsmooth Ill-posed Problem, Technical report, Cognitech, Inc. Talk presented at the Workshop on Mathematical Methods in Computer Vision, University of Minnesota, 1995.
[49]	D. Strong and T. Chan, Spatially and Scale Adaptive Total Variation Based Regularization and Anisotropic Diffusion in Image Processing, Technical report, UCLA, 1996.
[50]	D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization, Inverse Problems, 19 (2003), S165-S187.doi: 10.1088/0266-5611/19/6/059.
[51]	R. Temam, Navier-Stokes Equations, North-Holland, Amsterdam, 1977.
[52]	R. Verfürth, A Review of A Posteriori Error Estimation and Adaptive Mesh Refinement Techniques, Wiley Teubner, 1996.
[53]	C. R. Vogel, Computational Methods for Inverse Problems, volume 23 of Frontiers Appl. Math. SIAM-Society of Industrial and Applied Mathematics, 2002.doi: 10.1137/1.9780898717570.
[54]	G. Winkler, Image Analysis, Random Fields And Markov Chain Monte Carlo Methods: A Mathematical Introduction, Applications of mathematics. Springer, 2003.doi: 10.1007/978-3-642-55760-6.