Minimal Paths theory

The minimal path in geometrical optic

In order to understand the underlying law of refraction, behind the minimal path principle, let us imagine a straight seashore, separating the sea from the beach, as shown in figure 1.1.

Figure 1.1: Example of minimal path in a heterogeneous media

A lifeguard sitting at a point A in the beach sees a girl drowning at a point B in the sea. Assuming that the lifeguard can run on the beach three times faster than he can swim, the shortest time path is the broken line going straight from A to a point M on the shore, then straight from M to B. Considering the two angles of the straight lines to the normal to the shore, the ration of their sines is equal to the ratio of the corresponding speeds (Descartes/Snell' law of refraction). The principle of Fermat is that light waves of a given frequency travels the path between two points which takes the least time. The most obvious example of this is the passage of a light through a homogeneous medium, in which the speed of light does not change with position. In this case, shortest time is equivalent to the shortest distance between the points, which is a straight line, as shown in figure 1.2-left.

Figure 1.2: Example of minimal paths in synthetic media: left image represents the propagation of a light wave in a homogeneous medium, starting from a unique light source. The minimal paths between this light source and other position in the plane are straight lines. Middle image represents the propagation of a light wave in a medium where the refractive index is more important in the upper half part of the image than in the lower, starting from a light source in the upper part. Right image is a diagram which illustrates the mirage phenomenon on the basis of the propagation of the light in heterogeneous media, as shown in middle image.

When the medium is not homogeneous, as in figure 1.2-middle, there is a refraction angle at the interface between the two homogeneous regions. Figure 1.2-right can illustrate a well-known optical phenomenon, called mirage: The light source $S$ is visible from both points $R_1$, and $R_2$. But the light path between $S$ and $R_2$ is not a straight line, due to the difference of index of the two media. Therefore, $R_2$ ``sees'' S coming from location M, at the interface between the two media, while the image source is far from $M$. This phenomenon occurs when the variations in temperature are important enough to deviate the light path, resulting in ``visions'' of an oasis in the desert, for example. Hamilton defined optical path functions, which best known was defined by Burns as the applied to the development of a mathematical theory of optical systems. The is used to compute the minimal light paths for a refractive index, in the sense that the minimal path is the one which integral over the refractive index is minimal.

We are going to use this minimality property in order to extract curves in images, giving only the two extremities of the path, and using the equation developed by Hamilton for optical systems.

Minimal path for curve extraction

We explain how this minimal path principle can be used for curve extraction in images. Given a refractive index $P$, called potential in the following, which takes lower values near the edges or features, our goal is to find a single contour that best fits the boundary of a given object or a line of interest. This contour, considered between two fixed extremities, will be the one which integral over the potential $P$ is minimal.

Looking for a path which lies in a desired region of interest, the refractive index should model the desired properties of the targeted curve. For example, in figure 1.3, we want to extract a path which stays inside the vessel.

Figure 1.3: Example of a minimal path in a media defined by a grey level image: The minimal path (in white) superimposed on the date is the one that corresponds to the light wave propagation, using the grey-level information as a refractive index.

The dataset, a digital subtracted angiography (DSA) shows vessels in lower grey levels on a bright background. Since we want to extract a path which stays inside the vessel, a possible refractive index to be used with the Hamilton equations for extracting minimal paths, could be the simple image grey level values.

This `best fit' question leads to algorithms that seek for the minimal path, i.e. paths along which the integration over $P$ is minimal. Classical path extraction techniques are based on the snakes [82]. Snakes are a special case of deformable models as presented in [174]. Snakes start from a path close to the solution and converge to a local minimum of the energy. In this minimal path formulation, one interesting aspect is that the user input is limited to the end points, simplifying the initialization process. Unicity of this minimal path, for a given media avoids erroneous local minima. Motivated by the ideas put forward in [86,87] Cohen and Kimmel developed an efficient and consistent method to find the path of minimal cost between two points, using the surface of minimal action [151,87,178] and the fact that operating on a given potential (cost) function helps in finding the solution for our path of minimal action (also known as minimal geodesic, or path of minimal potential). In the following we show how the formulation of the minimal light path can be obtained through a modification of the classical formulation of the active contours, and we show the numerical implementation of the minimal path extraction.