nach oben

Journal of Scientific Computing

Erschienen in:

01.02.2013

Bregmanized Domain Decomposition for Image Restoration

verfasst von: Andreas Langer, Stanley Osher, Carola-Bibiane Schönlieb

Erschienen in: Journal of Scientific Computing | Ausgabe 2-3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Computational problems of large-scale data are gaining attention recently due to better hardware and hence, higher dimensionality of images and data sets acquired in applications. In the last couple of years non-smooth minimization problems such as total variation minimization became increasingly important for the solution of these tasks. While being favorable due to the improved enhancement of images compared to smooth imaging approaches, non-smooth minimization problems typically scale badly with the dimension of the data. Hence, for large imaging problems solved by total variation minimization domain decomposition algorithms have been proposed, aiming to split one large problem into N>1 smaller problems which can be solved on parallel CPUs. The N subproblems constitute constrained minimization problems, where the constraint enforces the support of the minimizer to be the respective subdomain.

In this paper we discuss a fast computational algorithm to solve domain decomposition for total variation minimization. In particular, we accelerate the computation of the subproblems by nested Bregman iterations. We propose a Bregmanized Operator Splitting–Split Bregman (BOS-SB) algorithm, which enforces the restriction onto the respective subdomain by a Bregman iteration that is subsequently solved by a Split Bregman strategy. The computational performance of this new approach is discussed for its application to image inpainting and image deblurring. It turns out that the proposed new solution technique is up to three times faster than the iterative algorithm currently used in domain decomposition methods for total variation minimization.

Vorheriger Artikel Negative-Order Norm Estimates for Nonlinear Hyperbolic Conservation Laws

Nächster Artikel Robust and Efficient Implicit Surface Reconstruction for Point Clouds Based on Convexified Image Segmentation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ambrosio, L., Fusco, N., Pallara, D.: Functions of Bounded Variation and Free Discontinuity Problems. Oxford Mathematical Monographs. Clarendon Press, Oxford (2000), p. xviii MATH

Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing. Partial Differential Equations and the Calculus of Variation. Springer, Berlin (2002)

Bregman, L.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex optimization. U.S.S.R. Comput. Math. Math. Phys. 7, 200–217 (1967) CrossRef

Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1–2), 89–97 (2004) MathSciNet

Chambolle, A., Darbon, J.: On total variation minimization and surface evolution using parametric maximum flows. Int. J. Comput. Vis. 84, 288–307 (2009) CrossRef

Chambolle, A., Lions, P.-L.: Image recovery via total variation minimization and related problems. Numer. Math. 76(2), 167–188 (1997) MathSciNetMATHCrossRef

Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20(6), 1964–1977 (1999) MathSciNetMATHCrossRef

Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005) MathSciNetMATHCrossRef

Daubechies, I., Defrise, M., DeMol, C.: An iterative thresholding algorithm for linear inverse problems. Commun. Pure Appl. Math. 57(11), 1413–1457 (2004) MathSciNetMATHCrossRef

10.

Daubechies, I., Teschke, G., Vese, L.: Iteratively solving linear inverse problems under general convex constraints. Inverse Probl. Theor. Imaging 1(1), 29–46 (2007) MathSciNetMATHCrossRef

11.

Darbon, J., Sigelle, M.: A fast and exact algorithm for total variation minimization. In: IbPRIA 2005. Lecture Notes in Computer Science, vol. 3522, pp. 717–765 (2005)

12.

Dobson, D., Vogel, C.R.: Convergence of an iterative method for total variation denoising. SIAM J. Numer. Anal. 34(5), 1779–1791 (1997) MathSciNetMATHCrossRef

13.

Engl, HW., Hanke, M., Neubauer, A.: Regularization of inverse problems. In: Mathematics and Its Applications (Dordrecht), vol. 375. Kluwer Academic Publishers, Dordrecht (1996)

14.

Evans, L.C., Gariepy, R.F.: Measure Theory and Fine Properties of Functions. CRC Press, Boca Raton (1992) MATH

15.

Fornasier, M.: Domain decomposition methods for linear inverse problems with sparsity constraints. Inverse Probl. 23(6), 2505–2526 (2007) MathSciNetMATHCrossRef

16.

Fornasier, M., Langer, A., Schönlieb, C.-B.: A convergent overlapping domain decomposition method for total variation minimization. Numer. Math. 116(4), 645–685 (2010) MathSciNetMATHCrossRef

17.

Fornasier, M., Schönlieb, C.-B.: Subspace correction methods for total variation and ℓ ₁-minimization. SIAM J. Numer. Anal. 47(4), 3397–3428 (2009) MathSciNetMATHCrossRef

18.

Frick, K., Scherzer, O.: Regularization of ill-posed linear equations by the non-stationary augmented Lagrangian method. J. Integral Equ. Appl. 22(2), 217–257 (2010) MathSciNetMATHCrossRef

19.

Goldstein, T., Osher, S.: The split Bregman method for ℓ ₁ regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009) MathSciNetMATHCrossRef

20.

Hintermüller, M., Stadler, G.: An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration. SIAM J. Sci. Comput. 28(1), 1–23 (2006) MathSciNetMATHCrossRef

21.

Ito, K., Kunisch, K.: Lagrange Multiplier Approach to Variational Problems and Applications. Advances in Design and Control, vol. 15. SIAM, Philadelphia (2008) MATHCrossRef

22.

Langer, A.: Convergence analysis of a non-overlapping domain decomposition algorithm for total variation minimization. J. Comput. Appl. Math. (2009, submitted)

23.

Langer, A.: Subspace correction and domain decomposition methods for total variation minimization. PhD Thesis, Johannes Kepler University Linz (2011)

24.

Loris, I.: On the performance of algorithms for the minimization of 1-penalized functionals. Inverse Probl. 25, 035007 (2009) MathSciNetCrossRef

25.

Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program., Ser. A 103, 127–152 (2005) MathSciNetMATHCrossRef

26.

Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4(2), 460–489 (2005) MathSciNetMATHCrossRef

27.

Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268 (1992) MATHCrossRef

28.

Schönlieb, C.-B.: Total variation minimization with an H ⁻¹ constraint. In: Singularities in Nonlinear Evolution Phenomena and Applications Proceedings, Scuola Normale Superiore Pisa. CRM Series, vol. 9, pp. 201–232 (2009)

29.

Setzer, S.: Split Bregman algorithm, Douglas–Rachford splitting and frame shrinkage. In: Tai, X.-C., et al. (eds.) Proceedings of the Second International Conference on Scale Space Methods and Proceedings of the 2nd International Conference on Scale Space and Variational Methods in Computer Vision. LNCS, vol. 5567, pp. 464–476. Springer, Berlin (2009) CrossRef

30.

Vese, L.: A study in the BV space of a denoising-deblurring variational problem. Appl. Math. Optim. 44, 131–161 (2001) MathSciNetMATHCrossRef

31.

Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for ℓ ₁-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008) MathSciNetMATHCrossRef

32.

Zhang, X., Burger, M., Bresson, X., Osher, S.: Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM J. Imaging Sci. 3(3), 253–276 (2010) MathSciNetMATHCrossRef

Titel: Bregmanized Domain Decomposition for Image Restoration
verfasst von: Andreas Langer
Stanley Osher
Carola-Bibiane Schönlieb
Publikationsdatum: 01.02.2013
Verlag: Springer US
Erschienen in: Journal of Scientific Computing / Ausgabe 2-3/2013
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-012-9603-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2-3/2013

Simulations of Supersonic Astrophysical Jets and Their Environments Using Level Set Methods

Preface

Negative-Order Norm Estimates for Nonlinear Hyperbolic Conservation Laws

Robust and Efficient Implicit Surface Reconstruction for Point Clouds Based on Convexified Image Segmentation

Error Forgetting of Bregman Iteration

Optimal Trajectories of Curvature Constrained Motion in the Hamilton–Jacobi Formulation