Patent Number: 7,822,289

Title: Locally adapted hierarchical basis preconditioning

Abstract: A "Finite Element Preconditioner" provides locally adapted hierarchical basis functions for preconditioning large data optimization problems. For example, a few of the many typical graphics applications that make use of iterative optimization solutions include tone mapping, gradient domain blending, colorization, and scattered data interpolation. Preconditioning image data for such optimization problems allows those image optimization problems to be solved using less computational overhead and therefore to produce better quality image outputs with less computational overhead. The Finite Element Preconditioner evaluates data, such as image data, to adapt hierarchical basis functions to inhomogeneous problems for preconditioning large optimization problems. Specifically, the Finite Element Preconditioner evaluates the local structure of a coefficient matrix derived from the data and performs a recursive set of variable eliminations, combined with a simplification of the resulting coarse level problems to obtain bases better suited for problems with inhomogeneous (spatially varying) data, smoothness, and boundary constraints.

Inventors: Szeliski; Richard (Bellevue, WA)

Assignee: Microsoft Corporation

International Classification: G06K 9/36 (20060101); G06K 9/40 (20060101)

Expiration Date: 2018-10-26 0:00:00