On a general smoothly truncated regularization for variational piecewise constant image restoration: construction and convergent algorithms. (English) Zbl 1471.94001
Summary: Image restoration is a typical inverse problem, and piecewise constant images have extensive applications in industry and business. Variational models with nonconvex, nonsmooth regularizations can achieve high-quality restorations with neat edges. In particular, a class of truncated potential functions effectively supports contrast-preserving restoration. However, these functions are not subdifferentially regular and thus yield no variational or convergence results for minimization algorithms. In this paper, we present a general smoothing scheme to overcome this nonregularity of the existing truncated regularizers. We also propose globally convergent algorithms to solve the noncoercive variational models with our new smoothly truncated regularizer (STR) functions by introducing a novel \(\ell_1\) proximal term. The limit point of the iterative sequence is shown to be a \(\beta\)-stationary point of the original objective function. We then give the implementation details for the inner subproblem by the alternating direction method of multipliers (ADMM). Numerical experiments are carried out to illustrate the good ability of the new regularizer to preserve neat edges and contrasts for piecewise constant images.
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 65K10 | Numerical optimization and variational techniques |
| 65J22 | Numerical solution to inverse problems in abstract spaces |
| 49N60 | Regularity of solutions in optimal control |
| 49N45 | Inverse problems in optimal control |
Keywords:
image restoration; contrast-preserving; variational method; smoothly truncated regularizer; \(\mathrm{e}\ell_1\) proximal term; lower bound; nonconvex regularizationsReferences:
| [1] | Attouch H and Bolte J 2009 On the convergence of the proximal algorithm for nonsmooth functions involving analytic features Math. Program.116 5-16 · Zbl 1165.90018 · doi:10.1007/s10107-007-0133-5 |
| [2] | Attouch H, Bolte J, Redont P and Soubeyran A 2010 Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality Math. Oper. Res.35 438-57 · Zbl 1214.65036 · doi:10.1287/moor.1100.0449 |
| [3] | Attouch H, Bolte J and Svaiter B F 2013 Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods Math. Program.137 91-129 · Zbl 1260.49048 · doi:10.1007/s10107-011-0484-9 |
| [4] | Bao C, Dong B, Hou L, Shen Z, Zhang X and Zhang X 2016 Image restoration by minimizing zero norm of wavelet frame coefficients Inverse Problems32 115004 · Zbl 1409.94026 · doi:10.1088/0266-5611/32/11/115004 |
| [5] | Beister M, Kolditz D and Kalender W A 2012 Iterative reconstruction methods in x-ray CT Phys. Med.28 94-108 · doi:10.1016/j.ejmp.2012.01.003 |
| [6] | Block K T, Uecker M and Frahm J 2007 Undersampled radial MRI with multiple coils iterative image reconstruction using a total variation constraint Magn. Reson. Med.57 1086-98 · doi:10.1002/mrm.21236 |
| [7] | Bolte J, Sabach S and Teboulle M 2014 Proximal alternating linearized minimization for nonconvex and nonsmooth problems Math. Program.146 459-94 · Zbl 1297.90125 · doi:10.1007/s10107-013-0701-9 |
| [8] | Bonettini S, Loris I, Porta F, Prato M and Rebegoldi S 2017 On the convergence of a linesearch based proximal-gradient method for nonconvex optimization Inverse Problems33 055005 · Zbl 1373.65040 · doi:10.1088/1361-6420/aa5bfd |
| [9] | Bonettini S, Prato M and Rebegoldi S 2018 A block coordinate variable metric linesearch based proximal gradient method Comput. Optim. Appl.71 5-52 · Zbl 1405.90123 · doi:10.1007/s10589-018-0011-5 |
| [10] | Candès E J, Wakin M B and Boyd S P 2008 Enhancing sparsity by reweighted ℓ1 minimization J. Fourier Anal. Appl.14 877-905 · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x |
| [11] | Chambolle A and Pock T 2011 A first-order primal-dual algorithm for convex problems with applications to imaging J. Math. Imaging Vis.40 120-45 · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1 |
| [12] | Chen P, Huang J and Zhang X 2013 A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration Inverse Problems29 025011 · Zbl 1279.65075 · doi:10.1088/0266-5611/29/2/025011 |
| [13] | Chen X, Ng M K and Zhang C 2012 Non-Lipschitz ℓp-regularization and box constrained model for image restoration IEEE Trans. Image Process.21 4709-21 · Zbl 1373.94080 · doi:10.1109/TIP.2012.2214051 |
| [14] | Chen X, Niu L and Yuan Y 2013 Optimality conditions and a smoothing trust region Newton method for nonlipschitz optimization SIAM J. Optim.23 1528-52 · Zbl 1291.90238 · doi:10.1137/120871390 |
| [15] | Chen X and Zhou W 2010 Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization SIAM J. Imaging Sci.3 765-90 · Zbl 1200.65031 · doi:10.1137/080740167 |
| [16] | Chen X and Zhou W 2014 Convergence of the reweighted ℓ1 minimization algorithm for ℓ2-ℓp minimization Comput. Optim. Appl.59 47-61 · Zbl 1326.90062 · doi:10.1007/s10589-013-9553-8 |
| [17] | Chen Y, Shen Y and Wu C 2020 A new globally convergent algorithm for ℓ0 regularized least absolute deviation in sparse signal reconstruction (in preparation) |
| [18] | Chouzenoux E, Pesquet J and Repetti A 2014 Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function J. Optim. Theory Appl.162 107-32 · Zbl 1318.90058 · doi:10.1007/s10957-013-0465-7 |
| [19] | Cocosco C A, Kollokian V, Kwan R K and Evans A C 1997 Brainweb: online interface to a 3D MRI simulated brain database NeuroImage5 425 |
| [20] | Coll B, Duran J and Sbert C 2015 Half-linear regularization for nonconvex image restoration models Inverse Problems Imaging9 337-70 · Zbl 1359.94029 · doi:10.3934/ipi.2015.9.337 |
| [21] | Daubechies I, Devore R, Fornasier M and Gunturk C S 2010 Iteratively reweighted least squares minimization for sparse recovery Commun. Pures Appl. Math.63 1-38 · Zbl 1202.65046 · doi:10.1002/cpa.20303 |
| [22] | Dong B, Li J and Shen Z 2013 X-ray CT image reconstruction via wavelet frame based regularization and Radon domain inpainting J. Sci. Comput.54 333-49 · Zbl 1308.94015 · doi:10.1007/s10915-012-9579-6 |
| [23] | Ehrhardt M J and Betcke M M 2016 Multi-contrast MRI reconstruction with structure-guided total variation SIAM J. Imaging Sci.9 1084-106 · Zbl 1346.47006 · doi:10.1137/15M1047325 |
| [24] | Fan J and Li R 2001 Variable selection via nonconcave penalized likelihood and its oracle properties J. Am. Stat. Assoc.96 1348-60 · Zbl 1073.62547 · doi:10.1198/016214501753382273 |
| [25] | Foucart S and Lai M J 2009 Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q < =1 Appl. Comput. Harmon. Anal.26 395-407 · Zbl 1171.90014 · doi:10.1016/j.acha.2008.09.001 |
| [26] | Frankel P, Garrigos G and Peypouquet J 2015 Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates J. Optim. Theory Appl.165 874-900 · Zbl 1316.49039 · doi:10.1007/s10957-014-0642-3 |
| [27] | Goldstein T and Osher S 2009 The split Bregman method for ℓ1-regularized problems SIAM J. Imaging Sci.2 323-43 · Zbl 1177.65088 · doi:10.1137/080725891 |
| [28] | Gu G, Jiang S and Yang J 2017 A TVSCAD approach for image deblurring with impulsive noise Inverse Problems33 125008 · Zbl 1394.94011 · doi:10.1088/1361-6420/aa9383 |
| [29] | Hintermuller M and Wu T 2013 Nonconvex TVq-models in image restoration: analysis and a trust-region regularization-based superlinearly convergent solver SIAM J. Imaging Sci.6 1385-415 · Zbl 1281.65033 · doi:10.1137/110854746 |
| [30] | Hong M, Luo Z and Razaviyayn M 2016 Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems SIAM J. Optim.26 337-64 · Zbl 1356.49061 · doi:10.1137/140990309 |
| [31] | Knoll F, Bredies K, Pock T and Stollberger R 2011 Second order total generalized variation (TGV) for MRI Magn. Reson. Med.65 480-91 · doi:10.1002/mrm.22595 |
| [32] | Knoll F, Clason C, Bredies K, Uecker M and Stollberger R 2012 Parallel imaging with nonlinear reconstruction using variational penalties Magn. Reson. Med.67 34-41 · doi:10.1002/mrm.22964 |
| [33] | Lai M J and Wang J Y 2011 An unconstrained ℓq minimization with 0<q⩽1 for sparse solution of underdetermined linear systems SIAM J. Optim.21 82-101 · Zbl 1220.65051 · doi:10.1137/090775397 |
| [34] | Lai M J, Xu Y Y and Yin W T 2013 Improved iteratively reweighted least squares for unconstrained smoothed ℓq minimization SIAM J. Numer. Anal.51 927-57 · Zbl 1268.49038 · doi:10.1137/110840364 |
| [35] | Lanza A, Morigi S and Sgallari F 2016 Constrained TVp -ℓ2 model for image restoration J. Sci. Comput.68 64-91 · Zbl 1344.65025 · doi:10.1007/s10915-015-0129-x |
| [36] | Li G and Pong T K 2015 Global convergence of splitting methods for nonconvex composite optimization SIAM J. Optim.25 2434-60 · Zbl 1330.90087 · doi:10.1137/140998135 |
| [37] | Lou Y, Zhang X, Osher S and Bertozzi A L 2010 Image recovery via nonlocal operators J. Sci. Comput.42 185-97 · Zbl 1203.65088 · doi:10.1007/s10915-009-9320-2 |
| [38] | Lustig M, Donoho D L and Pauly J M 2007 Sparse MRI: the application of compressed sensing for rapid MR imaging Magn. Reson. Med.58 1182-95 · doi:10.1002/mrm.21391 |
| [39] | Meyer Y 2001 Oscillating patterns in image processing and nonlinear evolution equations: the fifteenth dean jacqueline b. lewis memorial lectures Am. Math. Soc.22 · Zbl 0987.35003 |
| [40] | Micchelli C A, Shen L and Xu Y 2011 Proximity algorithms for image models: denoising Inverse Problems27 045009 · Zbl 1216.94015 · doi:10.1088/0266-5611/27/4/045009 |
| [41] | Nikolova M 2006 Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares SIAM J. Multiscale Model. Simul.4 960-91 · Zbl 1091.94007 · doi:10.1137/040619582 |
| [42] | Nikolova M, Ng M K and Tam C P 2010 Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction IEEE Trans. Image Process.19 3073-88 · Zbl 1371.94277 · doi:10.1109/TIP.2010.2052275 |
| [43] | Nikolova M, Ng M K, Zhang S and Ching W 2008 Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization SIAM J. Imaging Sci.1 2-25 · Zbl 1207.94017 · doi:10.1137/070692285 |
| [44] | Ochs P, Chen Y, Brox T and Pock T 2014 Ipiano: inertial proximal algorithm for nonconvex optimization SIAM J. Imaging Sci.7 1388-419 · Zbl 1296.90094 · doi:10.1137/130942954 |
| [45] | Ochs P, Dosovitskiy A, Brox T and Pock T 2015 On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision SIAM J. Imaging Sci.8 331-72 · Zbl 1326.65078 · doi:10.1137/140971518 |
| [46] | Rasch J, Kolehmainen V, Nivajarvi R, Kettunen M I, Grohn O, Burger M and Brinkmann E 2018 Dynamic MRI reconstruction from undersampled data with an anatomical prescan Inverse Problems34 074001 · Zbl 1397.78038 · doi:10.1088/1361-6420/aac3af |
| [47] | Rockafellar R T and Wets R J B 2009 Variational Analysis vol 317 (Berlin: Springer) |
| [48] | Rudin L, Osher S and Fatemi E 1992 Nonlinear total variation based noise removal algorithms Physica D 60 259-68 · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [49] | Sidky E Y and Pan X 2008 Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization Phys. Med. Biol.53 4777-807 · doi:10.1088/0031-9155/53/17/021 |
| [50] | Tikhonov A N 1963 Solution of incorrectly formulated problems and the regularization method Sov. Math. Dokl.4 1035-8 · Zbl 0141.11001 |
| [51] | Tovey R, Benning M, Brune C, Lagerwerf M J, Collins S M, Leary R K, Midgley P A and Schonlieb C 2019 Directional sinogram inpainting for limited angle tomography Inverse Problems35 024004 · Zbl 1407.92074 · doi:10.1088/1361-6420/aaf2fe |
| [52] | Wang Y, Yang J, Yin W and Zhang Y 2008 A new alternating minimization algorithm for total variation image reconstruction SIAM J. Imaging Sci.1 248-72 · Zbl 1187.68665 · doi:10.1137/080724265 |
| [53] | Wang Y, Yin W and Zeng J 2019 Global convergence of ADMM in nonconvex nonsmooth optimization J. Sci. Comput.78 29-63 · Zbl 1462.65072 · doi:10.1007/s10915-018-0757-z |
| [54] | Wu C, Liu Z and Wen S 2018 A general truncated regularization framework for contrast-preserving variational signal and image restoration: motivation and implementation Sci. China Math.61 1711-32 · Zbl 1411.94011 · doi:10.1007/s11425-017-9260-8 |
| [55] | Wu C and Tai X 2010 Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models SIAM J. Imaging Sci.3 300-39 · Zbl 1206.90245 · doi:10.1137/090767558 |
| [56] | You J, Jiao Y, Lu X and Zeng T 2019 A nonconvex model with minimax concave penalty for image restoration J. Sci. Comput.78 1063-86 · Zbl 1419.94014 · doi:10.1007/s10915-018-0801-z |
| [57] | Zeng C, Jia R and Wu C 2019 An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration J. Math. Imaging Vis.64 122-39 · Zbl 1487.94034 · doi:10.1007/s10851-018-0830-0 |
| [58] | Zeng C and Wu C 2018 On the edge recovery property of noncovex nonsmooth regularization in image restoration SIAM J. Numer. Anal.56 1168-82 · Zbl 1391.49050 · doi:10.1137/17M1123687 |
| [59] | Zeng C, Wu C and Jia R 2019 Non-Lipschitz models for image restoration with impulse noise removal SIAM J. Imaging Sci.12 420-58 · Zbl 1426.49037 · doi:10.1137/18M117769X |
| [60] | Zhan R and Dong B 2016 CT image reconstruction by spatial-Radon domain data-driven tight frame regularization SIAM J. Imaging Sci.9 1063-83 · Zbl 1343.92272 · doi:10.1137/16M105928X |
| [61] | Zhang X, Bai M and Ng M K 2017 Nonconvex-TV based image restoration with impulse noise removal SIAM J. Imaging Sci.10 1627-67 · Zbl 1382.49013 · doi:10.1137/16M1076034 |
| [62] | Zhang Y, Dong B and Lu Z 2013 ℓ0 minimization for wavelet frame based image restoration Math. Comput.82 995-1015 · Zbl 1277.80022 · doi:10.1090/S0025-5718-2012-02631-7 |
| [63] | Zheng Z, Wu C and Ng M K 2020 A globally convergent algorithm for a class of non-Lipschitz models with applications in poisson or multiplicative noise removal submitted |
| [64] | Zibetti M V W, Lin C and Herman G T 2018 Total variation superiorized conjugate gradient method for image reconstruction Inverse Problems34 034001 · Zbl 1430.94040 · doi:10.1088/1361-6420/aaa49b |
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.
