On variable splitting and augmented Lagrangian method for total variation-related image restoration models. (English) Zbl 07914346
Chen, Ke (ed.) et al., Handbook of mathematical models and algorithms in computer vision and imaging. Mathematical imaging and vision. Springer Reference. Cham: Springer. 503-549 (2023).
Summary: 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-\(\mathrm{L}^2\), TV-\(\mathrm{L}^1\), TV with nonquadratic fidelity term, multichannel TV, high-order TV, and curvature minimization models.
For the entire collection see [Zbl 1527.94003].
For the entire collection see [Zbl 1527.94003].
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 68U10 | Computing methodologies for image processing |
Keywords:
variable splitting; augmented Lagrangian method; total variation; image restoration; box constraintReferences:
| [1] | Acar, R., Vogel, C.R.: Analysis of bounded variation penalty methods for ill-posed problems. Inverse Prob. 10(6), 1217-1229 (1994) · Zbl 0809.35151 |
| [2] | Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, 2nd edn. Springer, New York (2010) |
| [3] | Bae, E., Shi. J., Tai, X.C.: Graph cuts for curvature based image denoising. IEEE Trans. Image Process 20(5), 1199-1210 (2010) · Zbl 1372.94015 |
| [4] | 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 · Zbl 1371.94049 |
| [5] | Bertalmio, M., Vese, L., Sapiro, G., Osher, S.: Simultaneous structure and texture image inpainting. IEEE Trans. Image Process. 12(8), 882-889 (2003) |
| [6] | Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Optimization and Neural Computation Series, Athena Scientific, Belmont, Mass (1996(firstly published in 1982)) · Zbl 0572.90067 |
| [7] | 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) |
| [8] | Boyd, S.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1-122 (2010) · Zbl 1229.90122 |
| [9] | Bredies, K., Kunisch, K., Pock, T.: Total generalized variation. SIAM J. Imaging Sci. 3(3), 492-526 (2010) · Zbl 1195.49025 |
| [10] | 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) · Zbl 1319.49018 |
| [11] | 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) |
| [12] | Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1/2), 89-97 (2004) · Zbl 1366.94048 |
| [13] | Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numer. Math. 76(2), 167-188 (1997) · Zbl 0874.68299 |
| [14] | 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) · Zbl 1255.68217 |
| [15] | 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) · Zbl 1279.68322 |
| [16] | Chan, T., Wong, C.K.: Total variation blind deconvolution. IEEE Trans. Image Process. 7(3), 370-375 (1998) |
| [17] | Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266-277 (2001) · Zbl 1039.68779 |
| [18] | Chan, T.F., Kang, S.H., Shen, J.: Euler’s elastica and curvature-based inpainting. SIAM J. Appl. Math. 63(2), 564-592 (2002) · Zbl 1028.68185 |
| [19] | 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) · Zbl 1352.49034 |
| [20] | 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) · Zbl 1402.90087 |
| [21] | 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) · Zbl 1373.94080 |
| [22] | Chen, Y., Levine, S., Rao, M.: Variable exponent, linear growth functionals in image restoration. SIAM J. Appl. Math. 66(4), 1383-1406 (2006) · Zbl 1102.49010 |
| [23] | 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) · Zbl 1538.94005 |
| [24] | 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) · Zbl 1379.65036 |
| [25] | 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) · Zbl 1289.94006 |
| [26] | 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) · Zbl 1302.90127 |
| [27] | 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) · Zbl 1397.49021 |
| [28] | Gao, Y., Liu, F., Yang, X.: Total generalized variation restoration with non-quadratic fidelity. Multidim. Syst. Sign. Process. 29(4), 1459-1484 (2018) · Zbl 1448.94013 |
| [29] | Glowinski, R., Tallec, P.L.: Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989) · Zbl 0698.73001 |
| [30] | Glowinski, R., Osher, S.J., Yin, W. (eds.): (2016) Splitting Methods in Communication, Imaging, Science, and Engineering. Springer, Cham · Zbl 1362.65002 |
| [31] | Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2(2), 323-343 (2009) · Zbl 1177.65088 |
| [32] | 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) |
| [33] | Hahn, J., Wu, C., Tai, X.C.: Augmented Lagrangian method for generalized TV-Stokes model. J. Sci. Comput. 50(2), 235-264 (2012) · Zbl 1253.94012 |
| [34] | 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) · Zbl 1245.90084 |
| [35] | 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) · Zbl 1098.49022 |
| [36] | Hintermüller, M., Wu, T.: Nonconvex TV q -models in image restoration: Analysis and a trust-region regularization-based superlinearly convergent solver. SIAM J. Imaging Sci. 6(3), 1385-1415 (2013) · Zbl 1281.65033 |
| [37] | Kang, S.H., Zhu, W., Jianhong, J.: Illusory shapes via corner fusion. SIAM J. Imaging Sci. 7(4), 1907-1936 (2014) · Zbl 1320.68217 |
| [38] | Lai, R., Chan, T.F.: A framework for intrinsic image processing on surfaces. Comput. Vis. Image Und 115(12), 1647-1661 (2011) |
| [39] | 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) |
| [40] | 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) · Zbl 1287.90066 |
| [41] | Li, G., Pong, T.K.: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4), 2434-2460 (2015) · Zbl 1330.90087 |
| [42] | 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) · Zbl 1449.94015 |
| [43] | Lou, Y., Zhang, X., Osher, S., Bertozzi, A.L.: Image recovery via nonlocal operators. J. Sci. Comput. 42(2), 185-197 (2010) · Zbl 1203.65088 |
| [44] | 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) · Zbl 1286.94020 |
| [45] | Micchelli, C.A., Shen, L., Xu, Y.: Proximity algorithms for image models: denoising. Inverse Prob. 27(4), 045,009 (2011) |
| [46] | Myllykoski, M., Glowinski, R., Karkkainen, T., Rossi, T.: A new augmented Lagrangian approach for L 1 -mean curvature image denoising. SIAM J. Imaging Sci. 8(1), 95-125 (2015) · Zbl 1330.94011 |
| [47] | Nikolova, M.: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vis. 20(1-2), 99-120 (2004) · Zbl 1366.94065 |
| [48] | 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) · Zbl 1091.94007 |
| [49] | 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) · Zbl 1321.90105 |
| [50] | Persson, M., Bone, D., Elmqvist, H.: Total variation norm for three-dimensional iterative recon-struction in limited view angle tomography. Phys. Med. Biol. 46(3), 853-866 (2001) |
| [51] | Ramani, S., Fessler, J.A.: Parallel MR image reconstruction using augmented Lagrangian methods. IEEE Trans. Med. Imaging 30(3), 694-706 (2011) |
| [52] | Rockafellar, R.T.: Augmented Lagrange multiplier functions and duality in nonconvex program-ming. SIAM J. Control 12(2), 268-285 (1974) · Zbl 0257.90046 |
| [53] | Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin/Heidelberg (1998) · Zbl 0888.49001 |
| [54] | Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259-268 (1992) · Zbl 0780.49028 |
| [55] | Sapiro, G., Ringach, D.: Anisotropic diffusion of multivalued images with applications to color filtering. IEEE Trans. Image Process. 5, 1582-1586 (1996) |
| [56] | 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) · Zbl 1485.94026 |
| [57] | 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) · Zbl 1371.94362 |
| [58] | 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) · Zbl 1215.68262 |
| [59] | 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) · Zbl 1034.49039 |
| [60] | Wang, X., Yuan, X.: The linearized alternating direction method of multipliers for dantzig selector. SIAM J. Sci. Comput. 34(5), A2792-A2811 (2012) · Zbl 1263.90061 |
| [61] | 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) · Zbl 1187.68665 |
| [62] | Wang, Y., Yin, W., Zeng, J.: Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1), 29-63 (2019) · Zbl 1462.65072 |
| [63] | 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) · Zbl 1206.90245 |
| [64] | 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) · Zbl 1225.80013 |
| [65] | 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) · Zbl 1253.94017 |
| [66] | 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) · Zbl 1411.94011 |
| [67] | Yan, M., Duan, Y.: Nonlocal elastica model for sparse reconstruction. J. Math. Imaging Vis. 62, 532-548 (2020) · Zbl 1455.94040 |
| [68] | 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) · Zbl 1181.68304 |
| [69] | 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) · Zbl 1366.94075 |
| [70] | 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) · Zbl 1391.49050 |
| [71] | 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) · Zbl 1415.49018 |
| [72] | 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) |
| [73] | Zhang, J., Chen, K.: A total fractional-order variation model for image restoration with nonhomo-geneous 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) · Zbl 1327.62388 |
| [74] | 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) · Zbl 1311.94015 |
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.
