Least squares surface reconstruction from gradients: Direct algebraic methods with spectral, Tikhonov, and constrained regularization
Authors:
- 1 June 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 2529-2536
Abstract
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 3 ) algorithm. In contrast, state-of-the-art algorithms are based on large-scale-linear-solvers, and use iterative techniques based on an O [n 6 ) linear sub-step. To emphasize this improvement, it is demonstrated that the new algorithms are upwards of 10 4 (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.Keywords
This publication has 16 references indexed in Scilit:
- An Algebraic Framework for Discrete Basis Functions in Computer Vision2008
- A graph-spectral method for surface height recoveryPattern Recognition, 2005
- Shapelets correlated with surface normals produce surfaces2005
- Depth from gradient fields and control points: bias correction in photometric stereoImage and Vision Computing, 2004
- Reconstructing discontinuous surfaces from a given gradient field using partial integrabilityComputer Vision and Image Understanding, 2003
- Matrix Algorithms, Volume II: EigensystemsApplied Mechanics Reviews, 2003
- Direct analytical methods for solving Poisson equations in computer vision problemsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990
- A line-integration based method for depth recovery from surface normalsComputer Vision, Graphics, and Image Processing, 1988
- On the Formal Differentiation of Traces and DeterminantsMultivariate Behavioral Research, 1985
- Photometric Method For Determining Surface Orientation From Multiple ImagesOptical Engineering, 1980