Fréchet Distance
   HOME

TheInfoList



OR:

In mathematics, the Fréchet distance is a
measure of similarity In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such mea ...
between
curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that ...
s that takes into account the location and ordering of the points along the curves. It is named after
Maurice Fréchet Maurice may refer to: *Maurice (name), a given name and surname, including a list of people with the name Places * or Mauritius, an island country in the Indian Ocean * Maurice, Iowa, a city * Maurice, Louisiana, a village * Maurice River, a t ...
.


Intuitive definition

Imagine a person traversing a finite curved path while walking their dog on a leash, with the dog traversing a separate finite curved path. Each can vary their speed to keep slack in the leash, but neither can move backwards. The Fréchet distance between the two curves is the length of the shortest leash sufficient for both to traverse their separate paths from start to finish. Note that the definition is symmetric with respect to the two curves—the Fréchet distance would be the same if the dog were walking its owner.


Formal definition

Let S be a
metric space In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
. A
curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that ...
A in S is a
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous ...
map A map is a symbolic depiction of interrelationships, commonly spatial, between things within a space. A map may be annotated with text and graphics. Like any graphic, a map may be fixed to paper or other durable media, or may be displayed on ...
from the
unit interval In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysi ...
into S, i.e., A : ,1\rightarrow S. A
reparameterization In mathematics, and more specifically in geometry, parametrization (or parameterization; also parameterisation, parametrisation) is the process of finding parametric equations of a curve, a surface, or, more generally, a manifold or a variety, ...
\alpha of ,1/math> is a continuous, non-decreasing,
surjection In mathematics, a surjective function (also known as surjection, or onto function ) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that . In other words, for a f ...
\alpha: ,1\rightarrow ,1/math>. Let A and B be two given curves in S. Then, the Fréchet distance between A and B is defined as the
infimum In mathematics, the infimum (abbreviated inf; : infima) of a subset S of a partially ordered set P is the greatest element in P that is less than or equal to each element of S, if such an element exists. If the infimum of S exists, it is unique ...
over ''all'' reparameterizations \alpha and \beta of ,1/math> of the maximum over all t \in ,1/math> of the distance in S between A(\alpha(t)) and B(\beta(t)). In mathematical notation, the Fréchet distance F(A,B) is F(A,B) = \inf_\,\,\max_ \,\, \biggl\ where d is the
distance function In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are a general setting fo ...
of S. Informally, we can think of the parameter t as "time". Then, A(\alpha(t)) is the position of the dog and B(\beta(t)) is the position of the dog's owner at time t (or vice versa). The length of the leash between them at time t is the distance between A(\alpha(t)) and B(\beta(t)). Taking the infimum over all possible reparametrizations of ,1/math> corresponds to choosing the walk along the given paths where the maximum leash length is minimized. The restriction that \alpha and \beta be non-decreasing means that neither the dog nor its owner can backtrack. The Fréchet metric takes into account the flow of the two curves because the pairs of points whose distance contributes to the Fréchet distance sweep continuously along their respective curves. This makes the Fréchet distance a better measure of similarity for curves than alternatives, such as the
Hausdorff distance In mathematics, the Hausdorff distance, or Hausdorff metric, also called Pompeiu–Hausdorff distance, measures how far two subsets of a metric space are from each other. It turns the set of non-empty set, non-empty compact space, compact subsets o ...
, for arbitrary point sets. It is possible for two curves to have small Hausdorff distance but large Fréchet distance. The Fréchet distance and its variants find application in several problems, from
morphing Morphing is a special effect in motion pictures and animations that changes (or morphs) one image or shape into another through a seamless transition. Traditionally such a depiction would be achieved through dissolving techniques on film. Si ...
. and
handwriting recognition Handwriting recognition (HWR), also known as handwritten text recognition (HTR), is the ability of a computer to receive and interpret intelligible handwriting, handwritten input from sources such as paper documents, photographs, touch-screens ...
. to protein structure alignment.. Alt and Godau. were the first to describe a polynomial-time algorithm to compute the Fréchet distance between two polygonal curves in
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
, based on the principle of parametric search. The running time of their algorithm is O(mn \cdot \log(mn)) for two polygonal curves with ''m'' and ''n'' segments.


The free-space diagram

An important tool for calculating the Fréchet distance of two curves is the free-space diagram, which was introduced by
Alt Alt or ALT may refer to: Abbreviations for words * Alt account, an alternative online identity also known as a sock puppet account * Alternate character, in online gaming * Alternate route, type of highway designation * Alternating group, mathem ...
and Godau. The free-space diagram between two curves for a given distance threshold ε is a two-dimensional region in the parameter space that consists of all point pairs on the two curves at distance at most ε: D_\varepsilon(A,B) := \bigl\ The Fréchet distance F(A,B) is at most ε if and only if the free-space diagram D_\varepsilon(A,B) contains a path from the lower left corner to the upper right corner, which is monotone both in the horizontal and in the vertical direction.


As a distance between probability distributions (the FID score)

In addition to measuring the distances between curves, the Fréchet distance can also be used to measure the difference between
probability distributions In probability theory and statistics, a probability distribution is a function that gives the probabilities of occurrence of possible events for an experiment. It is a mathematical description of a random phenomenon in terms of its sample spac ...
. For two multivariate Gaussian distributions with means \mu_X and \mu_Y and covariance matrices \Sigma_X and \Sigma_Y, the Fréchet distance between these distributions is d given by d^2 =, \mu_X-\mu_Y, ^2+\operatorname(\Sigma_X+\Sigma_Y-2(\Sigma_X\Sigma_Y)^). This distance is the basis for the Fréchet inception distance (FID) that is used in
machine learning Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
to compare images produced by an image generative model with a set of real images.


Variants

The weak Fréchet distance is a variant of the classical Fréchet distance without the requirement that the endpoints move monotonically along their respective curves — the dog and its owner are allowed to backtrack to keep the leash between them short. Alt and Godau describe a simpler algorithm to compute the weak Fréchet distance between polygonal curves, based on computing minimax paths in an associated
grid graph In graph theory, a lattice graph, mesh graph, or grid graph is a Graph (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...
. The discrete Fréchet distance, also called the coupling distance, is an approximation of the Fréchet metric for polygonal curves, defined by Eiter and Mannila.. The discrete Fréchet distance considers only positions of the leash where its endpoints are located at vertices of the two polygonal curves and never in the interior of an edge. This approximation unconditionally yields larger values than the corresponding (continuous) Fréchet distance. However, the approximation error is bounded by the largest distance between two adjacent vertices of the polygonal curves. Contrary to common algorithms of the (continuous) Fréchet distance, this algorithm is agnostic of the distance measures induced by the metric space. Its formulation as a dynamic programming problem can be implemented efficiently with a quadratic runtime and a linear memory overhead using only few lines of code. When the two curves are embedded in a metric space other than Euclidean space, such as a polyhedral terrain or some Euclidean space with obstacles, the distance between two points on the curves is most naturally defined as the length of the
shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...
between them. The leash is required to be a
geodesic In geometry, a geodesic () is a curve representing in some sense the locally shortest path ( arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a conn ...
joining its endpoints. The resulting metric between curves is called the geodesic Fréchet distance... Cook and Wenk describe a polynomial-time algorithm to compute the geodesic Fréchet distance between two polygonal curves in a
simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a Piecewise linear curve, piecewise-linear Jordan curve consisting of finitely many line segments. The ...
. If we further require that the leash must move continuously in the ambient metric space, then we obtain the notion of the homotopic Fréchet distance. between two curves. The leash cannot switch discontinuously from one position to another — in particular, the leash cannot jump over obstacles, and can sweep over a mountain on a terrain only if it is long enough. The motion of the leash describes a
homotopy In topology, two continuous functions from one topological space to another are called homotopic (from and ) if one can be "continuously deformed" into the other, such a deformation being called a homotopy ( ; ) between the two functions. ...
between the two curves. Chambers ''et al.'' describe a polynomial-time algorithm to compute the homotopic Fréchet distance between polygonal curves in the Euclidean plane with obstacles.


Examples

The Fréchet distance between two concentric circles of radius r_1 and r_2 respectively is , r_1 - r_2, . The longest leash is required when the owner stands still and the dog travels to the opposite side of the circle (r_1 + r_2), and the shortest leash when both owner and dog walk at a constant angular velocity around the circle (, r_1 - r_2, ).


Applications

Fréchet distance has been used to study
visual hierarchy Visual hierarchy, according to Gestalt psychology, is a pattern in the visual field wherein some elements tend to "stand out," or attract attention, more strongly than other elements, suggesting a hierarchy of importance. While it may occur natura ...
, a graphic design principle.


See also

* Fréchet inception distance * Fréchet mean


References


Further reading

*. *. *. {{DEFAULTSORT:Frechet Distance Metric geometry Distance Topology Geometric algorithms