FSIP
the Family of Shortest Isothetic PathsAlgorithm
M. Dutt, A. Biswas, P. Bhowmick, B. B. Bhattacharya,On the Family of Shortest Isothetic Paths in a Digital Object—An Algorithm with Applications ,
CVIU, Vol. 129, pp. 75-88, 2014.
What and Why
The family of shortest isothetic paths (FSIP) between two grid points in a digital object is the collection of all possible shortest isothetic paths connecting them. We have proposed a fast algorithm to compute the FSIP between two given grid points inside a hole-free digital object. The algorithm works just with the object boundary as input and does not resort to analysis of the interior pixels. Given the digital object $A$ with $n$ boundary pixels, it first constructs the inner isothetic cover that tightly inscribes $A$ in $O(\frac ng \log\frac ng)$ time, $g$ being the unit of the underlying square grid. Then for any two points on the inner cover, it computes the FSIP in $O(n/g)$ time, using certain combinatorial characterization of FSIP. Experimental results show its effectiveness and further prospects in shape analysis and related applications.
Inner isothetic cover
6 control points
6 control points
5 control points
4 control points