Circular shortest path in images

Shortest path algorithms have been used in a number of applications such as crack detection, road or linear feature extraction in images. There are applications where the starting and ending positions of the shortest path need to be constrained. In this paper, we present several new algorithms for the extraction of a circular shortest path in an image such that the starting and ending positions coincide. The new algorithms we developed include multiple search algorithm, image patching algorithm, multiple backtracking algorithm, the combination of image patching and multiple back-tracking algorithm, and approximate algorithm. The typical running time of our circular shortest path extraction algorithm on a 256 x 256 image is about 0.3 s on a rather slow 85 MHz Sun SPARC computer. A variety of real images for crack detection in borehole data and object boundary extraction have been tested and good results have been obtained. (C) 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.