Globally Optimal Energy Minimization Techniques - Bezier and Splines in Image Processing and Machine Vision - page 216

The algorithm makes use of a priority queue 1 Q of trial points in order to
maintain ecient access to the minimum distant point. Pseudocode for the
complete algorithm is provided in Figure 10.12.
Figure 10.13 shows that the fast marching algorithm calculates distance
functions that behave similarly to propagating electromagnetic radiation. In-
deed this example shows that the shortest path calculated via the fast march-
ing algorithm follows Snell's Law of Refraction from the field of optics. This
formula relates the angles of incidence and refraction where a ray of light
crosses a boundary between different media, such as air and glass. Snell's
law can be derived from Fermat's principle of least time, which states that
the path taken between two points by a ray of light is the path that can be
traversed in the least time-that is, a geodesic. Figure 10.14 shows a similar
computation on an inverse velocity cost function.

(a) (b)

Fig. 10.13. The fast marching algorithm calculates the surfaces of minimal action
(b) for the two-valued cost function of (a). Note that the geodesic shown in (b)
follows Snells' Law of refraction for optical and electromagnetic waves—that is, the
sine of the angle of incidence divided by the sine of the angle of refraction is a
constant determined by the properties of the two media at the interface (images
provided courtesy of Ben Appleton).

10.4 Globally Minimal Surfaces (GMS)

The planar segmentation technique outlined in the last section cannot be ex-
tended to higher dimensions, so we need an entirely new approach. Minimum
cuts and maximum flow techniques are naturally suited to globally optimal

1 The implemention employs a heap data structure and heap sort for ecient lo-
cation of the minimum.