Theoretical foundation of the weighted Laplace inpainting problem. (English) Zbl 07088741

Summary: Laplace interpolation is a popular approach in image inpainting using partial differential equations. The classic approach considers the Laplace equation with mixed boundary conditions. Recently a more general formulation has been proposed, where the differential operator consists of a point-wise convex combination of the Laplacian and the known image data. We provide the first detailed analysis on existence and uniqueness of solutions for the arising mixed boundary value problem. Our approach considers the corresponding weak formulation and aims at using the Theorem of Lax-Milgram to assert the existence of a solution. To this end we have to resort to weighted Sobolev spaces. Our analysis shows that solutions do not exist unconditionally. The weights need some regularity and must fulfil certain growth conditions. The results from this work complement findings which were previously only available for a discrete setup.


35J15 Second-order elliptic equations
35J70 Degenerate elliptic equations
46E35 Sobolev spaces and other spaces of “smooth” functions, embedding theorems, trace theorems
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Full Text: DOI arXiv


[1] Atkinson, K.; Han, W., Theoretical Numerical Analysis. A Functional Analysis Framework, Texts in Applied Mathematics 39, Springer, Berlin (2009)
[2] Azzam, A.; Kreyszig, E., On solutions of elliptic equations satisfying mixed boundary conditions, SIAM J. Math.Anal. 13 (1982), 254-262
[3] Belhachmi, Z.; Bucur, D.; Burgeth, B.; Weickert, J., How to choose interpolation data in images, SIAM J. Appl. Math. 70 (2009), 333-352
[4] Bertalmío, M.; Sapiro, G.; Caselles, V.; Ballester, C., Image inpainting, Proc. 27th Annual Conf. Computer Graphics and Interactive Techniques ACM Press/Addison-Wesley Publishing Company, New York 417-424 (2000)
[5] Bloor, M. I. G.; Wilson, M. J., Generating blend surfaces using partial differential equations, Comput.-Aided Des. 21 (1989), 165-171
[6] Bredies, K., A variational weak weighted derivative: Sobolev spaces and degenerate elliptic equations, Available at https://imsc.uni-graz.at/bredies/publications_de.html (2008)
[7] Brown, R., The mixed problem for Laplace’s equation in a class of Lipschitz domains, Commun. Partial Differ. Equations 19 (1994), 1217-1233
[8] Cantrell, R. S.; Cosner, C., Spatial Ecology via Reaction-Diffusion Equations, Wiley Series in Mathematical and Computational Biology, Wiley, Chichester (2003)
[9] Caselles, V.; Morel, J.-M.; Sbert, C., An axiomatic approach to image interpolation, IEEE Trans. Image Process. 7 (1998), 376-386
[10] Chabrowski, J., The Dirichlet Problem with \(L^2\) Boundary Data for Elliptic Linear Equations, Lecture Notes in Mathematics 1482, Springer, Berlin (1991)
[11] Chan, T. F.; Kang, S. H., Error analysis for image inpainting, J. Math. Imaging Vis. 26 (2006), 85-103
[12] Chan, T. F.; Shen, J., Mathematical models for local non-texture inpaintings, SIAM J. Appl. Math. 62 (2002), 1019-1043
[13] Crain, I. K., Computer interpolation and contouring of two-dimensional data: A review, Geoexploration 8 (1970), 71-86
[14] Maso, G. Dal; Mosco, U., Wiener’s criterion and \(\Gamma\)-convergence, Appl. Math. Optimization 15 (1987), 15-63
[15] Edmunds, D. E.; Opic, B., Weighted Poincaré and Friedrichs inequalities, J. Lon. Math. Soc., II. Ser. 47 (1993), 79-96
[16] Ern, A.; Guermond, J.-L., Theory and Practice of Finite Elements, Applied Mathematical Sciences 159, Springer, New York (2004)
[17] Fichera, G., Analisi esistenziale per le soluzioni dei problemi al contorno misti, relativi all’equazione e ai sistemi di equazioni del secondo ordine di tipo ellittico, autoaggiunti, Ann. Sc. Norm. Super. Pisa, Sci. Fis. Mat., III. Ser. 1 (1949), Italian 75-100
[18] Galić, I.; Weickert, J.; Welk, M.; Bruhn, A.; Belyaev, A.; Seidel, H.-P., Towards PDE-based image compression, N. Paragios et al. Variational, Geometric, and Level Set Methods in Computer Vision Lecture Notes in Computer Science 3752, Springer, Berlin (2005), 37-48
[19] Galić, I.; Weickert, J.; Welk, M.; Bruhn, A.; Belyaev, A.; Seidel, H.-P., Image compression with anisotropic diffusion, J. Math. Imaging Vis. 31 (2008), 255-269
[20] Gol’dshtein, V.; Ukhlov, A., Weighted Sobolev spaces and embedding theorems, Trans. Am. Math. Soc. 361 (2009), 3829-3850
[21] Guillemot, C.; Meur, O. Le, Image inpainting: Overview and recent advances, IEEE Signal Processing Magazine 31 (2014), 127-144
[22] Hoeltgen, L., Optimal interpolation data for image reconstructions, Ph.D. Thesis, Saarland University, Saarbrücken (2014)
[23] Hoeltgen, L., Understanding image inpainting with the help of the Helmholtz equation, Math. Sci., Springer 11 (2017), 73-77
[24] Hoeltgen, L.; Harris, I.; Breuß, M.; Kleefeld, A., Analytic existence and uniqueness results for PDE-based image reconstruction with the Laplacian, International Conference on Scale Space and Variational Methods in Computer Vision F. Lauze et al. Lecture Notes in Computer Science 10302, Springer, Cham (2017), 66-79
[25] L. Hoeltgen, M. Mainberger; S. Hoffmann; J. Weickert; C. H. Tang; S. Setzer; D. Johannsen; F. Neumann; B. Doerr, Optimizing spatial and tonal data for PDE-based inpainting, Variational Methods, In Imaging and Geometric Control M. Bergounioux et al. Radon Series on Computational and Applied Mathematics 18, De Gruyter, Berlin (2017), 35-83
[26] Hoeltgen, L.; Setzer, S.; Weickert, J., An optimal control approach to find sparse data for Laplace interpolation, Energy Minimization Methods in Computer Vision and Pattern Recognition A. Heyden et al. Lecture Notes in Computer Science 8081, Springer, Berlin (2013), 151-164
[27] Hoeltgen, L.; Weickert, J., Why does non-binary mask optimisation work for diffusion-based image compression?, X.-C. Tai et al. Energy Minimization Methods in Computer Vision and Pattern Recognition Lecture Notes in Computer Science 8932, Springer, Cham (2015), 85-98
[28] Kufner, A., Weighted Sobolev Spaces, Teubner-Texte zur Mathematik 31, BSB B. G. Teubner Verlagsgesellschaft, Leipzig (1980)
[29] Kufner, A.; Opic, B., The Dirichlet problem and weighted spaces. I, Čas. Pěst. Mat. 108 (1983), 381-408
[30] Kufner, A.; Opic, B., How to define reasonably weighted Sobolev spaces, Commentat. Math. Univ. Carol. 25 (1984), 537-554
[31] Kufner, A.; Opic, B., Some remarks on the definition of weighted Sobolev spaces, Partial Differential Equations, 1983 “Nauka” Sibirsk. Otdel, Novosibirsk (1986), 119-126 Russian
[32] Kufner, A.; Opic, B., The Dirichlet problem and weighted spaces. II, Čas. Pěstování Mat. 111 (1986), 242-253
[33] Kufner, A.; Sändig, A.-M., Some Applications of Weighted Sobolev Spaces, Teubner-Texte zur Mathematik 100, BSB B. G. Teubner Verlagsgesellschaft, Leipzig (1987)
[34] Mainberger, M.; Bruhn, A.; Weickert, J.; Forchhammer, S., Edge-based compression of \hbox{cartoon}-like images with homogeneous diffusion, Pattern Recognition 44 (2011), 1859-1873
[35] Mainberger, M.; Hoffmann, S.; Weickert, J.; Tang, C. H.; Johannsen, D.; Neumann, F.; Doerr, B., Optimising spatial and tonal data for homogeneous diffusion inpainting, Scale Space and Variational Methods in Computer Vision A. M. Bruckstein et al. Lecture Notes in Computer Science 6667, Springer, Berlin (2012), 26-37
[36] Martinet, B., Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4 (1970), 154-158 French
[37] Masnou, S.; Morel, J.-M., Level lines based disocclusion, Proceedings 1998 International Conference on Image Processing. ICIP98 IEEE (2002), 259-263
[38] Miranda, C., Sul problema misto per le equazioni lineari ellittiche, Ann. Mat. Pura Appl., IV. Ser. 39 (1955), 279-303 Italian
[39] Nochetto, R. H.; Otárola, E.; Salgado, A. J., Piecewise polynomial interpolation in Muckenhoupt weighted Sobolev spaces and applications, Numer. Math. 132 (2016), 85-130
[40] Noma, A. A.; Misulia, M. G., Programming topographic maps for automatic terrain model construction, Surveying and Mapping 19 (1959), 355-366
[41] Oleĭnik, O. A.; Radkevič, E. V., Second-Order Equations with Nonnegative Characteristic Form, American Mathematical Society, Providence (1973)
[42] Opic, B.; Kufner, A., Hardy-type Inequalities, Pitman Research Notes in Mathematics 219, Longman Scientific & Technical, Harlow; John Wiley & Sons, New York (1990)
[43] Peter, P.; Hoffmann, S.; Nedwed, F.; Hoeltgen, L.; Weickert, J., Evaluating the true potential of diffusion-based inpainting in a compression context, Signal Processing: Image Communication 46 (2016), 40-53
[44] Peter, P.; Hoffmann, S.; Nedwed, F.; Hoeltgen, L.; Weickert, J., From optimised inpainting with linear PDEs towards competitive image compression codecs, Image and Video Technology T. Bräunl et al. Lecture Notes in Computer Science 9431, Springer, Cham (2016), 63-74
[45] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes in C tt{++}. The Art of Scientific Computing, Cambridge University Press, Cambridge (2002)
[46] Sawyer, E. T.; Wheeden, R. L., Degenerate Sobolev spaces and regularity of subelliptic equations, Trans. Am. Math. Soc. 362 (2010), 1869-1906
[47] Schmaltz, C.; Weickert, J.; Bruhn, A., Beating the quality of JPEG 2000 with anisotropic diffusion, Pattern Recognition J. Denzler et al. Lecture Notes in Computer Science 5748, Springer, Berlin (2009), 452-461
[48] Schönlieb, C.-B., Partial Differential Equation Methods for Image Inpainting, Cambridge Monographs on Applied and Computational Mathematics 29, Cambridge University Press, Cambridge (2015)
[49] Solomon, C.; Breckon, T., Fundamentals of Digital Image Processing. A Practical Approach with Examples in Matlab, Wiley-Blackwell, Chichester (2014)
[50] Turesson, B. O., Nonlinear Potential Theory and Weighted Sobolev Spaces, Lecture Notes in Mathematics 1736, Springer, Berlin (2000)
[51] Višik, M. I.; Grušin, V. V., Boundary value problems for elliptic equations degenerate on the boundary of a domain, Math. USSR, Sb. 9 (1969), 423-454
[52] Wang, W.; Sun, J.; Zheng, Z., Poincaré inequalities in weighted Sobolev spaces, Appl. Math. Mech., Engl. Ed. 27 (2006), 125-132
[53] Weber, A., The USC-SIPI image database, 2014. Available at http://sipi.usc.edu/database/, https://swmath.org/software/15845
[54] Zaremba, S., Sur un problème mixte relatif à l’équation de Laplace, Bulletin international de l’Académie des sciences de Cracovie (1910), 313-344 French
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.