Abstract
High-quality image inpainting methods based on nonlinear higher-order partial differential equations have been developed in the last few years. These methods are iterative by nature, with a time variable serving as iteration parameter. For reasons of stability a large number of iterations can be needed which results in a computational complexity that is often too large for interactive image manipulation.
Based on a detailed analysis of stationary first order transport equations the current paper develops a fast noniterative method for image inpainting. It traverses the inpainting domain by the fast marching method just once while transporting, along the way, image values in a coherence direction robustly estimated by means of the structure tensor. Depending on a measure of coherence strength the method switches continuously between diffusion and directional transport. It satisfies a comparison principle. Experiments with the inpainting of gray tone and color images show that the novel algorithm meets the high level of quality of the methods of Bertalmio et al. (SIG-GRAPH ’00: Proc. 27th Conf. on Computer Graphics and Interactive Techniques, New Orleans, ACM Press/Addison-Wesley, New York, pp. 417–424, 2000), Masnou (IEEE Trans. Image Process. 11(2):68–76, 2002), and Tschumperlé (Int. J. Comput. Vis. 68(1):65–82, 2006), while being faster by at least an order of magnitude.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing. Springer, New York (2002)
Bertalmio, M., Bertozzi, A.L., Sapiro, G.: Navier-Stokes, fluid dynamics, and image and video inpainting. In: CVPR’01: Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition, Kauai, vol. I, pp. 355–362. IEEE Press, New York (2001)
Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: SIGGRAPH ’00: Proc. 27th Conf. on Computer Graphics and Interactive Techniques, New Orleans, pp. 417–424. ACM Press/Addison-Wesley, New York (2000)
Caselles, V., Masnou, S., Morel, J.-M., Sbert, C.: Image interpolation. In: Séminaire sur les Équations aux Dérivées Partielles, École Polytech., Palaiseau, 1997–1998. Exp. No. XII, p. 15 (1998), downloadable at the url citeseer.ist.psu.edu/caselles98image.html
Chan, T.F., Kang, S.H., Shen, J.: Euler’s elastica and curvature-based inpainting. SIAM J. Appl. Math. 63(2), 564–592 (2002)
Chan, T.F., Shen, J.: Inpainting based on nonlinear transport and diffusion. In: Inverse problems, image analysis, and medical imaging, New Orleans, LA, 2001. Contemporary Mathematics, vol. 313, pp. 53–65. AMS, Providence (2002)
Chan, T.F., Shen, J.: Mathematical models for local nontexture inpaintings. SIAM J. Appl. Math. 62(3), 1019–1043 (2002)
Chan, T.F., Shen, J.: Image Processing and Analysis. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2005)
Chan, T.F., Shen, J.: Variational image inpainting. Commun. Pure Appl. Math. 58(5), 579–619 (2005)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)
Esedoglu, S., Shen, J.: Digital inpainting based on the Mumford-Shah-Euler image model. Eur. J. Appl. Math. 13(4), 353–370 (2002)
Fuchs, F.G.: Eulers Elastica- und krümmungsbasiertes Inpainting. Master’s thesis, Technische Universität München (2006)
Gonzalez, R.C., Woods, R.E., Eddins, S.L.: Digital Image Processing Using Matlab. Pearson Prentice Hall, Upper Saddle River (2004)
Guichard, F., Morel, J.-M.: Image Analysis and PDEs. Unpublished book. Manuscript version 15/07/2000, 345 pp. (2000), downloadable at the url: citeseer.ist.psu.edu/guichard01image.html
Kimmel, R.: Numerical Geometry of Images. Springer, New York (2004)
Masnou, S.: Disocclusion: a variational approach using level lines. IEEE Trans. Image Process. 11(2), 68–76 (2002)
Masnou, S., Morel, J.-M.: Level lines based disocclusion. In: ICIP’98: Proc. IEEE Int. Conf. on Image Processing, Chicago, pp. 259–263. IEEE Press, New York (1998)
Oliveira, M.M., Bowen, B., McKenna, R., Chang, Y.-S.: Fast digital image inpainting. In: VIIP ’01: Proc. Int. Conf. on Visualization, Imaging, and Image Processing, Marbella, Spain, pp. 261–266 (2001)
Sapiro, G.: Geometric Partial Differential Equations and Image Analysis. Cambridge University Press, Cambridge (2001)
Sethian, J.A.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. U.S.A. 93(4), 1591–1595 (1996)
Sethian, J.A.: Level Set Methods and Fast Marching Methods, 2nd edn. Cambridge University Press, Cambridge (1999)
Soille, P.: Spatial distributions from contour lines: an efficient methodology based on distance transforms. J. Vis. Commun. Image Rep. 2(2), 138–150 (1991)
Soille, P.: Morphological Image Analysis. 2nd edn. Springer, Berlin (2003)
Telea, A.: An image inpainting technique based on the fast marching method. J. Graph. Tools 9(1), 23–34 (2004)
Tschumperlé, D.: Fast anisotropic smoothing of multi-valued images using curvature-preserving PDE’s. Int. J. Comput. Vis. 68(1), 65–82 (2006)
Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control 40(9), 1528–1538 (1995)
Weickert, J.: Anisotropic Diffusion in Image Processing. Teubner, Stuttgart (1998)
Weickert, J.: Coherence-enhancing diffusion of color images. Image Vis. Comput. 17(3–4), 201–212 (1999)
Weickert, J.: Coherence-enhancing shock filters. In: Michaelis, B., Krell, G. (eds.) Pattern Recognition. Lecture Notes in Computer Science, vol. 2781. Springer, New York (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bornemann, F., März, T. Fast Image Inpainting Based on Coherence Transport. J Math Imaging Vis 28, 259–278 (2007). https://doi.org/10.1007/s10851-007-0017-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-007-0017-6