“Interactive Editing of Massive Imagery Made Simple: Turning Atlanta Into Atlantis” by Summa, Scorzelli, Jiang, Bremer and Pascucci

  • ©Brian Summa, Giorgio Scorzelli, Ming Jiang, Peer-Timo Bremer, and Valerio Pascucci




    Interactive Editing of Massive Imagery Made Simple: Turning Atlanta Into Atlantis



    This article presents a simple framework for progressive processing of high-resolution images with minimal resources. We demonstrate this framework’s effectiveness by implementing an adaptive, multi-resolution solver for gradient-based image processing that, for the first time, is capable of handling gigapixel imagery in real time. With our system, artists can use commodity hardware to interactively edit massive imagery and apply complex operators, such as seamless cloning, panorama stitching, and tone mapping.
    We introduce a progressive Poisson solver that processes images in a purely coarse-to-fine manner, providing near instantaneous global approximations for interactive display (see Figure 1). We also allow for data-driven adaptive refinements to locally emulate the effects of a global solution. These techniques, combined with a fast, cache-friendly data access mechanism, allow the user to interactively explore and edit massive imagery, with the illusion of having a full solution at hand. In particular, we demonstrate the interactive modification of gigapixel panoramas that previously required extensive offline processing. Even with massive satellite images surpassing a hundred gigapixels in size, we enable repeated interactive editing in a dynamically changing environment. Images at these scales are significantly beyond the purview of previous methods yet are processed interactively using our techniques. Finally our system provides a robust and scalable out-of-core solver that consistently offers high-quality solutions while maintaining strict control over system resources.


    1. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. In ACM SIGGRAPH Papers. ACM, New York, 94.
    2. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. In ACM SIGGRAPH Papers. ACM, New York, 294–302.
    3. Agrawal, A., Raskar, R., Nayar, S. K., and Li, Y. 2005a. Removing photography artifacts using gradient projection and flash-exposure sampling. In ACM SIGGRAPH Papers. ACM, New York, 828–835.
    4. Agrawal, A. K., Chellappa, R., and Raskar, R. 2005b. An algebraic approach to surface reconstruction from gradient fields. In Proceedings of the International Conference on Computer Vision (ICCV). I. 174–181.
    5. Agrawal, A. K., Raskar, R., and Chellappa, R. 2006. What is the range of surface reconstructions from a gradient field? In Proceedings of the European Conference on Computer Vision (ECCV). I. 578–591.
    6. Axelsson, O. 1994. Iterative Solution Methods. Cambridge Universty Press, Cambridge, UK.
    7. Balmelli, L., Kovacevic, J., and Vetterli, M. 1999. Quadtrees for embedded surface visualization: Constraints and efficient data structures. In Proceedings of the IEEE International Conference on Image Processing (ICIP). 487–491.
    8. Berger, M. J. and Colella, P. 1989. Local adaptive mesh refinement for shock hydrodynamics. J. Comput. Phys. 82, 64–84.
    9. Bolitho, M., Kazhdan, M., Burns, R., and Hoppe, H. 2007. Multilevel streaming for out-of-core surface reconstruction. In Proceedings of the 5th Eurographics Symposium on Geometry Processing (SGP’07). Eurographics Association, 69–78.
    10. Bornemann, F. A. and Krause, R. 1996. Classical and cascadic multi- grid – a methodological comparison. In Proceedings of the 9th International Conference on Domain Decomposition Methods. Domain Decomposition Press, 64–71.
    11. Brandt, A. 1977. Multi-Level adaptive solutions to boundary-value problems. Math. Comput. 31, 138, 333–390.
    12. Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A Multigrid Tutorial, 2nd Ed. SIAM.
    13. Dorr, F. W. 1970. The direct solution of the discrete poisson equation on a rectangle. SIAM Rev. 12, 2, 248–263.
    14. Farbman, Z., Hoffer, G., Lipman, Y., Cohen-Or, D., and Lischinski, D. 2009. Coordinates for instant image cloning. In Proceedings of the 36th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’09). ACM, New York.
    15. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’02). ACM, New York, 249–256.
    16. Finlayson, G. D., Hordley, S. D., and Drew, M. S. 2002. Removing shadows from images. In Proceedings of the 7th European Conference on Computer Vision-Part IV (ECCV’02). Springer-Verlag, 823–836.
    17. GigaPan. Gigapan home page. http://www.gigapan.org/about.php.
    18. Gortler, S. and Cohen, M. 1995. Variational modeling with wavelets. In Proceedings of the Symposium on Interactive 3D Graphics. 35–42.
    19. Griebel, M. and Zumbusch, G. 1999. Parallel multigrid in an adaptive pde solver based on hashing and space-filling curves. Parall. Comput. 25, 7, 827–843.
    20. Hockney, R. W. 1965. A fast direct solution of Poisson’s equation using Fourier analysis. J. ACM 12, 1, 95–113.
    21. Horn, B. K. P. 1974. Determining lightness from an image. Comput. Grap Image Process 3, 1, 277–299.
    22. Jia, J., Sun, J., Tang, C.-K., and Shum, H.-Y. 2006. Drag-and-Drop pasting. In ACM SIGGRAPH Papers. ACM, New York, 631–637.
    23. Kazhdan, M. 2005. Reconstruction of solid models from oriented point sets. In Proceedings of the Eurographics Symposium on Geometry Processing. 73–82.
    24. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proceedings of the Eurographics Symposium on Geometry Processing. 61–70.
    25. Kazhdan, M. and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27, 3, 1–10.
    26. Kopf, J., Cohen, M. F., Lischinski, D., and Uyttendaele, M. 2007a. Joint bilateral upsampling. ACM Trans. Graph 26, 3, 96.
    27. Kopf, J., Uyttendaele, M.., Deussen, o., and Cohen, M. F. 2007b. Using space-filling curves for multi-dimensional indexing. In ACM SIGGRAPH Papers. ACM, New York, 93.
    28. Lawder, J. K. and King, P. J. H. 2000. Using space-filling curves for multi-dimensional indexing. Lecture Notes in Computer Science. Springer Verlag, 20–35.
    29. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain In Proceedings of the 8th European Conference on Computer Vision (ECCV’ 2004). Springer, 377–389.
    30. McCann, J. 2008. Recalling the single-FFT direct poisson solve. SIGGRAPH Posters. ACM, 71.
    31. McCann, J. and Pollard, N. S. 2008. Real-time gradient-domain painting. In ACM SIGGRAPH Papers. ACM, New York, 1–7.
    32. MegaPOV. Mega POV home page. http://megapov.inetart.net.
    33. NASA. NASA blue marble home page. http://earthobservatory.nasa.gov/Features/BlueMarble/.
    34. Niedermeier, R., Reinhardt, K., and Sanders, P. 1997. Towards optimal locality in meshindexings. In Proceedings of the Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol. 1279. Spinger, 364–375.
    35. Pascucci, V. and Frank, R. J. 2002. Hierarchical indexing for out-of-core access to multi-resolution data. In Hierarchical and Geometrical Methods in Scientific Visualization. Mathematics and Visualization. Springer, 225–241.
    36. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313–318.
    37. Ricker, P. M. 2008. A direct multigrid poisson solver for oct-tree adaptive meshes. Astrophy. J. Suppl. Series 176, 293–300.
    38. Sagan, H. 1994. Space-Filling Curves. Spinger-Verlag, Berlin.
    39. Simchony, T. and Chellappa, R. 1990. Direct analytical methods for solving Poisson equations in computer vision problems. IEEE Trans. Pattern Anal. Mach. Intell. 12, 435–446.
    40. Sun, J., Jia, J., Tang, C.-K., and Shum, H.-Y. 2004. Poisson matting. ACM Trans. Graph. 23, 3, 315–321.
    41. Szeliski, R. 2008. Locally adapted hierarchical basis preconditioning. ACM Trans. Graph. 27, 3, 1135–1143.
    42. Toledo, S. 1999. A survey of out-of-core algorithms in numerical linear algebra. In External Memory Algorithms. Dimacs Series Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Boston, MA, 161–179.
    43. Vitter, J. S. 2001. External memory algorithms and data structures: Dealing with massive data. ACM Comput. Surv. 33, 2, 209–271.
    44. Weiss, Y. 2001. Deriving intrinsic images from image sequences. In Proceedings of the International Conference on Computer Vision. 68–75.

ACM Digital Library Publication: