Distance from Hausdorff

In Topology, the distance from Hausdorff measurement distance of two Subset S of a metric Space. It bears the name of the German mathematician Felix Hausdorff.

Definition

That is to say a metric Space

(E, d)

. Are

A

and

B

two subsets compact not vacuums of

E

One defines first of all, for any subset $X$ of $E$ , the R - open Voisinage of $X$ as being the unit:

V (R, X) = \ {X \ in E | D (X, X)

i.e. union of the open balls centered on an element of

X

and ray

r

The distance from Hausdorff $D_H (has, B)$ between $A$ and $B$ is defined as being smallest Real number $r$ such as the R - vicinity of $A$ contains $B$ and the R - vicinity of $B$ contains $A$ . In other words:

$D_H (has, B)= \ inf \ {r>0 | With \ subset V (R, B), B \ subset V (R, A) \}$

Properties

The distance from Hausdorff on

E

defines a distance on the unit

K (E)

of the compact not-vacuums of E.

K (E)

is then a metric space and its topology depends on that of

E

If $E$ is a complete Espace, then $K (E)$ is complete. If $E$ is a compact Espace, then $K (E)$ is compact.

Consequently, all continuation $(A_n) _ {N \ in \ mathbb NR}$ of whole of $K (E)$ decreasing within the meaning of inclusion admits a limit within the meaning of the distance from Hausdorff, namely $\ bigcap_ {N \ in \ mathbb NR} {A_n}$

Generalization

If the distance on E is limited, the distance from Hausdorff can even be wide with the whole of the subspaces Fermé S (not necessarily compact) of

E

. In the contrary case, the “distance” thus defined can take infinite values.

It is also possible to define the distance from Hausdorff between two not closed subsets of $E$ as the distance from Hausdorff between their adherence. One thus provides the unit with the subsets of $E$ of a Pseudo-metric (since two distinct subsets but sharing same adherence will have a null distance from Hausdorff).

Measure similarity

The distance from Hausdorff ( D_H ) is regularly used in analysis of image. According to Rucklidge, she is regarded as a measurement of natural similarity between the forms.

Definition

The definition below is usually used in pattern recognition.

Are S and T two whole of points. The distance from Hausdorff is defined by

D_H ( S , T ) = max { f_d ( S , T ), f_d ( T , S )},

where f_d is called the relative distance from Hausdorff (or semi-distance of Hausdorff). It is defined by

f_d ( S , T ) = max_{p ∈ S} D ( p , T ).

Usually, the distance D used is the Euclidean Distance.

Property

The distance from Hausdorff D_H ( S , T ) is null if and only if S = T and it increases when increasingly important differences appear between S and T .

The calculation of the distance from Hausdorff can be done by using a Carte of distances.

Defect

The distance from Hausdorff does not regard the geometrical objects only as whole of points and not according to their own nature. Consequently, the measurements obtained by this distance can be incoherent compared to what we can observe. For example, if we take the case of two curves crossing in a great number of points, the distance from Hausdorff between these two curves will be weak whereas visually they appear very different.

Comparison of skeletons

According to Choi and Seidel, the distance from Hausdorff such as it is defined is not adapted to the comparison from forms by their skeleton balanced. Indeed, the squelettisation is a transformation very sensitive to the disturbances appearing in the forms. Even if the distance from Hausdorff of two forms is very weak (the forms are very similar), their respective skeletons can be very different. Thus, the distance from Hausdorff between skeletons can not correspond to the similarity of their forms of origin.

In order to solve problem, Choi and Seidel proposed to replace the Euclidean distance by the hyperbolic Distance in the calculation of the distance from Hausdorff.

Measure similarity: bibliography

Sung Woo Choi and Hans Peter Seidel. Hyperbolic Hausdorff outdistances for medial axis transform. Graphics Models , 63 (5): 369-384, 2001.
William Rucklidge. Efficient visual recognition using the Hausdorff outdistances , LNCS 1173. Springer Verlag, 1996.

See too

Topology
Distance
Convergence of Gromov-Hausdorff
Distance from Hausdorff modified

Random links: