“Multigrid and multilevel preconditioners for computational photography”
Conference:
Type(s):
Title:
- Multigrid and multilevel preconditioners for computational photography
Session/Category Title: Image Processing
Presenter(s)/Author(s):
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.
References:
1. Agarwala, A., et al. 2004. Interactive digital photomontage. ACM Trans. on Graphics (SIGGRAPH 2004) 23, 3 (August), 292–300. Google ScholarDigital Library
2. Agarwala, A. 2007. Efficient gradient-domain compositing using quadtrees. ACM Trans. on Graphics (SIGGRAPH 2007) 26, 3 (August), 94:1–94:5. Google ScholarDigital Library
3. Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A Multigrid Tutorial, second ed. SIAM, Philadelphia. Google ScholarDigital Library
4. Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM. Google ScholarDigital Library
5. Farbman, Z., Fattal, R., Lischinski, D., and Szeliski, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Trans. on Graphics (SIGGRAPH 2008) 27, 3 (August). Google ScholarDigital Library
6. Farbman, Z., Hoffer, G., Lipman, Y., Cohen-Or, D., and Lischinski, D. 2009. Coordinates for instant image cloning. ACM Trans. on Graphics (SIGGRAPH 2009) 28, 3 (August). Google ScholarDigital Library
7. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Trans. on Graphics 21, 3 (July), 249–256. Google ScholarDigital Library
8. Fattal, R. 2009. Edge-avoiding wavelets and their applications. ACM Trans. on Graphics (SIGGRAPH 2009) 28, 3 (August). Google ScholarDigital Library
9. Gastal, E. S. L., and Oliveira, M. M. 2011. Domain transform for edge-aware image and video processing. ACM Trans. on Graphics (SIGGRAPH 2011) 30, 4 (July). Google ScholarDigital Library
10. Gortler, S. J., and Cohen, M. F. 1995. Hierarchical and variational geometric modeling with wavelets. In Symp. on Interactive 3D Graphics, 35–43. Google ScholarDigital Library
11. Jeschke, S., Cline, D., and Wonka, P. 2009. A GPU Laplacian solver for diffusion curves and Poisson image editing. ACM Trans. on Graphics (SIGGRAPH Asia 2009) 28, 5 (December). Google ScholarDigital Library
12. Kazhdan, M., Surendran, D., and Hoppe, H. 2010. Distributed gradient-domain processing of planar and spherical images. ACM Trans. on Graphics 29, 2 (April). Google ScholarDigital Library
13. Koutis, I., Miller, G. L., and Tolliver, D. 2009. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. In 5th Intl. Symp. on Visual Computing (ISVC09), Springer. Google ScholarDigital Library
14. Krishnan, D., and Szeliski, R. 2011. Multigrid and multilevel preconditioners for computational photography. Tech. Rep. NYU-TR-941, New York University, October.Google Scholar
15. Kushnir, D., Galun, M., and Brandt, A. 2010. Efficient multilevel eigensolvers with applications to data analysis tasks. IEEE Trans. PAMI 32, 8 (August), 1377–1391. Google ScholarDigital Library
16. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Trans. on Graphics 23, 3 (August), 689–694. Google ScholarDigital Library
17. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In Eighth European Conference on Computer Vision (ECCV 2004), Springer-Verlag, vol. IV, 377–389.Google Scholar
18. Levin, A., Lischinski, D., and Weiss, Y. 2008. A closed-form solution to natural image matting. IEEE Trans. PAMI 30, 2 (Feb.), 228–242. Google ScholarDigital Library
19. McAdams, A., Sifakis, E., and Teran, J. 2010. A parallel multigrid Poisson solver for fluids simulation on large grids. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 65–74. Google ScholarDigital Library
20. McCann, J., and Pollard, N. 2008. Real-time gradient domain painting. ACM Trans. on Graphics (SIGGRAPH 2008) 27, 3 (August). Google ScholarDigital Library
21. Napov, A., and Notay, Y. 2011. Algebraic analysis of aggregation-based multigrid. Numerical Linear Algebra with Applications 18, 3 (May), 539–564.Google ScholarCross Ref
22. Pentland, A. P. 1994. Interpolation using wavelet bases. IEEE Trans. PAMI 16, 4 (April), 410–414. Google ScholarDigital Library
23. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Trans. on Graphics (SIGGRAPH 2003) 22, 3 (July), 313–318. Google ScholarDigital Library
24. Roberts, A. 2001. Simple and fast multigrid solutions of Poisson’s equation using diagonally oriented grids. ANZIAM J. 43 (July), E1–E36.Google ScholarCross Ref
25. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, second ed. SIAM. Google ScholarDigital Library
26. Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. http://www.cs. berkeley.edu/~jrs/, August.Google Scholar
27. Szeliski, R., Uyttendaele, M., and Steedly, D. 2011. Fast Poisson blending using multi-splines. In Intl. Conf. on Computational Photography (ICCP 11).Google Scholar
28. Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Trans. PAMI 12, 6 (June), 513–528. Google ScholarDigital Library
29. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Trans. on Graphics (SIGGRAPH 2006) 25, 3 (August), 1135–1143. Google ScholarDigital Library
30. Terzopoulos, D. 1986. Image analysis using multigrid relaxation methods. IEEE Trans. PAMI 8, 2 (March), 129–139. Google ScholarDigital Library
31. Trottenberg, U., Oosterlee, C. W., and Schuller, A. 2000. Multigrid. Academic Press. Google ScholarDigital Library
32. Wang, H., Raskar, R., and Ahuja, N. 2004. Seamless video editing. Proceedings of the Intl. Conf. Patt. Recognition, 858–861. Google ScholarDigital Library
