Richard Szeliski
ABSTRACT
This paper develops locally adapted hierarchical basis functions for effectively preconditioning large optimization problems that arise in computer graphics applications such as tone mapping, gradient-domain blending, colorization, and scattered data interpolation. By looking at the local structure of the coefficient matrix and performing a recursive set of variable eliminations, combined with a simplification of the resulting coarse level problems, we obtain bases better suited for problems with inhomogeneous (spatially varying) data, smoothness, and boundary constraints. Our approach removes the need to heuristically adjust the optimal number of preconditioning levels, significantly outperforms previously proposed approaches, and also maps cleanly onto data-parallel architectures such as modern GPUs.
Supplemental Material
- Agarwala, A., et al. 2004. Interactive digital photomontage. ACM Transactions on Graphics 23, 3 (August), 292--300. Google Scholar
Digital Library
- Bathe, K.-J., and Wilson, E. L. 1976. Numerical Methods in Finite Element Analysis. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.Google Scholar
- Bolz, J., et al. 2003. Sparse matrix solvers on the GPU: Conjugate gradients and multigrid. ACM Transactions on Graphics 22, 3 (July), 917--924. Google ScholarDigital Library
- Brand, C. W. 1992. An incomplete factorization preconditioning using repeated red-black ordering. Numer. Math. 61, 433--454.Google ScholarDigital Library
- Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A Multigrid Tutorial, second ed. Society for Industrial and Applied Mathematics, Philadelphia. Google ScholarDigital Library
- Ciarlet Jr., P. 1994. Repeated red-black ordering: a new approach. Numerical Algorithms 7, 295--324.Google ScholarCross Ref
- Crowley, J. L., and Stern, R. M. 1984. Fast computation of the difference of low-pass transform. IEEE Transactions on Pattern Analysis and Machine Intelligence 6, 2 (March), 212--222.Google Scholar
- Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. Clarendon Press, Oxford. Google ScholarDigital Library
- Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Transactions on Graphics (TOG) 21, 3, 249--256. Google ScholarDigital Library
- Feilner, M., et al. 2005. An orthogonal family of quincunx wavelets with continuously adjustable order. IEEE Transactions on Image Processing 14, 4 (April), 499--520. Google ScholarDigital Library
- Golub, G., and Van Loan, C. F. 1996. Matrix Computation, third edition. The John Hopkins University Press, Baltimore and London. Google ScholarDigital Library
- Gortler, S. J., and Cohen, M. F. 1995. Hierarchical and variational geometric modeling with wavelets. In Symposium on Interactive 3D Graphics, 35--43. Google ScholarDigital Library
- Gremban, K. D. 1996. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University. CMU-CS-96-123.Google Scholar
- Kobbelt, L., and Schröder, P. 1998. A multiresolution framework for variational subdivision. ACM Transactions on Graphics 17, 4 (October), 209--237. Google ScholarDigital Library
- Lai, S.-H., and Vemuri, B. C. 1997. Physically based adaptive preconditioning for early vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 19, 6 (June), 594--607. Google ScholarDigital Library
- Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Transactions on Graphics 23, 3 (August), 689--694. Google ScholarDigital Library
- 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, Prague, vol. IV, 377--389.Google Scholar
- Lischinski, D., Farbman, Z., Uytendaelle, M., and Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. ACM Transactions on Graphics 25, 3 (August). Google ScholarDigital Library
- Notay, Y., and Amar, Z. O. 1997. A nearly optimal preconditioning based on recursive red-black ordering. Numerical Linear Alg. Appl. 4, 369--391.Google ScholarCross Ref
- Pentland, A. P. 1994. Interpolation using wavelet bases. IEEE Transactions on Pattern Analysis and Machine Intelligence 16, 4 (April), 410--414. Google ScholarDigital Library
- Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics 22, 3 (July), 313--318. Google ScholarDigital Library
- Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, second ed. SIAM. Google ScholarDigital Library
- Schröder, P., and Sweldens, W. 1995. Spherical wavelets: Efficiently representing functions on the sphere. In Proceedings of SIGGRAPH 95, Computer Graphics Proceedings, Annual Conference Series, 161--172. Google ScholarDigital Library
- Sweldens, W. 1997. The lifting scheme: A construction of second generation wavelets. SIAM J. Math. Anal. 29, 2, 511--546. Google ScholarDigital Library
- Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 6 (June), 513--528. Google ScholarDigital Library
- Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. Tech. Rep. MSR-TR-2006-38, Microsoft Research, May.Google Scholar
- Terzopoulos, D., and Witkin, A. 1988. Physically-based models with rigid and deformable components. IEEE Computer Graphics and Applications 8, 6, 41--51. Google ScholarDigital Library
- Terzopoulos, D. 1983. Multilevel computational processes for visual surface reconstruction. Computer Vision, Graphics, and Image Processing 24, 52--96.Google ScholarCross Ref
- Terzopoulos, D. 1986. Regularization of inverse visual problems involving discontinuities. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8, 4 (July), 413--424. Google ScholarDigital Library
- Yaou, M.-H., and Chang, W.-T. 1994. Fast surface interpolation using multiresolution wavelets. IEEE Transactions on Pattern Analysis and Machine Intelligence 16, 7 (July), 673--689. Google ScholarDigital Library
- Yserentant, H. 1986. On the multi-level splitting of finite element spaces. Numerische Mathematik 49, 379--412. Google ScholarDigital Library
- Zhang, L., et al. 2002. Single view modeling of free-form scenes. Journal of Visualization and Computer Animation 13, 4, 225--235.Google ScholarCross Ref
Index Terms
- Locally adapted hierarchical basis preconditioning
Recommendations
Locally adapted hierarchical basis preconditioning
This paper develops locally adapted hierarchical basis functions for effectively preconditioning large optimization problems that arise in computer graphics applications such as tone mapping, gradient-domain blending, colorization, and scattered data ...
Multigrid and multilevel preconditioners for computational photography
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 ...
Multigrid and multilevel preconditioners for computational photography
SA '11: Proceedings of the 2011 SIGGRAPH Asia ConferenceThis 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 ...
Comments