×

An adaptive finite element method in \(L^2\)-TV-based image denoising. (English) Zbl 1404.65265

Summary: 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.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65K10 Numerical optimization and variational techniques
68U10 Computing methodologies for image processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

COMSOL; na14
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Acar, Analysis of bounded variation penalty methods for ill-posed problems,, Inverse Prolems, 10, 1217 (1994) · Zbl 0809.35151 · doi:10.1088/0266-5611/10/6/003
[2] R. A. Adams, <em>Sobolev Spaces</em>, volume 140., Academic Press (2003)
[3] M. Ainsworth, <em>A Posteriori Error Estimation in Finite Element Analysis</em>,, Wiley (2000) · Zbl 1008.65076 · doi:10.1002/9781118032824
[4] J. Alberty, Remarks around 50 lines of matlab: Short finite element implementation,, Numerical Algorithms, 20, 117 (1999) · Zbl 0938.65129 · doi:10.1023/A:1019155918070
[5] A. Almansa, A TV based restoration model with local constraints,, Journal Scientific Computing, 34, 209 (2008) · Zbl 1218.94007 · doi:10.1007/s10915-007-9160-x
[6] W. Bangerth, Adaptive finite element methods for the solution of inverse problems in optical tomography,, Inverse Problems, 24 (2008) · Zbl 1142.65087 · doi:10.1088/0266-5611/24/3/034011
[7] W. Bangerth, <em>Adaptive Finite Element Methods for Differential Equations</em>,, Birkhäuser (2003) · Zbl 1020.65058 · doi:10.1007/978-3-0348-7605-6
[8] E. Bänsch, A coarsening finite element strategy in images selective smoothing,, Computing and Visualization in Science, 1, 53 (1997) · Zbl 0971.65084
[9] C. Bazan, Adaptive finite element method for image processing,, In Proceedings of the COMSOL Multiphysics Conference 2005 Boston (2005)
[10] E. C. Bingham, <em>Fluidity and Plasticty</em>,, International chemical series. McGraw-Hill Book Company (1922)
[11] V. Bostan, A posteriori error estimation and adaptive solution of elliptic variational inequalities of the second kind,, Applied Numerical Mathematics, 52, 13 (2005) · Zbl 1069.65067 · doi:10.1016/j.apnum.2004.06.012
[12] D. Braess, A posteriori error estimators for the Raviart-Thomas element,, SIAM J. Numer. Anal., 33, 2431 (1996) · Zbl 0866.65071 · doi:10.1137/S0036142994264079
[13] F. Brezzi, <em>Mixed and Hybrid Finite Element Methods</em>,, Springer-Verlag (1991) · Zbl 0788.73002 · 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, 89 (2004) · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011321.19549.88
[15] A. Chambolle, Image recovery via total variation minimization and related problems,, Numerische Mathematik, 76, 167 (1997) · Zbl 0874.68299 · doi:10.1007/s002110050258
[16] Q. Chang, Acceleration methods for total variation-based image denoising,, SIAM J. Applied Mathematics, 25, 982 (2003) · Zbl 1046.65048 · doi:10.1137/S106482750241534X
[17] P. G. Ciarlet, <em>The Finite Element Method for Elliptic Problems</em>,, North Holland (1978) · Zbl 0383.65058
[18] P. Clément, Approximation by finite element functions using local regularization,, RAIRO Analyse Numérique, 9, 77 (1975) · Zbl 0368.65008
[19] E. J. Dean, On the numerical simulation of Bingham visco-plastic flow: Old and new results,, Journal of Non-Newtonian Fluid Mechanics, 142, 36 (2007) · Zbl 1107.76061 · doi:10.1016/j.jnnfm.2006.09.002
[20] D. C. Dobson, Convergence of an iterative method for total variation denoising,, SIAM J. Numer. Anal., 34, 1779 (1997) · Zbl 0898.65034 · doi:10.1137/S003614299528701X
[21] Y. Dong, Automated regularization parameter selection in multi-scale total variation models for image restoration,, Journal of Mathematical Imaging and Vision, 40, 82 (2011) · Zbl 1255.68230 · doi:10.1007/s10851-010-0248-9
[22] G. Duvaut, <em>Inequalities in Mechanics and Physics</em>,, Springer-Verlag (1976) · Zbl 0331.35002
[23] I. Ekeland, <em>Convex Analysis and Variational Problems</em>,, Classics Appl. Math. 28 (1999) · Zbl 0939.49002 · doi:10.1137/1.9781611971088
[24] X. Feng, Analysis of total variation flow and its finite element approximations,, ESAIM: Mathematical Modelling and Numerical Analysis, 37, 533 (2003) · Zbl 1050.35004 · doi:10.1051/m2an:2003041
[25] K. Frick, Statistical multiresolution dantzig estimation in imaging: Fundamental concepts and algorithmic framework,, Electronic Journal of Statistics, 6, 231 (2012) · Zbl 1314.62094 · doi:10.1214/12-EJS671
[26] K. Frick, Statistical multiresolution estimation for variational imaging: with an application in Poisson-biophotonics,, J. Math. Imaging Vision, 46, 370 (2013) · Zbl 1312.68222 · doi:10.1007/s10851-012-0368-5
[27] M. Fried, Multichannel image segmentation using adaptive finite elements,, Computing and Visualization in Science, 12, 125 (2009) · Zbl 1512.94005 · doi:10.1007/s00791-007-0082-9
[28] I. A. Frigaard, Uniaxial exchange flows of two Bingham fluids in a cylindrical duct,, IMA journal of applied mathematics, 61, 237 (1998) · Zbl 0928.76010 · doi:10.1093/imamat/61.3.237
[29] I. A. Frigaard, The effects of yield stress variation on uniaxial exchange flows of two Bingham fluids in a pipe,, SIAM J. Appl. Math., 60, 1950 (2000) · Zbl 0988.35007 · doi:10.1137/S0036139998335165
[30] E. Giusti, <em>Minimal Surfaces and Functions of Bounded Variation</em>,, Birkhäuser (1984) · Zbl 0545.49018 · doi:10.1007/978-1-4684-9486-0
[31] R. Glowinski, <em>Analyse Numérique des Inéquations Variationelles</em>,, Dunod (1976)
[32] E. J. Gumbel, Les valeurs extrêmes des distributions statistiques,, Annales de l’institut Henri Poincaré, 5, 115 (1935) · Zbl 0011.36102
[33] M. Guven et al, Effect of discretization error analysis and adaptive mesh generation in diffuse optical absorption imaging: I,, Inverse Problems, 23, 1115 (2007) · Zbl 1119.65112 · 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, 217 (2010)
[35] E. Haber, Adaptive finite volume method for distributed non-smooth parameter identification,, Inverse Problems, 23, 1659 (2007) · Zbl 1121.65074 · doi:10.1088/0266-5611/23/4/017
[36] E. Haber, An octree method for parametric image registration,, SIAM J. on Scientific Computing, 29, 2008 (2007) · Zbl 1151.94006 · doi:10.1137/060662605
[37] E. Haber, Adaptive mesh refinement for non parametric image registration,, SIAM J. on Scientific Computing, 30, 3012 (2008) · Zbl 1175.94017 · doi:10.1137/070687724
[38] E. Hashrova, Extremes of independent chi-square random vectors,, Extremes, 15, 35 (2012) · Zbl 1329.60028 · doi:10.1007/s10687-010-0125-3
[39] M. Hintermüller, An a posteriori error analysis of adaptive finite element methods for distributed elliptic control problems with control constraints,, ESAIM: COCV, 14, 540 (2008) · Zbl 1157.65039 · doi:10.1051/cocv:2007057
[40] M. Hintermüller, The primal-dual active set strategy as a semismooth newton method,, SIAM Journal on Optimization, 13, 865 (2002) · Zbl 1080.90074 · doi:10.1137/S1052623401383558
[41] M. Hintermüller, Total bounded variation regularization as bilaterally constrained optimization problem,, SIAM J. Appl. Math., 64, 1311 (2004) · Zbl 1055.94504 · doi:10.1137/S0036139903422784
[42] M. Hintermüller, An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration,, SIAM Journal on Scientific Computing, 28, 1 (2006) · Zbl 1136.94302 · doi:10.1137/040613263
[43] T. Hotz, Locally adaptive image denoising by a statistical multiresolution criterion,, Comput. Stat. Data Anal., 56, 543 (2012) · Zbl 1239.62116 · doi:10.1016/j.csda.2011.08.018
[44] S. Osher, An iterative regularization method for total variation-based image restoration,, SIAM Multiscale Model. and Simu., 4, 460 (2005) · Zbl 1090.94003 · doi:10.1137/040605412
[45] T. Preusser, 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
[46] N. Roquet, An adaptive finite element method for bingham fluid flows around a cylinder,, Computer Methods in Applied Mechanics and Engineering, 192, 3317 (2003) · Zbl 1054.76053 · doi:10.1016/S0045-7825(03)00262-7
[47] L. I. Rudin, Nonlinear total variation based noise removal algorithms,, Physica D, 60, 259 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[48] L. Rudin, <em>MTV-multiscale Total Variation Principle for a Pde-based Solution to Nonsmooth Ill-posed Problem,</em>, Technical report (1995)
[49] D. Strong, <em>Spatially and Scale Adaptive Total Variation Based Regularization and Anisotropic Diffusion in Image Processing</em>,, Technical report (1996)
[50] D. Strong, Edge-preserving and scale-dependent properties of total variation regularization,, Inverse Problems, 19 (2003) · Zbl 1043.94512 · doi:10.1088/0266-5611/19/6/059
[51] R. Temam, <em>Navier-Stokes Equations</em>,, North-Holland (1977) · Zbl 0335.35077
[52] R. Verfürth, <em>A Review of A Posteriori Error Estimation and Adaptive Mesh Refinement Techniques</em>,, Wiley Teubner (1996) · Zbl 0853.65108
[53] C. R. Vogel, <em>Computational Methods for Inverse Problems</em>, volume 23 of <em>Frontiers Appl. Math.</em>, SIAM-Society of Industrial and Applied Mathematics (2002) · Zbl 1008.65103 · doi:10.1137/1.9780898717570
[54] G. Winkler, <em>Image Analysis, Random Fields And Markov Chain Monte Carlo Methods: A Mathematical Introduction</em>,, Applications of mathematics. Springer (2003) · Zbl 1008.68147 · doi:10.1007/978-3-642-55760-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.