Vodolazskyi Y. Efficient methods for computing image similarity in the Frechet metric

The work is devoted to the problem of computing the Frechet distance, as a stronger metric than the Hausdorff metric, between various classes of metric space subsets, particularly between subspaces of R^2. The problems of computing the Frechet distance between closed polygonal curves, polygonal curves with branches (trees), sets of polygonal curves, defined as paths on acyclic directed graphs, as well as computing discrete Frechet distance between closed sequences (cycles) are considered. An efficient algorithm for deciding whether the Frechet distance between two closed polygonal curves is greater than a given number is proposed. The algorithm takes O(mn) time, where m,n are the numbers of line segments in two polygonal curves. An efficient algorithm for computing the discrete Frechet distance between two closed sequences (cycles) is proposed that takes O(mn log* (mn)) time, where log* is the iterated logarithm and m,n are the numbers of points in two cycles. A situation when polygonal lines for computing the Frechet distance are not unambiguously defined. Instead, two sets of polygonal lines are given as sets of paths on directed acyclic graph. A problem of deciding whether there exists a pair of polygonal lines, each from its respected graph, that the Frechet distance between them is not greater than a given number. An algorithm that solves this problem in O(mn) time is given, where m and n are the number of edges in two graphs respectively. A new concept of deviation of one tree to an etalon tree is given. Even though the proposed deviation is not a metric, it is a more strict measure than the Hausdorff metric. Deviation is not infinite though for non­isomorphic trees, as opposed to the Frechet metric, which is infinite. A polynomial time algorithm for deviation decision is proposed. A new problem of deciding whether two polygonal lines are non­conflicting is formulated, which is in a certain sense a dual problem to deciding whether two polygonal lines are similar in the Frechet metric. An algorithm with O(mn) running time is proposed.