Shortest Isothetic Path (SIP)
(A combinatorial technique based on concavity and convexity)Algorithm
M. Dutt, A. Biswas, P. Bhowmick, and B. B. Bhattacharya:On Finding a Shortest Isothetic Path and its Monotonicity inside a Digital Object, Annals of Mathematics and Artificial Intelligence, Vol. 75, pp. 27-51, 2015.
A preliminary version appeared as:
On Finding Shortest Isothetic Path inside a Digital Object.
15th International Workshop on Combinatorial Image Analysis: IWCIA'12, Austin, Texas, USA, Nov 28-30, 2012, LNCS 7655:1-15.
What's it?
Shortest path algorithms are recently finding interesting applications in various emerging areas of image analysis and computer vision with variegated need-based constraints. We have proposed an efficient combinatorial algorithm to find a/the shortest isothetic path (SIP) between two grid points in a digital object such that the SIP lies entirely inside the object. The algorithm obtains the inner isothetic cover of the object and then applies certain combinatorial rules to construct the SIP and its constituent monotone sub-paths. For a given grid size, the entire algorithm runs in O(nlogn) time, n being the number of grid points on the border of the cover. Experimentation shows its effectiveness and further prospects in shape analysis.Our Contribution
Our work is focused on finding the shortest isothetic path (SIP) inside a digital object A laid on a grid G such that the path lies entirely inside A and consists of moves along grid edges only. Although our problem has some similarity with certain problems of computational geometry, no efficient algorithmic solution is available for the concerned digital-geometric problem, till date. For a given grid size, our algorithm runs in O(n log n) time, n being the number of grid points on the border of the inner isothetic cover, P (maximum-area isothetic polygon inscribing A). Note that, if the shortest path is obtained directly from A (without using P), then the time complexity of an optimal algorithm would be no less than O(n2), since the number of constituent pixels of A can be O(n2).
