Distributed gradient-domain processing of planar and spherical images

Abstract

Gradient-domain processing is widely used to edit and combine images. In this article we extend the framework in two directions. First, we adapt the gradient-domain approach to operate on a spherical domain, to enable operations such as seamless stitching, dynamic-range compression, and gradient-based sharpening over spherical imagery. An efficient streaming computation is obtained using a new spherical parameterization with bounded distortion and localized boundary constraints. Second, we design a distributed solver to efficiently process large planar or spherical images. The solver partitions images into bands, streams through these bands in parallel within a networked cluster, and schedules computation to hide the necessary synchronization latency. We demonstrate our contributions on several datasets including the Digitized Sky Survey, a terapixel spherical scan of the night sky.

References

1. Adams, M. 2001. A distributed memory unstructured Gauss-Seidel algorithm for multigrid smoothers. In Proceedings of the ACM/IEEE Super Computer Conference.
2. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Trans. Graph.
3. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., and Cohen, M. 2004. Interactive digital photomontage. ACM Trans. Graph. 294--302.
4. Agrawal, A. and Raskar, R. 2007. Gradient domain manipulation techniques in vision and graphics. ICCV 2007 Course.
5. Agrawal, A., Raskar, R., Nayar, S. K., and Li, Y. 2005. Removing photography artifacts using gradient projection and flash-exposure sampling. ACM Trans. Graph. 828--835.
6. Bhat, P., Curless, B., Cohen, M., and Zitnick, L. 2008. Fourier analysis of the 2D screened Poisson equation for gradient domain problems. In Proceedings of the European Conference on Computer Vision. 114--128.
7. Briggs, W., Henson, V., and McCormick, S. 2000. A Multigrid Tutorial. Society for Industrial and Applied Mathematics.
8. Chow, E., Falgout, R., Hu, J., Tuminaro, R., and Yang, U. 2005. A survey of parallelization techniques for multigrid solvers. In Frontiers of Parallel Processing For Scientific Computing. SIAM.
9. Christara, C. and Smith, B. 1997. Multigrid and multilevel methods for quadratic spline collocation. BIT 37, 4, 781--803.
10. DSS. 2007. Digitized Sky Survey. http://archive.stsci.edu/dss/.
11. Fattal, R., Lischinksi, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Trans. Graph. 249--256.
12. Fekete, G. 1990. Rendering and managing spherical data with sphere quadtrees. In Proceedings of the 1st Conference on Visualization (VIS'90). 176--186.
13. Finlayson, G., Hordley, S., and Drew, M. 2002. Removing shadows from images. In Proceedings of the European Conference on Computer Vision. 129--132.
14. Fu, W., Wan, L., Wong, T., and Leung, C. 2009. The rhombic dodecahedron map: An efficient scheme for encoding panoramic video. IEEE Trans. Multimedia 11, 4, 634--644.
15. Google. 2008. Google Earth. http://earth.google.com/.
16. Górski, K., Hivon, E., Banday, A., Wandelt, B., Hansen, F., Reinecke, M., and Bartelmann, M. 2005. HEALPix: A framework for high-resolution discretization and fast analysis of data distributed on the sphere. Astrophys. J. 622, 759--771.
17. Horn, B. 1974. Determining lightness from an image. Comput. Graph. Image Proces. 3, 277--299.
18. Kazhdan, M. and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27.
19. Kopf, J., Uyttendaele, M., Deussen, O., and Cohen, M. 2007. Capturing and viewing gigapixel images. ACM Trans. Graph.
20. Kunszt, P., Szalay, A., and Thakar, A. 2001. The hierarchical triangular mesh. In Proceedings of the MPA/ESO/MPE Workshop (Mining the Sky). 631--637.
21. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In Proceedings of the European Conference on Computer Vision. 377--389.
22. McCann, J. 2008. Recalling the single-FFT direct Poisson solve. In SIGGRAPH Sketch. ACM.
23. McCann, J. and Pollard, N. 2008. Real-time gradient-domain painting. ACM Trans. Graph. 27.
24. Microsoft. 2008. Microsoft Virtual Earth. http://www.microsoft.com/virtualearth/.
25. Nabben, R. 2003. Comparisons between multiplicative and additive Schwarz iterations in domain decomposition methods. Numer. Math. 95, 145--162.
26. Orzan, A., Bousseau, A., Winnemöller, H., Barla, P., Thollot, J., and Salesin, D. 2008. Diffusion curves: A vector representation for smooth-shaded images. ACM Trans. Graph. 27.
27. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. Graph., 313--318.
28. Praun, E. and Hoppe, H. 2003. Spherical parametrization and remeshing. ACM Trans. Graph., 340--349.
29. Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. 2007. Numerical Recipes, 3rd Ed. Cambridge.
30. Schröder, P. and Sweldens, W. 1995. Spherical wavelets: Efficiently representing functions on the sphere. In ACM SIGGRAPH Conference Proceedings. 161--172.
31. Shum, H. and Szeliski, R. 2000. Systems and experiment paper: Construction of panoramic mosaics with global and local alignment. Int. J. Comput. Vision 36, 101--130.
32. Smith, B., Bjorstad, P., and Gropp, W. 2004. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, Cambridge, UK.
33. Stookey, J., Xie, Z., Cutler, B., Franklin, W., Tracy, D., and Andrade, M. 2008. Parallel ODETLAP for terrain compression and reconstruction. In Proceedings of the ACM International Conference on Advances in Geographic Information Systems (GIS).
34. Szeliski, R. and Shum, H. 1997. Creating full view panoramic image mosaics and environment maps. In ACM SIGGRAPH Conference Proceedings. 251--258.
35. Szyld, D. and Frommer, A. 1998. Weighted max norms, splittings, and overlapping additive Schwarz iterations. Numer. Math. 83, 259--278.
36. Wallin, D., Löf, H., Hagersten, E., and Holmgren, S. 2006. Multigrid and Gauss-Seidel smoothers revisited: Parallelization on chip multiprocessors. In Proceedings of the ACM International Conference on Super Computing (ICS'06).
37. Weiss, Y. 2001. Deriving intrinsic images from image sequences. In Proceedings of the International Conference on Computer Vision. 68--75.
38. Weyrich, T., Deng, J., Barnes, C., Rusinkiewicz, S., and Finkelstein, A. 2007. Digital bas-relief from 3D scenes. ACM Trans. Graph. 26.
39. WWT. 2008. WorldWide Telescope. http://www.worldwidetelescope.org.
40. Xu, J. 1992. Iterative methods by space decomposition and subspace correction. SIAM Rev. 34, 581--613.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision tasks