May  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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[4]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[9]

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

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[13]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[17]

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

[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. Google Scholar

[19]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[23]

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

[24]

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

[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. Google Scholar

[26]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[32]

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

[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. Google Scholar

show all references

References:
[1]

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

[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. Google Scholar

[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. Google Scholar

[4]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[9]

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

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[13]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[17]

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

[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. Google Scholar

[19]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[23]

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

[24]

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

[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. Google Scholar

[26]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[32]

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

[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. Google Scholar

[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]

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

[5]

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

[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, 2019, 15 (1) : 159-175. 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]

John R. Graef, Lingju Kong, Bo Yang. Positive solutions of a nonlinear higher order boundary-value problem. Conference Publications, 2009, 2009 (Special) : 276-285. doi: 10.3934/proc.2009.2009.276

[10]

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

[11]

Robert Jankowski, Barbara Łupińska, Magdalena Nockowska-Rosiak, Ewa Schmeidel. Monotonic solutions of a higher-order neutral difference system. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 253-261. doi: 10.3934/dcdsb.2018017

[12]

Alina Gleska, Małgorzata Migda. Qualitative properties of solutions of higher order difference equations with deviating arguments. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 239-252. doi: 10.3934/dcdsb.2018016

[13]

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

[14]

Aliang Xia, Jianfu Yang. Normalized solutions of higher-order Schrödinger equations. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 447-462. doi: 10.3934/dcds.2019018

[15]

Xuewei Cui, Mei Yu. Non-existence of positive solutions for a higher order fractional equation. Discrete & Continuous Dynamical Systems - A, 2019, 39 (3) : 1379-1387. doi: 10.3934/dcds.2019059

[16]

George J. Bautista, Ademir F. Pazoto. Decay of solutions for a dissipative higher-order Boussinesq system on a periodic domain. Communications on Pure & Applied Analysis, 2020, 19 (2) : 747-769. doi: 10.3934/cpaa.2020035

[17]

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

[18]

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

[19]

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

[20]

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

2018 Impact Factor: 1.469

Metrics

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

Other articles
by authors

[Back to Top]