“Locally adapted hierarchical basis preconditioning” by Szeliski

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.

1. Agarwala, A., et al. 2004. Interactive digital photomontage. ACM Transactions on Graphics 23, 3 (August), 292–300. Google ScholarDigital Library
2. Bathe, K.-J., and Wilson, E. L. 1976. Numerical Methods in Finite Element Analysis. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.Google Scholar
3. 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
4. Brand, C. W. 1992. An incomplete factorization preconditioning using repeated red-black ordering. Numer. Math. 61, 433–454.Google ScholarDigital Library
5. 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
6. Ciarlet Jr., P. 1994. Repeated red-black ordering: a new approach. Numerical Algorithms 7, 295–324.Google ScholarCross Ref
7. 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
8. Duff, I. S., Erisman, A. M., and Reid, J. K. 1986. Direct Methods for Sparse Matrices. Clarendon Press, Oxford. Google ScholarDigital Library
9. 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
10. 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
11. Golub, G., and Van Loan, C. F. 1996. Matrix Computation, third edition. The John Hopkins University Press, Baltimore and London. Google ScholarDigital Library
12. 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
13. Gremban, K. D. 1996. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University. CMU-CS-96-123.Google Scholar
14. 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
15. 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
16. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Transactions 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, Prague, vol. IV, 377–389.Google Scholar
18. 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
19. 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
20. Pentland, A. P. 1994. Interpolation using wavelet bases. IEEE Transactions on Pattern Analysis and Machine Intelligence 16, 4 (April), 410–414. Google ScholarDigital Library
21. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics 22, 3 (July), 313–318. Google ScholarDigital Library
22. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, second ed. SIAM. Google ScholarDigital Library
23. 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
24. Sweldens, W. 1997. The lifting scheme: A construction of second generation wavelets. SIAM J. Math. Anal. 29, 2, 511–546. Google ScholarDigital Library
25. 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
26. Szeliski, R. 2006. Locally adapted hierarchical basis preconditioning. Tech. Rep. MSR-TR-2006-38, Microsoft Research, May.Google Scholar
27. 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
28. Terzopoulos, D. 1983. Multilevel computational processes for visual surface reconstruction. Computer Vision, Graphics, and Image Processing 24, 52–96.Google ScholarCross Ref
29. 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
30. 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
31. Yserentant, H. 1986. On the multi-level splitting of finite element spaces. Numerische Mathematik 49, 379–412. Google ScholarDigital Library
32. 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