Finding Shortest Triangular Path and its Family inside a Digital Object

• Autorzy: Sarkar A. , Biswas A. , Dutt M. , Mondal S.

Identyfikatory

DOI

10.3233/FI-2018-1666

• Języki publikacji: EN

Abstrakty

EN

This article presents a combinatorial algorithm to find a shortest triangular path (STP) between two points inside a digital object imposed on triangular grid that runs in O(n/g log n/g) time, where n is the number of pixels on the contour of the object and g is the grid size. Initially, the inner triangular cover which maximally inscribes the object is constructed to ensure that the path lies within the object. An appropriate bounding parallelogram is considered with those two points in diagonally opposite corners and then one of the semi-perimeters of the parallelogram is traversed. Certain combinatorial rules are formulated based on the properties of triangular grid and are applied during the traversal whenever required to shorten the triangular path. A shortest triangular path between any two points may not be unique. Another combinatorial algorithm is presented, which finds the family of shortest triangular path (FSTP) (i.e., the region containing all possible shortest triangular paths) between two given points inside a digital object and runs in O(n/g log n/g) time. Experimental results are presented to verify the correctness, robustness, and efficacy of the algorithms. STP and FSTP can be useful for shape analysis of digital objects and determining shape signatures.

Słowa kluczowe

EN

digital object identifiers; combinatorial analysis; algorithms; parallelogram; robust statistics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 159, nr 3
• Strony: 297--325
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Sarkar A.

• Department of Computer Science and Technology, Indian Institute of Engineering Science and Technology, Shibpur, India

autor

Biswas A.

• Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, India

autor

Dutt M.

• Department of Computer Science and Engineering, St. Thomas College of Engineering and Technology, Kolkata, India

autor

Mondal S.

• Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India

Bibliografia

• [1] Ahuja RK, Magnanti TL, Orlin JB. Network Flows: Theory, Algorithms and Applications. Prentice Hall, 1993. ISBN: 0-13-617549-X.
• [2] Schrijver A. On the History of the Shortest Path Problem. Documenta Mathematica, 2012. pp. 155-167.
• [3] Shimbel A. Structural parameters of communication networks. Bulletin of Mathematical Biophysics, 1953. 15(4):501-507. doi:10.1007/BF02476438.
• [4] Bellman R. On a Routing Problem. Quarterly of Applied Mathematics, 1958. 16:87-90. Quarterly of Applied Mathematics, 1958. URL http://www.jstor.org/stable/43634538.
• [5] Moore E. The shortest path through a maze. In: Proceedings of an International Symposium on the Theory of Switching, 25 April 1957. arvard University Press, Cambridge, Massachusetts, 1959 pp. 285-292.
• [6] Dijkstra E. A note on two problems in connexion with graphs. Numerische Mathematik, 1959. 1:269-271. doi:10.1007/BF01386390.
• [7] Dutt M, Biswas A, Bhowmick P, Bhattacharya BB. On finding a shortest isothetic path and its monotonicity inside a digital object. Annals of Mathematics and Artificial Intelligence, 2015. 75:27-51. doi:10.1007/s10472-014-9421-y.
• [8] Dutt M, Biswas A, Bhowmick P, Bhattacharya BB. On Finding Shortest Isothetic Path inside a Digital Object. In: Proceedings of 15th International Workshop, IWCIA 2012. Springer Berlin Heidelberg, 2012 pp. 1-15. doi.10.1007/978-3-642-34732-0_1.
• [9] Dutt M, Biswas A, Bhowmick P, Bhattacharya BB. On the family of shortest isothetic paths in a digital object - An algorithm with applications. Computer Vision and Image Understanding, 2014. 129(C):75-88. doi:10.1016/j.cviu.2014.07.001.
• [10] Nagy B. Shortest paths in triangular grids with neighbourhood sequences. Journal of Computing and Information Technology, 2003. 11(2):111-122. URL https://doi.org/10.2498/cit.2003.02.04.
• [11] Balint GT, Nagy B. Finiteness of chain-code picture languages on the triangular grid. In: Image and Signal Processing and Analysis (ISPA). 2015 pp. 310-315. doi:10.1109/ISPA.2015.7306078.
• [12] Luczak E, Rosenfeld A. Distance on a hexagonal grid. IEEE Transactions on Computers, 1976. 25(5):532-533. doi:10.1109/TC.1976.1674642.
• [13] Freeman H. Algorithm for Generating a Digital Straight Line on a Triangular Grid. IEEE Transactions on Computers, 1979. 28:150-1152. doi:10.1109/TC.1979.1675305.
• [14] Pokorny P. Geodesics Revisited. Chaotic Modeling and Simulation, 2012. pp. 281-298.
• [15] Mitchell JSB, Mount DM, Papadimitriou CH. The Discrete Geodesic Problem. SIAM J. Comput., 1987. 16(4):647-668. doi:10.1137/0216045.
• [16] Kapoor S. Efficient Computation of Geodesic Shortest Paths. In: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC ’99. ACM, New York, NY, USA. 1999 pp. 770-779. ISBN: 1-58113-067-8.
• [17] Devadoss SL, O’Rourke J. Discrete and Computational Geometry. Princeton University Press, 2011. ISBN: 9781400838981.
• [18] Martinez D, Velho L, Carvalho PC. Geodesic paths on triangular meshes. In: Proceedings. 17th Brazilian Symposium on Computer Graphics and Image Processing. 2004 pp. 210-217. Quarterly of Applied Mathematics, 1958. doi:10.1109/SIBGRA.2004.1352963.
• [19] Das B, Dutt M, Biswas A, Bhowmick P, Bhattacharya BB. A Combinatorial Technique for Construction of Triangular Covers of Digital Objects. In: Combinatorial Image Analysis:16th International Workshop, IWCIA 2014. Springer, 2014 pp. 76-90. doi:10.1007/978-3-319-07148-0_8.
• [20] Klette R, Rosenfeld A. Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco, 2004. ISBN-10: 1558608613, 13: 978-1558608610.
• [21] Her I. Geometric Transformation on the Hexagonal Grid. IEEE Transaction on Image Processing, 1995. 4:1213-1222. doi:10.1109/83.413166.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).