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

Frédéric Chazal, directeur de recherche dans l'équipe Geometrica, explique les grands principes du domaine de recherche de son équipe en calcul géométrique en se basant sur des exemples concrets d'images.

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. Étonnamment, 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.

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

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

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.