Fast Dichotomic Multiple Search Algorithm for Shortest Cirular Path

Circular shortest path algorithms for polar objects segmentation have been proposed in the works of B. Appleton and C. Sun (2003, 2005) and C. Sun and S. Pallottino (2002) to address discrete case and extended in the work of B. Appleton and H. Talbot (2005) to the continuous domain for closed global optimal geodesic calculation. The best method up to date relies on a branch and bound approach and runs in O(u^1.6v) on average while O(u^1.6v) in worst case for a u times v discrete trellis warped in the direction of v. We propose an new algorithm called dichotomic multiple search (DMS) which finds the global minimum with a O(ulog₂(u)v) worst case scenario complexity. Our algorithm relies on the fact that two minimal paths never cross more than once. This allows to sequentially partition the trellis in a dichotomic manner. Each computed circular minimal path with chosen starting point allows cutting the trellis into two sub trellis. The algorithm is then recursively applied on each sub trellis. Application to object segmentation is presented