Least squares surface reconstruction from gradients: Direct algebraic methods with spectral, Tikhonov, and constrained regularization

This paper presents three new methods for regularizing the least squares solution of the reconstruction of a surface from its gradient field: firstly, the spectral regularization based on discrete generalized Fourier series (e.g., Gram Polynomials, Haar Functions, etc.); secondly, the Tikhonov regularization applied directly to the 2D domain problem; and thirdly, the regularization via constraints such as arbitrary Dirichlet boundary conditions. It is shown that the solutions to the aforementioned problems all satisfy Sylvester Equations, which leads to substantial computational gains; specifically, the solution of the Sylvester Equation is direct (non-iterative) and for an m × n surface is of the same complexity as computing an SVD of the same size, i.e., an O (n³) algorithm. In contrast, state-of-the-art algorithms are based on large-scale-linear-solvers, and use iterative techniques based on an O [n⁶) linear sub-step. To emphasize this improvement, it is demonstrated that the new algorithms are upwards of 10⁴ (ten-thousand) times faster than the state-of-the-art techniques incorporating regularization. In fact, the new algorithms allow for the realtime regularized reconstruction of surfaces on the order of megapixels, which is unprecedented for this computer vision problem.