A variational framework for exemplar-based image inpainting. (English) Zbl 1235.94015

Summary: Non-local methods for image denoising and inpainting have gained considerable attention in recent years. This is in part due to their superior performance in textured images, a known weakness of purely local methods. Local methods on the other hand have demonstrated to be very appropriate for the recovering of geometric structures such as image edges. The synthesis of both types of methods is a trend in current research. Variational analysis in particular is an appropriate tool for a unified treatment of local and non-local methods. In this work we propose a general variational framework for non-local image inpainting, from which important and representative previous inpainting schemes can be derived, in addition to leading to novel ones. We explicitly study some of these, relating them to previous work and showing results on synthetic and real images.


94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
49N45 Inverse problems in optimal control


Full Text: DOI Link


[1] Aharon, M., Elad, M., & Bruckstein, A. M. (2006). The K-SVD: an algorithm for designing of overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11), 4311–4322. · Zbl 1375.94040
[2] Almansa, A., Caselles, V., Haro, G., & Rougé, B. (2006). Restoration and zoom of irregularly sampled, blurred, and noisy images by accurate total variation minimization with local constraints. Multiscale Modeling & Simulation, 5(1), 235–272. · Zbl 1161.68822
[3] Arias, P., Caselles, V., & Sapiro, G. (2009). A variational framework for non-local image inpainting. In Lecture notes in computer science. EMMCVPR (pp. 345–358). Berlin: Springer.
[4] Aujol, J.-F., Ladjal, S., & Masnou, S. (2010). Exemplar-based inpainting from a variational point of view. SIAM Journal on Mathematical Analysis, 42(3), 1246–1285. · Zbl 1210.49002
[5] Awate, S. P., & Whitaker, R. T. (2005). Higher-order image statistics for unsupervised, information-theoretic, adaptive, image filtering. In Proc. of CVPR (pp. 44–51).
[6] Ballester, C., Bertalmío, M., Caselles, V., Sapiro, G., & Verdera, J. (2001). Filling-in by joint interpolation of vector fields and gray levels. IEEE Transactions on IP, 10(8), 1200–1211. · Zbl 1037.68771
[7] Barnes, C., Shechtman, E., Finkelstein, A., & Goldman, D. B. (2009). PatchMatch: a randomized correspondence algorithm for structural image editing. In Proc. of SIGGRAPH (pp. 1–11). New York: ACM.
[8] Bertalmío, M., Sapiro, G., Caselles, V., & Ballester, C. (2000). Image inpainting. In Proc. of SIGGRAPH (pp. 417–424). New York: ACM.
[9] Bertalmío, M., Vese, L., Sapiro, G., & Osher, S. J. (2003). Simultaneous structure and texture inpainting. IEEE Transactions on IP, 12(8), 882–889.
[10] Bornard, R., Lecan, E., Laborelli, L., & Chenot, J.-H. (2002). Missing data correction in still images and image sequences. In Proc. ACM int. conf. on multimedia.
[11] Bornemann, F., & März, T. (2007). Fast image inpainting based on coherence transport. Journal of Mathematical Imaging and Vision, 28(3), 259–278. · Zbl 1451.94007
[12] Brox, T., Kleinschmidt, O., & Cremers, D. (2008). Efficient nonlocal means for denoising of textural patterns. IEEE Transaction on IP, 17(7), 1057–1092.
[13] Buades, A., Coll, B., & Morel, J.-M. (2005). A non local algorithm for image denoising. In Proc. of the IEEE conf. on CVPR (Vol. 2, pp. 60–65). · Zbl 1108.94004
[14] Candes, E. J., & Wakin, M. B. (2008). An introduction to compressive sampling. IEEE Signal Processing Magazine, 25(2), 21–30.
[15] Cao, F., Gousseau, Y., Masnou, S., & Pérez, P. (2009). Geometrically guided exemplar-based inpainting. · Zbl 1235.94017
[16] Chambolle, A. (2004). An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision, 20(1–2), 89–97. · Zbl 1366.94056
[17] Chan, T., & Shen, J. H. (2001). Mathematical models for local nontexture inpaintings. SIAM Journal on Applied Mathematics, 62(3), 1019–1043. · Zbl 1050.68157
[18] Chan, T., Kang, S. H., & Shen, J. H. (2002). Euler’s elastica and curvature based inpaintings. SIAM Journal on Applied Mathematics, 63(2), 564–592. · Zbl 1028.68185
[19] Cheng, Y. (1995). Mean shift, mode seeking and clustering. IEEE Transactions on PAMI, 17(8), 790–799. · Zbl 05112121
[20] Criminisi, A., Pérez, P., & Toyama, K. (2004). Region filling and object removal by exemplar-based inpainting. IEEE Transactions on IP, 13(9), 1200–1212.
[21] Csiszár, I. (2008). Axiomatic characterizations of information measures. Entropy, 10(3), 261–273. · Zbl 1179.94043
[22] Demanet, L., Song, B., & Chan, T. (2003). Image inpainting by correspondence maps: a deterministic approach (Technical report). UCLA.
[23] Drori, I., Cohen-Or, D., & Yeshurun, H. (2003). Fragment-based image completion. In Proc. of ACM SIGGRAPH (pp. 303–312). New York: ACM.
[24] Efros, A. A., & Leung, T. K. (1999). Texture synthesis by non-parametric sampling. In Proc. of the IEEE ICCV, September 1999 (pp. 1033–1038).
[25] Elad, M., Starck, J. L., Querre, P., & Donoho, D. L. (2005). Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA). Applied and Computational Harmonic Analysis, 19(3), 340–358. · Zbl 1081.68732
[26] Esedoglu, S., & Shen, J. H. (2002). Digital image inpainting by the Mumford-Shah-Euler image model. European Journal of Applied Mathematics, 13, 353–370. · Zbl 1017.94505
[27] Facciolo, G., Arias, P., Caselles, V., & Sapiro, G. (2009). Exemplar-based interpolation of sparsely sampled images. In Lecture notes in computer science. EMMCVPR (pp. 331–344). Berlin: Springer.
[28] Fang, C.-W., & Lien, J.-J. J. (2009). Rapid image completion system using multiresolution patch-based directional and nondirectional approaches. IEEE Transactions on IP, 18(12), 2769–2779. · Zbl 1371.94123
[29] Gilboa, G., & Osher, S. J. (2007). Nonlocal linear image regularization and supervised segmentation. SIAM Multiscale Modeling and Simulation, 6(2), 595–630. · Zbl 1140.68517
[30] Gilboa, G., & Osher, S. (2008). Nonlocal operators with applications to image processing. Multiscale Modeling & Simulation, 7(3), 1005–1028. · Zbl 1181.35006
[31] Han, J., Zhou, K., Wei, L.-Y., Gong, M., Bao, H., Zhang, X., & Guo, B. (2006). Fast example-based surface texture synthesis via discrete optimization. The Visual Computer, 22(9), 918–925. · Zbl 05074952
[32] Harrison, P. (2005). Texture tools. PhD thesis, Monash University.
[33] Holtzman-Gazit, M., & Yavneh, I. (2008). A scale-consistent approach to image completion. International Journal of Multiscale Computer Engineering, 6(6), 617–628.
[34] Igehy, H., & Pereira, L. (1997). Image replacement through texture synthesis. In Proc. of the IEEE ICIP.
[35] Jaynes, E. T. (1957). Information theory and statistical mechanics. Physical Review, 106(4), 620–630. · Zbl 0084.43701
[36] Jia, J., & Tang, C.-K. (2004). Inference of segmented color and texture description by tensor voting. IEEE Transactions on PAMI, 26(6), 771–786. · Zbl 05111563
[37] Kawai, N., Sato, T., & Yokoya, N. (2009). Image inpainting considering brightness change and spatial locality of textures and its evaluation. In Ad. in image and video tech. (pp. 271–282). Berlin: Springer.
[38] Kimball, S., Mattis, P., & the GIMP Dev. Team (2009). GIMP: GNU Image Manipulation Program. http://www.gimp.org/ . Version 2.6.8 released on December 2009.
[39] Komodakis, N., & Tziritas, G. (2007). Image completion using efficient belief propagation via priority scheduling and dynamic pruning. IEEE Transactions on IP, 16(11), 2649–2661.
[40] Kwatra, V., Essa, I., Bobick, A., & Kwatra, N. (2005). Texture optimization for example-based synthesis. ACM Transactions on Graphics, 24(3), 795–802. · Zbl 05457407
[41] Levin, A., Zomet, A., & Weiss, Y. (2003). Learning how to inpaint from global image statistics. In Proc. of IEEE ICCV.
[42] Levina, E., & Bickel, P. (2006). Texture synthesis and non-parametric resampling of random fields. Annals of Statistics, 34(4). · Zbl 1246.62194
[43] Lezoray, O., Elmoataz, A., & Bougleux, S. (2007). Graph regularization for color image processing. Computer Vision Image Understanding, 107(1–2), 38–55. · Zbl 1143.94308
[44] Mairal, J., Sapiro, G., & Elad, M. (2008). Learning multiscale sparse representations for image and video restoration. SIAM Multiscale Modeling and Simulation, 7(1), 214–241. · Zbl 1194.49041
[45] Masnou, S. (2002). Disocclusion: a variational approach using level lines. IEEE Transactions on IP, 11(2), 68–76.
[46] Masnou, S., & Morel, J.-M. (1998). Level lines based disocclusion. In Proc. of IEEE ICIP.
[47] Morel, J.-M., & Yu, G. (2008). On the consistency of the SIFT method. Preprint, CMLA, 26.
[48] Pérez, P., Gangnet, M., & Blake, A. (2003). Poisson image editing. In Proc. of SIGGRAPH (pp. 313–318). New York: ACM.
[49] Pérez, P., Gangnet, M., & Blake, A. (2004). PatchWorks: example-based region tiling for image editing (Technical report). Microsoft Research.
[50] Peyré, G. (2009). Manifold models for signals and images. Computer Vision and Image Understanding, 113(2), 249–260. · Zbl 05690602
[51] Peyré, G., Bougleux, S., & Cohen, L. (2008). Non-local regularization of inverse problems. In ECCV ’08 (pp. 57–68). Berlin: Springer. · Zbl 1223.68116
[52] Peyré, G., Bougleux, S., & Cohen, L. D. (2009). Non-local regularization of inverse problems. Preprint Hal-00419791. · Zbl 1223.68116
[53] Pizarro, L., Mrázek, P., Didas, S., Grewenig, S., & Weickert, J. (2010). Generalised nonlocal image smoothing. International Journal of Computer Vision, 90, 62–87. · Zbl 1477.94020
[54] Protter, M., Elad, M., Takeda, H., & Milanfar, P. (2009). Generalizing the non-local-means to super-resolution reconstruction. IEEE Transactions on IP, 18(1), 36–51. · Zbl 1371.94300
[55] Shen, J., Jin, X., & Zhou, C. (2005). Gradient based image completion by solving Poisson equation. In Ad. in multimedia information processing (pp. 257–68).
[56] Sun, J., Yuan, L., Jia, J., & Shum, H. Y. (2005). Image completion with structure propagation. In Proc. of SIGGRAPH (pp. 861–868). New York: ACM.
[57] Tong, X., Zhang, J., Liu, L., Wang, X., Guo, B., & Shum, H.-Y. (2002). Synthesis of bidirectional texture functions on arbitrary surfaces. ACM Transactions on Graphics, 21(3), 665–672. · Zbl 05457628
[58] Tschumperlé, D., & Deriche, R. (2005). Vector-valued image regularization with PDE’s: a common framework for different applications. IEEE Transactions on PAMI, 27(4). · Zbl 1012.68786
[59] Wei, L.-Y., & Levoy, M. (2000). Fast texture synthesis using tree-structured vector quantization. In Proc. of the SIGGRAPH (pp. 479–488). New York: ACM.
[60] Wexler, Y., Shechtman, E., & Irani, M. (2007). Space-time completion of video. IEEE Transactions on PAMI, 29(3), 463–476. · Zbl 05340765
[61] Zhou, D., & Schölkopf, B. (2005). Regularization on discrete spaces. In Proceedings of the 27th DAGM symposium (pp. 361–368). Berlin: Springer.
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.