ℓ₀ Minimization for wavelet frame based image restoration

Zhang, Yong; Dong, Bin; Lu, Zhaosong

doi:10.1090/S0025-5718-2012-02631-7

$\ell _0$ Minimization for wavelet frame based image restoration
HTML articles powered by AMS MathViewer

by Yong Zhang, Bin Dong and Zhaosong Lu PDF

Math. Comp. 82 (2013), 995-1015 Request permission

Abstract:

The theory of (tight) wavelet frames has been extensively studied in the past twenty years and they are currently widely used for image restoration and other image processing and analysis problems. The success of wavelet frame based models, including balanced approach and analysis based approach, is due to their capability of sparsely approximating piecewise smooth functions like images. Motivated by the balanced approach and analysis based approach, we shall propose a wavelet frame based $\ell _0$ minimization model, where the $\ell _0$ “norm” of the frame coefficients is penalized. We adapt the penalty decomposition (PD) method of Lu and Zhang to solve the proposed optimization problem. Some convergence analysis of the adapted PD method will also be provided. Numerical results showed that the proposed model solved by the PD method can generate images with better quality than those obtained by either analysis based approach or balanced approach in terms of restoring sharp features as well as maintaining smoothness of the recovered images.

References

Anestis Antoniadis and Jianqing Fan, Regularization of wavelet approximations, J. Amer. Statist. Assoc. 96 (2001), no. 455, 939–967. With discussion and a rejoinder by the authors. MR 1946364, DOI 10.1198/016214501753208942
Gilles Aubert and Pierre Kornprobst, Mathematical problems in image processing, 2nd ed., Applied Mathematical Sciences, vol. 147, Springer, New York, 2006. Partial differential equations and the calculus of variations; With a foreword by Olivier Faugeras. MR 2244145
Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183–202. MR 2486527, DOI 10.1137/080716542
Ernesto G. Birgin, José Mario Martínez, and Marcos Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), no. 4, 1196–1211. MR 1777088, DOI 10.1137/S1052623497330963
Thomas Blumensath and Mike E. Davies, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl. 14 (2008), no. 5-6, 629–654. MR 2461601, DOI 10.1007/s00041-008-9035-z
Thomas Blumensath and Mike E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009), no. 3, 265–274. MR 2559726, DOI 10.1016/j.acha.2009.04.002
Jian-Feng Cai, Raymond H. Chan, Lixin Shen, and Zuowei Shen, Convergence analysis of tight framelet approach for missing data recovery, Adv. Comput. Math. 31 (2009), no. 1-3, 87–113. MR 2511575, DOI 10.1007/s10444-008-9084-5
Jian-Feng Cai, Raymond H. Chan, and Zuowei Shen, Simultaneous cartoon and texture inpainting, Inverse Probl. Imaging 4 (2010), no. 3, 379–395. MR 2671102, DOI 10.3934/ipi.2010.4.379
Jian-Feng Cai, Bin Dong, Stanley Osher, and Zuowei Shen, Image restoration: total variation, wavelet frames, and beyond, J. Amer. Math. Soc. 25 (2012), no. 4, 1033–1089. MR 2947945, DOI 10.1090/S0894-0347-2012-00740-1
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci. 2 (2009), no. 1, 226–252. MR 2486529, DOI 10.1137/080733371
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul. 8 (2009/10), no. 2, 337–369. MR 2581025, DOI 10.1137/090753504
Emmanuel J. Candès, Yonina C. Eldar, Deanna Needell, and Paige Randall, Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal. 31 (2011), no. 1, 59–73. MR 2795875, DOI 10.1016/j.acha.2010.10.002
Emmanuel J. Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489–509. MR 2236170, DOI 10.1109/TIT.2005.862083
Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI 10.1109/TIT.2005.858979
Emmanuel J. Candes and Terence Tao, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406–5425. MR 2300700, DOI 10.1109/TIT.2006.885507
Anwei Chai and Zuowei Shen, Deconvolution: a wavelet frame approach, Numer. Math. 106 (2007), no. 4, 529–587. MR 2317925, DOI 10.1007/s00211-007-0075-0
Antonin Chambolle and Pierre-Louis Lions, Image recovery via total variation minimization and related problems, Numer. Math. 76 (1997), no. 2, 167–188. MR 1440119, DOI 10.1007/s002110050258
Raymond H. Chan, Tony F. Chan, Lixin Shen, and Zuowei Shen, Wavelet algorithms for high-resolution image reconstruction, SIAM J. Sci. Comput. 24 (2003), no. 4, 1408–1432. MR 1976222, DOI 10.1137/S1064827500383123
Raymond H. Chan, Sherman D. Riemenschneider, Lixin Shen, and Zuowei Shen, Tight frame: an efficient way for high-resolution image reconstruction, Appl. Comput. Harmon. Anal. 17 (2004), no. 1, 91–115. MR 2067917, DOI 10.1016/j.acha.2004.02.003
R.H. Chan, L. Shen, and Z. Shen. A framelet-based approach for image inpainting. technical report, 4:325, 2005.
Raymond H. Chan, Zuowei Shen, and Tao Xia, A framelet algorithm for enhancing video stills, Appl. Comput. Harmon. Anal. 23 (2007), no. 2, 153–170. MR 2344608, DOI 10.1016/j.acha.2006.10.003
T. Chan, S. Esedoglu, F. Park, and A. Yip, Total variation image restoration: overview and recent developments, Handbook of mathematical models in computer vision, Springer, New York, 2006, pp. 17–31. MR 2232522, DOI 10.1007/0-387-28831-7_{2}
Tony F. Chan and Jianhong Shen, Image processing and analysis, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. Variational, PDE, wavelet, and stochastic methods. MR 2143289, DOI 10.1137/1.9780898717877
Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107, DOI 10.1137/1.9781611970104
Ingrid Daubechies, Bin Han, Amos Ron, and Zuowei Shen, Framelets: MRA-based constructions of wavelet frames, Appl. Comput. Harmon. Anal. 14 (2003), no. 1, 1–46. MR 1971300, DOI 10.1016/S1063-5203(02)00511-0
Ingrid Daubechies, Gerd Teschke, and Luminita Vese, Iteratively solving linear inverse problems under general convex constraints, Inverse Probl. Imaging 1 (2007), no. 1, 29–46. MR 2262744, DOI 10.3934/ipi.2007.1.29
Bin Dong, Aichi Chien, and Zuowei Shen, Frame based segmentation for medical images, Commun. Math. Sci. 9 (2011), no. 2, 551–559. MR 2815684
B. Dong and Z. Shen. \uppercase{MRA} based wavelet frames and applications. IAS Lecture Notes Series, Summer Program on “The Mathematics of Image Processing”, Park City Mathematics Institute, 2010.
Bin Dong and Zuowei Shen, Wavelet frame based surface reconstruction from unorganized points, J. Comput. Phys. 230 (2011), no. 22, 8247–8255. MR 2835419, DOI 10.1016/j.jcp.2011.07.022
David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
M. Elad, J.-L. Starck, P. Querre, and D. L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal. 19 (2005), no. 3, 340–358. MR 2186449, DOI 10.1016/j.acha.2005.03.005
M.J. Fadili and J.L. Starck. Sparse representations and bayesian image inpainting. Proceedings of SPARS, 2005.
M.J. Fadili, J.L. Starck, and F. Murtagh. Inpainting and zooming using sparse representations. The Computer Journal, 52(1):64, 2009.
Mário A. T. Figueiredo and Robert D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process. 12 (2003), no. 8, 906–916. MR 2008658, DOI 10.1109/TIP.2003.814255
M.A.T. Figueiredo and R.D. Nowak. A bound optimization approach to wavelet-based image deconvolution. IEEE International Conference on Image Processing, 2005.
D. Geman and C. Yang. Nonlinear image recovery with half-quadratic regularization. Image Processing, IEEE Transactions on, 4(7):932–946, 1995.
Tom Goldstein and Stanley Osher, The split Bregman method for $L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323–343. MR 2496060, DOI 10.1137/080725891
K.K. Herrity, A.C. Gilbert, and J.A. Tropp. Sparse approximation via iterative thresholding. IEEE International Conference on Acoustics, Speech and Signal Processing, 2006.
X. Jia, Y. Lou, B. Dong, and S. Jiang. GPU-based iterative cone beam CT reconstruction using tight frame regularization. Phys. Med. Biol. 56(13):3787–3807, 2011.
Z. Lu and Y. Zhang. Penalty decomposition methods for $l_0$-norm minimization. preprint, 2010.
Yves Meyer, Oscillating patterns in image processing and nonlinear evolution equations, University Lecture Series, vol. 22, American Mathematical Society, Providence, RI, 2001. The fifteenth Dean Jacqueline B. Lewis memorial lectures. MR 1852741, DOI 10.1090/ulect/022
Stanley Osher and Ronald Fedkiw, Level set methods and dynamic implicit surfaces, Applied Mathematical Sciences, vol. 153, Springer-Verlag, New York, 2003. MR 1939127, DOI 10.1007/b98879
R. Tyrrell Rockafellar and Roger J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR 1491362, DOI 10.1007/978-3-642-02431-3
Amos Ron and Zuowei Shen, Affine systems in $L_2(\mathbf R^d)$: the analysis of the analysis operator, J. Funct. Anal. 148 (1997), no. 2, 408–447. MR 1469348, DOI 10.1006/jfan.1996.3079
L. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Journal of Physics D, 60:259–268, 1992.
Guillermo Sapiro, Geometric partial differential equations and image analysis, Cambridge University Press, Cambridge, 2001. MR 1813971, DOI 10.1017/CBO9780511626319
Z. Shen. Wavelet frames and image restorations. Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010.
Zuowei Shen, Kim-Chuan Toh, and Sangwoon Yun, An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approach, SIAM J. Imaging Sci. 4 (2011), no. 2, 573–596. MR 2810898, DOI 10.1137/090779437
R.L. Siddon. Fast calculation of the exact radiological path for a three-dimensional CT array. Medical Physics, 12:252–255, 1985.
Jean-Luc Starck, Michael Elad, and David L. Donoho, Image decomposition via the combination of sparse representations and a variational approach, IEEE Trans. Image Process. 14 (2005), no. 10, 1570–1582. MR 2483314, DOI 10.1109/TIP.2005.852206
Gabriele Steidl, Joachim Weickert, Thomas Brox, Pavel Mrázek, and Martin Welk, On the equivalence of soft wavelet shrinkage, total variation diffusion, total variation regularization, and sides, SIAM J. Numer. Anal. 42 (2004), no. 2, 686–713. MR 2084232, DOI 10.1137/S0036142903422429
P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001), no. 3, 475–494. MR 1835069, DOI 10.1023/A:1017501703105
Yilun Wang, Junfeng Yang, Wotao Yin, and Yin Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci. 1 (2008), no. 3, 248–272. MR 2486032, DOI 10.1137/080724265