D'esopo's algorithm

This method is an improvement of a minimum cost path finding algorithm by D'esopo. It allows the user to interactively digitise a feature by clicking on successive points along the feature. As the user selects a point, the system finds the best path between the new point and the previous point. The new segment may be deleted and redigitised. In this way a feature can be rapidly digitised as a series of segments.

The criterion for finding the best path is specified by the user in terms of the way the feature appears in the image. The image may be preprocessed in advance to enhance the appearance of the feature before digitisation. If the algorithm fails to find a suitable path for a segment, that segment can be digitised manually as a series of straight lines.

A disadvantage of this approach is that only single segments can be digitised. If there are junctions, such as river tributaries, then these must be digitised separately and no information is kept about the junction.


Text and images by Mark Dobie, back to Mark's home page