Algorithm F*, now classical in the field of dynamic programming, was introduced in 1981 by FISCHLER et al. [M. A. Fischler, 1981]. The algorithm requires the preliminary calculation of a cost function for each pixel, typically the membership or not to a road. This constitutes the a priori knowledge to search the optimal path between two points. Detection is carried out by several detectors (DUDA, ROBERTS, SOBEL, HUECKEL) whose results are amalgamated.

Algorithm F* is iterative and converges towards an optimal solution whatever the context. That means that it finds a path even if there is no lineament between the extreme points, in return, it is possible to thwart the problem of occlusions.

Calculation of the cost is done in an alternative way, repeatedly until stabilization of the values:

• from the origin towards goal (OB),
• then goal towards origin (BO).

Phase OB calculates all the possible paths in a direction, with all the possible ramifications, then phase BO switches the process towards the most promising paths.

The process requires the use of two tables:

• one for the cost of each pixel,
• one for the cost of the paths leading to each pixel.

The cost of a path P(i, j) leading to the current pixel is the minimal value of the sums of the cost of the current pixel and the cost of the paths leading to its predecessors. More formally:

Phase OB	Phase BO

Iterations end when the minimal value of the updates is lower than the value of the cost of the path leading to the goal. Minimal path is described while following the minimal values since the goal towards the origin.

This algorithm is simple to implement and its efficiency is not any more to prove, nevertheless the quality of the result strongly depends on the quality of primary detection.

Considering the pixels one by one does not make it possible to take into account the context of the pixel, unless the methods of preliminary segmentation hold account of it. Moreover, the information about the form of the lineament is not exploited, whereas the local curve could guide the search of the optimal path and avoid uncontrolled jumps from a lineament to another, when they are close.

MERLET and ZERUBIA [N. Merlet, 1993a] [N. Merlet, 1993b] [N. Merlet, 1996] extend the energy of each pixel to the energy of cliques in the neighbourhood of the pixels. Each clique represents:

• either a possible ``seed'' point of the lineament, starting from a given point, or
• a portion of environment of the lineament.

This makes it possible to calculate:

• a local energy for the lineament,
• its contrast with the environment and,
• according to the form of the clic, the local curvature of the lineament.

These three criteria are then exploited in a process of research of the optimal path of modified type F*. The results obtained are very interesting, they show very well the contribution of each criterion to the improvement of the result.

                  
  
 IRIT-UPS