Circular shortest paths by branch and bound

摘要

Shortest path algorithms are used for a large variety of optimisation problems in network and transportation analysis. They are also used in image analysis for object segmentation, disparity estimation, path finding and crack detection. Sometimes the topology of the problem demands that the path be circular. Such circular path constraints occur in polar object segmentation, disparity estimation for panoramic stereo images and in shortest paths around a cylinder. In this paper we present a new efficient algorithm for circular shortest path determination on a u-by-v trellis in O(u1.6v) average time. We impose a binary search tree on the set of path endpoints and use a best-first Branch and Bound search technique to efficiently obtain the global minimum circular path. The typical running time of our circular shortest path algorithm on a 256×256 image is in the order of 0.1s on a 1GHz Dell P3 workstation under the Linux operating system. Applications to crack detection and object segmentation are presented.