“Coordinates for instant image cloning” by Farbman, Hoffer, Lipman, Cohen-Or and Lischinski

Seamless cloning of a source image patch into a target image is an important and useful image editing operation, which has received considerable research attention in recent years. This operation is typically carried out by solving a Poisson equation with Dirichlet boundary conditions, which smoothly interpolates the discrepancies between the boundary of the source patch and the target across the entire cloned area. In this paper we introduce an alternative, coordinate-based approach, where rather than solving a large linear system to perform the aforementioned interpolation, the value of the interpolant at each interior pixel is given by a weighted combination of values along the boundary. More specifically, our approach is based on Mean-Value Coordinates (MVC). The use of coordinates is advantageous in terms of speed, ease of implementation, small memory footprint, and parallelizability, enabling real-time cloning of large regions, and interactive cloning of video streams. We demonstrate a number of applications and extensions of the coordinate-based framework.

1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. Graph. 23, 3, 294–302. Google ScholarDigital Library
2. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Trans. Graph. 26, 3, 94. Google ScholarDigital Library
3. Bolz, J., Farmer, I., Grinspun, E., and Schröder, P. 2003. Sparse matrix solvers on the GPU: conjugate gradients and multigrid. ACM Trans. Graph. 22, 3, 917–924. Google ScholarDigital Library
4. Carrier, J., Greengard, L., and Rokhlin, V. 1988. A fast adaptive multipole algorithm for particle simulations. SIAM Journal on Scientific and Statistical Computing 9, 669–686.Google ScholarDigital Library
5. Cgal, 2007. Computational Geometry Algorithms Library. http://www.cgal.org.Google Scholar
6. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Trans. Graph. 21, 3, 249–256. Google ScholarDigital Library
7. Finlayson, G. D., Hordley, S. D., and Drew, M. S. 2002. Removing shadows from images. In Proc. ECCV, Springer-Verlag, London, UK, vol. IV, 823–836. Google ScholarDigital Library
8. Floater, M. S., Kós, G., and Reimers, M. 2005. Mean value coordinates in 3d. Comput. Aided Geom. Des. 22, 7, 623–631. Google ScholarDigital Library
9. Floater, M. S. 2003. Mean value coordinates. Comput. Aided Geom. Des. 20, 1, 19–27. Google ScholarDigital Library
10. Georgiev, T. 2004. Photoshop healing brush: a tool for seamless cloning. In Workshop on Applications of Computer Vission (ECCV 2004), 1–8.Google Scholar
11. Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. Computer Graphics (SIGGRAPH ’91 Proceedings) 25, 4 (July), 197–206. Google ScholarDigital Library
12. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Transactions on Graphics 25, 4, 1424–1441. Google ScholarDigital Library
13. Jia, J., Sun, J., Tang, C.-K., and Shum, H.-Y. 2006. Drag-and-drop pasting. ACM Trans. Graph. 25, 3 (July), 631–637. Google ScholarDigital Library
14. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, 71. Google ScholarDigital Library
15. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
16. Kazhdan, M. M., and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph 27, 3. Google ScholarDigital Library
17. Land, E. H., and McCann, J. J. 1971. Lightness and Retinex Theory. J. Opt. Soc. Amer. 61 (Jan.), 1–11.Google ScholarCross Ref
18. Langer, T., and Seidel, H.-P. 2008. Higher order barycentric coordinates. Computer Graphics Forum (Eurographics 2008) 27, 2, 459–466.Google Scholar
19. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In Proc. ECCV, Springer-Verlag, vol. IV, 377–389.Google Scholar
20. Levin, A., Lischinski, D., and Weiss, Y. 2008. A closed-form solution to natural image matting. IEEE Trans. Pattern Anal. Mach. Intell. 30, 2, 228–242. Google ScholarDigital Library
21. McCann, J., and Pollard, N. S. 2008. Real-time gradient-domain painting. ACM Transactions on Graphics (SIGGRAPH 2008) 27, 3 (Aug.). Google ScholarDigital Library
22. Palmer, S. E. 1999. Vision Science: Photons to Phenomenology. The MIT Press, May.Google Scholar
23. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318. Google ScholarDigital Library
24. Sun, J., Jia, J., Tang, C.-K., and Shum, H.-Y. 2004. Poisson matting. ACM Trans. Graph. 23, 3, 315–321. Google ScholarDigital Library
25. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Trans. Graph 25, 3, 1135–1143. Google ScholarDigital Library
26. Wachpress, E. L. 1975. A Rational Finite Element Basis. Academic Press, New York.Google Scholar
27. Wang, J., and Cohen, M. F. 2007. Optimized color sampling for robust matting. In Proc. CVPR, 1–8.Google Scholar
28. Wang, H., Raskar, R., and Ahuja, N. 2004. Seamless video editing. In Proc. ICPR ’04, IEEE Computer Society, Washington, DC, USA, vol. 3, 858–861. Google ScholarDigital Library
29. Warren, J. 1996. Barycentric coordinates for convex polytopes. Advances in Computational Mathematics 6, 2, 97–108.Google ScholarCross Ref
30. Weiss, Y. 2001. Deriving intrinsic images from image sequences. In Proc. ICCV, 68–75.Google ScholarCross Ref