Fast marching method

The fast marching method is a numerical method for solving boundary value problems of the Eikonal equation:

F(x)|\nabla T(x)|=1.

Typically, such a problem describes the evolution of a closed curve as a function of time $T$ with speed $F(x)$ in the normal direction at a point $x$ on the curve. The speed function is specified, and the time at which the contour crosses a point $x$ is obtained by solving the equation.

The algorithm is similar to Dijkstra's algorithm and uses the fact that information only flows outward from the seeding area.

This problem is a special case of level set methods. More general algorithms exist but are normally slower.

Extensions to non-flat (triangulated) domains solving:

F(x)|\nabla_S T(x)|=1, \,\, \mbox{for the surface} \,\, S, \, \mbox{and} \,\, x\in S.

was introduced by Ron Kimmel and James Sethian.

Maze as speed function shortest path
Distance map multi-stencils with random source points

External links

Djikstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995
The Fast Marching Method and its Applications by James A. Sethian
Multi-Stencils Fast Marching Methods
Multi-Stencils Fast Marching Matlab Implementation
Implementation Details of the Fast Marching Methods
Generalized Fast Marching method by Forcadel et al. [2008] for applications in image segmentation.
See Chapter 8 in Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior

This article is issued from Wikipedia - version of the Wednesday, March 18, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Fast marching method

See also

External links