Distance de Hausdorff

Un article de Wikipédia, l'encyclopédie libre.

En topologie, la distance de Hausdorff mesure l’éloignement de deux sous-ensembles d’un espace métrique. Elle porte le nom du mathématicien allemand Felix Hausdorff.

De façon informelle, la distance de Hausdorff entre deux ensembles de points est la distance maximale d'un point d'un sous-ensemble au point le plus proche de l'autre sous-ensemble.

Sommaire

[modifier] Définition

Soit un espace métrique (E,d). Soient A et B deux sous-ensembles compacts non vides de E.

On définit tout d’abord, pour tout sous-ensemble X de E, le r-voisinage ouvert de X comme étant l’ensemble :

V(r,X)=\{x\in E | \exists a\in X, d(x,a)<r\}

c’est-à-dire l’union des boules ouvertes centrées sur un élément de X et de rayon r.


La distance de Hausdorff DH(A,B) entre A et B est définie comme étant le plus petit nombre réel r tel que le r-voisinage de A contienne B et le r-voisinage de B contienne A. En d’autres termes :

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

[modifier] Propriétés

La distance de Hausdorff sur E définit une distance sur l’ensemble K(E) des compacts non-vides de E. K(E) est alors un espace métrique et sa topologie dépend de celle de E.

Si E est un espace complet, alors K(E) est complet. Si E est un espace compact, alors K(E) est compact.

Par conséquent, toute suite (A_n)_{n\in \mathbb N} d’ensembles de K(E) décroissante au sens de l’inclusion admet une limite au sens de la distance de Hausdorff, à savoir \bigcap_{n \in \mathbb N}{A_n}

[modifier] Généralisation

Si la distance sur E est bornée, la distance de Hausdorff peut même être étendue à l'ensemble des sous-espaces fermés (non nécessairement compacts) de E. Dans le cas contraire, la « distance » ainsi définie peut prendre des valeurs infinies.

Il est également possible de définir la distance de Hausdorff entre deux sous-ensembles non fermés de E comme la distance de Hausdorff entre leur adhérence. On munit ainsi l’ensemble des sous-ensembles de E d’une pseudo-métrique (puisque deux sous-ensembles distincts mais partageant la même adhérence auront une distance de Hausdorff nulle).

[modifier] Mesure de similarité

La distance de Hausdorff (DH) est régulièrement utilisée en analyse d'image. D'après Rucklidge, elle est considérée comme une mesure de similarité naturelle entre les formes.

[modifier] Définition

La définition ci-dessous est habituellement utilisée en reconnaissance de forme.

Soient S et T deux ensembles de points. La distance de Hausdorff est définie par

DH(S,T) = max {fd(S,T), fd(T,S)},

où fd est appelée la distance de Hausdorff relative (ou semi-distance de Hausdorff). Elle est définie par

fd(S,T) = maxp∈S d(p,T).

Habituellement, la distance d utilisée est la distance euclidienne.

[modifier] Propriété

La distance de Hausdorff DH(S,T) est nulle si et seulement si S = T et elle augmente lorsque des différences de plus en plus importantes apparaissent entre S et T.

Le calcul de la distance de Hausdorff peut se faire en utilisant une carte de distances.

[modifier] Défaut

La distance de Hausdorff considère les objets géométriques seulement comme des ensembles de points et non selon leur propre nature. En conséquence, les mesures obtenues par cette distance peuvent être incohérentes par rapport à ce que nous pouvons observer. Par exemple, si nous prenons le cas de deux courbes se croisant en un grand nombre de points, la distance de Hausdorff entre ces deux courbes sera faible alors que visuellement elles paraissent très différentes.

[modifier] Comparaison de squelettes

Selon Choi et Seidel, la distance de Hausdorff telle qu'elle est définie n'est pas adaptée à la comparaison de formes par leur squelette pondéré. En effet, la squelettisation est une transformation très sensible aux perturbations apparaissant dans les formes. Même si la distance de Hausdorff de deux formes est très faible (les formes sont très similaires), leurs squelettes respectifs peuvent être très différents. Ainsi, la distance de Hausdorff entre des squelettes peut ne pas correspondre à la similarité de leur formes d'origine.

Afin de résoudre de problème, Choi et Seidel ont proposé de remplacer la distance euclidienne par la distance hyperbolique dans le calcul de la distance de Hausdorff.

[modifier] Mesure de similarité: bibliographie

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

[modifier] Voir aussi