Locally Adapted Hierarchical Basis Preconditioning

Richard Szeliski

Abstract

This paper develops locally adapted hierarchical basis functions for effectively preconditioning large optimization problems that arise in computer vision, computer graphics, and computational photography applications such as surface interpolation, optic flow, tone mapping, gradient-domain blending, and colorization. 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 previous approaches, and also maps cleanly onto data-parallel architectures such as modern GPUs. [ Errata in (8) and (9) fixed October, 2007 ]

Details

Publication typeTechReport
NumberMSR-TR-2006-38
Pages37
InstitutionMicrosoft Research
> Publications > Locally Adapted Hierarchical Basis Preconditioning