Operator splittings, Bregman methods and frame shrinkage in image processing. (English) Zbl 1235.68314
Summary: We examine the underlying structure of popular algorithms for variational methods used in image processing. We focus here on operator splittings and Bregman methods based on a unified approach via fixed point iterations and averaged operators. In particular, the recently proposed alternating split Bregman method can be interpreted from different points of view-as a Bregman, as an augmented Lagrangian and as a Douglas-Rachford splitting algorithm which is a classical operator splitting method. We also study similarities between this method and the forward-backward splitting method when applied to two frequently used models for image denoising which employ a Besov-norm and a total variation regularization term, respectively. In the first setting, we show that for a discretization based on Parseval frames the gradient descent reprojection and the alternating split Bregman algorithm are equivalent and turn out to be a frame shrinkage method. For the total variation regularizer, we also present a numerical comparison with multistep methods.
MSC:
| 68U10 | Computing methodologies for image processing |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Keywords:
Douglas-Rachford splitting; forward-backward splitting; Bregman methods; augmented Lagrangian method; alternating split Bregman algorithm; image denoisingSoftware:
RecPFReferences:
| [1] | Aubin, J. P., & Frankowska, H. (2009). Set-valued analysis. Boston: Birkhäuser. · Zbl 1168.49014 |
| [2] | Aujol, J. F. (2009). Some first-order algorithms for total variation based image restoration. Journal of Mathematical Imaging and Vision, 34(3), 307–327. · Zbl 1287.94012 · doi:10.1007/s10851-009-0149-y |
| [3] | Barzilai, J., & Borwein, J. M. (1988). Two-point step size gradient methods. IMA Journal of Numerical Analysis, 8, 141–148. · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [4] | Bauschke, H. H., & Borwein, J. M. (1996). On projection algorithms for solving convex feasibility problems. SIAM Review, 38(3), 367–426. · Zbl 0865.47039 · doi:10.1137/S0036144593251710 |
| [5] | Bechler, P., DeVore, R., Kamont, A., Petrova, G., & Wojtaszczyk, P. (2006). Greedy wavelet projections are bounded on BV. Transactions of the American Mathematical Society, 359(2), 619–635. · Zbl 1134.42022 · doi:10.1090/S0002-9947-06-03903-1 |
| [6] | Beck, A., & Teboulle, M. (2009a). Fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1), 183–202. · Zbl 1175.94009 · doi:10.1137/080716542 |
| [7] | Beck, A., & Teboulle, M. (2009b). Fast gradient-based algorithms for constrained total variation image denoising and deblurring. IEEE Transactions on Image Processing, 18(11), 2419–2434. · Zbl 1371.94049 · doi:10.1109/TIP.2009.2028250 |
| [8] | Bioucas-Dias, J., & Figueiredo, M. (2009). Total variation restoration of speckled images using a split-Bregman algorithm. In Proceedings of the international conference on image processing, ICIP 2009, Cairo, Egypt (pp. 3717–3720). New York: IEEE. |
| [9] | Bonnans, J. F., & Shapiro, A. (2000). Springer series in operations research : Vol. 7. Perturbation analysis of optimization problems. Berlin: Springer. · Zbl 0966.49001 |
| [10] | Borwein, J. M., & Zhu, Q. J. (2005). Techniques of variational analysis. New York: Springer. · Zbl 1076.49001 |
| [11] | Borwein, J. M., & Zhu, Q. J. (2006). Variational methods in convex analysis. Journal of Global Optimization, 35(2), 197–213. · Zbl 1103.49005 · doi:10.1007/s10898-005-3835-3 |
| [12] | Bregman, L. M. (1967). The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3), 200–217. · Zbl 0186.23807 · doi:10.1016/0041-5553(67)90040-7 |
| [13] | Browder, F. E., & Petryshyn, W. V. (1966). The solution by iteration of nonlinear functional equations in Banach spaces. Bulletin of the American Mathematical Society, 72, 571–575. · Zbl 0138.08202 · doi:10.1090/S0002-9904-1966-11544-6 |
| [14] | Buades, A., Coll, B., & Morel, J. M. (2008). Nonlocal image and movie denoising. International Journal of Computer Vision, 76(2), 123–139. · doi:10.1007/s11263-007-0052-1 |
| [15] | Byrne, C. (2004). A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Problems, 20, 103–120. · Zbl 1051.65067 · doi:10.1088/0266-5611/20/1/006 |
| [16] | Cai, J. F., Chan, R. H., & Shen, Z. (2008). A framelet-based image inpainting algorithm. Applied and Computational Harmonic Analysis, 24, 131–149. · Zbl 1135.68056 · doi:10.1016/j.acha.2007.10.002 |
| [17] | Cai, J. F., Osher, S., & Shen, Z. (2009). Split Bregman methods and frame based image restoration (Technical report). UCLA Computational and Applied Mathematics. · Zbl 1189.94014 |
| [18] | Censor, Y., & Lent, A. (1981). An iterative row-action method for interval convex programming. Journal of Optimization Theory and Applications, 34(3), 321–353. · Zbl 0431.49042 · doi:10.1007/BF00934676 |
| [19] | Censor, Y., & Zenios, S. A. (1992). Proximal minimization algorithm with D-functions. Journal of Optimization Theory and Applications, 73(3), 451–464. · Zbl 0794.90058 · doi:10.1007/BF00940051 |
| [20] | Censor, Y., & Zenios, S. A. (1997). Parallel optimization: Theory, algorithms, and applications. New York: Oxford University Press. · Zbl 0945.90064 |
| [21] | Chambolle, A. (2004). An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision, 20(1–2), 89–97. · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011320.81911.38 |
| [22] | Chambolle, A. (2005). Total variation minimization and a class of binary MRF models. In A. Rangarajan, B. C. Vemuri, & A. L. Yuille (Eds.), Lecture notes in computer science : Vol. 3757. Energy minimization methods in computer vision and pattern recognition, EMMCVPR (pp. 136–152). Berlin: Springer. |
| [23] | Chan, R. H., Setzer, S., & Steidl, G. (2008). Inpainting by flexible Haar-wavelet shrinkage. SIAM Journal on Imaging Science, 1, 273–293. · Zbl 1187.68649 · doi:10.1137/070711499 |
| [24] | Cohen, A., DeVore, R., Petrushev, P., & Xu, H. (1999). Nonlinear approximation and the space BV(\(\mathbb{R}\)2). American Journal of Mathematics, 121, 587–628. · Zbl 0931.41019 · doi:10.1353/ajm.1999.0016 |
| [25] | Combettes, P. L. (2004). Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization, 53(5–6), 475–504. · Zbl 1153.47305 · doi:10.1080/02331930412331327157 |
| [26] | Combettes, P. L., & Pesquet, J. C. (2007). A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE Journal of Selected Topics in Signal Processing, 1(4), 564–574. · doi:10.1109/JSTSP.2007.910264 |
| [27] | Combettes, P. L., & Wajs, V. R. (2005). Signal recovery by proximal forward-backward splitting. Multiscale Modelling & Simulation, 4, 1168–1200. · Zbl 1179.94031 · doi:10.1137/050626090 |
| [28] | Daubechies, I., Han, B., Ron, A., & Shen, Z. (2003). Framelets: MRA-based construction of wavelet frames. Applied and Computational Harmonic Analysis, 14, 1–46. · Zbl 1035.42031 · doi:10.1016/S1063-5203(02)00511-0 |
| [29] | DeVore, R. A., & Lucier B. J. (1992). Fast wavelet techniques for near-optimal image processing. In IEEE MILCOM ’92 conf. rec. (Vol. 3, pp. 1129–1135). San Diego: IEEE Press. |
| [30] | Dong, B., & Shen, Z. (2007). Pseudo-splines, wavelets and framelets. Applied and Computational Harmonic Analysis, 22, 78–104. · Zbl 1282.42035 · doi:10.1016/j.acha.2006.04.008 |
| [31] | Douglas, J., & Rachford, H. H. (1956). On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society, 82(2), 421–439. · Zbl 0070.35401 · doi:10.1090/S0002-9947-1956-0084194-4 |
| [32] | Eckstein, J. (1989). Splitting methods for monotone operators with applications to parallel optimization. PhD thesis, Massachusetts Institute of Technology. |
| [33] | Eckstein, J. (1993). Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Mathematics of Operations Research, 18(1), 202–226. · Zbl 0807.47036 · doi:10.1287/moor.18.1.202 |
| [34] | Eckstein, J., & Bertsekas, D. P. (1992). On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55, 293–318. · Zbl 0765.90073 · doi:10.1007/BF01581204 |
| [35] | Ekeland, I., & Temam, R. (1976). Convex analysis and variational problems. Amsterdam: North-Holland. · Zbl 0322.90046 |
| [36] | Esser, E. (2009). Applications of Lagrangian-based alternating direction methods and connections to split Bregman (Technical report). UCLA Computational and Applied Mathematics. |
| [37] | Esser, E., Zhang, X., & Chan, T. F. (2009). A general framework for a class of first order primal-dual algorithms for TV minimization (Technical report). UCLA Computational and Applied Mathematics. |
| [38] | Figueiredo, M., & Bioucas-Dias, J. (2009). Deconvolution of Poissonian images using variable splitting and augmented Lagrangian optimization. In IEEE workshop on statistical signal processing. Cardiff. |
| [39] | Frick, K. (2008). The augmented Lagrangian method and associated evolution equations. PhD thesis. |
| [40] | Gabay, D. (1983). Applications of the method of multipliers to variational inequalities. In M. Fortin & R. Glowinski (Eds.), Studies in mathematics and its applications : Vol. 15. Augmented Lagrangian methods: Applications to the numerical solution of boundary-value problems (pp. 299–331). Amsterdam: North-Holland. Chap. 9. |
| [41] | Gabay, D., & Mercier, B. (1976). A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 2, 17–40. · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1 |
| [42] | Gilboa, G., & Osher, S. (2008). Nonlocal operators with applications to image processing. Multiscale Modelling & Simulation, 7(3), 1005–1028. · Zbl 1181.35006 · doi:10.1137/070698592 |
| [43] | Gilboa, G., Darbon, J., Osher, S., & Chan, T. F. (2006). Nonlocal convex functionals for image regularization (UCLA CAM Report 06-57). |
| [44] | Glowinski, R., & Marroco, A. (1975). Sur l’approximation par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. Revue Française d’Automatique, Informatique, Recherche Opérationnelle Analyse Numérique, 9(2), 41–76. · Zbl 0368.65053 |
| [45] | Goldstein, T., & Osher, S. (2009). The split Bregman method for L1-regularized problems. SIAM Journal on Imaging Sciences, 2(2), 323–343. · Zbl 1177.65088 · doi:10.1137/080725891 |
| [46] | Goldstein, T., Bresson, X., & Osher, S. (2009). Geometric applications of the split Bregman method: Segmentation and surface reconstruction (Technical report). UCLA Computational and Applied Mathematics. · Zbl 1203.65044 |
| [47] | Hestenes, M. R. (1969). Multiplier and gradient methods. Journal of Optimization Theory and Applications, 4, 303–320. · Zbl 0174.20705 · doi:10.1007/BF00927673 |
| [48] | Iusem, A. N. (1999). Augmented Lagrangian methods and proximal point methods for convex optimization. Investigación Operativa, 8, 11–49. |
| [49] | Kindermann, S., Osher, S., & Jones, P. W. (2005). Deblurring and denoising of images by nonlocal functionals. Multiscale Modelling & Simulation, 4(4), 1091–1115. · Zbl 1161.68827 · doi:10.1137/050622249 |
| [50] | Kiwiel, K. C. (1997). Proximal minimization methods with generalized Bregman functions. SIAM Journal on Control and Optimization, 35(4), 1142–1168. · Zbl 0890.65061 · doi:10.1137/S0363012995281742 |
| [51] | Krasnoselskii, M. A. (1955). Two observations about the method of successive approximations. Uspekhi Matematicheskikh Nauk, 10, 123–127 (in Russian). |
| [52] | Levenberg, K. (1944). A method for the solution of certain problems in least squares. Quarterly of Applied Mathematics, 2, 164–168. · Zbl 0063.03501 |
| [53] | Lions, P. L., & Mercier, B. (1979). Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6), 964–979. · Zbl 0426.65050 · doi:10.1137/0716071 |
| [54] | Mann, W. R. (1953). Mean value methods in iteration. Proceedings of the American Mathematical Society, 16(4), 506–510. · Zbl 0050.11603 · doi:10.1090/S0002-9939-1953-0054846-3 |
| [55] | Marquardt, D. (1963). An algorithm for least-squares estimation of nonlinear parameters. SIAM Journal of Applied Mathematics, 11, 431–441. · Zbl 0112.10505 · doi:10.1137/0111030 |
| [56] | Moreau, J. J. (1965). Proximité et dualité dans un espace hilbertien. Bulletin de la Societé Mathématique de France, 93, 273–299. · Zbl 0136.12101 |
| [57] | Mrázek, P., & Weickert, J. (2003). Rotationally invariant wavelet shrinkage. In B. Michaelis & G. Krell (Eds.), Pattern recognition (Vol. 2781, pp. 156–163). Berlin: Springer. · Zbl 1067.68758 |
| [58] | Nesterov, Y. E. (1983). A method of solving a convex programming problem with convergence rate O(1/k 2). Soviet Mathematics Doklady, 27(2), 372–376. · Zbl 0535.90071 |
| [59] | Nesterov, Y. E. (2005). Smooth minimization of non-smooth functions. Mathematical Programming, 103, 127–152. · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
| [60] | Opial, Z. (1967). Weak convergence of a sequence of successive approximations for nonexpansive mappings. Bulletin of the American Mathematical Society, 73, 591–597. · Zbl 0179.19902 · doi:10.1090/S0002-9904-1967-11761-0 |
| [61] | Osher, S., Burger, M., Goldfarb, D., Xu, J., & Yin, W. (2005). An iterative regularization method for the total variation based image restoration. Multiscale Modeling & Simulation, 4, 460–489. · Zbl 1090.94003 · doi:10.1137/040605412 |
| [62] | Passty, G. B. (1979). Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications, 72, 383–390. · Zbl 0428.47039 · doi:10.1016/0022-247X(79)90234-8 |
| [63] | Powell, M. J. D. (1969). A method for nonlinear constraints in minimization problems. London: Academic Press. · Zbl 0194.47701 |
| [64] | Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press. · Zbl 0193.18401 |
| [65] | Rockafellar, R. T. (1976). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research, 1(2), 97–116. · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 |
| [66] | Ron, A., & Shen, Z. (1997). Affine systems in L 2(\(\mathbb{R}\) d ): The analysis of the analysis operator. Journal of Functional Analysis, 148, 408–447. · Zbl 0891.42018 · doi:10.1006/jfan.1996.3079 |
| [67] | Rudin, L. I., Osher, S., & Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Physica D, 60, 259–268. · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [68] | Schäfer, H. (1957). Über die Methode sukzessiver Approximationen. Jahresbericht der Deutschen Mathematiker-Vereinigung, 59, 131–140. · Zbl 0077.11002 |
| [69] | Setzer, S. (2009a). Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage. In A. Lie, M. Lysaker, K. Morken, & X. C. Tai (Eds.), Lecture notes in computer science : Vol. 5567. Second international conference on scale space methods and variational methods in computer vision, SSVM 2009, Proceedings (pp. 464–476). Voss, Norway, June 1–5, 2009. Berlin: Springer. |
| [70] | Setzer, S. (2009b). Splitting methods in image processing. PhD thesis, University of Mannheim. |
| [71] | Setzer, S., Steidl, G., & Teuber, T. (2010). Deblurring Poissonian images by split Bregman methods. Journal of Visual Communication and Image Representation, 21(3), 193–199. · doi:10.1016/j.jvcir.2009.10.006 |
| [72] | Steidl, G., & Teuber, T. (2010). Removing multiplicative noise by Douglas-Rachford splitting methods. International Journal of Mathematical Imaging and Vision, 36(2), 168–184. · Zbl 1287.94016 · doi:10.1007/s10851-009-0179-5 |
| [73] | Tai, X. C., & Wu, C. (2009). Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model. In A. Lie, M. Lysaker, K. Morken, & X. C. Tai (Eds.), Lecture notes in computer science : Vol. 5567. Second international conference on scale space methods and variational methods in computer vision, SSVM 2009, Proceedings (pp. 502–513). Voss, Norway, June 1–5, 2009. Berlin: Springer. · Zbl 1371.94362 |
| [74] | Tseng, P. (1991). Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM Journal on Control and Optimization, 29, 119–138. · Zbl 0737.90048 · doi:10.1137/0329006 |
| [75] | Wang, Y., Yang, J., Yin, W., & Zhang, Y. (2008). A new alternating minimization algorithm for total variation image reconstruction. SIAM Journal on Imaging Sciences, 1(3), 248–272. · Zbl 1187.68665 · doi:10.1137/080724265 |
| [76] | Weiss, P., Blanc-Féraud, L., & Aubert, G. (2009). Efficient schemes for total variation minimization under constraints in image processing. SIAM Journal on Scientific Computing, 31(3), 2047–2080. · Zbl 1191.94029 · doi:10.1137/070696143 |
| [77] | Welk, M., Steidl, G., & Weickert, J. (2008). Locally analytic schemes: A link between diffusion filtering and wavelet shrinkage. Applied and Computational Harmonic Analysis, 24, 195–224. · Zbl 1161.68831 · doi:10.1016/j.acha.2007.05.004 |
| [78] | Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008). Bregman iterative algorithms for 1-minimization with applications to compressed sensing. SIAM Journal on Imaging Sciences, 1(1), 143–168. · Zbl 1203.90153 · doi:10.1137/070703983 |
| [79] | Zhu, M. (2008). Fast numerical algorithms for total variation based image restoration. PhD thesis, University of California, Los Angeles, USA. |
| [80] | Zhu, M., & Chan, T. F. (2008). An efficient primal-dual hybrid gradient algorithm for total variation image restauration (Technical report). UCLA Computational and Applied Mathematics. |
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.
