Distance de Hausdorff

Distance de Hausdorff
Felix Hausdorff (1868 - 1942) est le mathématicien à l'origine de la distance portant maintenant son nom.

En mathématiques, et plus précisément en géométrie, la distance de Hausdorff est un outil topologique qui mesure l’éloignement de deux sous-ensembles d’un espace métrique sous-jacent.

Cette distance apparait dans deux contextes bien différents. Pour le traitement d'images, elle est un outil aux propriétés multiples, source de nombreux algorithmes. Elle indique si deux formes sont les mêmes et, si elles sont différentes, la distance quantifie ces dissemblances. En dimension 2, la distance de Hausdorff permet de numériser une image ou encore de reconnaître une forme. Cet outil, issu des mathématiques pures, n'est pas toujours adapté pour les traitements industriels. Par exemple, deux formes aux contours de longueurs différentes peuvent être proches, au sens de cette distance. Pour ces raisons, on utilise parfois des variantes, comme la distance de Hausdorff modifiée.

Pour le mathématicien pur, cette distance est à la géométrie, ce que la norme de la convergence uniforme est à l'analyse. La convergence uniforme, en analyse fonctionnelle procède d'une démarche qui consiste à travailler sur un nouvel ensemble. On n'étudie plus le comportement des nombres, réels ou complexes, sur lesquels est définie la fonction, mais celui d'un ensemble de fonctions. Typiquement, on cherche à résoudre une question à l'aide d'une suite de fonctions, qui sont vues comme des points d'un vaste espace, et qui convergent vers la solution. Les séries de Fourier procèdent d'une démarche de cette nature. Il est tentant d'aborder un problème de géométrie de la même manière. Un point de l'espace devient un solide, on recherche à trouver une solution à l'aide d'une suite de solides convergeant vers la solution. La notion de convergence demande une topologie, celle induite par la distance de Hausdorff offre une réponse.

Un exemple d'application est le problème isopérimétrique dans le plan euclidien. La question est de savoir quelle est la surface de plus grande aire possible, pour un périmètre donnée, la réponse est le disque. Une méthode consiste à construire une suite, par exemple de polygones, qui converge vers la solution.

Les premières questions qui se posent sont un peu de même nature que celles de l'analyse fonctionnelle. Dans quel cas l'espace est complet, quels sont les compacts, dispose-t-on d'applications continues, existe-t-il des sous-espaces aisément manipulables et denses, un peu à l'image des polynômes ? Les réponses sont suffisamment positives pour que la démarche soit féconde. Si l'espace sous-jacent est complet, l'espace utilisant la distance de Hausdorff l'est aussi. Les compacts, si l'espace métrique est euclidien, sont des ensembles fermés bornés, les polygones forment un ensemble dense, enfin la somme de Minkowski est continue.

La richesse des théorèmes sont autant d'atouts pour la mise au point d'algorithmes spécifiques aux besoins de l'industrie.

Sommaire

Construction de la distance

Approche intuitive

Distance de Hausdorff entre deux ensembles C et D.

L'idée intuitive de Hausdorff est de définir la distance entre deux ensembles C et D comme indiqué sur la figure de droite. C représente le carré rouge et D le disque bleu de même surface et de même centre. A l'endroit où les deux figures coïncident la couleur est violette, sinon elle est bleue ou rouge. Les différences entre les deux figures se matérialisent sous la forme de 4 lunules bleues et 4 presque triangles rouges.

On considère le point du carré le plus éloigné du disque, c'est un sommet du carré, à une distance a du disque. On considère ensuite le point du disque le plus éloigné du carré, c'est le sommet de la lunule et sa distance au carré est notée b. La distance de Hausdorff est la plus grande valeur des deux, en l'occurrence a, pour l'exemple choisi. Les valeurs a et b sont parfois appelées distance de Hausdorff relative.

La distance de Hausdorff, pour l'ingénieur en imagerie, est un indicateur de similarité entre deux formes géométriques, c'est la raison même de son utilité[1].

Pour que cette distance puisse vérifier le premier axiome, c'est-à-dire celui indiquant que la distance entre deux figures distinctes n'est jamais nulle, on ne peut considérer tous les ensembles. Deux boules, une ouverte et l'autre fermée, de même centre et de même rayon seraient deux ensembles différents à une distance nulle. Une autre raison pousse à limiter les ensembles considérés. La distance entre une droite et une boule serait infinie, ce qui n'est pas possible d'après les axiomes de la distance. Pour cette raison, Hausdorff limite l'ensemble aux bornés. Cette distance est souvent utilisée pour étudier des géométries proches de celles d'un espace de dimension finie, pour cette raison, on impose parfois aux ensembles d'être compacts[2]. Enfin, il n'est pas possible de donner un sens à la distance entre un fermé borné quelconque et l'ensemble vide, pour cette raison, l'ensemble vide n'est pas considéré.

Formulations de la distance

Il existe différentes manières d'exprimer la distance d(X, Y) entre deux ensembles fermés bornés non vides X et Y d'un espace métrique (E, δ). La première correspond à la définition du paragraphe précédent :

d(X,Y) = \max \; \{ \sup_{y\in Y} \inf_{x \in X} \delta(x,y), \quad \sup_{x\in X} \inf_{y \in Y} \delta(x,y)\}

Une autre formulation consiste à considérer les ensembles Xr et Yr, où r est un réel positif. Ici, Xr (resp. Yr) désigne l'ensemble des points de E à une distance inférieure ou égale à r de X (resp. Y). La distance prend alors la forme suivante :[3]

d(X,Y) = \min \{r \in \mathbb R_+ \quad X \subset Y_r \quad \text{et}\quad Y \subset X_r\}

Enfin, il est possible de remarquer que l'ensemble Xr correspond à la somme de Minkowski de X et de r.B, si B désigne la boule unité fermée.

d(X,Y) = \min \{r \in \mathbb R_+ \quad X \subset Y + r\mathcal B \quad \text{et}\quad Y \subset X + r\mathcal B\}

Définition formelle

Soient (E, δ) un espace métrique et EH l'ensemble des fermés bornés de E non vides. La distance de Hausdorff d de EH est l'application de EHxEH dans R+ définie par :

\forall X,Y \in E_H \quad d(X,Y) = \min \{r \in \mathbb R_+ \quad X \subset Y_r \quad \text{et}\quad Y \subset X_r\}

Ces notations sont utilisées dans tout le reste de l'article.

Remarque : Il est utile de bien séparer la distance d de celle de δ. On remarque en effet que la distance entre le vecteur nul et B est égale à 0, en revanche, la distance de Hausdorff entre le singleton vecteur nul et B est égale à 1.

\delta (0, \mathcal B) = 0 \quad\text{et}\quad d(\{0\}, \mathcal B) = 1

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’un écart (puisque deux sous-ensembles distincts mais partageant la même adhérence auront une distance de Hausdorff nulle).

Continuité

Ensemble dense

Article détaillé : Densité (mathématiques).
Exemple d'image matricielle.
Les polygones et les carrés choisis sur une grille définissent 2 ensembles denses.

L'existence d'ensembles denses intéresse autant le mathématicien que l'ingénieur en traitement d'images. Pour l'ingénieur, un sous ensemble dense permet d'approximer n'importe quel point de EH (le terme point désigne un élément de l'ensemble étudié, ici des figures géométriques). Ainsi FH est dense dans EH lorsque pour tout point X de EH et pour tout nombre réel ε strictement positif, il existe un point Y de FH à une distance inférieure à ε de X.

L'ensemble dense est choisi plus petit pour pouvoir être travaillé plus commodément. La figure de droite illustre deux ensembles denses, si E est un espace euclidien, comme le plan pour le traitement d'images. Le premier exemple correspond aux pixels. L'espace est quadrillé par un ensemble de droites (des hyperplans en dimension quelconque) dont les directions sont toutes orthogonales à un vecteur d'une base orthonormale et les droites parallèles entre elles sont régulièrement espacées. Cette grille définit un ensemble de petits carrés (d'hypercubes si la dimension est quelconque), le premier ensemble dense est celui constitué d'un ensemble fini de petits carrés de cette nature. Les ingénieurs parlent d'image matricielle

En mathématiques, on choisit souvent le pas de la grille égal à 1/2n, où n est un entier quelconque, il existe ainsi une infinité de tailles de grille possibles, de plus en plus précise à mesure que n augmente. Une forme, par exemple le cercle violet sur la figure de droite, est approximée par ces petits carrés. Un algorithme consiste à sélectionner un petit carré s'il possède une intersection non vide avec la figure qu'il doit approximer.

Une deuxième méthode consiste à choisir comme ensemble dense les polygones, ou encore les polyèdres dans le cas d'une dimension quelconque. Pour un ingénieur, beaucoup moins d'informations sont nécessaires pour décrire une figure géométrique avec cette méthode. Cette approche permet, soit un gain de temps, soit une précision accrue. La deuxième figure de droite est une approximation polygonale, aussi appelée image vectorielle. Pour le mathématicien, les polyèdres forment un ensemble contenant strictement le précédent, il est donc naturel qu'il soit dense, lui aussi.

Il est parfois utile de conserver la convexité, une fois encore, les polyèdres convexes forment un ensemble dense parmi les convexes de EH.

Fonctions continues

La courbe de Koch permet de construire une suite convergente pour la distance de Hausdorff et dont le périmètre diverge.

Si une fonction est continue, ce qu'elle représente est bien conservée par de petites modifications. Un exemple essentiel est la somme de Minkowski. A deux ensembles X et Y, on associe l'ensemble des vecteurs de la forme x + yx est élément de X et y de Y. En imagerie, sommer une figure avec un petit disque permet d'atténuer les contours. En mathématiques pures, la somme de Minkowski intervient dans de nombreux théorèmes isopérimétriques. Le fait que C soit un compact convexe implique l'égalité C + C = 2C (ce qui n'est pas une évidence, la première partie correspondant à une somme de Minkowski et la deuxième à une homothétie de rapport 2). C'est un élément clé de la démonstration du théorème de Minkowski, utilisé en théorie algébrique des nombres.

Un deuxième exemple est donné par la fonction mesure, si E est un espace euclidien. La mesure de Lebesgue associe à une figure son volume. Elle possède une forme de continuité pour la distance de Hausdorff, elle est semi continue supérieurement. Cela indique que si un algorithme construit une figure à l'aide d'approximations de plus en plus précises, la figure finale possède une mesure qui ne fait pas de saut vers le bas. Mathématiquement, on le modélise par une suite (Xn) de figures qui converge vers une figure X, au sens de Hausdorff. Le volume de la figure X n'est pas beaucoup plus petit que celui de Xn, si n est grand. Si μ désigne la mesure de Lebesgue, c'est-à-dire la fonction qui à une figure associe son volume :

\limsup_{n \to \infty} \mu(X_n) \leq \mu(X)

S'il n'existe pas de possibilité de saut vers le bas, il peut y en avoir vers le haut. On peut s'en rendre compte en construisant une image à l'aide d'étapes successives, notées (Xn). On suppose que l'image est composée de pixels trop petits pour être visibles. A chaque étape, l'algorithme ajoute quelques points isolés dans une surface C. Comme ils sont isolés, les images Xn ne contiennent rien de visible dans C tant que n reste petit. En revanche, si n devient très élevé, on peut voir apparaître une surface visible dans C, de mesure non nulle, qui est souvent un artéfact indésirable. Mathématiquement, cela provient du fait qu'il existe un ensemble dénombrable de points, qui forment chacun un ensemble de mesure nulle, dont l'adhérence n'est pas de mesure nulle. On peut prendre par exemple les points de C à coordonnées rationnelles.

A la différence du volume, la fonction périmètre, ou plus précisément la mesure de la frontière, ne possède aucune continuité. Il est possible de construire deux figures très proches, au sens de Hausdorff, et de périmètres aussi éloignés qu'on le souhaite. A l'aide de la courbe de Koch, il est possible de construire une suite convergente de figures géométriques, dont les périmètres successifs divergent. Cette discontinuité, pour l'ingénieur, signifie qu'un algorithme uniquement fondé sur la distance de Hausdorff risque de ne pas respecter précisément les contours. C'est une des raisons qui poussent à utiliser des distances modifiées[4].

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}

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.

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 ce problème, Choi et Seidel ont proposé de remplacer la distance euclidienne par la distance hyperbolique dans le calcul de la distance de Hausdorff.

Notes et références

  1. W. Rucklidge Efficient visual recognition using the Hausdorff distance Berlin : Springer , 1996 (ISBN 3540619933)
  2. Le choix de la compacité n'est pas toujours pris, on accepte alors tous les fermés bornés : J. Henrikson Completeness and Total Boundedness of the Hausdorff Metric MIT Undergraduate Journal of Mathematics
  3. Les deux dernières expressions sont utilisés par exemple par : A. Treibergs Inequalities that Imply the Isoperimetric Inequality University of Utah
  4. Un exemple de cette nature est donné par : E. Baudrier Méthode de comparaison d’images binaires Université de La Rochelle

Sources

  • H. Federer Geometric Measure Theory Springer Édition Réédition (1996) (ISBN 3540606564)
  • J. Munkres Topology; A First Course, Prentice Hall; 2nd edition (1999) (ISBN 0131816292)
Mesure de similarité
  • 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.

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Distance de Hausdorff de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Distance De Hausdorff — Felix Hausdorff (1868 1942) est le mathématicien à l origine de la distance portant maintenant son nom. En géométrie, la distance de Hausdorff est un outil topologique qui mesure l’éloignement de deux sous ensembles d’un espace …   Wikipédia en Français

  • Distance de hausdorff — Felix Hausdorff (1868 1942) est le mathématicien à l origine de la distance portant maintenant son nom. En géométrie, la distance de Hausdorff est un outil topologique qui mesure l’éloignement de deux sous ensembles d’un espace …   Wikipédia en Français

  • Distance De Hausdorff Modifiée — La distance de Hausdorff modifiée (MHD) a été développée par Dubuisson et Jain sur la base de la distance de Hausdorff. Ceux ci considèrent cette distance comme étant l une des plus adaptées pour la reconnaissance de formes. Définition La… …   Wikipédia en Français

  • Distance de Hausdorff modifiee — Distance de Hausdorff modifiée La distance de Hausdorff modifiée (MHD) a été développée par Dubuisson et Jain sur la base de la distance de Hausdorff. Ceux ci considèrent cette distance comme étant l une des plus adaptées pour la reconnaissance… …   Wikipédia en Français

  • Distance de hausdorff modifiée — La distance de Hausdorff modifiée (MHD) a été développée par Dubuisson et Jain sur la base de la distance de Hausdorff. Ceux ci considèrent cette distance comme étant l une des plus adaptées pour la reconnaissance de formes. Définition La… …   Wikipédia en Français

  • Distance de Hausdorff modifiée — La distance de Hausdorff modifiée (MHD) a été développée par Dubuisson et Jain sur la base de la distance de Hausdorff. Ceux ci considèrent cette distance comme étant l une des plus adaptées pour la reconnaissance de formes. Définition La… …   Wikipédia en Français

  • Distance Hyperbolique — La distance hyperbolique a été développée par Choi et Seidel afin de permettre la comparaison de formes par la distance de Hausdorff à partir de leur squelette. Soient P1(p1,r1) et P2(p2,r2) deux points du squelette pondéré de la forme S. La… …   Wikipédia en Français

  • Hausdorff — may refer to:* A Hausdorff space, when used as an adjective, as in the real line is Hausdorff. * Felix Hausdorff, the German mathematician that Hausdorff spaces are named after. * Hausdorff dimension, a measure theoretic concept of dimension. *… …   Wikipedia

  • Distance (Mathématiques) — Pour les articles homonymes, voir Distance. En mathématiques, une distance est une application qui formalise l idée intuitive de distance, c est à dire la longueur qui sépare deux points. Sommaire 1 Distance sur un ensemble …   Wikipédia en Français

  • Distance (mathematiques) — Distance (mathématiques) Pour les articles homonymes, voir Distance. En mathématiques, une distance est une application qui formalise l idée intuitive de distance, c est à dire la longueur qui sépare deux points. Sommaire 1 Distance sur un… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”