Coordinates for instant image cloning

ABSTRACT

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.

REFERENCES

• 1: Aseem Agarwala , Mira Dontcheva , Maneesh Agrawala , Steven Drucker , Alex Colburn , Brian Curless , David Salesin , Michael Cohen, Interactive digital photomontage, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 2: Aseem Agarwala, Efficient gradient-domain compositing using quadtrees, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 3: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 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.
• 5: Cgal, 2007. Computational Geometry Algorithms Library. http://www.cgal.org.
• 6: Raanan Fattal , Dani Lischinski , Michael Werman, Gradient domain high dynamic range compression, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 7: Graham D. Finlayson , Steven D. Hordley , Mark S. Drew, Removing Shadows from Images, Proceedings of the 7th European Conference on Computer Vision-Part IV, p.823-836, May 28-31, 2002
• 8: Michael S. Floater , Géza Kós , Martin Reimers, Mean value coordinates in 3D, Computer Aided Geometric Design, v.22 n.7, p.623-631, October 2005 [doi>10.1016/j.cagd.2005.06.004]
• 9: Michael S. Floater, Mean value coordinates, Computer Aided Geometric Design, v.20 n.1, p.19-27, March 2003 [doi>10.1016/S0167-8396(02)00002-5]
• 10: Georgiev, T. 2004. Photoshop healing brush: a tool for seamless cloning. In Workshop on Applications of Computer Vission (ECCV 2004), 1--8.
• 11: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.197-206, July 1991
• 12: Kai Hormann , Michael S. Floater, Mean value coordinates for arbitrary planar polygons, ACM Transactions on Graphics (TOG), v.25 n.4, p.1424-1441, October 2006 [doi>10.1145/1183287.1183295]
• 13: Jiaya Jia , Jian Sun , Chi-Keung Tang , Heung-Yeung Shum, Drag-and-drop pasting, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 14: Pushkar Joshi , Mark Meyer , Tony DeRose , Brian Green , Tom Sanocki, Harmonic coordinates for character articulation, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 15: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: Michael Kazhdan , Hugues Hoppe, Streaming multigrid for gradient-domain operations on large images, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 17: Land, E. H., and McCann, J. J. 1971. Lightness and Retinex Theory. J. Opt. Soc. Amer. 61 (Jan.), 1--11.
• 18: Langer, T., and Seidel, H.-P. 2008. Higher order barycentric coordinates. Computer Graphics Forum (Eurographics 2008) 27, 2, 459--466.
• 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.
• 20: Anat Levin , Dani Lischinski , Yair Weiss, A Closed-Form Solution to Natural Image Matting, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.30 n.2, p.228-242, February 2008 [doi>10.1109/TPAMI.2007.1177]
• 21: James McCann , Nancy S. Pollard, Real-time gradient-domain painting, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 22: Palmer, S. E. 1999. Vision Science: Photons to Phenomenology. The MIT Press, May.
• 23: Patrick Pérez , Michel Gangnet , Andrew Blake, Poisson image editing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 24: Jian Sun , Jiaya Jia , Chi-Keung Tang , Heung-Yeung Shum, Poisson matting, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 25: Richard Szeliski, Locally adapted hierarchical basis preconditioning, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 26: Wachpress, E. L. 1975. A Rational Finite Element Basis. Academic Press, New York.
• 27: Wang, J., and Cohen, M. F. 2007. Optimized color sampling for robust matting. In Proc. CVPR, 1--8.
• 28: Hongcheng Wang , Ramesh Raskar , Narendra Ahuja, Seamless Video Editing, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 3, p.858-861, August 23-26, 2004 [doi>10.1109/ICPR.2004.806]
• 29: Warren, J. 1996. Barycentric coordinates for convex polytopes. Advances in Computational Mathematics 6, 2, 97--108.
• 30: Weiss, Y. 2001. Deriving intrinsic images from image sequences. In Proc. ICCV, 68--75.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

General Terms:
Algorithms, Design, Theory

Keywords:
Poisson equation, gradient domain, image editing, matting, mean-value coordinates, seamless cloning, stitching