Circular shortest path on regular grids

摘要

Shortest path algorithms have been used for a number of applications such as crack detection, road or linear feature extraction on images. In this paper, we presents several new algorithms for the extraction of a circular shortest path on regular grids such that the starting and ending positions are connected. 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 algorithms on a 256 × 256 image is in the order of 0.3 seconds on a rather slow 85MHz Sun SPARC computer. A variety of real images for crack detection on borehole data, object boundary extraction, and panoramic stereo matching have been tested, and good results have been obtained.