“Streaming multigrid for gradient-domain operations on large images” by Kazhdan and Hoppe

  • ©Michael Kazhdan and Hugues Hoppe




    Streaming multigrid for gradient-domain operations on large images



    We introduce a new tool to solve the large linear systems arising from gradient-domain image processing. Specifically, we develop a streaming multigrid solver, which needs just two sequential passes over out-of-core data. This fast solution is enabled by a combination of three techniques: (1) use of second-order finite elements (rather than traditional finite differences) to reach sufficient accuracy in a single V-cycle, (2) temporally blocked relaxation, and (3) multi-level streaming to pipeline the restriction and prolongation phases into single streaming passes. A key contribution is the extension of the B-spline finite-element method to be compatible with the forward-difference gradient representation commonly used with images. Our streaming solver is also efficient for in-memory images, due to its fast convergence and excellent cache behavior. Remarkably, it can outperform spatially adaptive solvers that exploit application-specific knowledge. We demonstrate seamless stitching and tone-mapping of gigapixel images in about an hour on a notebook PC.


    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 (SIGGRAPH ’04), 294–302. Google ScholarDigital Library
    2. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Transactions on Graphics (SIGGRAPH ’07). Google ScholarDigital Library
    3. 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 (SIGGRAPH ’05), 828–835. Google ScholarDigital Library
    4. Bae, S., Paris, S., and Durand, F. 2006. Two-scale tone management for photographic look. ACM Transactions on Graphics (SIGGRAPH ’06). Google ScholarDigital Library
    5. Bolitho, M., Kazhdan, M., Burns, R., and Hoppe, H. 2007. Multilevel streaming for out-of-core surface reconstruction. In Symposium on Geometry Processing, 69–78. 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 (SIGGRAPH ’03), 917–924. Google ScholarDigital Library
    7. Brandt, A. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 333–390.Google ScholarCross Ref
    8. Briggs, W., Henson, V., and McCormick, S. 2000. A Multigrid Tutorial. Society for Industrial and Applied Mathematics. Google ScholarDigital Library
    9. Christara, C., and Smith, B. 1997. Multigrid and multilevel methods for quadratic spline collocation. BIT 37, 4, 781–803.Google ScholarDigital Library
    10. Douglas, C., Hu, J., Kowarschik, M., Rüde, U., and Weiss, C. 2000. Cache optimization for structured and unstructured grid multigrid. Electronic Transactions on Numerical Analysis 10, 21–40.Google Scholar
    11. Fattal, R., Lischinksi, D., and Werman, M. 2002. Gradient domain high dynamic range compression. In ACM SIGGRAPH, 249–256. Google ScholarDigital Library
    12. Finlayson, G., Hordley, S., and Drew, M. 2002. Removing shadows from images. In European Conference on Computer Vision, 129–132. Google ScholarDigital Library
    13. Fletcher, C. 1984. Computational Galerkin Methods. Springer.Google Scholar
    14. Göddeke, D., Strzodka, R., Mohd-Yusof, J., McCormick, P., Wobker, H., Becker, C., and Turek, S. 2008. Using GPUs to improve multigrid solver performance on a cluster. Intnl. J. of Computational Science and Engineering. Google ScholarDigital Library
    15. Goodnight, N., Woolley, C., Lewin, G., Luebke, D., and Humphreys, G. 2003. A multigrid solver for boundary value problems using programmable graphics hardware. In Proc. of Graphics Hardware, 102–111. Google ScholarDigital Library
    16. Gortler, S., and Cohen, M. 1995. Variational modeling with wavelets. In Symposium on Interactive 3D Graphics, 35–42. Google ScholarDigital Library
    17. Höllig, K., Reif, U., and Wipper, J. 2001. Weighted extended B-spline approximation of Dirichlet problems. SIAM Journal on Numerical Analysis 39, 442–462. Google ScholarDigital Library
    18. Horn, B. 1974. Determining lightness from an image. Computer Graphics and Image Processing 3, 277–299.Google ScholarCross Ref
    19. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, 73–82. Google ScholarDigital Library
    20. Kopf, J., Cohen, M., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM Transactions on Graphics (SIGGRAPH ’07). Google ScholarDigital Library
    21. Kopf, J., Uyttendaele, M., Deussen, O., and Cohen, M. 2007. Capturing and viewing gigapixel images. ACM Transactions on Graphics (SIGGRAPH ’07). Google ScholarDigital Library
    22. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In European Conference on Computer Vision, 377–389.Google Scholar
    23. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Transactions on Graphics (SIGGRAPH ’04), 457–462. Google ScholarDigital Library
    24. McCann, J., and Pollard, N. 2008. Real-time gradient-domain painting. ACM Transactions on Graphics (SIGGRAPH ’08). Google ScholarDigital Library
    25. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics (SIGGRAPH ’03), 313–318. Google ScholarDigital Library
    26. Pfeifer, C. 1963. Data flow and storage allocation for the PDQ-5 program on the Philco-2000. Communications of the ACM 6, 7, 365–366.Google Scholar
    27. Szeliski, R., Uyttendaele, M., and Steedly, D. 2008. Fast Poisson blending using multi-splines. Tech. Rep. MSR-TR-2008-58, Microsoft Research.Google Scholar
    28. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Transactions on Graphics (SIGGRAPH ’06), 1135–1143. Google ScholarDigital Library
    29. Toledo, S. 1999. A survey of out-of-core algorithms in numerical linear algebra. In External Memory Algorithms and Visualization, J. Abello and J. S. Vitter, Eds. American Mathematical Society Press, Providence, RI, 161–180. Google ScholarDigital Library
    30. Weiss, Y. 2001. Deriving intrinsic images from image sequences. In International Conference on Computer Vision, 68–75.Google ScholarCross Ref

ACM Digital Library Publication: