Streaming multigrid for gradient-domain operations on large images
ACM Trans. Graphics (SIGGRAPH), 27(3), 2008.
Perform k multigrid V-cycles in just k-1 streaming passes over the
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.
In later work, we
the solver computation over a cluster to handle terapixel images,
and generalized the approach to operate over
ACM Copyright Notice
Copyright by the Association for Computing Machinery, Inc. Permission to make digital or
hard copies of part or all of this work for personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the
full citation on the first page. Copyrights for components of this work owned by others than ACM must be
honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to
redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications
Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be
found at ACM's Digital Library http://www.acm.org/dl/.