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

  • ©Zeev Farbman, Gil Hoffer, Yaron Lipman, Daniel Cohen-Or, and Daniel (Dani) Lischinski




    Coordinates for instant image cloning



    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

ACM Digital Library Publication: