American Institute of Mathematical Sciences

Advanced
December  2017, 10(6): 1207-1232. doi: 10.3934/dcdss.2017066

Iterative finite element solution of a constrained total variation regularized model problem

Sören Bartels , and  Marijo Milicevic

Department of Applied Mathematics, Mathematical Institute, University of Freiburg, Hermann-Herder-Str. 9,79104 Freiburg i. Br., Germany

* Corresponding author: Sören Bartels

Dedicated to Professor T. Roubíčcek on the occasion of his 60th birthday.

Received  May 2016 Revised  November 2016 Published  June 2017

The discretization of a bilaterally constrained total variation minimization problem with conforming low order finite elements is analyzed and three iterative schemes are proposed which differ in the treatment of the non-differentiable terms. Unconditional stability and convergence of the algorithms is addressed, an application to piecewise constant image segmentation is presented and numerical experiments are shown.

Keywords: Total variation, bilateral constraint, finite elements, iterative schemes, image processing.
Mathematics Subject Classification: Primary: 65K15, 49M27; Secondary: 94A08.
Citation: Sören Bartels, Marijo Milicevic. Iterative finite element solution of a constrained total variation regularized model problem. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1207-1232. doi: 10.3934/dcdss.2017066
References:
[1]

H. Attouch, G. Buttazzo and G. Michaille, Variational Analysis in Sobolev and BV Spaces, MPS/SIAM Series on Optimization (vol. 6), Philadelphia, 2006.  Google Scholar

[2]

S. Bartels, Numerical Methods for Nonlinear Partial Differential Equations, Springer, Heidelberg, 2015. doi: 10.1007/978-3-319-13797-1.  Google Scholar

[3]

S. Bartels and M. Milicevic, Stability and experimental comparison of prototypical iterative schemes for total variation regularized problems, Computational Methods in Applied Mathematics, 16 (2016), 361-388.  doi: 10.1515/cmam-2016-0014.  Google Scholar

[4]

S. Bartels, R. H. Nochetto and A. J. Salgado, Discrete total variation flows without regularization, SIAM J. Numer. Anal., 52 (2014), 363-385.  doi: 10.1137/120901544.  Google Scholar

[5]

S. Bartels, R. H. Nochetto and A. J. Salgado, A total variation diminishing interpolation operator and applications, Mathematics of Computation, 84 (2015), 2569-2587.  doi: 10.1090/mcom/2942.  Google Scholar

[6]

A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Transactions on Image Processing, 18 (2009), 2419-2434.  doi: 10.1109/TIP.2009.2028250.  Google Scholar

[7]

B. Berkels, An unconstrained multiphase thresholding approach for image segmentation, in Scale Space and Variational Methods in Computer Vision (eds. X.-C. Tai, K. Mørken, M. Lysaker, K.-A. Lie), 5567 (2009), 26–37. doi: 10.1007/978-3-642-02256-2_3.  Google Scholar

[8]

B. Berkels, A. Effland and M. Rumpf,A posteriori error control for the binary Mumford-Shah model, Math. Comp., 86 (2017), 1769-1791, arXiv: 1505.05284 doi: 10.1090/mcom/3138.  Google Scholar

[9]

S. C. Brenner and L. R. Scott, The Mathematical Theory of Finite Element Methods, 3rd edition, Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. doi: 10.1007/978-0-387-75934-0.  Google Scholar

[10]

E. Casas, K. Kunisch and C. Pola, Regularization by functions of bounded variation and application to image enhancement, Appl. Math. Optim., 40 (1999), 229-257.  doi: 10.1007/s002459900124.  Google Scholar

[11]

A. Chambolle, An algorithm for total variation minmization and applications, J. Math. Imaging Vision, 20 (2004), 89-97.  doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[12]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), 120-145.  doi: 10.1007/s10851-010-0251-1.  Google Scholar

[13]

T. F. Chan, S. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Appl. Math., 66 (2006), 1632-1648.  doi: 10.1137/040615286.  Google Scholar

[14]

R. H. Chan, M. Tao and X. Yuan, Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imaging Sci., 6 (2013), 680-697.  doi: 10.1137/110860185.  Google Scholar

[15]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods, 1st edition, North-Holland Publishing Co. , Amsterdam, 1983.  Google Scholar

[16]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer, New York, 1984. doi: 10.1007/978-3-662-12613-4.  Google Scholar

[17]

M. Hintermüller, C. N. Rautenberg and J. Hahn, Functional-analytic and numerical issues in splitting methods for total variation-based image reconstruction, Inverse Problems, 30 (2014), 055014, 34pp. doi: 10.1088/0266-5611/30/5/055014.  Google Scholar

[18]

R. T. Rockafellar, Convex Analysis, Princeton University Press, New Jersey, 1970.  Google Scholar

[19]

T. Roubiček and J. Valdman, Perfect plasticity with damage and healing at small strains, its modelling, analysis, and computer implementation, SIAM J. Appl. Math., 76 (2016), 314-340.  doi: 10.1137/15M1019647.  Google Scholar

[20]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[21]

M. Thomas, Quasistatic damage evolution with spatial BV-regularization, Discrete Contin. Dyn. Syst. Ser. S, 6 (2013), 235-255.  doi: 10.3934/dcdss.2013.6.235.  Google Scholar

[22]

C. Wu and X.-C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and higher order models, SIAM J. Imaging Sci., 3 (2010), 300-339.  doi: 10.1137/090767558.  Google Scholar

[23]

M. Zhu, Fast Numerical Algorithms for Total Variation Based Image Restoration, Ph. D thesis, University of California in Los Angeles, 2008.  Google Scholar

show all references

References:
[1]

H. Attouch, G. Buttazzo and G. Michaille, Variational Analysis in Sobolev and BV Spaces, MPS/SIAM Series on Optimization (vol. 6), Philadelphia, 2006.  Google Scholar

[2]

S. Bartels, Numerical Methods for Nonlinear Partial Differential Equations, Springer, Heidelberg, 2015. doi: 10.1007/978-3-319-13797-1.  Google Scholar

[3]

S. Bartels and M. Milicevic, Stability and experimental comparison of prototypical iterative schemes for total variation regularized problems, Computational Methods in Applied Mathematics, 16 (2016), 361-388.  doi: 10.1515/cmam-2016-0014.  Google Scholar

[4]

S. Bartels, R. H. Nochetto and A. J. Salgado, Discrete total variation flows without regularization, SIAM J. Numer. Anal., 52 (2014), 363-385.  doi: 10.1137/120901544.  Google Scholar

[5]

S. Bartels, R. H. Nochetto and A. J. Salgado, A total variation diminishing interpolation operator and applications, Mathematics of Computation, 84 (2015), 2569-2587.  doi: 10.1090/mcom/2942.  Google Scholar

[6]

A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Transactions on Image Processing, 18 (2009), 2419-2434.  doi: 10.1109/TIP.2009.2028250.  Google Scholar

[7]

B. Berkels, An unconstrained multiphase thresholding approach for image segmentation, in Scale Space and Variational Methods in Computer Vision (eds. X.-C. Tai, K. Mørken, M. Lysaker, K.-A. Lie), 5567 (2009), 26–37. doi: 10.1007/978-3-642-02256-2_3.  Google Scholar

[8]

B. Berkels, A. Effland and M. Rumpf,A posteriori error control for the binary Mumford-Shah model, Math. Comp., 86 (2017), 1769-1791, arXiv: 1505.05284 doi: 10.1090/mcom/3138.  Google Scholar

[9]

S. C. Brenner and L. R. Scott, The Mathematical Theory of Finite Element Methods, 3rd edition, Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. doi: 10.1007/978-0-387-75934-0.  Google Scholar

[10]

E. Casas, K. Kunisch and C. Pola, Regularization by functions of bounded variation and application to image enhancement, Appl. Math. Optim., 40 (1999), 229-257.  doi: 10.1007/s002459900124.  Google Scholar

[11]

A. Chambolle, An algorithm for total variation minmization and applications, J. Math. Imaging Vision, 20 (2004), 89-97.  doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[12]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), 120-145.  doi: 10.1007/s10851-010-0251-1.  Google Scholar

[13]

T. F. Chan, S. Esedoglu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Appl. Math., 66 (2006), 1632-1648.  doi: 10.1137/040615286.  Google Scholar

[14]

R. H. Chan, M. Tao and X. Yuan, Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imaging Sci., 6 (2013), 680-697.  doi: 10.1137/110860185.  Google Scholar

[15]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods, 1st edition, North-Holland Publishing Co. , Amsterdam, 1983.  Google Scholar

[16]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer, New York, 1984. doi: 10.1007/978-3-662-12613-4.  Google Scholar

[17]

M. Hintermüller, C. N. Rautenberg and J. Hahn, Functional-analytic and numerical issues in splitting methods for total variation-based image reconstruction, Inverse Problems, 30 (2014), 055014, 34pp. doi: 10.1088/0266-5611/30/5/055014.  Google Scholar

[18]

R. T. Rockafellar, Convex Analysis, Princeton University Press, New Jersey, 1970.  Google Scholar

[19]

T. Roubiček and J. Valdman, Perfect plasticity with damage and healing at small strains, its modelling, analysis, and computer implementation, SIAM J. Appl. Math., 76 (2016), 314-340.  doi: 10.1137/15M1019647.  Google Scholar

[20]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[21]

M. Thomas, Quasistatic damage evolution with spatial BV-regularization, Discrete Contin. Dyn. Syst. Ser. S, 6 (2013), 235-255.  doi: 10.3934/dcdss.2013.6.235.  Google Scholar

[22]

C. Wu and X.-C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and higher order models, SIAM J. Imaging Sci., 3 (2010), 300-339.  doi: 10.1137/090767558.  Google Scholar

[23]

M. Zhu, Fast Numerical Algorithms for Total Variation Based Image Restoration, Ph. D thesis, University of California in Los Angeles, 2008.  Google Scholar

Figure 1.  $L^2$-error between approximate minimizer $\tilde{u}_h$ of $E$ (generated by the split-split method) and iterates $u_h^j$, $s_h^j$ of the Heron-penalty method, $h=\sqrt{2}2^{-6}$, $\varepsilon=h$, for Example 1. Note that the iterates $u_h^j$ serve as good approximations of $\tilde{u}_h$ when $\delta=h/\alpha$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  $L^2$-error between approximate minimizer $\tilde{u}_h$ of $E$ (generated by the split-split method) and iterates $u_h^j$, $s_h^j$ of the Heron-penalty method, $h=\sqrt{2}2^{-6}$, $\varepsilon=h$, for Example 2. Again, the iterates $u_h^j$ approximate $\tilde{u}_h$ properly when $\delta=h/\alpha$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Original image and outputs of Algorithm 5 using the split-split, Heron-penalty and Heron-split method in step (2), respectively (horizontal white lines are due to image conversion)
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Iteration numbers with (5), (6), (7) for Example 1 and $\sigma_1=h^{-3/2}$ for the split-split method and $\tau=1$ for the Heron-penalty and the Heron-split method
Split-splitHeron-penaltyHeron-split
$\sigma_2$$\delta$$\sigma$
$1$$\alpha$$1/h$$h/\alpha$$h$$1$$\alpha$$1/h$
$\sqrt{2}/2^5$$344$$39$$37$$89$$42$$892$$52$$57$
$\sqrt{2}/2^6$$289$$79$$79$$143$$55$$576$$77$$77$
$\sqrt{2}/2^7$$283$$77$$78$$211$$69$$473$$94$$94$
$\sqrt{2}/2^8$$287$$115$$120$$426$$101$$373$$148$$151$
Table Options

Download as excel

Split-splitHeron-penaltyHeron-split
$\sigma_2$$\delta$$\sigma$
$1$$\alpha$$1/h$$h/\alpha$$h$$1$$\alpha$$1/h$
$\sqrt{2}/2^5$$344$$39$$37$$89$$42$$892$$52$$57$
$\sqrt{2}/2^6$$289$$79$$79$$143$$55$$576$$77$$77$
$\sqrt{2}/2^7$$283$$77$$78$$211$$69$$473$$94$$94$
$\sqrt{2}/2^8$$287$$115$$120$$426$$101$$373$$148$$151$
Table 2.  Iteration numbers with (5), (6), (7) for Example 2 and $\sigma_1=h^{-3/2}$ for the split-split method and $\tau=1$ for the Heron-penalty and the Heron-split method
Split-splitHeron-penaltyHeron-split
$\sigma_2$$\delta$$\sigma$
$1$$\alpha$$1/h$$h/\alpha$$h$$1$$\alpha$$1/h$
$\sqrt{2}/2^5$$2745$$10$$124$$74$$24$$4592$$15$$189$
$\sqrt{2}/2^6$$2808$$15$$65$$156$$27$$3586$$21$$72$
$\sqrt{2}/2^7$$2847$$23$$35$$298$$35$$3133$$25$$42$
$\sqrt{2}/2^8$$-$$29$$30$$572$$43$$-$$33$$37$
Table Options

Download as excel

Split-splitHeron-penaltyHeron-split
$\sigma_2$$\delta$$\sigma$
$1$$\alpha$$1/h$$h/\alpha$$h$$1$$\alpha$$1/h$
$\sqrt{2}/2^5$$2745$$10$$124$$74$$24$$4592$$15$$189$
$\sqrt{2}/2^6$$2808$$15$$65$$156$$27$$3586$$21$$72$
$\sqrt{2}/2^7$$2847$$23$$35$$298$$35$$3133$$25$$42$
$\sqrt{2}/2^8$$-$$29$$30$$572$$43$$-$$33$$37$
[1]

Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems & Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008
[2]

Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems & Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455
[3]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547
[4]

Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems & Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031
[5]

Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems & Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064
[6]

Luca Calatroni, Bertram Düring, Carola-Bibiane Schönlieb. ADI splitting schemes for a fourth-order nonlinear partial differential equation from image processing. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 931-957. doi: 10.3934/dcds.2014.34.931
[7]

Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022
[8]

Fredrik Hellman, Patrick Henning, Axel Målqvist. Multiscale mixed finite elements. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : 1269-1298. doi: 10.3934/dcdss.2016051
[9]

Ke Chen, Yiqiu Dong, Michael Hintermüller. A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration. Inverse Problems & Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323
[10]

Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191
[11]

Jianhong (Jackie) Shen, Sung Ha Kang. Quantum TV and applications in image processing. Inverse Problems & Imaging, 2007, 1 (3) : 557-575. doi: 10.3934/ipi.2007.1.557
[12]

Rinaldo M. Colombo, Francesca Monti. Solutions with large total variation to nonconservative hyperbolic systems. Communications on Pure & Applied Analysis, 2010, 9 (1) : 47-60. doi: 10.3934/cpaa.2010.9.47
[13]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017
[14]

Yan Jin, Jürgen Jost, Guofang Wang. A new nonlocal variational setting for image processing. Inverse Problems & Imaging, 2015, 9 (2) : 415-430. doi: 10.3934/ipi.2015.9.415
[15]

Peter Monk, Jiguang Sun. Inverse scattering using finite elements and gap reciprocity. Inverse Problems & Imaging, 2007, 1 (4) : 643-660. doi: 10.3934/ipi.2007.1.643
[16]

Claire david@lmm.jussieu.fr David, Pierre Sagaut. Theoretical optimization of finite difference schemes. Conference Publications, 2007, 2007 (Special) : 286-293. doi: 10.3934/proc.2007.2007.286
[17]

Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems & Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273
[18]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507
[19]

Lu Liu, Zhi-Feng Pang, Yuping Duan. Retinex based on exponent-type total variation scheme. Inverse Problems & Imaging, 2018, 12 (5) : 1199-1217. doi: 10.3934/ipi.2018050
[20]

Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237

2018 Impact Factor: 0.545

Tools

Metrics

  • PDF downloads (29)
  • HTML views (80)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences