Abstract
Variable splitting and augmented Lagrangian method are widely used in image processing. This chapter briefly reviews its applications for solving the total variation (TV) related image restoration problems. Due to the nonsmoothness of TV, related models and variants are nonsmooth convex or nonconvex minimization problems. Variable splitting and augmented Lagrangian method can benefit from the separable structure and efficient subsolvers, and has convergence guarantee in convex cases. We present this approach for a number of TV minimization models including TV-L2, TV-L1, TV with nonquadratic fidelity term, multichannel TV, high-order TV, and curvature minimization models.
Similar content being viewed by others
References
Acar, R., Vogel, C.R.: Analysis of bounded variation penalty methods for ill-posed problems. Inverse Prob. 10(6), 1217–1229 (1994)
Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, 2nd edn. Springer, New York (2010)
Bae, E., Shi. J., Tai, X.C.: Graph cuts for curvature based image denoising. IEEE Trans. Image Process 20(5), 1199–1210 (2010)
Beck, A., Teboulle, M.: Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. 18(11), 2419–2434 (2009)
Bertalmio, M., Vese, L., Sapiro, G., Osher, S.: Simultaneous structure and texture image inpainting. IEEE Trans. Image Process. 12(8), 882–889 (2003)
Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Optimization and Neural Computation Series, Athena Scientific, Belmont, Mass (1996(firstly published in 1982))
Blomgren, P., Chan, T.F.: Color TV: Total variation methods for restoration of vector-valued images. IEEE Trans. Image Process. 7(3), 304–309 (1998)
Boyd, S.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2010)
Bredies, K., Kunisch, K., Pock, T.: Total generalized variation. SIAM J. Imaging Sci. 3(3), 492–526 (2010)
Bredies, K., Pock, T., Wirth, B.: A convex, lower semicontinuous approximation of Euler’s elastica energy. SIAM J. Math. Anal. 47(1), 566–613 (2015)
Brune, C., Sawatzky, A., Burger, M.: Bregman-em-tv methods with application to optical nanoscopy. In: Tai, X.C., Mørken, K., Lysaker, M., Lie, K.A. (eds.) Scale Space and Variational Methods in Computer Vision. Springer, Berlin/Heidelberg, pp. 235–246 (2009)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1/2), 89–97 (2004)
Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numer. Math. 76(2), 167–188 (1997)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)
Chan, R.H., Tao, M., Yuan, X.: Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers. SIAM J. Imaging Sci. 6(1), 680–697 (2013)
Chan, T., Wong, C.K.: Total variation blind deconvolution. IEEE Trans. Image Process. 7(3), 370–375 (1998)
Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266–277 (2001)
Chan, T.F., Kang, S.H., Shen, J.: Euler’s elastica and curvature-based inpainting. SIAM J. Appl. Math. 63(2), 564–592 (2002)
Chang, H., Lou, Y., Ng, M., Zeng, T.: Phase retrieval from incomplete magnitude information via total variation regularization. SIAM J. Sci. Comput. 38(6), A3672–A3695 (2016)
Chen, C., Chen, Y., Ouyang, Y., Pasiliao, E.: Stochastic accelerated alternating direction method of multipliers with importance sampling. J. Optim. Theory Appl. 179(2), 676–695 (2018)
Chen, X., Ng, M.K., Zhang, C.: Non-Lipschitz ℓp-regularization and box constrained model for image restoration. IEEE Trans. Image Process. 21(12), 4709–4721 (2012)
Chen, Y., Levine, S., Rao, M.: Variable exponent, linear growth functionals in image restoration. SIAM J. Appl. Math. 66(4), 1383–1406 (2006)
Deng, L.J., Glowinski, R., Tai, X.C.: A new operator splitting method for the Euler elastica model for image smoothing. SIAM J. Imaging Sci. 12(2):1190–1230 (2019)
Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889–916 (2016)
Duan, Y., Wang, Y., Hahn, J.: A fast augmented Lagrangian method for Euler’s elastica models. Numer. Math. Theory Methods Appl. 006(001), 47–71 (2013)
Fazel, M., Pong, T.K., Sun, D., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34(3), 946–977 (2013)
Feng, X., Wu, C., Zeng, C.: On the local and global minimizers of ℓ0 gradient regularized model with box constraints for image restoration. Inverse Prob. 34(9), 095,007 (2018)
Gao, Y., Liu, F., Yang, X.: Total generalized variation restoration with non-quadratic fidelity. Multidim. Syst. Sign. Process. 29(4), 1459–1484 (2018)
Glowinski, R., Tallec, P.L.: Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989)
Glowinski, R., Osher, S.J., Yin, W. (eds.): (2016) Splitting Methods in Communication, Imaging, Science, and Engineering. Springer, Cham
Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009)
Güven, H.E., Güngör. A., Çetin, M.: An augmented Lagrangian method for complex-valued compressed SAR imaging. IEEE Trans. Comput. Imag. 2(3), 235–250 (2016)
Hahn, J., Wu, C., Tai, X.C.: Augmented Lagrangian method for generalized TV-Stokes model. J. Sci. Comput. 50(2), 235–264 (2012)
He, B., Yuan, X.: On the o(1∕n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700–709 (2012)
Hinterberger, W., Scherzer, O.: Variational methods on the space of functions of bounded Hessian for convexification and denoising. Computing 76(1–2), 109–133 (2006)
Hintermüller, M., Wu, T.: Nonconvex TVq-models in image restoration: Analysis and a trust-region regularization–based superlinearly convergent solver. SIAM J. Imaging Sci. 6(3), 1385–1415 (2013)
Kang, S.H., Zhu, W., Jianhong, J.: Illusory shapes via corner fusion. SIAM J. Imaging Sci. 7(4), 1907–1936 (2014)
Lai, R., Chan, T.F.: A framework for intrinsic image processing on surfaces. Comput. Vis. Image Und 115(12), 1647–1661 (2011)
Le, T., Chartrand, R., Asaki, T.J.: A variational approach to reconstructing images corrupted by Poisson noise. J. Math. Imaging Vis. 27, 257–263 (2007)
Li, C., Yin, W., Jiang, H., Zhang, Y.: An efficient augmented Lagrangian method with applications to total variation minimization. Comput. Optim. Appl. 56(3), 507–530 (2013)
Li, G., Pong, T.K.: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4), 2434–2460 (2015)
Liu, Z., Wali, S., Duan, Y., Chang, H., Wu, C., Tai, X.C.: Proximal ADMM for Euler’s elastica based image decomposition model. Numer. Math. Theory Methods Appl. 12(2), 370–402 (2018)
Lou, Y., Zhang, X., Osher, S., Bertozzi, A.L.: Image recovery via nonlocal operators. J. Sci. Comput. 42(2), 185–197 (2010)
Lysaker, M., Lundervold, A., Tai, X.: Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time. IEEE Trans. Image Process. 12(12), 1579–1590 (2003)
Micchelli, C.A., Shen, L., Xu, Y.: Proximity algorithms for image models: denoising. Inverse Prob. 27(4), 045,009 (2011)
Myllykoski, M., Glowinski, R., Karkkainen, T., Rossi, T.: A new augmented Lagrangian approach for L1-mean curvature image denoising. SIAM J. Imaging Sci. 8(1), 95–125 (2015)
Nikolova, M.: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vis. 20(1–2), 99–120 (2004)
Nikolova, M.: Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares. Multiscale Model. Simul. 4(3), 960–991 (2005)
Ouyang, Y., Chen, Y., Lan, G., Pasiliao, E.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644–681 (2015)
Persson, M., Bone, D., Elmqvist, H.: Total variation norm for three-dimensional iterative reconstruction in limited view angle tomography. Phys. Med. Biol. 46(3), 853–866 (2001)
Ramani, S., Fessler, J.A.: Parallel MR image reconstruction using augmented Lagrangian methods. IEEE Trans. Med. Imaging 30(3), 694–706 (2011)
Rockafellar, R.T.: Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Control 12(2), 268–285 (1974)
Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin/Heidelberg (1998)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Sapiro, G., Ringach, D.: Anisotropic diffusion of multivalued images with applications to color filtering. IEEE Trans. Image Process. 5, 1582–1586 (1996)
Selesnick, I., Lanza, A., Morigi, S., Sgallari, F.: Non-convex total variation regularization for convex denoising of signals. J. Math. Imaging Vis. 62(6), 825–841 (2020)
Tai, X.C., Wu, C.: Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model. In: Scale Space and Variational Methods in Computer Vision, Second International Conference, SSVM 2009, Voss, 1–5 June 2009. Proceedings, pp 502–513 (2009)
Tai, X.C., Hahn, J., Chung, G.J.: A fast algorithm for Euler’s elastica model using augmented Lagrangian method. SIAM J. Imaging Sci. 4(1), 313–344 (2011)
Vese, L.A., Osher, S.J.: Modeling textures with total variation minimization and oscillating patterns in image processing. J. Sci. Comput. 19(1/3), 553–572 (2003)
Wang, X., Yuan, X.: The linearized alternating direction method of multipliers for dantzig selector. SIAM J. Sci. Comput. 34(5), A2792–A2811 (2012)
Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1(3), 248–272 (2008)
Wang, Y., Yin, W., Zeng, J.: Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1), 29–63 (2019)
Wu, C., Tai, X.C.: Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM J. Imaging Sci. 3(3), 300–339 (2010)
Wu, C., Zhang, J., Tai, X.C.: Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Probl. Imaging 5(1), 237–261 (2011)
Wu, C., Zhang, J., Duan, Y., Tai, X.C.: Augmented lagrangian method for total variation based image restoration and segmentation over triangulated surfaces. J. Sci. Comput. 50(1), 145–166 (2012)
Wu, C., Liu, Z., Wen, S.: A general truncated regularization framework for contrast-preserving variational signal and image restoration: Motivation and implementation. Sci. China Math. 61(9), 1711–1732 (2018)
Yan, M., Duan, Y.: Nonlocal elastica model for sparse reconstruction. J. Math. Imaging Vis. 62, 532–548 (2020)
Yang, J., Yin, W., Zhang, Y., Wang, Y.: A fast algorithm for edge-preserving variational multichannel image restoration. SIAM J. Imaging Sci. 2(2), 569–592 (2009)
Yashtini, M., Kang, S.H.: A fast relaxed normal two split method and an effective weighted TV approach for Euler’s elastica image inpainting. SIAM J. Imaging Sci. 9(4), 1552–1581 (2016)
Zeng, C., Wu, C.: On the edge recovery property of noncovex nonsmooth regularization in image restoration. SIAM J. Numer. Anal. 56(2), 1168–1182 (2018)
Zeng, C., Wu, C.: On the discontinuity of images recovered by noncovex nonsmooth regularized isotropic models with box constraints. Adv. Comput. Math. 45(2), 589–610 (2019)
Zhang, H., Wu, C., Zhang, J., Deng, J.: Variational mesh denoising using total variation and piecewise constant function space. IEEE Trans. Vis. Comput. Graphics 21(7), 873–886 (2015)
Zhang, J., Chen, K.: A total fractional-order variation model for image restoration with nonhomogeneous boundary conditions and its numerical solution. SIAM J. Imaging Sci. 8(4), 2487–2518 (2015)
Zhu, W., Chan, T.: Image denoising using mean curvature of image surface. SIAM J. Imaging Sci. 5(1), 1–32 (2012)
Zhu, W., Tai, X.C., Chan, T.: Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Prob. Imaging 7(4), 1409–1432 (2013)
Acknowledgements
Tai is supported by NSFC/RGC Joint Research Scheme (N_HKBU214/19), Initiation Grant for Faculty Niche Research Areas(RC-FNRA-IG/19-20/SCI/01) and CRF (C1013-21GF).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2023 Springer Nature Switzerland AG
About this entry
Cite this entry
Liu, Z., Duan, Y., Wu, C., Tai, XC. (2023). On Variable Splitting and Augmented Lagrangian Method for Total Variation-Related Image Restoration Models. In: Chen, K., Schönlieb, CB., Tai, XC., Younces, L. (eds) Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging. Springer, Cham. https://doi.org/10.1007/978-3-030-03009-4_84-2
Download citation
DOI: https://doi.org/10.1007/978-3-030-03009-4_84-2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03009-4
Online ISBN: 978-3-030-03009-4
eBook Packages: Springer Reference MathematicsReference Module Computer Science and Engineering
Publish with us
Chapter history
-
Latest
On Variable Splitting and Augmented Lagrangian Method for Total Variation-Related Image Restoration Models- Published:
- 08 October 2022
DOI: https://doi.org/10.1007/978-3-030-03009-4_84-2
-
Original
On Variable Splitting and Augmented Lagrangian Method for Total Variation-Related Image Restoration Models- Published:
- 28 August 2021
DOI: https://doi.org/10.1007/978-3-030-03009-4_84-1