ADI splitting schemes for a fourth-order nonlinear partial differential equation from image processing

Luca Calatroni; Bertram Düring; Carola-Bibiane Schönlieb

doi:10.3934/dcds.2014.34.931

Article Contents

2014, Volume 34, Issue 3: 931-957. Doi: 10.3934/dcds.2014.34.931

This issue Previous Article On Volterra integral operators with highly oscillatory kernels Next Article A Lie--Deprit perturbation algorithm for linear differential equations with periodic coefficients

ADI splitting schemes for a fourth-order nonlinear partial differential equation from image processing

1.
Cambridge Centre for Analysis, University of Cambridge, Wilberforce Road, CB3 0WA, Cambridge
2.
Department of Mathematics, University of Sussex, Pevensey II, BN1 9QH, Brighton
3.
Department of Applied Mathematics and Theoretical Physics (DAMTP), University of Cambridge, Wilberforce Road, CB3 0WA, Cambridge

Received: December 2012

Revised: May 2013

Published: March 2014

Abstract / Introduction Related Papers Cited by

Abstract

We present directional operator splitting schemes for the numerical solution of a fourth-order, nonlinear partial differential evolution equation which arises in image processing. This equation constitutes the $H^{-1}$-gradient flow of the total variation and represents a prototype of higher-order equations of similar type which are popular in imaging for denoising, deblurring and inpainting problems. The efficient numerical solution of this equation is very challenging due to the stiffness of most numerical schemes. We show that the combination of directional splitting schemes with implicit time-stepping provides a stable and computationally cheap numerical realisation of the equation.

Keywords:

Mathematics Subject Classification: 35K25, 35K55, 35G20, 65M06, 65M12.

Citation:

Related Papers

Cited by

References

[1]	L. Ambrosio, N. Fusco and D. Pallara, "Functions of Bounded Variation and Free Discontinuity Problems," Oxford Mathematical Monographs, Oxford, 2000.
[2]	J.-F. Aujol and A. Chambolle, Dual norms and image decomposition models, International Journal of Computer Vision, 63 (2005), 85-104.doi: 10.1007/s11263-005-4948-3.
[3]	J.-F. Aujol and G. Gilboa, Constrained and SNR-based solutions for TV-Hilbert space image denoising, Journal of Mathematical Imaging and Vision, 26 (2006), 217-237.doi: 10.1007/s10851-006-7801-6.
[4]	D. Barash, M. Israeli and R. Kimmel, An accurate operator splitting scheme for nonlinear diffusion filtering, in "Scale-Space and Morphology in Computer Vision" (ed. M. Kerckhove), Lecture Notes in Computer Science 2106 (2006), 281-289.
[5]	M. Benning, "Singular Regularization of inverse Problems," PhD thesis, University of Münster, 2011.
[6]	M. Benning, L. Calatroni, B. Düring and C.-B. Schönlieb, A primal-dual approach for a total variation Wasserstein flow, to appear in GSI 2013 LNCS proceedings, Springer, (2013).
[7]	M. Burger, M. Franek and C.-B. Schönlieb, Regularised Regression and Density estimation based on Optimal Transport, Appl. Math. Res. Express (AMRX), 2012, 209-253.
[8]	M. Burger, L. He and C.-B. Schönlieb, Cahn-Hilliard inpainting and a generalization for grayvalue images, SIAM J. Imaging Sci., 2 (2009), 1129-1167.doi: 10.1137/080728548.
[9]	T. F. Chan and J. J. Shen, "Image Processing and Analysis Variational, PDE, wavelet, and stochastic methods," SIAM, 2005.doi: 10.1137/1.9780898717877.
[10]	A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.
[11]	A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems, Numer. Math. 76 (1997), 167-188.doi: 10.1007/s002110050258.
[12]	T. F. Chan, S. H. Kang and J. Shen, Euler's elastica and curvature-based inpainting, SIAM J. Appl. Math., 63 (2002), 564-592.doi: 10.1137/S0036139901390088.
[13]	T. F. Chan and P. Mulet, On the convergence of the lagged diffusivity fixed point method in total variation image restoration, SIAM Journal on Numerical Analysis, 36 (1999), 354-367.doi: 10.1137/S0036142997327075.
[14]	T. F. Chan and J. Shen, Mathematical models for local non-texture inpaintings, SIAM J. Appl. Math., 62 (2001), 1019-1043.doi: 10.1137/S0036139900368844.
[15]	T. F. Chan and J. Shen, Non-texture inpainting by curvature driven diffusions (CDD), J. Visual Comm. Image, Rep., 12 (2001), 436-449.
[16]	T. F. Chan and J. Shen, Variational image inpainting, Comm. Pure Applied Math, 58 (2005), 579-619.doi: 10.1002/cpa.20075.
[17]	W. Chen and Z. Ditzian, Mixed and directional derivatives, Proceedings of the American Mathematical Society, 108 (1990), 177-185.doi: 10.1090/S0002-9939-1990-0994773-0.
[18]	S. D. Conte and R. T. James, An alternating direction method for solving the biharmonic equation, Math. Tables Aids Comput., 12 (1958), 198-205.doi: 10.2307/2002021.
[19]	S. Didas, J. Weickert and B. Burgeth, Stability and local feature enhancement of higher order nonlinear diffusion filtering, in "Pattern Recognition" (Eds. W. Kropatsch, R. Sablatnig and A. Hanbury), Lecture Notes in Computer Science, Springer, Berlin, 3663 (2005), 451-458.doi: 10.1007/11550518_56.
[20]	B. Düring and C.-B. Schönlieb, A high-contrast fourth-order PDE from imaging: Numerical solution by ADI splitting, in "Multi-scale and High-Contrast Partial Differential Equations" (eds. H. Ammari et al.), 93-103, Contemporary Mathematics 577, American Mathematical Society, Providence, (2012).doi: 10.1090/conm/577/11465.
[21]	B. Düring, D. Matthes and J.-P. Milisic, A gradient flow scheme for nonlinear fourth order equations, Discrete Contin. Dyn. Syst. Ser. B, 14 (2010), 935-959.doi: 10.3934/dcdsb.2010.14.935.
[22]	C. M. Elliott and D. A. French, Numerical studies of the Cahn-Hilliard equation for phase separation, IMA J. Appl. Math., 38 (1987), 97-128.doi: 10.1093/imamat/38.2.97.
[23]	C. M. Elliott and S. A. Smitheman, Analysis of the TV regularization and H-1 fidelity model for decomposing an image into cartoon plus texture, Commun. on Pure and Appl. Anal., 6 (2007), 917-936.doi: 10.3934/cpaa.2007.6.917.
[24]	C. M. Elliott and S. A. Smitheman, Numerical analysis of the TV regularization and $H^{-1}$ fidelity model for decomposing an image into cartoon plus texture, IMA Journal of Numerical Analysis, (2008), 1-39.doi: 10.1093/imanum/drn025.
[25]	S. Esedoglu and J.-H. Shen, Digital inpainting based on the Mumford-Shah-Euler image model, Eur. J. Appl. Math., 13 (2002), 353-370.doi: 10.1017/S0956792502004904.
[26]	T. Goldstein and S. Osher, The split Bregman method for $L^1$ regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343.doi: 10.1137/080725891.
[27]	L. Gosse and G. Toscani, Lagrangian numerical approximations to one-dimensional convolution-diffusion equations, SIAM J. Sci. Comput., 28 (2006), 1203-1227.doi: 10.1137/050628015.
[28]	K. J. in 't Hout and B. D. Welfert, Stability of ADI schemes applied to convection-diffusion equations with mixed derivative terms, Appl. Numer. Math., 57 (2007), 19-35.doi: 10.1016/j.apnum.2005.11.011.
[29]	K. J. in 't Hout and B. D. Welfert, Unconditional stability of second-order ADI schemes appliet to multi-dimensional diffusion equations with mixed derivative terms, Appl. Numer. Math., 59 (2009), 677-692.doi: 10.1016/j.apnum.2008.03.016.
[30]	P. J. van der Houwen and J. G. Verwer, One-step splitting methods for semi-discrete parabolic equations, Computing, 22 (1979), 291-309.doi: 10.1007/BF02265311.
[31]	W. Hundsdorfer and J. G. Verwer, "Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations," Berlin: Springer-Verlag, 2003.
[32]	W. Hundsdorfer, Accuracy and stability of splitting with Stabilizing Corrections, Appl. Numer. Math., 42 (2002), 213-233.doi: 10.1016/S0168-9274(01)00152-0.
[33]	L. Lieu and L. Vese, Image restoration and decompostion via bounded total variation and negative Hilbert-Sobolev spaces, Applied Mathematics & Optimization, 58 (2008), 167-193.doi: 10.1007/s00245-008-9047-8.
[34]	T. Lu, P. Neittaanmälki and X.-C. Tai, A parallel splitting up method and its application to Navier-Stokes equations, Appl. Math. Lett., 4 (1991), 25-29.doi: 10.1016/0893-9659(91)90161-N.
[35]	T. Lu, P. Neittaanmälki and X.-C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier-Stokes equations, RAIRO Modél. Math. Anal. Numér., 26 (1992), 673-708.
[36]	O. M. Lysaker and X.-C. Tai, Iterative image restoration combining total variation minimization and a second-order functional, International Journal of Computer Vision, 66 (2006), 5-18.doi: 10.1007/s11263-005-3219-7.
[37]	S. Masnou and J. Morel, Level Lines based Disocclusion, 5th IEEE Int'l Conf. on Image Processing, Chicago, IL, (1998), 259-263.doi: 10.1109/ICIP.1998.999016.
[38]	Y. Meyer, "Oscillating Patterns in Image Processing and Nonlinear Evolution Equations," Univ. Lecture Ser., 22, AMS, Providence, RI, 2002.
[39]	J. Müller, "Parallel Total Variation Minimization," Diploma Thesis, University of Münster, WWU, 2008.
[40]	D. Mumford and B. Gidas, Stochastic models for generic images, Quart. Appl. Math., 59 (2001), 85-111.
[41]	T. G. Myers, Thin films with high surface tension, SIAM Rev., 40 (1998), 441-462.doi: 10.1137/S003614459529284X.
[42]	A. Novick-Cohen and L. A. Segel, Nonlinear aspects of the Cahn-Hilliard equation, Phys. D, 10 (1984), 277-298.doi: 10.1016/0167-2789(84)90180-5.
[43]	A. Oron, S. H. Davis and S. G. Bankoff, Long-scale evolution of thin liquid films, Phys. Rev. Let., 85 (2000), 2108-2111.doi: 10.1103/RevModPhys.69.931.
[44]	S. Osher, A. Sole and L. Vese, Image decomposition and restoration using total variation minimization and the $H^{-1}$ norm, Multiscale Modelling and Simulation: A SIAM Interdisciplinary Journal, 1 (2003), 349-370.doi: 10.1137/S1540345902416247.
[45]	D. W. Peaceman and H. H. Rachford Jr., The numerical solution of parabolic and elliptic differential equations, J. Soc. Industr. Appl. Math, 3 (1955), 28-41.doi: 10.1137/0103003.
[46]	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.
[47]	L. Rudin and S. Osher, Total variation based image restoration with free local constraints, Proc. 1st IEEE ICIP, 1 (1994), 31-35.doi: 10.1109/ICIP.1994.413269.
[48]	C.-B. Schönlieb and A. Bertozzi, Unconditionally stable schemes for higher order inpainting, Commun. Math. Sci., 9 (2011), 413-457.
[49]	C.-B. Schönlieb, A. Bertozzi, M. Burger and L. He, Image inpainting using a fourth-order total variation flow, Proc. Int. Conf. SampTA09, Marseilles, (2009).
[50]	C.-B. Schönlieb, Total variation minimization with an $H^{-1}$ constraint, CRM Series 9, Singularities in Nonlinear Evolution Phenomena and Applications Proceedings, Scuola Normale Superiore Pisa, (2009), 201-232.
[51]	P. Smereka, Semi-implicit level set methods for curvature and surface diffusion motion, Special Issue in Honor of the Sixtieth Birthday of Stanley Osher, J. Sci. Comput., 19 (2003), 439-456.doi: 10.1023/A:1025324613450.
[52]	L. Vese, A study in the BV space of a denoising-deblurring variational problem, Appl. Math. Optim., 44 (2001), 131-161.doi: 10.1007/s00245-001-0017-7.
[53]	L. Vese and S. Osher, Image denoising and decomposition with total variation minimization and oscillatory functions, J. Math. Imaging Vision, 20 (2004), 7-18.doi: 10.1023/B:JMIV.0000011316.54027.6a.
[54]	J. Weickert, B. M. ter Haar Romeny and M. A. Viergever, Efficient and reliable schemes for nonlinear diffusion filtering, IEEE Transactions on Image Processing, 7 (1998), 398-410.doi: 10.1109/83.661190.
[55]	T. P. Witelski and M. Bowen, ADI schemes for higher-order nonlinear diffusion equations, Appl. Numer. Math., 45 (2003), 331-351.doi: 10.1016/S0168-9274(02)00194-0.