Optimal Algorithm for Shape from Shading and Path Planning

An optimal algorithm for the reconstruction of a surface from its shading image is presented. The algorithm solves the 3D reconstruction from a single shading image problem. The shading image is treated as a penalty function and the height of the reconstructed surface is a weighted distance. A consistent numerical scheme based on Sethian's fast marching method is used to compute the reconstructed surface. The surface is a viscosity solution of an Eikonal equation for the vertical light source case. For the oblique light source case, the reconstructed surface is the viscosity solution to a different partial differential equation. A modification of the fast marching method yields a numerically consistent, computationally optimal, and practically fast algorithm for the classical shape from shading problem. Next, the fast marching method coupled with a back tracking via gradient descent along the reconstructed surface is shown to solve the path planning problem in robot navigation.