Numerical methods for linear shape from shading and height from gradients

Abstract

This thesis presents research to analyze finite difference algorithms for the linear shape from shading (SFS) problem, and numeric algorithms for the height from gradient (HFG) problem. Many SFS algorithms have been developed. However, theoretical proofs of convergence have not yet been done so far for most SFS algorithms. Experimental verification of the convergence of the algorithms is always questionable. Motivated by this observation, this thesis analyzes four explicit, two implicit and four semi-implicit finite difference algorithms for the linear SFS problem. Theoretical proofs are given for the solvability, stability and convergence of these algorithms. Comparisons indicate that both the weighted semi-implicit scheme and the box scheme have advantages over the other schemes such as being easily implementable, fast in convergence and unconditionally stable. Subsequent research results in the derivation of algorithms for the HFG problem, namely, a class of Fourier transform based approaches and a wavelet-based algorithm. The Fourier transform based methods have some distinct advantages. Firstly, the derivation process of the algorithms has generality, and can be used for reconstructing surfaces from sparse data. Secondly, they are noniterative algorithms so boundary conditions are not needed, and surface height is constructed in one pass utilizing all of the gradient estimates. In addition, their robustness to noisy gradient estimates can be improved by choosing associated weighting parameters. The wavelet-based algorithm overcomes the implicit requirement that a surface height function is periodic as in Fourier transform based methods.