A stable method solving the total variation dictionary model with $L^\infty$ constraints

Liyan Ma; Lionel Moisan; Jian Yu; Tieyong Zeng

doi:10.3934/ipi.2014.8.507

Article Contents

2014, Volume 8, Issue 2: 507-535. Doi: 10.3934/ipi.2014.8.507

This issue Previous Article A new computer-aided method for detecting brain metastases on contrast-enhanced MR images Next Article Kozlov-Maz'ya iteration as a form of Landweber iteration

A stable method solving the total variation dictionary model with $L^\infty$ constraints

1.
Institute of Microelectronics, Chinese Academy of Sciences, Beijing
2.
MAP5, Université Paris Descartes, Paris, 75006
3.
School of Computer and Information Technology, Beijing Jiaotong University, Beijing
4.
Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

Received: October 31, 2011

Revised: April 30, 2013

Published: April 2014

Abstract Related Papers Cited by

Abstract

Image restoration plays an important role in image processing, and numerous approaches have been proposed to tackle this problem. This paper presents a modified model for image restoration, that is based on a combination of Total Variation and Dictionary approaches. Since the well-known TV regularization is non-differentiable, the proposed method utilizes its dual formulation instead of its approximation in order to exactly preserve its properties. The data-fidelity term combines the one commonly used in image restoration and a wavelet thresholding based term. Then, the resulting optimization problem is solved via a first-order primal-dual algorithm. Numerical experiments demonstrate the good performance of the proposed model. In a last variant, we replace the classical TV by the nonlocal TV regularization, which results in a much higher quality of restoration.

Keywords:

Mathematics Subject Classification: 52A41, 65F22, 65K10, 65K05, 68U10, 90C25, 90C47.

Citation:

Related Papers

Cited by

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-2356.doi: 10.1109/TIP.2010.2047910.
[2]	L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problem, Oxford, U.K.: Oxford Univ. Press 2000.
[3]	G. Aubert and P. Kornprobst, Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, Applied Mathematical Sciences, 147. Springer, New York, 2006.
[4]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 2 (2009), 183-202.doi: 10.1137/080716542.
[5]	M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, in Proc. SIGGRAPH, New York, (2000), 417-424.doi: 10.1145/344779.344972.
[6]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.doi: 10.1017/CBO9780511804441.
[7]	J. P. Boyle and R. L. Dykstra, A method for finding projections onto the intersection of convex sets in Hilbert spaces, Lecture Notes in Statistics, 37 (1986), 28-47.doi: 10.1007/978-1-4613-9940-7_3.
[8]	X. Bresson, A Short Note for Nonlocal TV Minimization, Technical Report, 2009.
[9]	X. Bresson and T. F. Chan, Fast dual minimization of the vectorial total variation norm and applications to color image processing, Inverse Problems and Imaging, 2 (2008), 455-484.doi: 10.3934/ipi.2008.2.455.
[10]	A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one, Multiscale Model. Simul., 4 (2005), 490-530.doi: 10.1137/040616024.
[11]	A. Bugeau, M. Bertalmio, V. Caselles and G. Sapiro, A Comprehensive Framework for Image Inpainting, IEEE Trans. Image Process., 19 (2010), 2634-2645.doi: 10.1109/TIP.2010.2049240.
[12]	E. Candes and F. Guo, A new multiscale transform, minimum total variation synthesis: Application to edge-preserving image reconstruction, Signal Processing, 82 (2002), 1519-1543.
[13]	A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imag. Vis., 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.
[14]	A. Chambolle, R. DeVore, N.-Y. Lee and B. Lucier, Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process., 7 (1998), 319-335.doi: 10.1109/83.661182.
[15]	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.
[16]	T. F. Chan, G. H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comp., 20 (1999), 1964-1977.doi: 10.1137/S1064827596299767.
[17]	T. F. Chan, A. M. Yip and F. E. Park, Simultaneous total variation image inpainting and blind deconvolution, Int. J. of Imaging Systems and Technology, 15 (2005), 92-102.doi: 10.1002/ima.20041.
[18]	T. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005.doi: 10.1137/1.9780898717877.
[19]	C. Chaux, J. C. Pesquet and N. Pustelnik, Nested iterative algorithms for convex constrained image recovery problems, SIAM J. Imag. Sci., 2 (2009), 730-762.doi: 10.1137/080727749.
[20]	P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward backward splitting, Multiscale Model. Simul., 4 (2005), 1168-1200.doi: 10.1137/050626090.
[21]	I. Daubechies, Ten Lectures on Wavelets, SIAM Publ., Philadelphia, 1992.doi: 10.1137/1.9781611970104.
[22]	I. Daubechies, M. Defriese and C. D. Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun.Pure Appl. Math., 57 (2004), 1413-1457.doi: 10.1002/cpa.20042.
[23]	D. L. Donoho and I. M. Johnstone, Ideal spatial adaptation by wavelet shrinkage, Biometrika, 81 (1994), 425-455.doi: 10.1093/biomet/81.3.425.
[24]	D. L. Donoho and I. M. Johnstone, Adapting to unknown smoothness via wavelet shrinkage, J. Amer. Statist. Assoc., 90 (1995), 1200-1224.doi: 10.1080/01621459.1995.10476626.
[25]	I. Ekeland and R. Temam, Convex Analysis and Variational Problems, Studies Math. Appl., American Elsevier, Amsterdam, New York, 1976.
[26]	D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Solution of Boundary-Valued Problems, M. Fortin and R. Glowinski, eds., North-Holland, Amsterdam, 1983, 299-331.
[27]	G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, Multiscale Model. Simul., 7 (2008), 1005-1028.doi: 10.1137/070698592.
[28]	T. Goldstein and S. Osher, The split Bregman method for l1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343.doi: 10.1137/080725891.
[29]	S. Lintner and F. Malgouyres, Solving a variational image restoration model which involves contraints, Inverse. Probl., 20 (2004), 815-831.doi: 10.1088/0266-5611/20/3/010.
[30]	J. Liu, X-C. Tai, H. Huang and Z. Huan, A weighted dictionary learning model for denoising images corrupted by mixed noise, IEEE Trans. on Image Process, 22 (2013), 1108-1120.doi: 10.1109/TIP.2012.2227766.
[31]	F. Malgouyres, A framework for image deblurring using wavelet packet bases, Appl. and Comp. Harmonic Analysis, 12 (2002), 309-331.doi: 10.1006/acha.2002.0379.
[32]	F. Malgouyres, Mathematical analysis of a model which combines total variation and wavelets for image restoration, Journal of Information Processes, 2 (2002), 1-10.
[33]	F. Malgouyres, Minimizing the total variation under a general convex constraint for image restoration, IEEE Trans. on Image Process, 11 (2002), 1450-1456.doi: 10.1109/TIP.2002.806241.
[34]	S. Masnou and J.-M. Morel, Level lines based disocclusion, Int. Conf. on Image Processing, 3 (1998), 259-263.doi: 10.1109/ICIP.1998.999016.
[35]	C. A. Micchelli, L. Shen and Y. Xu, Proximity algorithms for image models: Denoising, Inverse Probl., 27 (2011), 45009-45038.doi: 10.1088/0266-5611/27/4/045009.
[36]	J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C.R. Acad. Sci. Paris Ser. A Math, 255 (1962), 2897-2899.
[37]	J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.
[38]	Y. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^2)$, (Russian), Dokl. Akad. Nauk SSSR, 269 (1983), 543-547.
[39]	M. Ng, W. Fan and X. Yuan, Inexact alternating direction methods for image recovery, SIAM J. Sci. Comp., 33 (2011), 1643-1668.doi: 10.1137/100807697.
[40]	G. Peyre, S. Bougleux and L. Cohen, Non-local regularization of inverse problems, Inverse Problems and Imaging, 5 (2011), 511-530.doi: 10.3934/ipi.2011.5.511.
[41]	L. Rudin S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.
[42]	S. Setzer, Operator splittings, Bregman methods and frame shrinkage in image processing, Int. J. Comput. Vis., 92 (2011), 265-280.doi: 10.1007/s11263-010-0357-3.
[43]	G. Steidl, J.Weickert, T. Brox, P. Mrázek and M. Welk, On the equivalence of soft wavelet shrinkage, total variation diffusion, total variation regularization, and sides, SIAM J. Numer. Anal., 42 (2004), 686-713.doi: 10.1137/S0036142903422429.
[44]	X.-C. Tai and C. Wu, Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model, SSVM 2009, LNCS 5567, Springer, 42 (2009), 502-513.
[45]	A. Tikhonov and V. Arsenin, Solution of Ill-Posed Problems, Winston and Sons, Washington, DC, 1977.
[46]	C. Wu, J. Zhang and X.-C. Tai, Augmented Lagrangian method for total variation restoration with non-quadratic fidelity, Inverse Problems and Imaging, 5 (2011), 237-261.doi: 10.3934/ipi.2011.5.237.
[47]	C. Zalinescu, Convex Analysis in General Vector Spaces, Singapore: World Scientific, 2002.doi: 10.1142/9789812777096.
[48]	T. Zeng, Incorporating known features into a total variation dictionary model for source separation, Int. Conf. on Image Processing, (2008), 577-580.doi: 10.1109/ICIP.2008.4711820.
[49]	T. Zeng and F. Malgouyres, Using Gabor dictionaries in a TV-$L^\infty$ model for denoising, Int. Conf. on Acoust. Speech and Signal Proc., (2006), 865-868.
[50]	T. Zeng and M. K. Ng, On the total variation dictionary model, IEEE trans. on Image Process., 19 (2010), 821-825.doi: 10.1109/TIP.2009.2034701.
[51]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized Nonlocal Regularization for Deconvolution and Sparse Reconstruction, SIAM J. Imag. Sci., 3 (2010), 253-276.doi: 10.1137/090746379.
[52]	M. Zhu and T. Chan, An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, UCLA CAM Report 08-34 (2008).