“Image completion with structure propagation” by Sun, Yuan, Jia and Shum

In this paper, we introduce a novel approach to image completion, which we call structure propagation. In our system, the user manually specifies important missing structure information by extending a few curves or line segments from the known to the unknown regions. Our approach synthesizes image patches along these user-specified curves in the unknown region using patches selected around the curves in the known region. Structure propagation is formulated as a global optimization problem by enforcing structure and consistency constraints. If only a single curve is specified, structure propagation is solved using Dynamic Programming. When multiple intersecting curves are specified, we adopt the Belief Propagation algorithm to find the optimal patches. After completing structure propagation, we fill in the remaining unknown regions using patch-based texture synthesis. We show that our approach works well on a number of examples that are challenging to state-of-the-art techniques.

1. Ashikhmin, M. 2001. Synthesizing natural textures. In ACM Symposium on Interactive 3D Graphics, 217–226. Google ScholarDigital Library
2. Ballester, C., Bertalmio, M., Caselles, V., Sapiro, G., and Verdera, J. 2001. Filling in by joint interpolation of vector fields and gray levels. IEEE Trans. Image Processing 10, 8, 1200–1211. Google ScholarDigital Library
3. Barret, A., and Cheney, A. 2002. Object-based image editing. In Proceedings of ACM SIGGRAPH 2002, 777–784. Google ScholarDigital Library
4. Bellman, R. E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Google ScholarDigital Library
5. Bertalmio, M., Sapiro, G., Ballester, C., and Caselles, V. 2000. Image inpainting. In Proceedings of ACM SIGGRAPH 2000, 417–424. Google ScholarDigital Library
6. Bertalmio, M., Bertozzi, A., and Sapiro, G. 2001. Navier-stokes, fluid dynamics, and image and video inpainting. In Proc. Conf. Comp. Vision Pattern Rec., I.355–362.Google Scholar
7. Bertalmio, M., Vese, L., Sapiro, G., and Osher, S. 2003. Simultaneous structure and texture image inpainting. In Proc. Conf. Comp. Vision Pattern Rec., II.707–714.Google Scholar
8. Bornard, R., Lecan, E., Laborelli, L., and Chenot, J.-H. 2002. Missing data correction in still images and image sequences. In Proc. ACM Int. Conf. on Multimedia, 355–361. Google ScholarDigital Library
9. Chan, T., and Shen, J. 2001. Non-texture inpaintings by curvature-driven diffusions. J. Visual Comm. Image Rep. 12, 4, 436–449.Google ScholarDigital Library
10. Criminisi, A., Perez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. In In Proc. Conf. Comp. Vision Pattern Rec., 417–424.Google Scholar
11. Drori, I., Cohen-Or, D., and Yeshurun, H. 2003. Fragment-based image completion. In Proceedings of ACM SIGGRAPH 2003, 303–312. Google ScholarDigital Library
12. Efros, A., and Freeman, W. 2001. Image quilting for texture synthesis and transfer. In Proceedings of ACM SIGGRAPH 2001, 341–346. Google ScholarDigital Library
13. Efros, A., and Leung, T. 1999. Texture synthesis by non-parametric sampling. In Proceedings of Inte. Conf. on Comp. Vision, 1033–1038. Google ScholarDigital Library
14. Freeman, W., Pasztor, E., and Carmichael, O. 2000. Learning low-level vision. Int. J. Computer Vision 40, 1, 25–47. Google ScholarDigital Library
15. Harrison, P. 2001. A non-hierarchical procedure for re-synthesis of complex textures. In Proc. Int. Conf. Central Europe Comp. Graphics, Visua. and Comp. Vision.Google Scholar
16. Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. 2001. Image analogies. In Proceedings of ACM SIGGRAPH 2001, 327–340. Google ScholarDigital Library
17. Igehy, H., and Pereira. L. 1997. Image replacement through texture synthesis. In Proc. of Inte. Conf. on Image Processing, 186–189. Google ScholarDigital Library
18. Jia, J., and Tang, C. K. 2003. Image repairing: robust image synthesis by adaptive nd tensor voting. In Proc. Conf. Comp. Vision Pattern Rec., 1643–650. Google ScholarDigital Library
19. Koffka, K. 1935, 1967. Principles of gestalt psychology. New York, Hartcourt, Brace and World.Google Scholar
20. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. In Proceedings of ACM SIGGRAPH 2003, 277–286. Google ScholarDigital Library
21. Levin, A., Zomet, A., and Weiss, Y. 2003. Learning how to inpaint from global image statistics. In Proceedings of Inte. Conf. on Comp. Vision. II.305–313. Google ScholarDigital Library
22. Liang, L., Liu, C., Xu, Y. Q., Guo, B., and Shum, H. 2001. Real-time texture synthesis by patch-based sampling. ACM Transactions on Graphics 20, 3, 127–150. Google ScholarDigital Library
23. Noe, A., Pessoa, L., and Thompson, E. 1998. Finding out about filling-in: A guide to perceptual completion for visual science and the philosophy of perception. Behavioral and Brain Sciences 6, 723–748.Google Scholar
24. Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, California. Google ScholarDigital Library
25. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. In Proceedings of ACM SIGGRAPH 2003, 313–318. Google ScholarDigital Library
26. Pérez, P., Gangnet, M., and Blake, A. 2004. Patchworks: example-based region tiling for image editing. Technical Report, Microsoft Research, MSR–TR-2004-04.Google Scholar
27. Sharf, A., Alexa, M., and Cohen-Or, D. 2004. Context-based surface completion. In Proceedings of ACM SIGGRAPH 2004, 878–887. Google ScholarDigital Library
28. Sun, J., Shum, H. Y., and Zheng, N. N. 2002. Stereo matching using belief propagation. In Proceedings of European Conference on Computer Vision 2002, vol. II, 510–524. Google ScholarDigital Library
29. Wei, L. W., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of ACM SIGGRAPH 2000, 479–488. Google ScholarDigital Library
30. Weiss, Y., and Freeman, W. T. 2001. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory. 47, 2, 723–735. Google ScholarDigital Library
31. Wexler, Y., Shechtman, E., and Irani, M. 2004. Space-time video completion. In Proc. Conf. Comp. Vision Pattern Rec., I:120–127.Google Scholar
32. Yedidia, J. S., Freeman, W. T., and Weiss, Y. 2002. Understanding belief propagation and its generalizations. Technical Report, Mitsubishi Electric Research Laboratories, MERL-TR-2001-22.Google Scholar