“Efficient gradient-domain compositing using quadtrees” by Agarwala

We describe a hierarchical approach to improving the efficiency of gradient-domain compositing, a technique that constructs seamless composites by combining the gradients of images into a vector field that is then integrated to form a composite. While gradient-domain compositing is powerful and widely used, it suffers from poor scalability. Computing an n pixel composite requires solving a linear system with n variables; solving such a large system quickly overwhelms the main memory of a standard computer when performed for multi-megapixel composites, which are common in practice. In this paper we show how to perform gradient-domain compositing approximately by solving an O(p) linear system, where p is the total length of the seams between image regions in the composite; for typical cases, p is O(√n). We achieve this reduction by transforming the problem into a space where much of the solution is smooth, and then utilize the pattern of this smoothness to adaptively subdivide the problem domain using quadtrees. We demonstrate the merits of our approach by performing panoramic stitching and image region copy-and-paste in significantly reduced time and memory while achieving visually identical results.

1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Transactions on Graphics 23, 3 (Aug.), 294–302. Google ScholarDigital Library
2. Agarwala, A., Zheng, K. C., Pal, C., Agrawala, M., Cohen, M., Curless, B., Salesin, D. H., and Szeliski, R. 2005. Panoramic video textures. ACM Transactions on Graphics 24, 3 (Aug.), 821–827. Google ScholarDigital Library
3. Agarwala, A., Agrawala, M., Cohen, M., Salesin, D., and Szeliski, R. 2006. Photographing long scenes with multi-viewpoint panoramas. ACM Transactions on Graphics 25, 3 (July), 853–861. Google ScholarDigital Library
4. Agrawal, A., Raskar, R., Nayar, S. K., and Li, Y. 2005. Removing photography artifacts using gradient projection and flash-exposure sampling. ACM Transactions on Graphics 24, 3 (Aug.), 828–835. Google ScholarDigital Library
5. Bae, S., Paris, S., and Durand, F. 2006. Two-scale tone management for photographic look. ACM Transactions on Graphics 25, 3 (July), 637–645. Google ScholarDigital Library
6. Bolz, J., Farmer, I., Grinspun, E., and Schröder, P. 2003. Sparse matrix solvers on the GPU: Conjugate gradients and multigrid. ACM Transactions on Graphics 22, 3 (July), 917–924. Google ScholarDigital Library
7. Dyer, C. 1982. The space efficiency of quadtrees. Computer Graphics and Image Processing 19, 4 (Aug.), 335–348.Google ScholarCross Ref
8. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Transactions on Graphics 21, 3, 249–256. Google ScholarDigital Library
9. Finlayson, G., and Drew, S. H. M. 2002. Removing shadows from images. In European Conference on Computer Vision (ECCV 02), 823–831. Google ScholarDigital Library
10. Fuhrmann, D. R. 1988. Quadtree traversal algorithms for pointer-based and depth-first representations. IEEE Transactions on Pattern Analysis and Machine Intelligence 10, 6, 955–960. Google ScholarDigital Library
11. Georgiev, T. 2004. Photoshop healing brush: a tool for seamless cloning. In Workshop on Applications of Computer Vision (ECCV 2004), 1–8.Google Scholar
12. Goldman, D. B., and Chen, J.-H. 2005. Vignette and exposure calibration and compensation. In International Conference on Computer Vision (ICCV 05), 899–906. Google ScholarDigital Library
13. Hays, J., and Efros, A. 2007. Scene completion using millions of photographs. ACM Transactions on Graphics 26, 3, To appear. Google ScholarDigital Library
14. Jia, J., Sun, J., Tang, C.-K., and Shum, H.-Y. 2006. Drag-and-drop pasting. ACM Transactions on Graphics 25, 3 (July), 631–637. Google ScholarDigital Library
15. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM Transactions on Graphics 22, 3, 277–286. Google ScholarDigital Library
16. Land, E. H. 1977. The retinex theory of color vision. Scientific American 237, 6, 108–128.Google ScholarCross Ref
17. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In European Conference on Computer Vision (ECCV 04), 377–389.Google Scholar
18. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Transactions on Graphics 23, 3 (Aug.), 457–462. Google ScholarDigital Library
19. Moore, D. 1995. The cost of balancing generalized quadtrees. In Proceedings of the Third ACM Symposium on Solid Modeling and Applications, 305–312. Google ScholarDigital Library
20. Palmer, S. E. 1999. Vision Science: Photons to Phenomenology. The MIT Press.Google Scholar
21. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics 22, 3 (July), 313–318. Google ScholarDigital Library
22. Saad, Y. 2003. Iterative methods for sparse linear systems, 2nd ed. Society for Industrial and Applied Mathematics (SIAM). Google ScholarDigital Library
23. Samet, H. 1990. Applications for spatial data structures: computer graphics, image processing, and GIS. Addison-Wesley. Google ScholarDigital Library
24. Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. Rep. CS-94-125, Carnegie Mellon University. Google ScholarDigital Library
25. Simchony, T., Chellappa, R., and Shao, M. 1990. Direct analytical methods for solving Poisson equations in computer vision problems. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 5, 435–446. Google ScholarDigital Library
26. Sun, J., Jia, J., Tang, C.-K., and Shum, H.-Y. 2004. Poisson matting. ACM Transactions on Graphics 23, 3 (Aug.), 315–321. Google ScholarDigital Library
27. Szeliski, R., and Shum, H.-Y. 1996. Motion estimation with quadtree splines. IEEE Transactions on Pattern Analysis and Machine Intelligence 18, 12, 1199–1210. Google ScholarDigital Library
28. Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 6, 513–528. Google ScholarDigital Library
29. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Transactions on Graphics 25, 3 (July), 1135–1143. Google ScholarDigital Library
30. Toledo, S. 1999. A survey of out-of-core algorithms in numerical linear algebra. In External Memory Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 161–180. Google ScholarDigital Library
31. Wang, H., Raskar, R., and Ahuja, N. 2004. Seamless video editing. In Proceedings of the International Conference on Pattern Recognition (ICPR), 858–861. Google ScholarDigital Library
32. Weiss, Y. 2001. Deriving intrinsic images from image sequences. In International Conference On Computer Vision (ICCV 01), 68–75.Google ScholarCross Ref
33. Zomet, A., Levin, A., Peleg, S., and Weiss, Y. 2006. Seamless image stitching by minimizing false edges. IEEE Transactions on Image Processing 15, 4, 969–977. Google ScholarDigital Library