REGULARIZED SHORTEST-PATH EXTRACTION

Regularization of shortest-paths and active contours has been consider ed and attempted by a number of workers. However, it was not until the development of the ''time-delayed dynamic programming'' algorithm of Amini et al. (1990) in the active contours context that a method was f ound which was able to apply a simple and intuitive smoothness constra int with an efficient computational scheme. We show that, when applied to the shortest-path problem, this technique gives rise to a simple a nd efficient algorithm. However, we find that the method is not practi cally useful in some situations because of discretization effects. A m odification using pixel subdivision is proposed which to a large exten t overcomes this problem. The modified method is illustrated using two examples: fracture detection in borehole images and road detection in satellite images. (C) 1997 Elsevier Science B.V.