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

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