research-article

Streaming multigrid for gradient-domain operations on large images

Authors:

Michael Kazhdan,

Hugues HoppeAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 27, Issue 3

Pages 1 - 10

https://doi.org/10.1145/1360612.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

Li YZhai WCao YZha Z(2023)Location-Free Camouflage Generation NetworkIEEE Transactions on Multimedia10.1109/TMM.2022.318925025(5234-5247)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TMM.2022.3189250
Petruzza SSumma BGooch ALaney CGoulden TSchreiner JCallahan SPascucci V(2023)Interactive Visualization and Portable Image Blending of Massive Aerial Image Mosaics2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386428(3365-3370)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386428
Ferreira HGastal E(2023)Efficient 2D Tikhonov smoothness regularization with recursive filteringPattern Recognition Letters10.1016/j.patrec.2023.07.001175(95-103)Online publication date: Nov-2023
https://doi.org/10.1016/j.patrec.2023.07.001
Show More Cited By

Index Terms

Streaming multigrid for gradient-domain operations on large images

Recommendations

Out-of-core multigrid solver for streaming meshes

We present an out-of-core multigrid for solving the Poisson equation defined over gigantic meshes. This enables gradient-domain operations on out-of-core meshes with irregular connectivity. Taking a streaming mesh and boundary constraints as input, our ...
Out-of-core multigrid solver for streaming meshes
SIGGRAPH Asia '09: ACM SIGGRAPH Asia 2009 papers

We present an out-of-core multigrid for solving the Poisson equation defined over gigantic meshes. This enables gradient-domain operations on out-of-core meshes with irregular connectivity. Taking a streaming mesh and boundary constraints as input, our ...
Sixth order compact scheme combined with multigrid method and extrapolation technique for 2D poisson equation

We develop a sixth order finite difference discretization strategy to solve the two dimensional Poisson equation, which is based on the fourth order compact discretization, multigrid method, Richardson extrapolation technique, and an operator based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 27, Issue 3

August 2008

844 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1360612

Issue’s Table of Contents

Copyright © 2008 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2008

Published in TOG Volume 27, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

107
Total Citations
View Citations
1,239
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YZhai WCao YZha Z(2023)Location-Free Camouflage Generation NetworkIEEE Transactions on Multimedia10.1109/TMM.2022.318925025(5234-5247)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TMM.2022.3189250
Petruzza SSumma BGooch ALaney CGoulden TSchreiner JCallahan SPascucci V(2023)Interactive Visualization and Portable Image Blending of Massive Aerial Image Mosaics2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386428(3365-3370)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386428
Ferreira HGastal E(2023)Efficient 2D Tikhonov smoothness regularization with recursive filteringPattern Recognition Letters10.1016/j.patrec.2023.07.001175(95-103)Online publication date: Nov-2023
https://doi.org/10.1016/j.patrec.2023.07.001
Wang SLv WZhao XZhang XSu JZeng L(2023)Refined-mask guided multi-stream blending networkMultimedia Tools and Applications10.1007/s11042-023-17793-683:19(56445-56462)Online publication date: 12-Dec-2023
https://doi.org/10.1007/s11042-023-17793-6
Saad NDahalan ASaudi A(2022)Modified Poisson compositing technique on skewed gridAIMS Mathematics10.3934/math.20221247:2(2176-2194)Online publication date: 2022
https://doi.org/10.3934/math.2022124
Ferreira HGastal E(2022)Recursive filtering 2D Tikhonov regularization2022 35th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI)10.1109/SIBGRAPI55357.2022.9991783(168-173)Online publication date: 24-Oct-2022
https://doi.org/10.1109/SIBGRAPI55357.2022.9991783
Wang XZhu Y(2022)A Quadtree Based Piecewise Poisson Seamless Composition Algorithm for Image Stitching2022 International Conference on Informatics, Networking and Computing (ICINC)10.1109/ICINC58035.2022.00049(209-213)Online publication date: Oct-2022
https://doi.org/10.1109/ICINC58035.2022.00049
Xu KHao XLin J(2022)Automated fibre placement path generation for complex surfaces via digital image deconvolution algorithmComposites Part A: Applied Science and Manufacturing10.1016/j.compositesa.2022.107246163(107246)Online publication date: Dec-2022
https://doi.org/10.1016/j.compositesa.2022.107246
Yuan LCao HZhang YLi KLu PYue Yde Supinski BHall MGamblin T(2021)Temporal vectorization for stencilsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3458817.3476149(1-13)Online publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1145/3458817.3476149
Liu HZhang JBen-Chen MJacobson A(2021)Surface multigrid via intrinsic prolongationACM Transactions on Graphics10.1145/3450626.345976840:4(1-13)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459768
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents