November  2015, 9(4): 1171-1191. doi: 10.3934/ipi.2015.9.1171

Iterative choice of the optimal regularization parameter in TV image restoration

1. 

CREATIS, CNRS UMR 5220; INSERM U1044; INSA de Lyon; Université de Lyon 1, Université de Lyon, 69621, Villeurbanne Cedex, France, France, France

Received  June 2014 Revised  April 2015 Published  October 2015

We present iterative methods for choosing the optimal regularization parameter for linear inverse problems with Total Variation regularization. This approach is based on the Morozov discrepancy principle or on a damped version of this principle and on an approximating model function for the data term. The theoretical convergence of the method of choice of the regularization parameter is demonstrated. The choice of the optimal parameter is refined with a Newton method. The efficiency of the method is illustrated on deconvolution and super-resolution experiments on different types of images. Results are provided for different levels of blur, noise and loss of spatial resolution. The damped Morozov discrepancy principle often outerperforms the approaches based on the classical Morozov principle and on the Unbiased Predictive Risk Estimator. Moreover, the proposed methods are fast schemes to select the best parameter for TV regularization.
Citation: Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171
References:
[1]

M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization,, IEEE Trans. Image Process., 19 (2010), 2345. doi: 10.1109/TIP.2010.2047910.

[2]

M. Afonso, J. Bioucas-Dias and M. Figueiredo, An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems,, IEEE Trans. Image Process., 20 (2011), 681. doi: 10.1109/TIP.2010.2076294.

[3]

L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems,, Clarendon Press Oxford, (2000).

[4]

J. F. Aujol and G. Gilboa, Constrained and SNR-based solutions for TV-Hibert space image denoising,, J. Math. Imaging Vis., 26 (2006), 217. doi: 10.1007/s10851-006-7801-6.

[5]

S. D. Babacan, R. Molina and A. K. Katsaggelos, Parameter estimation in TV image restoration using variational distribution approximation,, IEEE Trans. Image Process., 17 (2008), 326. doi: 10.1109/TIP.2007.916051.

[6]

S. D. Babacan, R. Molina and A. K. Katsaggelos, Total Variation Super Resolution Using A Variational Approach,, Proc. Int.Conf. Image Process., (2008), 641.

[7]

S. Becker, J. Bobin and E. Candes, NESTA: A fast and accurate first-order method for sparse recovery,, SIAM Journal on Imaging Sciences, 4 (2011), 1. doi: 10.1137/090756855.

[8]

T. Blu and F. Luisier, The SURE-LET approach to image denoising,, IEEE Trans. Image Process., 16 (2007), 2778. doi: 10.1109/TIP.2007.906002.

[9]

L. M. Bregman, The relaxation method for finding common points of convex sets and its application to the solution of problems in convex programming,, USSR Comput. Math. Math+, 7 (1967), 200.

[10]

M. Burger and S. Osher, Convergence rates of convex variational regularization,, Inverse Probl., 20 (2004), 1411. doi: 10.1088/0266-5611/20/5/005.

[11]

C. A. Deledalle, S. Vaiter, J. Fadili and G. Peyre, Stein Unbiased Gradient estimator for the risk (SUGAR) for multiple parameter selection,, SIAM Journal on Imaging Sciences, 7 (2014), 2448. doi: 10.1137/140968045.

[12]

Y. C. Eldar, Generalized SURE for exponential families: Application to regularization,, IEEE Trans. Signal Process., 57 (2009), 471. doi: 10.1109/TSP.2008.2008212.

[13]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, Mathematics and its Applications, (1996). doi: 10.1007/978-94-009-1740-8.

[14]

E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman,, CAM report, (2009).

[15]

J. M. Fadili, G. Peyre, S. Vaiter, C. Deledalle and J. Salmon, Stable recovery with analysis decomposable priors,, preprint, ().

[16]

K. Frick, D. A. Lorenz and E. Resmerita, Morozov's principle for the augmented Lagrangian method applied to linear inverse problems,, Multiscale Model Simul., 9 (2011), 1528. doi: 10.1137/100812835.

[17]

G. H. Golub, M. T. Heath and C. Wahba, Generalized cross-validation as a method for choosing a good ridge parameter,, Technometrics, 21 (1979), 215. doi: 10.2307/1268518.

[18]

M. Grasmair, Linear convergence rates for Tikhonov regularization with positively homogeneous functionals,, Inverse Problems, 27 (2011). doi: 10.1088/0266-5611/27/7/075014.

[19]

P. C. Hansen and D. P. O'Leary, The use of the L-curve in the regularization of discrete ill-posed problem,, SIAM Journal on Scientific Computing, 14 (1993), 1487. doi: 10.1137/0914086.

[20]

M. F. Hutchinson, A stochastic estimator of the trace of the influence matrix for laplacian smooting splines,, Commun. Stat. Simulat., 19 (1990), 433. doi: 10.1080/03610919008812864.

[21]

K. C. Kiwiel, Proximal minimization methods with generalized Bregman functions,, SIAM J. Control Optim., 35 (1997), 1142. doi: 10.1137/S0363012995281742.

[22]

K. Kunisch and J. Zou, Iterative choices of regularization parameters in linear inverse problems,, Inverse Probl., 14 (1998), 1247. doi: 10.1088/0266-5611/14/5/010.

[23]

K. Kunisch, On a class of damped Morozov principles,, Computing, 50 (1993), 185. doi: 10.1007/BF02243810.

[24]

H. Liao, F. Li and M. K. Ng, Selection of regularization parameter in total variation restoration,, JOSA A, 26 (2009), 2311. doi: 10.1364/JOSAA.26.002311.

[25]

Y.Lin, B.Wohlberg and H.Guo, UPRE method for total variation parameter selection,, Signal Processing, 90 (2010), 2546.

[26]

V. A. Morozov, Methods for Solving Incorrectly Posed Problems,, Springer-Verlag, (1984). doi: 10.1007/978-1-4612-5280-1.

[27]

M. K. Ng, P. Weiss and X. Yuan, Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods,, SIAM Journal on Scientific Computing, 32 (2010), 2710. doi: 10.1137/090774823.

[28]

S. Ramani, T. Blu and M. Unser, Monte-Carlo SURE: A black-box optimization of regularization parameters for general denoising algorithms,, IEEE Trans. Image Process., 17 (2008), 1540. doi: 10.1109/TIP.2008.2001404.

[29]

S. Ramani, Z. Liu, J. Rosen, J. Nielsen and J. A. Fessler, Regularization parameter selection for nonlinear iterative image restoration and MRI reconstruction using GCV and SURE-based methods,, IEEE Transactions on Image Processing, 21 (2012), 3659. doi: 10.1109/TIP.2012.2195015.

[30]

Z. Ren, C. He and Q. Zhang, Fractional order total variation regularization for image super-resolution,, Signal Process., 93 (2013), 2408.

[31]

E. Resmerita, Regularization of ill-posed problems in Banach spaces: Convergence rates,, Inverse Probl., 21 (2005), 1303. doi: 10.1088/0266-5611/21/4/007.

[32]

L. I. Rudin , S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Phys. D, 60 (1992), 259.

[33]

M. Salome, F. Peyrin, P. Cloetens, C. Odet, A. M. Laval-Jeantet, J. Barucheland and P. Spanne, A synchrotron radiation microtomography system for the analysis of trabecular bone samples,, Medical Physics, 26 (1999), 2194.

[34]

O. Scherzer, M. Grassmair, H. Grossauer, M. Haltmaier and F. Lenzen, Variational Methods in Imaging,, Springer Verlag, (2008).

[35]

A. N. Tikhonov and V. Y. Arsenin, Solutions to ill-posed problems,, Winston-Wiley, (1977).

[36]

E. Van den Berg E and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions,, SIAM Journal on Scientific Computing, 31 (2008), 890. doi: 10.1137/080714488.

[37]

S. Vaiter, A. Deledalle, G. Peyre, C. Dossal and J. Fadili, Local behavior of sparse analysis regularization: Applications to risk estimation,, Applied and Computational Harmonic Analysis, 35 (2013), 433. doi: 10.1016/j.acha.2012.11.006.

[38]

C. R. Vogel, Computational Methods for Inverse Problems,, SIAM, (2002). doi: 10.1137/1.9780898717570.

[39]

C. Vonesch, S. Ramani and M. Unser, Risk estimation for non-linear image deconvolution with a wavelet-domain sparsity constraint,, Inverse Problems, 27 (2011).

[40]

C. Vonesch, S. Ramani and M. Unser, Recursive risk estimation for non-linear image deconvolution with a wavelet-domain sparsity constraint,, ICIP 2008, (2008), 665.

[41]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction,, SIAM Journal on Imaging Sciences, 1 (2008), 248. doi: 10.1137/080724265.

[42]

Y. W. Wen and R. H. Chan, Parameter selection for total-variation-based image restoration using discrepancy principle,, IEEE Trans. Image Process., 21 (2012), 1770. doi: 10.1109/TIP.2011.2181401.

[43]

J. Yang, W. Yin, Y. Zhang and Y. Wang, A fast algorithm for edge-preserving variational multichannel image restoration,, SIAM Journal on Imaging Sciences, 2 (2009), 569. doi: 10.1137/080730421.

show all references

References:
[1]

M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization,, IEEE Trans. Image Process., 19 (2010), 2345. doi: 10.1109/TIP.2010.2047910.

[2]

M. Afonso, J. Bioucas-Dias and M. Figueiredo, An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems,, IEEE Trans. Image Process., 20 (2011), 681. doi: 10.1109/TIP.2010.2076294.

[3]

L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems,, Clarendon Press Oxford, (2000).

[4]

J. F. Aujol and G. Gilboa, Constrained and SNR-based solutions for TV-Hibert space image denoising,, J. Math. Imaging Vis., 26 (2006), 217. doi: 10.1007/s10851-006-7801-6.

[5]

S. D. Babacan, R. Molina and A. K. Katsaggelos, Parameter estimation in TV image restoration using variational distribution approximation,, IEEE Trans. Image Process., 17 (2008), 326. doi: 10.1109/TIP.2007.916051.

[6]

S. D. Babacan, R. Molina and A. K. Katsaggelos, Total Variation Super Resolution Using A Variational Approach,, Proc. Int.Conf. Image Process., (2008), 641.

[7]

S. Becker, J. Bobin and E. Candes, NESTA: A fast and accurate first-order method for sparse recovery,, SIAM Journal on Imaging Sciences, 4 (2011), 1. doi: 10.1137/090756855.

[8]

T. Blu and F. Luisier, The SURE-LET approach to image denoising,, IEEE Trans. Image Process., 16 (2007), 2778. doi: 10.1109/TIP.2007.906002.

[9]

L. M. Bregman, The relaxation method for finding common points of convex sets and its application to the solution of problems in convex programming,, USSR Comput. Math. Math+, 7 (1967), 200.

[10]

M. Burger and S. Osher, Convergence rates of convex variational regularization,, Inverse Probl., 20 (2004), 1411. doi: 10.1088/0266-5611/20/5/005.

[11]

C. A. Deledalle, S. Vaiter, J. Fadili and G. Peyre, Stein Unbiased Gradient estimator for the risk (SUGAR) for multiple parameter selection,, SIAM Journal on Imaging Sciences, 7 (2014), 2448. doi: 10.1137/140968045.

[12]

Y. C. Eldar, Generalized SURE for exponential families: Application to regularization,, IEEE Trans. Signal Process., 57 (2009), 471. doi: 10.1109/TSP.2008.2008212.

[13]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, Mathematics and its Applications, (1996). doi: 10.1007/978-94-009-1740-8.

[14]

E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman,, CAM report, (2009).

[15]

J. M. Fadili, G. Peyre, S. Vaiter, C. Deledalle and J. Salmon, Stable recovery with analysis decomposable priors,, preprint, ().

[16]

K. Frick, D. A. Lorenz and E. Resmerita, Morozov's principle for the augmented Lagrangian method applied to linear inverse problems,, Multiscale Model Simul., 9 (2011), 1528. doi: 10.1137/100812835.

[17]

G. H. Golub, M. T. Heath and C. Wahba, Generalized cross-validation as a method for choosing a good ridge parameter,, Technometrics, 21 (1979), 215. doi: 10.2307/1268518.

[18]

M. Grasmair, Linear convergence rates for Tikhonov regularization with positively homogeneous functionals,, Inverse Problems, 27 (2011). doi: 10.1088/0266-5611/27/7/075014.

[19]

P. C. Hansen and D. P. O'Leary, The use of the L-curve in the regularization of discrete ill-posed problem,, SIAM Journal on Scientific Computing, 14 (1993), 1487. doi: 10.1137/0914086.

[20]

M. F. Hutchinson, A stochastic estimator of the trace of the influence matrix for laplacian smooting splines,, Commun. Stat. Simulat., 19 (1990), 433. doi: 10.1080/03610919008812864.

[21]

K. C. Kiwiel, Proximal minimization methods with generalized Bregman functions,, SIAM J. Control Optim., 35 (1997), 1142. doi: 10.1137/S0363012995281742.

[22]

K. Kunisch and J. Zou, Iterative choices of regularization parameters in linear inverse problems,, Inverse Probl., 14 (1998), 1247. doi: 10.1088/0266-5611/14/5/010.

[23]

K. Kunisch, On a class of damped Morozov principles,, Computing, 50 (1993), 185. doi: 10.1007/BF02243810.

[24]

H. Liao, F. Li and M. K. Ng, Selection of regularization parameter in total variation restoration,, JOSA A, 26 (2009), 2311. doi: 10.1364/JOSAA.26.002311.

[25]

Y.Lin, B.Wohlberg and H.Guo, UPRE method for total variation parameter selection,, Signal Processing, 90 (2010), 2546.

[26]

V. A. Morozov, Methods for Solving Incorrectly Posed Problems,, Springer-Verlag, (1984). doi: 10.1007/978-1-4612-5280-1.

[27]

M. K. Ng, P. Weiss and X. Yuan, Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods,, SIAM Journal on Scientific Computing, 32 (2010), 2710. doi: 10.1137/090774823.

[28]

S. Ramani, T. Blu and M. Unser, Monte-Carlo SURE: A black-box optimization of regularization parameters for general denoising algorithms,, IEEE Trans. Image Process., 17 (2008), 1540. doi: 10.1109/TIP.2008.2001404.

[29]

S. Ramani, Z. Liu, J. Rosen, J. Nielsen and J. A. Fessler, Regularization parameter selection for nonlinear iterative image restoration and MRI reconstruction using GCV and SURE-based methods,, IEEE Transactions on Image Processing, 21 (2012), 3659. doi: 10.1109/TIP.2012.2195015.

[30]

Z. Ren, C. He and Q. Zhang, Fractional order total variation regularization for image super-resolution,, Signal Process., 93 (2013), 2408.

[31]

E. Resmerita, Regularization of ill-posed problems in Banach spaces: Convergence rates,, Inverse Probl., 21 (2005), 1303. doi: 10.1088/0266-5611/21/4/007.

[32]

L. I. Rudin , S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Phys. D, 60 (1992), 259.

[33]

M. Salome, F. Peyrin, P. Cloetens, C. Odet, A. M. Laval-Jeantet, J. Barucheland and P. Spanne, A synchrotron radiation microtomography system for the analysis of trabecular bone samples,, Medical Physics, 26 (1999), 2194.

[34]

O. Scherzer, M. Grassmair, H. Grossauer, M. Haltmaier and F. Lenzen, Variational Methods in Imaging,, Springer Verlag, (2008).

[35]

A. N. Tikhonov and V. Y. Arsenin, Solutions to ill-posed problems,, Winston-Wiley, (1977).

[36]

E. Van den Berg E and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions,, SIAM Journal on Scientific Computing, 31 (2008), 890. doi: 10.1137/080714488.

[37]

S. Vaiter, A. Deledalle, G. Peyre, C. Dossal and J. Fadili, Local behavior of sparse analysis regularization: Applications to risk estimation,, Applied and Computational Harmonic Analysis, 35 (2013), 433. doi: 10.1016/j.acha.2012.11.006.

[38]

C. R. Vogel, Computational Methods for Inverse Problems,, SIAM, (2002). doi: 10.1137/1.9780898717570.

[39]

C. Vonesch, S. Ramani and M. Unser, Risk estimation for non-linear image deconvolution with a wavelet-domain sparsity constraint,, Inverse Problems, 27 (2011).

[40]

C. Vonesch, S. Ramani and M. Unser, Recursive risk estimation for non-linear image deconvolution with a wavelet-domain sparsity constraint,, ICIP 2008, (2008), 665.

[41]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction,, SIAM Journal on Imaging Sciences, 1 (2008), 248. doi: 10.1137/080724265.

[42]

Y. W. Wen and R. H. Chan, Parameter selection for total-variation-based image restoration using discrepancy principle,, IEEE Trans. Image Process., 21 (2012), 1770. doi: 10.1109/TIP.2011.2181401.

[43]

J. Yang, W. Yin, Y. Zhang and Y. Wang, A fast algorithm for edge-preserving variational multichannel image restoration,, SIAM Journal on Imaging Sciences, 2 (2009), 569. doi: 10.1137/080730421.

[1]

You-Wei Wen, Raymond Honfu Chan. Using generalized cross validation to select regularization parameter for total variation regularization problems. Inverse Problems & Imaging, 2018, 12 (5) : 1103-1120. doi: 10.3934/ipi.2018046

[2]

Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems & Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565

[3]

Juan Carlos De los Reyes, Estefanía Loayza-Romero. Total generalized variation regularization in data assimilation for Burgers' equation. Inverse Problems & Imaging, 2019, 13 (4) : 755-786. doi: 10.3934/ipi.2019035

[4]

Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511

[5]

Bernadette N. Hahn. Dynamic linear inverse problems with moderate movements of the object: Ill-posedness and regularization. Inverse Problems & Imaging, 2015, 9 (2) : 395-413. doi: 10.3934/ipi.2015.9.395

[6]

Raymond H. Chan, Haixia Liang, Suhua Wei, Mila Nikolova, Xue-Cheng Tai. High-order total variation regularization approach for axially symmetric object tomography from a single radiograph. Inverse Problems & Imaging, 2015, 9 (1) : 55-77. doi: 10.3934/ipi.2015.9.55

[7]

Matteo Negri. Crack propagation by a regularization of the principle of local symmetry. Discrete & Continuous Dynamical Systems - S, 2013, 6 (1) : 147-165. doi: 10.3934/dcdss.2013.6.147

[8]

Vinicius Albani, Adriano De Cezaro. A connection between uniqueness of minimizers in Tikhonov-type regularization and Morozov-like discrepancy principles. Inverse Problems & Imaging, 2019, 13 (1) : 211-229. doi: 10.3934/ipi.2019012

[9]

Armin Lechleiter, Marcel Rennoch. Non-linear Tikhonov regularization in Banach spaces for inverse scattering from anisotropic penetrable media. Inverse Problems & Imaging, 2017, 11 (1) : 151-176. doi: 10.3934/ipi.2017008

[10]

Thorsten Hohage, Mihaela Pricop. Nonlinear Tikhonov regularization in Hilbert scales for inverse boundary value problems with random noise. Inverse Problems & Imaging, 2008, 2 (2) : 271-290. doi: 10.3934/ipi.2008.2.271

[11]

Luca Rondi. On the regularization of the inverse conductivity problem with discontinuous conductivities. Inverse Problems & Imaging, 2008, 2 (3) : 397-409. doi: 10.3934/ipi.2008.2.397

[12]

Frank Pörner, Daniel Wachsmuth. Tikhonov regularization of optimal control problems governed by semi-linear partial differential equations. Mathematical Control & Related Fields, 2018, 8 (1) : 315-335. doi: 10.3934/mcrf.2018013

[13]

Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems & Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019

[14]

Vinicius Albani, Adriano De Cezaro, Jorge P. Zubelli. On the choice of the Tikhonov regularization parameter and the discretization level: A discrepancy-based strategy. Inverse Problems & Imaging, 2016, 10 (1) : 1-25. doi: 10.3934/ipi.2016.10.1

[15]

Johnathan M. Bardsley. A theoretical framework for the regularization of Poisson likelihood estimation problems. Inverse Problems & Imaging, 2010, 4 (1) : 11-17. doi: 10.3934/ipi.2010.4.11

[16]

Len Margolin, Catherine Plesko. Discrete regularization. Evolution Equations & Control Theory, 2019, 8 (1) : 117-137. doi: 10.3934/eect.2019007

[17]

Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems & Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337

[18]

Matthew A. Fury. Regularization for ill-posed inhomogeneous evolution problems in a Hilbert space. Conference Publications, 2013, 2013 (special) : 259-272. doi: 10.3934/proc.2013.2013.259

[19]

Daniela Calvetti, Erkki Somersalo. Microlocal sequential regularization in imaging. Inverse Problems & Imaging, 2007, 1 (1) : 1-11. doi: 10.3934/ipi.2007.1.1

[20]

Jussi Korpela, Matti Lassas, Lauri Oksanen. Discrete regularization and convergence of the inverse problem for 1+1 dimensional wave equation. Inverse Problems & Imaging, 2019, 13 (3) : 575-596. doi: 10.3934/ipi.2019027

2017 Impact Factor: 1.465

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]