A wide range of computer vision applications require an accurate solution of a particular Hamilton-Jacobi (HJ) equation, known as the Eikonal equation¹. In this project, we propose an improved version of the fast marching method (FMM) that is highly accurate for both 2D and 3D Cartesian domains. The new method is called multi-stencils fast marching (MSFM), which computes the solution at each grid point by solving the Eikonal equation along several stencils and then picks the solution that satisfies the upwind condition. The stencils are centered at each grid point and cover its entire nearest neighbors. In 2D space, 2 stencils cover the 8-neighbors of the point, while in 3D space, 6 stencils cover its 26-neighbors. For those stencils that are not aligned with the natural coordinate system, the Eikonal equation is derived using directional derivatives and then solved using higher order finite difference schemes. The accuracy of the proposed method over the state-of-the-art FMM-based techniques has been demonstrated through comprehensive numerical experiments.

¹The Eikonal equation is derived about 150 years ago by Sir William Rowan Hamilton. The word Eikonal was introduced in 1895 by H. Burns. It comes from the Greek word εικων, from which the modern word icon derives. The equation’s title is descriptive because it controls the formation of images in optical systems.

(a)                                                       (b)                                                      (c)

Cross sections in the arrival time field of a 3D unit speed wave that propagates from the center of a coarse grid of size 41×41×41 using
(a) 1st order fast marching method (FMM1)  (b) 2nd order fast marching method (FMM2), and (c) the proposed 2nd order multi-stencils fast marching method (MSFM2).
 

Cross section in the arrival time field of a 3D unit speed wave that propagates by the proposed method MSFM2 from two source points.
 

Iso-contours of the exact solution (solid), the 2nd order  fast marching method (FMM2) (dashed dot), and the proposed 2nd order multi-stencils fast marching (MSFM2) (dashed) for a unit speed wave that propagates from one source point (51,51)

Iso-contours of the exact solution (solid), the second order fast marching method (FMM2) (dashed dot), and the proposed second order multi-stencils fast marching (MSFM2) (dashed) for a unit speed wave that propagates from two source points at (51,35) and (51,67).

Notice that the proposed MSFM2 provides a better high curvature solution than related methods.