Trouver la géométrie dans une meule de points

Piste bleue 12 octobre 2012  - Ecrit par  Frédéric Chazal Voir les commentaires

Grâce aux progrès récents de l’informatique, la représentation et la manipulation virtuelle d’objets physiques réels 3D sont devenues ces dernières années une nécessité et une pratique courante dans de nombreux domaines de l’industrie, de la science et même de la vie de tous les jours. Les exemples sont nombreux : un archéologue découvrant une statue peut la scanner et en envoyer en quelques instants un modèle numérique à un expert situé à des milliers de kilomètres afin d’avoir un avis ; un géographe ayant relevé les coordonnées de nombreux points sur un massif montagneux peut en extraire une carte 3D ; une entreprise disposant d’un prototype de pièce mécanique (comme celle de la figure ci-dessous) peut la scanner pour en obtenir un modèle numérique sur lequel elle pourra simuler différents type d’opérations (tests de déformation sous différentes contraintes, tests d’aérodynamisme,…) et qu’elle pourra aussi envoyer à une usine qui reproduira la pièce à l’autre bout du monde…

Dans chacun de ces cas, l’obtention du modèle numérique 3D nécessite de « reconstruire » une représentation continue de l’objet utilisable par l’ordinateur à partir des coordonnées d’un ensemble fini de points mesurés à sa surface. Il s’agit d’un problème délicat, connu sous le nom de « reconstruction de surface », qui a été largement étudié depuis une vingtaine d’années et pour lequel des solutions algorithmiques variées ont été proposées. Le rôle du mathématicien est de proposer des méthodes et des algorithmes permettant d’obtenir une surface ayant les mêmes caractéristiques géométriques et qui soit le plus proche possible de l’objet physique mesuré. Ce n’est que récemment que des résultats mathématiques généraux assurant la validité de nombreux algorithmes ont été établis. Etonnamment, ils reposent sur des idées très simples que nous allons esquisser dans cet article.

Reconstruire en remplaçant les points par des boules

Une idée très simple pour retrouver la géométrie de l’objet considéré à partir d’un ensemble de points mesurés à sa surface consiste à remplacer chaque point par une boule de rayon fixé centrée en ce point et à considérer la réunion de ces boules comme illustré sur la figure ci-dessous. On considère un objet en forme de bouée (ou de donut pour les gourmands) comme celui de la figure ci-dessous, appelé tore en termes mathématiques. Grâce à un scanner ou à un autre instrument de mesure on échantillonne cet objet en relevant les coordonnées d’un ensemble de points à sa surface (image de gauche). On fixe alors un nombre $r$ , et on considère la réunion des boules de rayon $r$ centrées en chacun des points de l’échantillonnage. Évidemment, si le rayon des boules (c’est-à-dire le nombre $r$) est choisi trop petit, leur réunion est pleine de trous et ne reflète pas la géométrie du tore (image du milieu). En revanche, pour un choix judicieux du rayon, nous obtenons une forme dont la surface, appelée bord en mathématiques, est semblable à celle du tore (image de droite) : elle est proche de l’objet initial et a la propriété de pouvoir être déformée continument en l’objet initial sans se recouper ou se déchirer. On dit alors que notre surface reconstruite est isotope à notre objet initial.

A partir d’un ensemble de points mesurés à la surface du tore couleur cuivre ci-dessus (image de gauche) on peut retrouver une surface proche en remplaçant chaque point par une boule de rayon convenable (image de droite).

Bien sûr, même si elle se confirme sur bon nombre de cas pratiques, la constatation précédente n’a pas valeur de résultat général et il est facile d’imaginer des situations où notre idée ne permet pas de reconstruire correctement la surface de l’objet échantillonné. Par exemple, si le nombre de points mesurés est insuffisant, oubliant de larges zones de l’objet, ou si certaines mesures sont erronées et représentent des points éloignés de l’objet (comme c’est le cas sur la figure ci-dessous), aucun choix de rayon des boules ne permettra de retrouver la géométrie de l’objet. Cependant, les mathématiques permettent d’identifier le domaine de validité de notre méthode et de transformer l’idée simple de départ en un résultat de reconstruction rigoureux. On dit que l’objet et l’échantillon sont proches au sens de Hausdorff lorsque tous les points de l’objet sont proches d’un point mesuré (aucune zone de l’objet n’a été oubliée) et lorsque tous les points mesurés sont proches de l’objet (il n’y a pas de mesure erronée).
En utilisant quelques outils classiques (mais non élémentaires) de géométrie et d’analyse, il a été démontré que si l’échantillon des points mesurés et l’objet sont suffisamment proches au sens de Hausdorff alors il existe un choix de rayon pour lequel la surface obtenue en remplaçant chaque point de l’échantillon par une boule de ce rayon est isotope à la surface de l’objet initial.

La distance de Hausdorff.

On peut quantifier rigoureusement la notion de proximité au sens de Hausdorff entre notre ensemble de points et notre objet, ou plus généralement entre deux objets $A$ et $B$ (en termes mathématiques on parle de sous-ensembles) de la façon suivante : considérons la plus petite des quantités $d$ telle que tous les points de $A$ soient à distance au plus $d$ d’un point de $B$ et réciproquement tous les points de $B$ soient à distance au plus $d$ d’un point de $A$. Cette quantité s’appelle la distance de Hausdorff entre $A$ et $B$.
En mathématiques, une distance sur un ensemble $X$ est une application $D$ qui, à chaque paire $(x,y)$ d’éléments de $X$, associe un nombre positif ou nul $D(x,y)$ vérifiant les trois propriétés suivantes :

  1. la distance de $x$ à $y$ est la même que celle de $y$ à $x : D(x,y) = D(y,x)$ ;
  2. si la distance entre $x$ et $y$ est nulle ($D(x,y) = 0$) alors $x$ et $y$ sont un seul et même élément de $X$ ($x=y$) ;
  3. si $x,y$ et $z$ sont des éléments de $X$ alors la distance de $x$ à $z$ est inférieure ou égale à la somme des distances de $x$ à $y$ et de $y$ à $z : D(x,z) \leq D(x,y) + D(y,z)$. On appelle cette propriété l’inégalité triangulaire.

Le caractère symétrique de la définition de Hausdorff implique qu’elle vérifie la propriété 1 et un raisonnement élémentaire (pas si évident lorsqu’on le fait pour la première fois) permet de prouver qu’elle vérifie la propriété 3. En revanche, la propriété 2 ne se vérifie pas en toute généralité [1] mais elle est satisfaite lorsqu’on se restreint à une classe de sous-ensembles (incluant les objets et les ensembles de points que nous considérons) appelés compacts. On touche là à une subtilité d’une branche des mathématiques appelée la topologie qui sort du cadre de cet article.
En résumé, la distance de Hausdorff donne au mathématicien un moyen de mesurer l’éloignement entre les objets que nous étudions, tout comme la distance usuelle permet de mesurer l’éloignement entre deux points de l’espace. Définir des distances sur les ensembles d’objets que l’on étudie est une démarche courante et classique en mathématiques.

Quand le bruit s’en mêle…

Il n’est pas rare en pratique que l’ensemble des points mesurés contienne des valeurs erronées créant des points aberrants loin de l’objet étudié [2].
Les boules centrées sur ces points créent alors des composantes « parasites » conduisant à un résultat désastreux (voir la figure ci-dessous). Dans ce cas, l’échantillon n’est plus proche de l’objet au sens de Hausdorff et le résultat de reconstruction énoncé précédemment n’est plus valable.

Lorsque l’ensemble échantillonné à la surface du tore contient des points aberrants (image de gauche), remplacer les points par des boules a un effet catastrophique : les points aberrants créent des composantes parasites qui ne permettent plus de retrouver la géométrie de l’objet de départ (image du milieu). L’image de droite représente une surface de niveau de la fonction « moyenne des distances aux 5 plus proches voisins » : elle est un peu « cabossée » mais on retrouve la géométrie du tore échantillonné !

Pour surmonter cette difficulté, il nous faut revenir sur l’approche précédente avec un regard un peu plus mathématique qui va nous indiquer la piste à suivre. La réunion de l’ensemble des boules d’un rayon $R$ centrées sur l’échantillon est exactement l’ensemble des points de l’espace situés à distance inférieure à $R$ d’un point de l’échantillon. De plus, la surface bordant cette union est l’ensemble des points qui se situent exactement à distance $R$ de l’ensemble des points de l’échantillon. En d’autres termes, la surface que nous reconstruisons est une surface de niveau de la fonction qui à chaque point de l’espace associe sa distance au point qui lui est le plus proche dans l’échantillon [3].
On parle alors de fonction distance à l’échantillon. C’est l’étude des propriétés mathématiques de ces fonctions distance qui permet de prouver le résultat de reconstruction énoncé précédemment.
Pour obtenir une méthode de reconstruction valide en présence de points aberrants, l’idée consiste à remplacer la fonction distance à l’échantillon par une nouvelle fonction dont certaines surfaces de niveau fourniront une reconstruction correcte de l’objet. Pour cela, plutôt que d’associer à chaque point de l’espace la distance à son plus proche voisin dans l’échantillon, on lui associe la moyenne des distances à ses $k$ plus proches voisins où $k$ est un nombre entier choisi plus petit que le nombre de points de l’échantillon [4]. Le procédé de reconstruction consiste alors à choisir une des surfaces de niveau de cette nouvelle fonction « moyenne des distances au $k$ plus proches voisins dans l’échantillon ». Nous l’illustrons pour un ensemble de points du plan sur la figure suivante.

L’image en haut à droite représente un ensemble de 200 points du plan dont 150 ont été échantillonnés près d’un cercle de rayon 1 et les 50 autres sont des points « aberrants » choisis au hasard. Sur l’image en haut à droite, nous avons représenté la réunion des disques de rayon 1 centrés sur l’ensemble de points. Les points aberrants empêchent de retrouver la géométrie du cercle. Les deux images du bas représentent une courbe de niveau de la fonction « moyenne des distances aux $k$ plus proches voisins » pour des valeurs de $k=3$ (à gauche) et $k=5$ (à droite). La zone en jaune représente l’ensemble des points où cette fonction est inférieure à 0.1. La courbe de niveau est donc celle délimitant la zone jaune de la zone rouge. On remarque que pour $k=3$ il reste encore 3 petites composantes parasites qui disparaissent pour $k=5$ permettant ainsi de retrouver une courbe de niveau ayant une géométrie proche de celle du cercle échantillonné.

On peut alors démontrer un résultat mathématique semblable à celui du paragraphe précédent valable pour des échantillons proches de l’objet en un sens beaucoup moins restrictif que celui de Hausdorff : si la proportion de points proches de l’objet au sens de Hausdorff est largement supérieure à la proportion de points aberrants (on parle dans ce cas de proximité au sens de Wasserstein) alors il existe une surface de niveau de la fonction « moyenne des distances » qui est isotope à la surface de l’objet échantillonné.

La distance de Wasserstein

La notion de proximité au sens de Wasserstein peut également se quantifier à l’aide d’une distance au prix d’une définition rigoureuse techniquement et conceptuellement plus sophistiquée que celle de distance de Hausdorff. Tâchons cependant d’en donner une idée à travers notre exemple du tore et de l’ensemble de points échantillonnés. Supposons que nous ayons décidé de peindre notre tore. Supposons également que la quantité totale de peinture nécessaire, qui est proportionnelle à la surface du tore, est répartie en parts égales dans des pots suspendus à chaque point de l’échantillon. Notre tâche consiste alors à utiliser les pots les uns après les autres et à en transporter le contenu sur un morceau de la surface du tore qui n’a pas encore été peinte. Il existe une grande variété de façons de procéder suivant l’endroit où nous choisissons de répandre chaque petit pot de peinture. On peut associer un coût à chaque façon de peindre : pour chaque pot, on multiplie la distance [5] qu’on fait parcourir à la peinture qu’il contient pour arriver à l’endroit où elle est répandue par la masse de peinture contenue dans le pot, puis on additionne chacune de ces quantités. On obtient ainsi le « coût » de notre façon de peindre. La distance de Wasserstein entre l’échantillon et le tore est alors le plus petit des coûts qu’il est possible d’obtenir. Intuitivement, si la majorité des pots de peinture est bien répartie autour du tore et si seulement quelques pots se trouvent loin, on pourra se débrouiller pour peindre le tore sans faire faire de longs trajets à la peinture située dans la majorité des pots.
On remarquera que, contrairement à la distance de Hausdorff, la notion de distance de Wasserstein ne fait pas seulement intervenir la distance entre les points de l’échantillon et le tore mais aussi une notion de masse (celle de la peinture) qui est transportée des points vers la surface du tore. Pour donner une définition rigoureuse de cette distance, il faut adopter un regard nouveau qui considère nos objets et nos échantillons non plus comme des sous-ensembles de l’espace ambiant mais comme des distributions de masse (des mesures en termes mathématiques).

Inférence géométrique et analyse des données

Une particularité intéressante de l’approche précédente est sa remarquable généralité. Elle permet d’étudier la structure géométrique d’ensembles finis de points sans se restreindre au cas de mesures effectuées à la surface d’objets physiques. Les progrès récents des moyens d’acquisition de données dans tous les domaines de la science, de l’économie ou même de la vie de tous les jours permettent d’obtenir d’immenses masses de données dont il faut comprendre la structure et l’organisation pour en tirer des informations pertinentes. Souvent, chaque observation est le résultat de mesures quantitatives (par exemple les coordonnées d’une position, une température, une intensité,…) qui peuvent être interprétées comme les coordonnées d’un point dans un espace de dimension 2, 3 ou plus, le nombre de dimensions étant égal au nombre de mesures pour chaque observation. On obtient ainsi des ensembles de points qui se concentrent autour de structures géométriques parfois complexes, comme par exemple dans le cas de la figure ci-dessous. Inférer et comprendre ces structures est un enjeu important de l’analyse des données qui génère depuis quelques années une importante activité de recherche mathématique. L’approche et les résultats que nous avons évoqués dans les paragraphes précédents pour la reconstruction de surfaces se généralisent à ce contexte d’analyse des données et apportent de nouveaux outils et méthodes mathématiques et algorithmiques pour l’inférence géométrique.

Un exemple de données représentées par un ensemble de points portant une structure géométrique. L’image de gauche de la figure ci-dessus représente un ensemble de données où chaque élément est un point dont les coordonnées représentent la position d’une galaxie observée dans une portion de l’univers (on travaille ici à une échelle tellement grande qu’une galaxie peut être assimilée à un point !). Il est connu des astrophysiciens que les galaxies ne sont pas distribuées uniformément dans l’univers mais ont tendance à se concentrer autour de structures géométriques filamentaires. L’image de droite qui met en évidence ces structures filamentaires a été obtenue grâce à une adaptation des méthodes de reconstruction présentées dans cet article.

Bibliographie

Les trois références suivantes contiennent les énoncés techniques et formels des résultats présentés dans cet article.

[CCSL1] F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compact Sets in Euclidean Spaces, in Discrete and Computational Geometry, Vol 41, 3, (2009).

[CCSL2] F. Chazal, D. Cohen-Steiner, A. Lieutier, Normal Cone Approximation and Offset Shape Isotopy, in Comp. Geom : Theory and Applications vol 42, 6-7, 2009.

[CCSM] F. Chazal, D. Cohen-Steiner, Q. Mérigot, Geometric Inference for Probability Measures, Journal on Foundations of computational Mathematics, 2011, volume 11, number 6.

Post-scriptum :

La rédaction d’Images des maths et les auteurs, remercient pour leur relecture attentive, les relecteurs dont le pseudonyme est le suivant : François Béguin, BOrel, François Brunault, fred, Carole Gaboriau, Julien, Frédéric Le Roux, Petru Mironescu, Gérard Besson.

Article édité par Frédéric Le Roux

Notes

[1par exemple si $A$ est une boule (pleine) et si $B$ est cette même boule à laquelle on a retiré le point au centre, alors $A$ et $B$ sont distincts et leur distance de Hausdorff est nulle : tout point autre que le centre de la boule est à la fois dans $A$ et dans $B$ ; le centre de la boule est dans $A$ et pour toute quantité $d>0$ à distance inférieure à $d$ d’un point de $B$.

[2On parle dans ce cas de bruit dans les données. C’est une analogie avec le bruit sonore qui parasite la musique.

[3Rappelons qu’une fonction est un objet mathématique qui à chaque point d’un ensemble (dans notre cas l’espace tridimensionel dans lequel nous vivons) associe une valeur numérique. On appelle surface de niveau associée à une valeur numérique fixée $r$, l’ensemble des points de l’espace en lesquels la fonction prend la valeur $r$. C’est exactement l’analogue tridimensionnel d’une courbe de niveau sur une carte où la fonction étudiée est celle qui associe son altitude à chaque point de la zone couverte par la carte.

[4En réalité pour des raisons techniques sortant du cadre de cet article on considère la racine carrée de la moyenne des carrés des distances (qui n’est pas égale à la moyenne des distances !) aux $k$ plus proches voisins.

[5Ici encore pour des raisons techniques, c’est le carré de la distance qu’on utilise dans notre contexte d’inférence géométrique

Partager cet article

Pour citer cet article :

Frédéric Chazal — «Trouver la géométrie dans une meule de points» — Images des Mathématiques, CNRS, 2012

Crédits image :

img_8548 - The model is provided courtesy of INRIA by the AIM@SHAPE Shape Repository

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM