Distance de Hausdorff
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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.

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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) d’abord, pour tout sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut...) X de E, le r-voisinage ouvert de X comme étant l’ensemble :

V(r,X)=\{x\in E | d(x,X)<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 (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.) DH(A,B) entre A et B est définie comme étant le plus petit nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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) \}

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 (En mathématiques, un espace métrique est un ensemble au sein duquel une notion de distance entre les éléments de l'ensemble est définie. C'est un cas...) et sa topologie (La topologie est une branche des mathématiques concernant l'étude des déformations spatiales par des transformations continues (sans arrachages ni recollement des structures).) dépend de celle de E.

Si E est un espace complet (En mathématiques, un espace métrique M est dit complet ou espace complet si toute suite de Cauchy de M a une limite dans M (c’est-à-dire qu'elle converge dans M). La propriété de complétude dépend...), alors K(E) est complet. Si E est un espace compact (En topologie de la droite réelle, la propriété de Borel-Lebesgue est une propriété topologique remarquable des segments, basée sur la notion de recouvrement....), 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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du vieillissement, suivi de son...) de l’inclusion admet une limite au sens de la distance de Hausdorff, à savoir \bigcap_{n \in \mathbb N}{A_n}

Généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de façon à ce qu'ils puissent être...)

La distance de Hausdorff peut être définie de la même manière pour les sous-espaces fermés non-compacts de E, mais la " distance " ainsi créée peut prendre des valeurs infinies et la topologie induite dépend de la métrique employée sur E.

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).

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.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.)

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)},

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

fd(S,T) = maxpS d(p,T).

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

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 (La carte de distances, aussi appelée transformée de distances, est une représentation d'une image numérique. Elle associe à chaque pixel de l'image la distance au point obstacle le plus proche. Ces points...).

Défaut

La distance de Hausdorff ne 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.

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 (Le squelette est une charpente animale rigide servant de support pour les muscles. Il est à la base de l'evolution des vertébrés. Celui ci leur a fourni un avantage sélectif...) 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), leur squelette 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és de remplacer la distance euclidienne par la distance hyperbolique dans le calcul de la distance de Hausdorff.

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.
Page générée en 0.076 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique