Control Systems and Computers, N1, 2021, Article 3
https://doi.org/10.15407/csc.2021.01.029
Control Systems and Computers, 2021, Issue 1 (291), pp. 29-34.
UDK 519.6
YE.V. VODOLAZSKIY, Senior Research Associate, International Research and Training Centre of Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, waterlaz@gmail.com
FRECHET SIMILARITY BETWEEN TWO
AMBIGUOUSLY DEFINED POLYGONAL LINES
The paper considers the problem of comparing two polygonal lines that are not strictly defined. Instead, two sets of polygonal lines are given assets of paths on two acyclic directed graphs. The problem is to determine whether there exists a pair of lines each from its respective set such that the Frechet distance between them is not greater than a given number. An algorithm is given that solves the problem in time, were and are the sets of edges in each graph respectively.
Завантажити повний текст! (англійською)
Keywords: computational geometry, Frechet distance, computational complexity.
- Matas J., Chum O., Urban M., Pajdla T., 2004. “Robust wide baseline stereo from maximally stable extremal regions”, Image and Vision Computing, 22, pp. 761-767.
https://doi.org/10.1016/j.imavis.2004.02.006 - Marot J., Caulier Y., Kuleschov A., Spinnler K., Bourennane S., 2008. “Contour detection for industrial image processing by means of level set methods”, Advanced Concepts for Intelligent Vision Systems, pp. 655-663.
https://doi.org/10.1007/978-3-540-88458-3_59 - Kass M., Witkin A., Terzopoulos D., 1988. “Snakes: Active contour models”, IEEE Proc, on Computer Vision and Pattern Recognition, 1, pp. 321-331.
https://doi.org/10.1007/BF00133570 - Adamek T., O’Connor N., 2003. “Efficient contour-based shape representation and matching”, Proceedings of the 5th ACM SIGMM International Workshop on Multimedia Information Retrieval (MIR’03), pp. 138-143. [online] Available at: <https://core.ac.uk/download/pdf/147596517.pdf>.
https://doi.org/10.1145/973264.973287 - Marvaniya S., 2013. “Simultaneous Part-Decomposition and Contour Matching using Dynamic Programming”, PhD thesis, Indian Institute of Technology. DOI: 10.13140/RG.2.2.22615.42400.
- Alt H., Godau M., 1995. “Computing the frechet distance between two polygonal curves”, International Journal on Computational Geometry and Appication, 5 (1), pp. 75-91.
https://doi.org/10.1142/S0218195995000064 - Driemel A., Har-Peled S., Wenk C., 2012. “Approximating the frechet distance for realistic curves in near linear time”, Discrete & Computational Geometry, 48, pp. 94-127. [online] Available at: <https://link.springer.com/article/10.1007/s00454-012-9402-z>.
https://doi.org/10.1007/s00454-012-9402-z - Schlesinger M., Vodolazskiy E., Yakovenko V., 2016. “Frechet similarity of closed polygonal curves”, International Journal of Computational Geometry and Applications, 26 (1), pp. 53-66. DOI: 10.1142/S0218195916500035.
https://doi.org/10.1142/S0218195916500035 - Schlesinger M., Vodolazskiy E., Yakovenko V., 2014. “Recognizing the similarity of polygons in a strengthened hausdorff metric”, Cybernetics and Systems Analysis, 3, pp. 174-187.
https://doi.org/10.1007/s10559-014-9636-2.
Received 10.03.2021
