Sherman-morrison-woodbury-formula-based algorithms for the surface smoothing problem

Surface smoothing applied to range-elevation data acquired using a variety of sources has been a very active area of research in computational vision over the past decade. Generalized splines have emerged as the single most popular approximation tool to this end. In this paper we present a new and fast algorithm for solving the surface smoothing problem using a membrane, a thin-plate, or a thin-plate—membrane spline for data containing discontinuities. Our approach involves imbedding the surface smoothing problem specified on an irregular domain (in the sense of discontinuities and boundaries) in a rectangular region using the capacitance-matrix method based on the Sherman-Morrison-Woodbury formula of matrix analysis. This formula is used in converting the problem of solving the original linear system resulting from a finite-element discretization of the variational formulation of the surface smoothing problem to solving a Lyapunov matrix equation or a cascade of two Lyapunov matrix equations. The reduced problem can then be solved very efficiently using the ADI method and the bi-conjugate-gradient technique. Our solution requires the generation of a dense capacitance matrix, for which we propose a practical and efficient method. We demonstrate the efficiency of our algorithm via experiments on sparse-data surface smoothing, making performance comparisons with the conjugate-gradient and hierarchical-basis preconditioned conjugate-gradient algorithms.