next up previous contents
Next: Coupled algorithm Up: Coupling between the topological Previous: Minimal paths   Contents

Fast marching

The fastest way to compute the distance function defined by equation (2.61) is to solve a front propagation equation:

$\displaystyle \frac{\partial C(s,t)}{\partial t} = \frac{1}{P(C(s,t))+\alpha}\ {\bf n}_C(s,t),$ (2.62)

where $ {\bf n}_C(s,t)$ is the outer normal unit vector to the front $ C$ . We initialize the propagation with $ C(s,0)$ equal to a infinitely small circle centered at $ x_0$ .

This path evolves with a propagation speed inversely proportional to the potential function. If for example a point in the outer part of the front has a large potential (i.e. a large cost), then the propagation speed will be nearly equal to 0 and the front will not expand at this point. From the theory of Eikonal equations, the distance $ D(x;x_0)$ is simply the instant $ t$ at which the front, initialized at point $ x_0$ , reaches point $ x$ [118,56].


Back to home page