×

On a nonlinear multigrid algorithm with primal relaxation for the image total variation minimisation. (English) Zbl 1096.94003

Summary: Digital image restoration has drawn much attention in the recent years and a lot of research has been done on effective variational partial differential equation models and their theoretical studies. However there remains an urgent need to develop fast and robust iterative solvers, as the underlying problem sizes are large. This paper proposes a fast multigrid method using primal relaxations. The basic primal relaxation is known to get stuck at a ‘local’ non-stationary minimum of the solution, which is usually believed to be ‘non-smooth’. Our idea is to utilize coarse level corrections, overcoming the deadlock of a basic primal relaxation scheme. A further refinement is to allow non-regular coarse levels to correct the solution, which helps to improve the multilevel method. Numerical experiments on both 1D and 2D images are presented.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
35K57 Reaction-diffusion equations
65K10 Numerical optimization and variational techniques
90C59 Approximation methods and heuristics in mathematical programming
65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65M32 Numerical methods for inverse problems for initial value and initial-boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
68U10 Computing methodologies for image processing

Software:

NEWUOA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Acar and C.R. Vogel, Analysis of total variation penalty method for ill-posed problems, Inverse Probl. 10 (1994) 1217–1229. · Zbl 0809.35151 · doi:10.1088/0266-5611/10/6/003
[2] L. Alvarez, P.L. Lions and J.M. Morel, Image selective smoothing and edge detection by nonlinear diffusion II, SIAM J. Numer. Anal. 29 (1992) 845–866. · Zbl 0766.65117 · doi:10.1137/0729052
[3] H.C. Andrews and B.R. Hunt, Digital image restoration (Prentice-Hall, 1977). · Zbl 0379.62098
[4] P. Blomgren, T.F. Chan, P. Mulet, L. Vese and W.L. Wan, Variational pde models and methods for image processing, in: Research Notes in Mathematics, 420 (Chapman & Hall/CRC, 2000) pp. 43–67. · Zbl 0953.68621
[5] M.M. Bronstein, A.M. Bronstein, R. Kimmel and I. Yavneh, Multigrid multidimensional scaling, Numer. Lin. Algebra Appl. (2006) to appear. · Zbl 1174.68537
[6] D. Calvetti, B. Lewis and L. Reichel, Krylov subspace iterative methods for nonsymmetric discrete ill-posed problems in image restoration, in: Advanced Signal Processing Algorithms, Architectures, and Implementations X, ed. F.T. Luk, Proceedings of the Society of Photo-Optical Instrumentation Engineers (SPIE), vol. 4116 (The International Society for Optical Engineering, Bellingham, Washington, 2001).
[7] J.L. Carter, Dual method for total variation-based image restoration, CAM report 02–13, UCLA, USA (2002); see http://www.math.ucla.edu/applied/cam/index.html.
[8] E. Casas, K. Kunisch and C. Pola, Regularization of functions of bounded variation and applications to image enhancement, Appl. Math. Optim. 40 (1999) 229–257. · Zbl 0942.49014 · doi:10.1007/s002459900124
[9] A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis. 20 (2004) 89–97. · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011320.81911.38
[10] A. Chambolle and P.L. Lions, Image recovery via total variation minimization and related problems, Numer. Math. 76 (1997) 167–188. · Zbl 0874.68299 · doi:10.1007/s002110050258
[11] R.H. Chan, T.F. Chan and W.L. Wan, Multigrid for differential convolution problems arising from image processing, in: Proc. Sci. Comput. Workshop, Springer-Verlag, eds. R. Chan, T.F. Chan and G.H. Golub, (1997) see also CAM report 97–20, UCLA, USA. · Zbl 0922.65097
[12] R.H. Chan, T.F. Chan and C.K. Wong, Cosine transform based preconditioners for total variation minimization problems in image processing, IEEE Trans. Image Proc., 8 (1999) pp.1472–1478; see also CAM report 97–44, UCLA.
[13] R.H. Chan, Q.S. Chang and H.W. Sun, Multigrid method for ill-conditioned symmetric toeplitz systems, SIAM J. Sci. Comput. 19 (1998) 516–529. · Zbl 0916.65029 · doi:10.1137/S1064827595293831
[14] T.F. Chan and P. Mulet, Iterative methods for total variation restoration, CAM report 96–38, UCLA, USA (1996); see http://www.math.ucla.edu/applied/cam/index.html.
[15] T.F. Chan, G.H. Golub and P. Mulet, A nonlinear primal dual method for total variation based image restoration, SIAM J. Sci. Comput. 20 (6)(1999) 1964–1977. · Zbl 0929.68118 · doi:10.1137/S1064827596299767
[16] Q.S. Chang and I.L. Chern, Acceleration methods for total variation-based image denoising, SIAM J. Sci. Comput. 25 (2003) 982–994. · Zbl 1046.65048 · doi:10.1137/S106482750241534X
[17] K. Chen, Matrix Preconditioning Techniques and Applications, Series: Cambridge Monographs on Applied and Computational Mathematics (No. 19) (Cambridge University Press, UK, 2005).
[18] D. Goldfarb and W.T. Yin, Second-order cone programming methods for total variation-based image restoration, SIAM J. Sci. Comput. 27 (2) (2005) 622–645. · Zbl 1094.68108 · doi:10.1137/040608982
[19] R.C. Gonzalez and R.E. Woods, Digital image processing (Addison-Wesley, 1993).
[20] S. Henn and K. Witsch, A multigrid approach for minimizing a nonlinear functional for digital image matching, Computing 64 (4) (1999) 339–348. · Zbl 0961.65120 · doi:10.1007/s006070070029
[21] C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising, Comput Visual Sci. 7 (2004) 199–206. · Zbl 1071.65093
[22] M. Hintermüller and K. Kunisch, Total bounded variation regularization as a bilaterally constrained optimization problem, SIAM J. Appl. Math. 64 (2004) 1311–1333. · Zbl 1055.94504 · doi:10.1137/S0036139903422784
[23] Hintermüller and G. Stadler, An infeasible primal–dual algorithm for TV-based infconvolution-type image restoration, Technical Report TR04–15, (CAAM Dept. Rice University, USA, 2004). · Zbl 1136.94302
[24] W. Hinterberger, M. Hintermüller, K. Kunisch, M. von Oehsen and O. Scherzer, Tube methods for BV regularization, J. Math. Imaging Vis. 19 (2003) 219–235. · Zbl 1101.68927 · doi:10.1023/A:1026276804745
[25] K. Ito and K. Kunisch, An active set strategy based on the augmented Lagrangian formulation for image restoration, Math. Mod. Numer. Anal. (M2AN) 33 (1) (1999) 1–21. · Zbl 0918.65050 · doi:10.1051/m2an:1999102
[26] T. Kärkkäinen and K. Majava, Nonmonotone and monotone active set methods for image restoration. II. Numerical results, J. Optim. Theory Appl. 106 (2000) 81–105. · Zbl 1050.90033 · doi:10.1023/A:1004607123926
[27] T. Kärkkäinen, K. Majava and M.M. Mäkelä, Comparison of Formulations and Solution Methods for Image Restoration Problems, Series B Report No. B 14/2000 (Department of Mathematical Information Technology, University of Jyväskylä, Finland, 2000).
[28] S.H. Lee and J.K. Seo, Noise removal with Gauss curvature driven diffusion, IEEE Trans. Image Process 14 (7) (2005) 904–909. · Zbl 05453081 · doi:10.1109/TIP.2005.849294
[29] Y.Y. Li and F. Santosa, A computational algorithm for minimizing total variation in image restoration, IEEE Trans. Image Process 5 (1996) 987–995. · doi:10.1109/83.503914
[30] S. Nash, A multigrid approach to discretized optimisation problems, J. Opt. Methods Softw. 14 (2000) 99–116. · Zbl 0988.90040 · doi:10.1080/10556780008805795
[31] S. Osher and A. Marquina, Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal, SIAM J. Sci. Comput. 22 (2)(2000) 387–405. · Zbl 0969.65081 · doi:10.1137/S1064827599351751
[32] M.J.D. Powell, The NEWUOA software for unconstrained optimization without derivatives, NA2004/08 (Cambridge University, UK, 2004). · Zbl 1108.90005
[33] W.H. Press, et al., Numerical Recipes in C (Cambridge University Press, UK, 1992). · Zbl 0778.65003
[34] E. Radmoser, O. Scherzer and J. Schöberl, A Cascadic Algorithm for Bounded Variation Regularization, SFB-Report No. 00–23 (Johannes Kepler University of Linz, Austria, 2000).
[35] K.L. Riley, Two-Level Preconditioners for Regularized Ill-Posed Problems, PhD thesis (Montana State University, USA, 1999).
[36] L.I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D 60 (1992) 259–268. · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[37] G. Sapiro, Geometrical Differential Equations and Image Analysis (Cambridge University Press, UK, 2001). · Zbl 0968.35001
[38] J. Savage and K. Chen, An improved and accelerated nonlinear multigrid method for total-variation denoising, Int. J. Comput. Math. 82 (8) (2005) 1001–1015. · Zbl 1072.65096 · doi:10.1080/00207160500069904
[39] K. Stuben, Algebraic Multigrid Methods, in: Multigrid, eds. U. Trottenberg, C. Oosterlee and A. Schuller (Academic, London, 2001).
[40] C.R. Vogel, A multigrid method for total variation-based image denoising, in: Computation and Control IV, 20, Progress in Systems and Control Theory, eds. K. Bowers and J. Lund (Birkhauser, 1995). · Zbl 0831.93062
[41] C.R. Vogel, Negative results for multilevel precondtioners in image deblurring, in: Scale–Space Theories in Computer Vision, ed. M. Nielson et al. (Springer, Berlin Heidelberg New York, 1999) pp. 292–304.
[42] C.R. Vogel, Computational methods for inverse problems (SIAM, USA, 2002). · Zbl 1008.65103
[43] C.R. Vogel and M.E. Oman, Iterative methods for total variation denoising, SIAM J. Sci. Statist. Comput. 17 (1996) 227–238. · Zbl 0847.65083 · doi:10.1137/0917016
[44] C.R. Vogel and M.E. Oman, Fast, robust total variation-based reconstruction of noisy, blurred images, IEEE Trans. Image Process 7 (1998) 813–824. · Zbl 0993.94519 · doi:10.1109/83.679423
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.