Half-linear regularization for nonconvex image restoration models

Bartomeu Coll; Joan Duran; Catalina Sbert

doi:10.3934/ipi.2015.9.337

Article Contents

2015, Volume 9, Issue 2: 337-370. Doi: 10.3934/ipi.2015.9.337

This issue Previous Article On the range of the attenuated magnetic ray transform for connections and Higgs fields Next Article Some geometric inverse problems for the linear wave equation

Half-linear regularization for nonconvex image restoration models

1.
Department of Mathematics and Computer Science, University of Balearic Islands, Ctra. Valldemossa Km. 7.5, 07122 Palma de Mallorca

Received: September 30, 2013

Revised: March 31, 2014

Published: April 2015

Abstract Related Papers Cited by

Abstract

Image restoration is the problem of recovering an original image from an observation of it in order to extract the most meaningful information. In this paper, we study this problem from a variational point of view through the minimization of energies composed of a quadratic data-fidelity term and a nonsmooth nonconvex regularization term. In the discrete setting, existence of minimizer is proved for arbitrary linear operators. For this kind of problems, fully segmented solutions can be found by minimizing objective nonconvex functionals. We propose a dual formulation of the model by introducing an auxiliary variable with a double function. On one hand, it marks the edges and it ensures their preservation from smoothing. On the other hand, it makes the criterion half-linear in the sense that the dual energy depends linearly on the gradient of the image to be recovered. This leads to design an efficient optimization algorithm with wide applicability to several image restoration tasks such as denoising and deconvolution. Finally, we present experimental results and we compare them with TV-based image restoration algorithms.

Keywords:

Mathematics Subject Classification: 68U10, 94A08, 65F22, 90C26, 90C46, 65K10, 65K05.

Citation:

Related Papers

Cited by

References

[1]	H. Attouch, J. Bolte, P. Redont and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality, Math. Oper. Res., 35 (2010), 438-457.doi: 10.1287/moor.1100.0449.
[2]	G. Aubert, A. El Hamidi, C. Ghannam and M. Ménard, On a class of ill-posed minimization problems in image processing, J. Math. Anal. Appl., 352 (2009), 380-399.doi: 10.1016/j.jmaa.2008.06.049.
[3]	G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing, Applied Mathematical Sciences, Springer-Verlag, New York, 2006.
[4]	A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process., 18 (2009), 2419-2434.doi: 10.1109/TIP.2009.2028250.
[5]	J. Bect, L. Blanc-Féraud, G. Aubert and A. Chambolle, A $l^1-$unified variational framework for image restoration, in Proc. of 8th European Conf. Computer Vision (ECCV), Lecture Notes Comput. Sci., 3024, Springer-Verlag, 2004, 1-13.
[6]	J. E. Besag, Digital image processing: Towards Bayesian image analysis, J. Appl. Stat., 16 (1989), 395-407.doi: 10.1080/02664768900000049.
[7]	P. Blomgren and T. F. Chan, Color TV: Total variation methods for restoration of vector-valued images, IEEE Trans. Image Process., 7 (1998), 304-309.doi: 10.1109/83.661180.
[8]	J. Bolte, S. Sabach and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), 459-494.doi: 10.1007/s10107-013-0701-9.
[9]	J. V. Burke, A. S. Lewis and M. L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15 (2005), 751-779.doi: 10.1137/030601296.
[10]	G. Carlier and M. Comte, On a weighted total variation minimization problem, J. Funct. Anal., 250 (2007), 214-226.doi: 10.1016/j.jfa.2007.05.022.
[11]	F. Catté, P.-L. Lions, J.-M. Morel and T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM J. Numer. Anal., 29 (1992), 182-193.doi: 10.1137/0729012.
[12]	A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.
[13]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), 120-145.doi: 10.1007/s10851-010-0251-1.
[14]	P. Charbonnier, L. Blanc-Féraud, G. Aubert and M. Barlaud, Deterministic edge-preserving regularization in computed imaging, IEEE Trans. Image Process., 6 (1997), 298-311.doi: 10.1109/83.551699.
[15]	X. Chen and W. Zhou, Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 3 (2010), 765-790.doi: 10.1137/080740167.
[16]	P. L. Combettes and V. Wajs, Signal recovery by proximal forward-backward splitting, SIAM J. Multiscale Model. Simul., 4 (2005), 1168-1200.doi: 10.1137/050626090.
[17]	A. H. Delaney and Y. Bresler, Globally convergent edge-preserving regularized reconstruction: An application to limited-angle tomography, IEEE Trans. Image Process., 7 (1998), 204-221.doi: 10.1109/83.660997.
[18]	J. Duran, B. Coll and C. Sbert, Chambolle's projection algorithm for total variation denoising, Image Process. On Line, 3 (2013), 301-321.doi: 10.5201/ipol.2013.61.
[19]	D. Geman and G. Reynolds, Constrained restoration and the recovery of discontinuities, IEEE Trans. Pattern Anal. Mach. Intell., 14 (1993), 367-383.doi: 10.1109/34.120331.
[20]	D. Geman and C. Yang, Nonlinear image recovery with half-quadratic regularization, IEEE Trans. Image Process., 4 (1995), 932-946.doi: 10.1109/83.392335.
[21]	S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images, Journal of Applied Statistics, 20 (1993), 25-62.doi: 10.1080/02664769300000058.
[22]	P. Getreuer, Rudin-Osher-Fatemi total variation denoising using Split Bregman, Image Process. On Line, 2 (2012), 74-95.doi: 10.5201/ipol.2012.g-tvd.
[23]	T. Goldstein and S. Osher, The Split Bregman method for $l^1-$regularized problems, SIAM J. Imaging Sci., 2 (2009), 323-343.doi: 10.1137/080725891.
[24]	A. Hamidi, M. Ménard, M. Lugiez and C. Ghannam, Weighted and extended total variation for image restoration and decomposition, Pattern Recogn., 43 (2010), 1564-1576.
[25]	M. Hintermuller and T. Wu, Nonconvex $\text{TV}^q$ models in image restoration: Analysis and a trust-region regularization-based superlinearly convergent solver, SIAM J. Imaging Sci., 6 (2013), 1385-1415.doi: 10.1137/110854746.
[26]	K. Ivanov, Conditions for well-posedness in the Hadamard sense in spaces of generalized functions, Siberian Math. J., 28 (1987), 906-911.doi: 10.1007/BF00969468.
[27]	S. Kindermann, S. Osher and P. W. Jones, Deblurring and denoising of images by nonlocal functionals, SIAM J. Multiscale Model. Simul., 4 (2005), 1091-1115.doi: 10.1137/050622249.
[28]	A. Marquina and S. Osher, Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal, SIAM J. Sci. Comput., 22 (2000), 387-405.doi: 10.1137/S1064827599351751.
[29]	R. R. Meyer, Sufficient conditions for the convergence of monotic mathematical programming algorithms, J. Comput. Syst. Sci., 12 (1976), 108-121.doi: 10.1016/S0022-0000(76)80021-9.
[30]	J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci. Paris Sér. A Math., 255 (1962), 2897-2899.
[31]	J.-M. Morel and G. Yu, Is SIFT scale invariant?, Inverse Probl. Imag., 5 (2011), 115-136.doi: 10.3934/ipi.2011.5.115.
[32]	D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure and Appl. Math., 42 (1989), 577-685.doi: 10.1002/cpa.3160420503.
[33]	Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program., 103 (2005), 127-152.doi: 10.1007/s10107-004-0552-5.
[34]	M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM J. Numer. Anal., 40 (2002), 965-994.doi: 10.1137/S0036142901389165.
[35]	M. Nikolova, Analytical bounds on the minimizers of (nonconvex) regularized least-squares, Inverse Probl. Imag., 2 (2008), 133-149.doi: 10.3934/ipi.2008.2.133.
[36]	M. Nikolova, M. K. Ng and C.-P. Tam, Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction, IEEE Trans. Image Process., 19 (2010), 3073-3088.doi: 10.1109/TIP.2010.2052275.
[37]	M. Nikolova, M. K. Ng, S. Zhang and W.-K. Ching, Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 1 (2008), 2-25.doi: 10.1137/070692285.
[38]	P. Ochs, A. Dosovitskiy, T. Brox and T. Pock, An iterated $l^1$ algorithm for non-smooth nonconvex optimization in computer vision, in Proc. of IEEE Int. Conf. Computer Vision and Pattern Recognition (CVPR), IEEE, 2013, 1759-1766.
[39]	P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Mach. Intell., 12 (1990), 629-639.doi: 10.1109/34.56205.
[40]	T. Pock and A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, in Proc. of IEEE Int. Conf. Computer Vision (ICCV), IEEE, 2011, 1762-1769.doi: 10.1109/ICCV.2011.6126441.
[41]	M. Robini, A. Lachal and I. Magnin, A stochastic continuation approach to piecewise constant reconstruction, IEEE Trans. Image Process., 16 (2007), 2576-2589.doi: 10.1109/TIP.2007.904975.
[42]	M. Robini, T. Rastello and I. Magnin, Simulated annealing, acceleration techniques, and image restoration, IEEE Trans. Image Process., 8 (1999), 1374-1387.doi: 10.1109/83.791963.
[43]	L. I. Rudin, S. J. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[44]	J. Weickert, Anisotropic Diffusion in Image Processing, ECMI Series, Teubner-Verlag, Stuttgart, 1998.
[45]	W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l^1-$minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168.doi: 10.1137/070703983.
[46]	X. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput., 46 (2011), 20-46.doi: 10.1007/s10915-010-9408-8.