Streaming multigrid for gradient-domain operations on large images

ABSTRACT

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.

REFERENCES

• 1: Aseem Agarwala , Mira Dontcheva , Maneesh Agrawala , Steven Drucker , Alex Colburn , Brian Curless , David Salesin , Michael Cohen, Interactive digital photomontage, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 2: Aseem Agarwala, Efficient gradient-domain compositing using quadtrees, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 3: Amit Agrawal , Ramesh Raskar , Shree K. Nayar , Yuanzhen Li, Removing photography artifacts using gradient projection and flash-exposure sampling, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 4: Soonmin Bae , Sylvain Paris , Frédo Durand, Two-scale tone management for photographic look, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 5: Matthew Bolitho , Michael Kazhdan , Randal Burns , Hugues Hoppe, Multilevel streaming for out-of-core surface reconstruction, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 6: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 7: Brandt, A. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 333--390.
• 8: William L. Briggs , Van Emden Henson , Steve F. McCormick, A multigrid tutorial: second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 9: Christara, C., and Smith, B. 1997. Multigrid and multilevel methods for quadratic spline collocation. BIT 37, 4, 781--803.
• 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.
• 11: Raanan Fattal , Dani Lischinski , Michael Werman, Gradient domain high dynamic range compression, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 12: Graham D. Finlayson , Steven D. Hordley , Mark S. Drew, Removing Shadows from Images, Proceedings of the 7th European Conference on Computer Vision-Part IV, p.823-836, May 28-31, 2002
• 13: Fletcher, C. 1984. Computational Galerkin Methods. Springer.
• 14: Dominik Goddeke , Robert Strzodka , Jamaludin Mohd-Yusof , Patrick McCormick , Hilmar Wobker , Christian Becker , Stefan Turek, Using GPUs to improve multigrid solver performance on a cluster, International Journal of Computational Science and Engineering, v.4 n.1, p.36-55, November 2008 [doi>10.1504/IJCSE.2008.021111]
• 15: Nolan Goodnight , Cliff Woolley , Gregory Lewin , David Luebke , Greg Humphreys, A multigrid solver for boundary value problems using programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 16: Steven J. Gortler , Michael F. Cohen, Hierarchical and variational geometric modeling with wavelets, Proceedings of the 1995 symposium on Interactive 3D graphics, p.35-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199410]
• 17: Klaus Höllig , Ulrich Reif , Joachim Wipper, Weighted Extended B-Spline Approximation of Dirichlet Problems, SIAM Journal on Numerical Analysis, v.39 n.2, p.442-462, 2001 [doi>10.1137/S0036142900373208]
• 18: Horn, B. 1974. Determining lightness from an image. Computer Graphics and Image Processing 3, 277--299.
• 19: Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symposium on Geometry Processing, 73--82.
• 20: Johannes Kopf , Michael F. Cohen , Dani Lischinski , Matt Uyttendaele, Joint bilateral upsampling, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 21: Johannes Kopf , Matt Uyttendaele , Oliver Deussen , Michael F. Cohen, Capturing and viewing gigapixel images, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 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.
• 23: Frank Losasso , Frédéric Gibou , Ron Fedkiw, Simulating water and smoke with an octree data structure, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 24: James McCann , Nancy S. Pollard, Real-time gradient-domain painting, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 25: Patrick Pérez , Michel Gangnet , Andrew Blake, Poisson image editing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 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.
• 27: Szeliski, R., Uyttendaele, M., and Steedly, D. 2008. Fast Poisson blending using multi-splines. Tech. Rep. MSR-TR-2008-58, Microsoft Research.
• 28: Richard Szeliski, Locally adapted hierarchical basis preconditioning, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 29: Sivan Toledo, A survey of out-of-core algorithms in numerical linear algebra, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 30: Weiss, Y. 2001. Deriving intrinsic images from image sequences. In International Conference on Computer Vision, 68--75.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
      G.1.8 Partial Differential Equations
          Subjects: Multigrid and multilevel methods; Finite element methods

General Terms:
Algorithms, Design, Theory

Keywords:
B-spline finite elements, Poisson equation, gigapixel images, multi-level streaming, out-of-core multigrid solver