2015, 9(2): 511-550. doi: 10.3934/ipi.2015.9.511

A study of the one dimensional total generalised variation regularisation problem

1. 

Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, CB3 0WA, Cambridge, United Kingdom

2. 

Institute for Mathematics and Scientific Computing, University of Graz, Heinrichstrasse 36, A-8010, Graz, Austria

Received  October 2013 Revised  October 2014 Published  March 2015

In this paper we study the one dimensional second order total generalised variation regularisation (TGV) problem with $L^{2}$ data fitting term. We examine the properties of this model and we calculate exact solutions using simple piecewise affine functions as data terms. We investigate how these solutions behave with respect to the TGV parameters and we verify our results using numerical experiments.
Citation: Konstantinos Papafitsoros, Kristian Bredies. A study of the one dimensional total generalised variation regularisation problem. Inverse Problems & Imaging, 2015, 9 (2) : 511-550. doi: 10.3934/ipi.2015.9.511
References:
[1]

L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems,, Oxford University Press, (2000).

[2]

H. Attouch and H. Brezis, Duality for the sum of convex functions in general Banach spaces,, North-Holland Mathematical Library, 34 (1986), 125. doi: 10.1016/S0924-6509(09)70252-1.

[3]

P. Belhumeur, A binocular stereo algorithm for reconstructing sloping, creased, and broken surfaces in the presence of half-occlusion,, in Proceedings of the Fourth International Conference on Computer Vision, (1993), 431. doi: 10.1109/ICCV.1993.378184.

[4]

M. Benning, Singular Regularization of Inverse Problems, Bregman Distances and Applications to Variational Frameworks with Singular Regularization Energies,, Ph.D thesis, (2011).

[5]

M. Benning, C. Brune, M. Burger and J. Müller, Higher-order TV methods - Enhancement via Bregman iteration,, Journal of Scientific Computing, 54 (2013), 269. doi: 10.1007/s10915-012-9650-3.

[6]

M. Benning and M. Burger, Ground states and singular vectors of convex variational regularization methods,, Methods and Applications of Analysis, 20 (2013), 295. doi: 10.4310/MAA.2013.v20.n4.a1.

[7]

K. Bredies, Recovering piecewise smooth multichannel images by minimization of convex functionals with total generalized variation penalty,, in Efficient Algorithms for Global Optimization Methods in Computer Vision, (2014), 44. doi: 10.1007/978-3-642-54774-4_3.

[8]

K. Bredies and M. Holler, Artifact-free decompression and zooming of JPEG compressed images with total generalized variation,, in Computer Vision, (2013), 242. doi: 10.1007/978-3-642-38241-3_16.

[9]

K. Bredies, K. Kunisch and T. Pock, Total generalized variation,, SIAM Journal on Imaging Sciences, 3 (2010), 492. doi: 10.1137/090769521.

[10]

K. Bredies, K. Kunisch and T. Valkonen, Properties of $L^1$-$TGV^{2}$: The one-dimensional case,, Journal of Mathematical Analysis and Applications, 398 (2013), 438. doi: 10.1016/j.jmaa.2012.08.053.

[11]

K. Bredies and T. Valkonen, Inverse problems with second-order total generalized variation constraints,, in Proceedings of SampTA 2011 - 9th International Conference on Sampling Theory and Applications, (2011).

[12]

V. Caselles, A. Chambolle and M. Novaga, The discontinuity set of solutions of the {TV} denoising problem and some extensions,, Multiscale Modeling & Simulation, 6 (2007), 879. doi: 10.1137/070683003.

[13]

A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems,, Numerische Mathematik, 76 (1997), 167. doi: 10.1007/s002110050258.

[14]

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

[15]

T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation,, SIAM Journal on Applied Mathematics, 65 (2005), 1817. doi: 10.1137/040604297.

[16]

G. Dal Maso, I. Fonseca, G. Leoni and M. Morini, A higher order model for image restoration: The one dimensional case,, SIAM Journal on Mathematical Analysis, 40 (2009), 2351. doi: 10.1137/070697823.

[17]

F. Demengel, Fonctions à Hessien borné,, Annales de l'Institut Fourier, 34 (1984), 155. doi: 10.5802/aif.969.

[18]

V. Duval, J. Aujol and Y. Gousseau, The TVL1 model: A geometric point of view,, SIAM Journal on Multiscale Modeling and Simulation, 8 (2009), 154. doi: 10.1137/090757083.

[19]

I. Ekeland and R. Temam, Convex Analysis and Variational Problems,, Vol. 1, (1976).

[20]

M. Grasmair, The equivalence of the taut string algorithm and BV-regularization,, Journal of Mathematical Imaging and Vision, 27 (2007), 59. doi: 10.1007/s10851-006-9796-4.

[21]

W. Hinterberger, M. Hintermüller, K. Kunisch, M. Von Oehsen and O. Scherzer, Tube methods for BV regularization,, Journal of Mathematical Imaging and Vision, 19 (2003), 219. doi: 10.1023/A:1026276804745.

[22]

F. Knoll, K. Bredies, T. Pock and R. Stollberger, Second order total generalized variation (TGV) for MRI,, Magnetic Resonance in Medicine, 65 (2011), 480. doi: 10.1002/mrm.22595.

[23]

Y. Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations: The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures,, Vol. 22, (2001).

[24]

J. Müller, Advanced Image Reconstruction and Denoising - Bregmanized (Higher Order) Total Variation and Application in PET,, Ph.D thesis, (2013).

[25]

M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers,, SIAM Journal on Numerical Analysis, 40 (2002), 965. doi: 10.1137/S0036142901389165.

[26]

K. Papafitsoros, Novel Higher Order Regularisation Methods for Image Reconstruction,, Ph.D thesis, (2014).

[27]

C. Pöschl and O. Scherzer, Exact solutions of one-dimensional total generalized variation,, Communications in Mathematical Sciences, 13 (2015), 171. doi: 10.4310/CMS.2015.v13.n1.a9.

[28]

C. Pöschl and O. Scherzer, Characterization of minimizers of convex regularization functionals,, Contemporary mathematics, 451 (2008), 219. doi: 10.1090/conm/451/08784.

[29]

W. Ring, Structural properties of solutions to total variation regularization problems,, ESAIM: Mathematical Modelling and Numerical Analysis, 34 (2000), 799. doi: 10.1051/m2an:2000104.

[30]

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

[31]

D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization,, Inverse Problems, 19 (2003). doi: 10.1088/0266-5611/19/6/059.

[32]

R. Temam, Mathematical Problems in Plasticity,, Vol. 12, (1983).

[33]

T. Valkonen, K. Bredies and F. Knoll, Total generalized variation in diffusion tensor imaging,, SIAM Journal on Imaging Sciences, 6 (2013), 487. doi: 10.1137/120867172.

show all references

References:
[1]

L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems,, Oxford University Press, (2000).

[2]

H. Attouch and H. Brezis, Duality for the sum of convex functions in general Banach spaces,, North-Holland Mathematical Library, 34 (1986), 125. doi: 10.1016/S0924-6509(09)70252-1.

[3]

P. Belhumeur, A binocular stereo algorithm for reconstructing sloping, creased, and broken surfaces in the presence of half-occlusion,, in Proceedings of the Fourth International Conference on Computer Vision, (1993), 431. doi: 10.1109/ICCV.1993.378184.

[4]

M. Benning, Singular Regularization of Inverse Problems, Bregman Distances and Applications to Variational Frameworks with Singular Regularization Energies,, Ph.D thesis, (2011).

[5]

M. Benning, C. Brune, M. Burger and J. Müller, Higher-order TV methods - Enhancement via Bregman iteration,, Journal of Scientific Computing, 54 (2013), 269. doi: 10.1007/s10915-012-9650-3.

[6]

M. Benning and M. Burger, Ground states and singular vectors of convex variational regularization methods,, Methods and Applications of Analysis, 20 (2013), 295. doi: 10.4310/MAA.2013.v20.n4.a1.

[7]

K. Bredies, Recovering piecewise smooth multichannel images by minimization of convex functionals with total generalized variation penalty,, in Efficient Algorithms for Global Optimization Methods in Computer Vision, (2014), 44. doi: 10.1007/978-3-642-54774-4_3.

[8]

K. Bredies and M. Holler, Artifact-free decompression and zooming of JPEG compressed images with total generalized variation,, in Computer Vision, (2013), 242. doi: 10.1007/978-3-642-38241-3_16.

[9]

K. Bredies, K. Kunisch and T. Pock, Total generalized variation,, SIAM Journal on Imaging Sciences, 3 (2010), 492. doi: 10.1137/090769521.

[10]

K. Bredies, K. Kunisch and T. Valkonen, Properties of $L^1$-$TGV^{2}$: The one-dimensional case,, Journal of Mathematical Analysis and Applications, 398 (2013), 438. doi: 10.1016/j.jmaa.2012.08.053.

[11]

K. Bredies and T. Valkonen, Inverse problems with second-order total generalized variation constraints,, in Proceedings of SampTA 2011 - 9th International Conference on Sampling Theory and Applications, (2011).

[12]

V. Caselles, A. Chambolle and M. Novaga, The discontinuity set of solutions of the {TV} denoising problem and some extensions,, Multiscale Modeling & Simulation, 6 (2007), 879. doi: 10.1137/070683003.

[13]

A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems,, Numerische Mathematik, 76 (1997), 167. doi: 10.1007/s002110050258.

[14]

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

[15]

T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation,, SIAM Journal on Applied Mathematics, 65 (2005), 1817. doi: 10.1137/040604297.

[16]

G. Dal Maso, I. Fonseca, G. Leoni and M. Morini, A higher order model for image restoration: The one dimensional case,, SIAM Journal on Mathematical Analysis, 40 (2009), 2351. doi: 10.1137/070697823.

[17]

F. Demengel, Fonctions à Hessien borné,, Annales de l'Institut Fourier, 34 (1984), 155. doi: 10.5802/aif.969.

[18]

V. Duval, J. Aujol and Y. Gousseau, The TVL1 model: A geometric point of view,, SIAM Journal on Multiscale Modeling and Simulation, 8 (2009), 154. doi: 10.1137/090757083.

[19]

I. Ekeland and R. Temam, Convex Analysis and Variational Problems,, Vol. 1, (1976).

[20]

M. Grasmair, The equivalence of the taut string algorithm and BV-regularization,, Journal of Mathematical Imaging and Vision, 27 (2007), 59. doi: 10.1007/s10851-006-9796-4.

[21]

W. Hinterberger, M. Hintermüller, K. Kunisch, M. Von Oehsen and O. Scherzer, Tube methods for BV regularization,, Journal of Mathematical Imaging and Vision, 19 (2003), 219. doi: 10.1023/A:1026276804745.

[22]

F. Knoll, K. Bredies, T. Pock and R. Stollberger, Second order total generalized variation (TGV) for MRI,, Magnetic Resonance in Medicine, 65 (2011), 480. doi: 10.1002/mrm.22595.

[23]

Y. Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations: The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures,, Vol. 22, (2001).

[24]

J. Müller, Advanced Image Reconstruction and Denoising - Bregmanized (Higher Order) Total Variation and Application in PET,, Ph.D thesis, (2013).

[25]

M. Nikolova, Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers,, SIAM Journal on Numerical Analysis, 40 (2002), 965. doi: 10.1137/S0036142901389165.

[26]

K. Papafitsoros, Novel Higher Order Regularisation Methods for Image Reconstruction,, Ph.D thesis, (2014).

[27]

C. Pöschl and O. Scherzer, Exact solutions of one-dimensional total generalized variation,, Communications in Mathematical Sciences, 13 (2015), 171. doi: 10.4310/CMS.2015.v13.n1.a9.

[28]

C. Pöschl and O. Scherzer, Characterization of minimizers of convex regularization functionals,, Contemporary mathematics, 451 (2008), 219. doi: 10.1090/conm/451/08784.

[29]

W. Ring, Structural properties of solutions to total variation regularization problems,, ESAIM: Mathematical Modelling and Numerical Analysis, 34 (2000), 799. doi: 10.1051/m2an:2000104.

[30]

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

[31]

D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization,, Inverse Problems, 19 (2003). doi: 10.1088/0266-5611/19/6/059.

[32]

R. Temam, Mathematical Problems in Plasticity,, Vol. 12, (1983).

[33]

T. Valkonen, K. Bredies and F. Knoll, Total generalized variation in diffusion tensor imaging,, SIAM Journal on Imaging Sciences, 6 (2013), 487. doi: 10.1137/120867172.

[1]

Denis R. Akhmetov, Renato Spigler. $L^1$-estimates for the higher-order derivatives of solutions to parabolic equations subject to initial values of bounded total variation. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1051-1074. doi: 10.3934/cpaa.2007.6.1051

[2]

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

[3]

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

[4]

Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591

[5]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022

[6]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018037

[7]

Raymond H. Chan, Haixia Liang, Suhua Wei, Mila Nikolova, Xue-Cheng Tai. High-order total variation regularization approach for axially symmetric object tomography from a single radiograph. Inverse Problems & Imaging, 2015, 9 (1) : 55-77. doi: 10.3934/ipi.2015.9.55

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Florian Krügel. Some properties of minimizers of a variational problem involving the total variation functional. Communications on Pure & Applied Analysis, 2015, 14 (1) : 341-360. doi: 10.3934/cpaa.2015.14.341

[14]

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

[15]

Adriana González, Laurent Jacques, Christophe De Vleeschouwer, Philippe Antoine. Compressive optical deflectometric tomography: A constrained total-variation minimization approach. Inverse Problems & Imaging, 2014, 8 (2) : 421-457. doi: 10.3934/ipi.2014.8.421

[16]

Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems & Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565

[17]

Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167

[18]

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

[19]

John Baxley, Mary E. Cunningham, M. Kathryn McKinnon. Higher order boundary value problems with multiple solutions: examples and techniques. Conference Publications, 2005, 2005 (Special) : 84-90. doi: 10.3934/proc.2005.2005.84

[20]

Hiroshi Takeda. Global existence of solutions for higher order nonlinear damped wave equations. Conference Publications, 2011, 2011 (Special) : 1358-1367. doi: 10.3934/proc.2011.2011.1358

2016 Impact Factor: 1.094

Metrics

  • PDF downloads (1)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]