Regularization with Solution-driven Adaptivity

Frank Lenzen¹

joint work with Florian Becker¹, Johannes Berger², Jan Lellmann³, Stefania Petra⁴ and Christoph Schnörr^1,2

¹ Heidelberg Collaboratory for Image Processing (HCI), University of Heidelberg
² Image and Pattern Analysis Group (IPA), University of Heidelberg
³ Department of Applied Mathematics and Theoretical Physics (DAMTP), University of Cambridge
⁴ Mathematical Imaging Group, University of Heidelberg

Content

2. Adaptive Total Variation Regularization

Background

For image restoration tasks such as denoising, deblurring and inpainting an appropriate reconstruction of prominent image structures such as edges and corners is of importance.

Total variation (TV) based regularization approaches of first and higher order (see e.g.[6,27]) have proven to be suitable with this respect. In particular those methods, which locally adapt to image structures in the data have shown a high potential for providing good reconstruction results [1-5,9-22,25,26,28-30]. We distinguish between methods which locally adapt the regularization strength ('weighted TV') [5,11-13,16,25,26,29-30] and methods which introduce an anisotropic, i.e. directionally dependent penalization of the image gradient (or of higher order derivatives) [1-3,10,15,17-22,28]. We refer to the latter as 'anisotropic TV' methods. Moreover, there exist methods which locally change from TV to a quadratic regularization of the image gradient, see e.g. [4].

Adaptive regularization methods require additional information which steers the adaptivity. The standard strategy is to pre-process the input data to determine specific image structures or to provide a guiding image for adaptivity. We refer to such models of adaptivity as data-driven.

However, these data only provide an estimate of the image structures of the undistorted image. Therefore, it is beneficial to propose adaptive models which are steered directly by the unknown image. We refer to this kind of adaptivity as solution-driven. Several approaches of this kind have been introduced in literature [1,10,15,17-22]. Below, we focus on a special kind of solution-driven adaptive regularization approach, which is stated in terms of a fixed point problem. Before discussing this approach, we first consider a more general model of adaptive regularization and introduce some notation.

Adaptive Total Variation Regularization

We consider the task of restoring an image u from some given input data f by means of a variational method. To this end, we consider the minimization task

min_u F(u) = min_u S(u) + R(u),

where S(u) is some data or fidelity term and R(u) is some regularization term. (Different to the standard notation, we assume the regularization strength, i.e. the factor coupling both terms, as implicitly included in R.) As mentioned above, adaptive regularization requires some parameters to locally steer the adaptivity. Typically these parameters depend on the input image f, a guiding image g or the unknown image u. To account for this dependency we introduce an additional argument v of R, i.e. R=R(u;v), where v represents an arbitrary image, based on which the adaptivity is determined.

We then consider the minimization problem

min_u F(u) = min_u S(u) + R(u;v).

(Note that all additional parameters such as a global regularization parameter are assumed to be fixed and are not explicitly listed as arguments.) In view of a well-posed optimization problem, we assume that R(.;v) for fixed v is convex, proper, weakly lower semi-continuous and that there exists constants c₁,c₂ independent from v such that

c₁ TV(u) ≤ R(u;v) ≤ c₂ TV(u).

Data-driven adaptivity then can be modeled by setting v=f.

Remark: In a similar manner, we can introduce adaptive second-order TV regularization.

Proposed Approach

When aiming at a solution-driven regularization approach, the straight-forward way would be to directly solve

min_u S(u) + R(u;u) (1)

However, we observe that such an approach in general would lead to a non-convex optimization problem [15]. Moreover, a numerical method to solve (1) would require the derivative of v ↦ R(u,v), which might be difficult to evaluate. We propose a different approach, which leads to a fixed point problem. To this end, we introduce the operator

T(v):=argmin_u S(u) + R(u;v). (2)

We assume that the optimization problem in (2) is well-posed and has a unique solution. Consequently, T(v) is well defined. We then search for a fixed point u^* of T:

u^* = T(u^*).

For such a fixed point, we find

u^*=argmin_u S(u) + R(u;u^*),

i.e. we ended up with a solution-driven adaptive regularization approach. We achieved the following theoretical results:

Continuous setting:	In [18] we showed existence of a fixed point under sufficient conditions on R.
Discrete setting:	In the discrete setting, our approach is equivalent to solving a quasi-variational inequality (QVI) [8,24].
	We were able to show existence and uniqueness under sufficient conditions on R [19,21,22].

Results


MSSIM index:	0.808	0.808	0.820

MSSIM index:	0.766	0.783	0.841

MSSIM index:	0.945	0.946	0.973
input image	standard TV	anisotropic data-driven TV	anisotropic solution-driven TV
Fig 1.: Solution driven anisotropic TV regularization for image denoising (first row), deblurring (second row) and inpainting (third row). We compare with standard TV and the data-driven variant. The parameters for each method were found by a hierarchical grid search maximizing the MSSIM index [31] to the undistorted image. The resulting MSSIM values are listed below each image. Solution-driven anisotropic TV outperforms both standard TV and data-driven anisotropic TV.

Fig.1 shows the results of a solution-driven anisotropic TV regularization applied for denoising, deblurring and inpainting. We compare to standard TV [27] and the data-driven adaptive variant. For a quantitative and qualitative comparison to additional state-of-the-art methods we refer to [18].

References

[1]	F. Åström, G. Baravdish, and M. Felsberg, A tensor variational formulation of gradient energy total variation, Energy Minimization Methods in Computer Vision and Pattern Recognition, volume 8932 of LNCS, pp. 307-320, Springer, 2015
[2]	I. Bayram and M.E. Kamasak, Directional total variation minimization,, proceedings of 20th Signal Processing and Communications Applications Conference (SIU) 2012, pp. 1-4, 2012
[3]	B. Berkels, M. Burger, M. Droske, O. Nemitz and M. Rumpf, Cartoon Extraction Based on Anisotropic Image Classification, Vision, Modeling, and Visualization Proceedings, pp. 293-300, 2006
[4]	E.M. Bollt, R. Chartrand, S. Esedoglu, P. Schultz and K.R. Vixie, Graduated adaptive image denoising: local compromise between total variation and isotropic diffusion, Advances in Computational Mathematics, vol. 31(1-3), pp. 61-85, 2009
[5]	K. Bredies, Y. Dong, and M. Hintermüller, Spatially dependent regularization parameter selection in total generalized variation models for image restoration, International Journal of Computer Mathematics, vol. 90(1), pp.109-123, 2013
[6]	K. Bredies, K. Kunisch and T. Pock, Total Generalized Variation, SIAM Journal on Imaging Sciences, 3(3), 492-526, 2010
[7]	A. Chambolle, An Algorithm for Total Variation Minimization and Applications, Math. Imaging Vision, vol. 20(1), pp. 89-97, 2004
[8]	D. Chan and T. Pang, The generalized quasi-variational inequality problem, Math. Operat. Res., vol 7 (2), pp. 211-222, 1982
[9]	S. Esedoglu and S. Osher, Decomposition of images by the anisotropic Rudin - Osher - Fatemi model, Comm. Pure and Appl. Math, vol. 57, pp. 1609-1626, 2004
[10]	V. Estellers, S. Soato, and X. Bresson, Adaptive regularization with the structure tensor, Image Processing, IEEE Transactions on, vol 24 (6), pp. 1777-1790, 2015
[11]	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, vol. 40(1), pp. 82-104, Springer, 2011
[12]	K. Frick, P. Marnitz and A. Munk, Statistical Multiresolution Estimation for Variational Imaging: With an Application in Poisson-Biophotonics, J. Math. Imaging Vision, vol. 46(3), pp. 370-387, 2013
[13]	S. Fu and C. Zhang. Adaptive non-convex total variation regularisation for image restoration, Electronics Letters, 46(13), pp. 907-908, 2010
[14]	M. Grasmair. Locally adaptive total variation regularization, proceedings SSVM '09, LNCS, vol. 5567, pp. 331-342, 2009
[15]	M. Grasmair and F. Lenzen, Anisotropic total variation filtering, Applied Mathematics & Optimization, 62(3), pp. 323-339, Springer, 2010 [pdf]
[16]	M. Hintermüller and M.M. Rincon-Camacho, Expected Absolute Value Estimators for a Spatially Adapted Regularization Parameter Choice Rule in L1-TV-Based Image Restoration, Inverse Problems, vol. 26(8), 2010
[17]	S. Lefkimmiatis, A. Roussos, P. Maragos, and M. Unser, Structure tensor total variation,, SIAM J. Imaging Sci, vol. 8(2), pp. 1090-1122, 2015
[18]	F. Lenzen and J. Berger, Solution-driven adaptive total variation regularization,, Proceedings of SSVM 2015, volume 9087 of LNCS, pages 203-215, 2015 [pdf] [Springer online].
[19]	F. Lenzen, J. Lellmann, F. Becker and C. Schnörr, Solving QVIs for Image Restoration with Adaptive Constraint Sets, SIAM Journal on Imaging Sciences (SIIMS), vol. 7(4), pp. 2139-2174, 2015 [pdf]
[20]	F. Lenzen, F. Becker and J. Lellmann, Adaptive Second-Order Total Variation, An Approach Aware of Slope Discontinuities, proceedings SSVM 2013, LNCS, vol. 7893, pp. 61-73, Springer, 2013 [pdf]
[21]	F. Lenzen, F. Becker, J. Lellmann, S. Petra and C. Schnörr, Variational Image Denoising with Adaptive Constraint Sets, proceedings SSVM '11, LNCS, vol. 6667, 2012 [Springer online] [pdf]
[22]	F. Lenzen, F. Becker, J. Lellmann, S. Petra and C. Schnörr, A Class of Quasi-Variational Inequalities for Adaptive Image Denoising and Decomposition, Comput. Optim. Appl., 2012 [Springer online] [pdf]
[23]	Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations, vol. 22 of University Lecture Series. AMS, 2001
[24]	Y. Nesterov and L. Scrimali, Solving strongly monotone variational and quasi-variational inequalities, Discrete Contin. Dynam. Systems, vol. 31(4), 2011
[25]	R. Rojas and P. Rodriguez, Spatially adaptive total variation image denoising under salt and pepper noise, In Proceedings of the European Signal Processing Conference (EUSIPCO'11), pp. 314-318, 2011
[26]	Y. Ruan, H. Fang, and Q. Chen, Semiblind image deconvolution with spatially adaptive total variation regularization, Mathematical Problems in Engineering, 2014
[27]	L.I. Rudin, S.Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D. Nonlinear Phenomena, vol. 60(1-4), pp. 259-268, 1992
[28]	G. Steidl and T. Teuber, Anisotropic smoothing using double orientations, proceedings SSVM '09, LNCS, pp. 477-489, 2009
[29]	D.M. Strong, P. Blomgren and T.F. Chan, Spatially adaptive local-feature-driven total variation minimizing image restoration, In Optical Science, Engineering and Instrumentation'97, vol. 3167, pp. 222-233. International Society for Optics and Photonics, 1997
[30]	D.M. Strong and T.F. Chan, Spatially and scale adaptive total variation based regularization and anisotropic diffusion in image processing, In Diffusion in Image Processing, UCLA Math Department CAM Report, 1996
[31]	Z. Wang, A.C. Bovik, H.R. Sheikh and E.P. Simoncelli, Image quality assessment: from error visibility to structural similarity, Image Processing, IEEE Transactions on, vol. 13(4), pp. 600-612, 2004