Multigrid and multilevel preconditioners for computational photography
Authors:
Open Access
- 12 December 2011
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 30 (6) , 1-10
Abstract
This paper unifies multigrid and multilevel (hierarchical) preconditioners, two widely-used approaches for solving computational photography and other computer graphics simulation problems. It provides detailed experimental comparisons of these techniques and their variants, including an analysis of relative computational costs and how these impact practical algorithm performance. We derive both theoretical convergence rates based on the condition numbers of the systems and their preconditioners, and empirical convergence rates drawn from real-world problems. We also develop new techniques for sparsifying higher connectivity problems, and compare our techniques to existing and newly developed variants such as algebraic and combinatorial multigrid. Our experimental results demonstrate that, except for highly irregular problems, adaptive hierarchical basis function preconditioners generally outperform alternative multigrid techniques, especially when computational complexity is taken into account.Keywords
This publication has 23 references indexed in Scilit:
- Domain transform for edge-aware image and video processingACM Transactions on Graphics, 2011
- Algebraic analysis of aggregation-based multigridNumerical Linear Algebra with Applications, 2010
- Distributed gradient-domain processing of planar and spherical imagesACM Transactions on Graphics, 2010
- A GPU Laplacian solver for diffusion curves and Poisson image editingACM Transactions on Graphics, 2009
- Edge-avoiding wavelets and their applicationsACM Transactions on Graphics, 2009
- Real-time gradient-domain paintingACM Transactions on Graphics, 2008
- Edge-preserving decompositions for multi-scale tone and detail manipulationACM Transactions on Graphics, 2008
- Poisson image editingACM Transactions on Graphics, 2003
- Interpolation using wavelet basesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1994
- Fast surface interpolation using hierarchical basis functionsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990