Regularised shortest-path extraction

Regularization of shortest-paths and active contours has been considered 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. in the active contours context that a method was found which was able to apply a simple and intuitive smoothness constraint with an efficient computational scheme. We show that, when applied to the shortest-path problem, this technique gives rise to a simple and efficient algorithm. However, we find that the method is not practically useful in some situations because of discretization effects. A modification using pixel subdivision is proposed which to a large extent overcomes this problem. The modified method is illustrated using two examples: fracture detection in borehole images and road detection in satellite images.