A new energy minimization framework and sparse linear system for path planning and shape from shading

For over 30 years, the static Hamilton-Jacobi (HJ) equation, specifically its incarnation as the eikonal equation, has been a bedrock for a plethora of computer vision models, including popular applications such as shape-from-shading, medial axis representations, level-set segmentation, and geodesic processing (i.e. path planning). Numerical solutions to this nonlinear partial differential equation have long relied on staples like fast marching and fast sweeping algorithms—approaches which rely on intricate convergence analysis, approximations, and specialized implementations. Here, we present a new variational functional on a scalar field comprising a spatially varying quadratic term and a standard regularization term. The Euler-Lagrange equation corresponding to the new functional is a linear differential equation which when discretized results in a linear system of equations. This approach leads to many algorithm choices since there are myriad efficient sparse linear solvers. The limiting behavior, for a particular case, of this linear differential equation can be shown to converge to the nonlinear eikonal. In addition, our approach eliminates the need to explicitly construct viscosity solutions as customary with direct solutions to the eikonal. Though our solution framework is applicable to the general class of eikonal problems, we detail specifics for the popular vision applications of shape-from-shading, vessel segmentation, and path planning. We showcase experimental results on a variety of images and complex mazes, in which we hold our own against state-of-the art fast marching and fast sweeping techniques, while retaining the considerable advantages of a linear systems approach.