On finding shortest isothetic path inside a digital object.(English)Zbl 1377.68270
Barneva, Reneta P. (ed.) et al., Combinatorial image analysis. 15th international workshop, IWCIA 2012, Austin, TX, USA, November 28–30, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-34731-3/pbk). Lecture Notes in Computer Science 7655, 1-15 (2012).
Summary: Shortest path algorithms are finding interesting applications in recent times in various emerging areas of image analysis and computer vision. Such algorithms are designed to solve shortest path problems with variegated need-based constraints. We present here 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 first obtains the inner isothetic cover (simple and without holes) 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(n \log n)\) time, \(n\) being the number of grid points on the border of the cover. Experimental results show the effectiveness of the algorithm and its further prospects in shape analysis.
For the entire collection see [Zbl 1259.68001].
For the entire collection see [Zbl 1259.68001].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68T45 | Machine vision and scene understanding |
| 68U10 | Computing methodologies for image processing |
Cite
Full Text:DOI
