research-article

Streaming multigrid for gradient-domain operations on large images

Authors:

Michael Kazhdan,

Hugues HoppeAuthors Info & Claims

SIGGRAPH '08: ACM SIGGRAPH 2008 papers

Article No.: 21, Pages 1 - 10

https://doi.org/10.1145/1399504.1360620

Published: 01 August 2008 Publication History

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.

Supplementary Material

MOV File (a21-kazhdan.mov)

Download
20.54 MB

References

[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.

Digital Library

[2]

Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Transactions on Graphics (SIGGRAPH '07).

Digital 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.

Digital Library

[4]

Bae, S., Paris, S., and Durand, F. 2006. Two-scale tone management for photographic look. ACM Transactions on Graphics (SIGGRAPH '06).

Digital 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.

Digital 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.

Digital Library

[7]

Brandt, A. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 333--390.

[8]

Briggs, W., Henson, V., and McCormick, S. 2000. A Multigrid Tutorial. Society for Industrial and Applied Mathematics.

Digital Library

[9]

Christara, C., and Smith, B. 1997. Multigrid and multilevel methods for quadratic spline collocation. BIT 37, 4, 781--803.

Digital 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.

[11]

Fattal, R., Lischinksi, D., and Werman, M. 2002. Gradient domain high dynamic range compression. In ACM SIGGRAPH, 249--256.

Digital Library

[12]

Finlayson, G., Hordley, S., and Drew, M. 2002. Removing shadows from images. In European Conference on Computer Vision, 129--132.

Digital Library

[13]

Fletcher, C. 1984. Computational Galerkin Methods. Springer.

[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.

Digital 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.

Digital Library

[16]

Gortler, S., and Cohen, M. 1995. Variational modeling with wavelets. In Symposium on Interactive 3D Graphics, 35--42.

Digital 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.

Digital Library

[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.

Digital Library

[20]

Kopf, J., Cohen, M., Lischinski, D., and Uyttendaele, M. 2007. Joint bilateral upsampling. ACM Transactions on Graphics (SIGGRAPH '07).

Digital Library

[21]

Kopf, J., Uyttendaele, M., Deussen, O., and Cohen, M. 2007. Capturing and viewing gigapixel images. ACM Transactions on Graphics (SIGGRAPH '07).

Digital 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.

[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.

Digital Library

[24]

McCann, J., and Pollard, N. 2008. Real-time gradient-domain painting. ACM Transactions on Graphics (SIGGRAPH '08).

Digital Library

[25]

Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics (SIGGRAPH '03), 313--318.

Digital 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.

[27]

Szeliski, R., Uyttendaele, M., and Steedly, D. 2008. Fast Poisson blending using multi-splines. Tech. Rep. MSR-TR-2008-58, Microsoft Research.

[28]

Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Transactions on Graphics (SIGGRAPH '06), 1135--1143.

Digital 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.

Digital Library

[30]

Weiss, Y. 2001. Deriving intrinsic images from image sequences. In International Conference on Computer Vision, 68--75.

Cited By

Zhang LWen TShi J(2020)Deep Image Blending2020 IEEE Winter Conference on Applications of Computer Vision (WACV)10.1109/WACV45572.2020.9093632(231-240)Online publication date: Mar-2020
https://doi.org/10.1109/WACV45572.2020.9093632
Jiang ZGong XFei H(2017)Color-luminance adjustment for image cloning based on mean-value coordinates2017 International Conference on Security, Pattern Analysis, and Cybernetics (SPAC)10.1109/SPAC.2017.8304287(262-267)Online publication date: Dec-2017
https://doi.org/10.1109/SPAC.2017.8304287
Magdics MSzirmay-Kalos LNeumann L(2017)Gradient-Domain PET Reconstruction2017 IEEE Nuclear Science Symposium and Medical Imaging Conference (NSS/MIC)10.1109/NSSMIC.2017.8532694(1-5)Online publication date: Oct-2017
https://doi.org/10.1109/NSSMIC.2017.8532694
Show More Cited By

Index Terms

Streaming multigrid for gradient-domain operations on large images

Recommendations

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 ...
Edge subdivision schemes and the construction of smooth vector fields
SIGGRAPH '06: ACM SIGGRAPH 2006 Papers

Vertex- and face-based subdivision schemes are now routinely used in geometric modeling and computational science, and their primal/dual relationships are well studied. In this paper, we interpret these schemes as defining bases for discrete ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '08: ACM SIGGRAPH 2008 papers

August 2008

887 pages

ISBN:9781450301121

DOI:10.1145/1399504

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part 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, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGGRAPH '08

Sponsor:

SIGGRAPH

SIGGRAPH '08: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 11 - 15, 2008

California, Los Angeles

Acceptance Rates

SIGGRAPH '08 Paper Acceptance Rate 90 of 518 submissions, 17%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
1,169
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LWen TShi J(2020)Deep Image Blending2020 IEEE Winter Conference on Applications of Computer Vision (WACV)10.1109/WACV45572.2020.9093632(231-240)Online publication date: Mar-2020
https://doi.org/10.1109/WACV45572.2020.9093632
Jiang ZGong XFei H(2017)Color-luminance adjustment for image cloning based on mean-value coordinates2017 International Conference on Security, Pattern Analysis, and Cybernetics (SPAC)10.1109/SPAC.2017.8304287(262-267)Online publication date: Dec-2017
https://doi.org/10.1109/SPAC.2017.8304287
Magdics MSzirmay-Kalos LNeumann L(2017)Gradient-Domain PET Reconstruction2017 IEEE Nuclear Science Symposium and Medical Imaging Conference (NSS/MIC)10.1109/NSSMIC.2017.8532694(1-5)Online publication date: Oct-2017
https://doi.org/10.1109/NSSMIC.2017.8532694
Vallet BLelégard L(2013)Partial iterates for symmetrizing non-parametric color correctionISPRS Journal of Photogrammetry and Remote Sensing10.1016/j.isprsjprs.2013.05.00582(93-101)Online publication date: Aug-2013
https://doi.org/10.1016/j.isprsjprs.2013.05.005
Viola FFitzgibbon ACipolla R(2012)A unifying resolution-independent formulation for early vision2012 IEEE Conference on Computer Vision and Pattern Recognition10.1109/CVPR.2012.6247713(494-501)Online publication date: Jun-2012
https://doi.org/10.1109/CVPR.2012.6247713
Li PSun HHuang CShen JNie Y(2012)VEA 2012Computers and Graphics10.1016/j.cag.2012.07.00436:8(1048-1059)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1016/j.cag.2012.07.004
Li PSun HSheng BShen J(2012)Image stylization with enhanced structure on GPUScience China Information Sciences10.1007/s11432-012-4558-y55:5(1093-1105)Online publication date: 14-Mar-2012
https://doi.org/10.1007/s11432-012-4558-y
Li PSun HHuang CShen JNie YLiu ZJorge JPan ZZhang XAu ODong W(2011)Efficient image/video retexturing using parallel bilateral gridsProceedings of the 10th International Conference on Virtual Reality Continuum and Its Applications in Industry10.1145/2087756.2087774(131-140)Online publication date: 11-Dec-2011
https://dl.acm.org/doi/10.1145/2087756.2087774
Chuang MKazhdan M(2011)Interactive and anisotropic geometry processing using the screened Poisson equationACM Transactions on Graphics10.1145/2010324.196495230:4(1-10)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.1145/2010324.1964952
Dick CGeorgii JWestermann R(2011)A Hexahedral Multigrid Approach for Simulating Cuts in Deformable ObjectsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2010.26817:11(1663-1675)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1109/TVCG.2010.268
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents