Optimal algorithm for shape from shading and path planning

An optimal algorithm for the reconstruction of a surface from its shading i mage 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 consi stent numerical scheme based on Sethian's fast marching method is used to c ompute 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 diff erent partial differential equation. A modification of the fast marching me thod yields a numerically consistent, computationally optimal, and practica lly fast algorithm for the classical shape from shading problem. Next, the fast marching method coupled with a back tracking via gradient descent alon g the reconstructed surface is shown to solve the path planning problem in robot navigation.