Fast marching method: Difference between revisions

Revision as of 13:51, 1 November 2017

Latest revision as of 10:42, 26 October 2024

(7 intermediate revisions by 7 users not shown)

Line 1:

{{short description|Algorithm for solving boundary value problems of the Eikonal equation}}

The '''fast marching method'''<ref name="sethian_fmm">J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996. [https://math.berkeley.edu/~sethian/2006/Papers/sethian.fastmarching.pdf]</ref> is a [[numerical method]] created by [[James Sethian]] for solving [[boundary value problem]]s of the [[Eikonal equation]]:

: <math>|\nabla u(x)|=1/f(x) \text{ for } x \in \Omega</math>

: <math>u(x) = 0 \text{ for } x \in \partial \Omega</math>

Typically, such a problem describes the evolution of a closed surface as a function of time <math>u</math> with speed <math>f</math> in the normal direction at a point <math>x</math> on the propagating surface. The speed function is specified, and the time at which the contour crosses a point <math>x</math> is obtained by solving the equation. Alternatively, <math>u(x)</math> can be thought of as the minimum amount of time it would take to reach <math>\partial\Omega</math> starting from the point <math>x</math>. The fast marching method takes advantage of this [[optimal control]] interpretation of the problem in order to build a solution outwards starting from the "known information", i.e. the boundary values.

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 method]]s. [[Eikonal equation#Computational algorithms|More general algorithms exist]] but are normally slower.

Extensions to non-flat (triangulated) domains solving

Line 22 ⟶ 24:

==Algorithm==

First, assume that the ___domain has been discretized into a mesh. We will refer to meshpointsmesh points as nodes. Each node <math>x_i</math> has a corresponding value <math>U_i = U(x_i) \approx u(x_i)</math>.

The algorithm works just like Dijkstra's algorithm but differs in how the nodes' values are calculated. In Dijkstra's algorithm, a node's value is calculated using a single one of the neighboring nodes. However, in solving the [[Partial differential equation|PDE]] in <math>\mathbb{R}^n</math>, between <math>1</math> and <math>n</math> of the neighboring nodes [[Eikonal equation#Numerical Approximation|are used]].

Nodes are labeled as ''far'' (not yet visited), ''considered'' (visited and value tentatively assigned), and ''accepted'' (visited and value permanently assigned).

Line 36 ⟶ 38:

==See also==

* [[Level -set method]]

* [[Fast sweeping method]]

* [[Bellman-FordBellman–Ford algorithm]]

==External links==

* [httphttps://www.mit.edu/~jnt/dijkstra.html DjikstraDijkstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995]

* [http://math.berkeley.edu/~sethian/ The Fast Marching Method and its Applications by James A. Sethian]

* [https://web.archive.org/web/20110719232108/http://mecca.louisville.edu/~msabry/projects/msfm.htm Multi-Stencils Fast Marching Methods]

Line 48 ⟶ 50:

* [https://rd.springer.com/article/10.1007/s11075-008-9183-x Generalized Fast Marching method] by Forcadel et al. [2008] for applications in image segmentation.

* [https://github.com/scikit-fmm/scikit-fmm Python Implementation of the Fast Marching Method]

*See Chapter 8 in [http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior] {{Webarchive|url=https://web.archive.org/web/20130820063106/http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf |date=2013-08-20 }}

==Notes==