Analyse sans paramètre des surfaces discrètes – PARADIS

Ce projet vise à proposer un cadre théorique et pratique pour l'analyse automatique des surfaces digitales. Une opportunité de réaliser une avancée majeure est le développement récent d'algorithmes originaux. Ces algorithmes décident à la volée où sonder la surface digitale et font croître un morceau de plan digital tangent par construction. La direction de croissance est donnée par des propriétés arithmétiques et géométriques du plan digital ajusté et c'est pour cette raison que le terme «plane-probing« en anglais qualifie ce type d'algorithme. Nous pensons que ces algorithmes donnent la bonne direction à suivre car ils fournissent un moyen d'obtenir un morceau de plan digital localement ajusté à la surface digitale sans aucun paramètre. Nous nous attendons aussi à ce que le vecteur normal de ce morceau de plan digital soit une estimation précise du vecteur normal local.

Nous avons d'abord proposé un nouvel algorithme de type «plane-probing« moins coûteux en temps de calcul que les algorithmes existants. Il exige un plus petit nombre de sondages, c'est-à-dire d'appels au prédicat «est-ce qu'un point x donné appartient au plan digital P ?«. La borne supérieure théorique est en effet abaissée de O(w log w) à O(w) appels au prédicat, où w est l'épaisseur arithmétique du plan digital P, mais beaucoup moins d'appels sont observés en moyenne. Cette réduction est rendue possible par une étude qui montre comment éviter les calculs qui ne contribuent pas à la solution finale.
Dans un deuxième temps, nous avons surmonté la principale difficulté dans l'utilisation pratique des algorithmes existants. En effet, ils retournent maintenant un vecteur normal correct à partir de n'importe quel point de départ et non pas uniquement lorsqu'ils sont initialisés à partir de certains points bien identifiés. Cette généralisation est rendue possible notamment par des déplacements progressifs au cours du calcul de manière à simuler un départ depuis les points les plus appropriés.

Une étude bornant la taille de la zone dans laquelle sont localisés les calculs est en cours. Elle devrait nous permettre de mieux généraliser nos algorithmes aux surfaces digitales arbitraires. En utilisant ces algorithmes, nous espérons en déduire un estimateur de vecteur normaux efficace, sans paramètre, précis et donner une évaluation théorique de la précision par rapport à la résolution.
De plus, les algorithmes de type «plane-probing« ne fournissent pas seulement un vecteur normal, mais aussi une taille de voisinage requise, ainsi qu'une information de position, ce qui sera utile pour une analyse multi-échelle des surfaces digitales.

J-O. Lachaud, J. Meyron, T. Roussillon, An Optimized Framework
for Plane-Probing Algorithms, Journal of Mathematical Imaging
and Vision, 2020 (https://doi.org/10.1007/s10851-020-00965-6)

T. Roussillon, J-O. Lachaud, Digital Plane Recognition with Fewer
Probes, 21 st IAPR Int. Conf. on Discrete Geometry for Computer
Imagery, LNCS, Vol. 11414, p. 380-393, 2019
(https://dx.doi.org/10.1007/978-3-030-14085-4_30)

Dans de nombreuses applications (en science des matériaux ou en imagerie médicale par exemple), des dispositifs d'acquisition non invasifs comme l'imagerie par résonance magnétique et la tomographie ou microtomographie aux rayons X, sont nécessaires pour l'observation, la prise de mesures ou l'aide au diagnostique. Ces dispositifs génèrent habituellement des données volumiques, c'est-à-dire des images 3D, composées de données régulièrement espacées dans un domaine rectangulaire. Les volumes 3D proviennent de la segmentation de telles images. Ils peuvent aussi être synthétisés, car de nombreux schémas numériques de simulation reposent sur la régularité du support des données.

Le projet PARADIS porte sur la géométrie des frontières des volumes 3D, appelées surfaces digitales. Conserver la nature discrète des données est un avantage pour effectuer des calculs exacts en nombres entiers, pour réaliser des opérations géométriques booléennes ou pour utiliser des structures de données efficaces. Un inconvénient est sa pauvre géométrie : une surface discrète est seulement composée d'éléments de surface quadrangulaires dont le vecteur normal est parallèle à l'un des axes, cela quelle que soit la résolution. De nombreuses tâches en informatique graphique, vision par ordinateur ou analyse d'image 3D, nécessitent une géométrie plus riche : le rendu, les déformations de surface pour la simulation physique ou le suivi, les mesures de précision, etc. Pour réaliser des tâches géométriques pertinentes et bénéficier en même temps des avantages cités précédemment, on a besoin d'enrichir la géométrie des surfaces digitales en estimant des informations supplémentaires en chaque élément de surface. Ce projet porte plus particulièrement sur l'estimation de quantités géométriques locales et du premier-ordre, telle que la direction du vecteur normal. Il vise à fournir des estimateurs précis et sans paramètre basés sur une portion de la surface autour de chaque élément, de taille adaptée. Puisque nous cherchons des estimations du premier-ordre, cette portion sera typiquement un morceau de plan digital localement ajusté à la surface.

Un défi est de recouvrir toute la surface par des morceaux de plan digital. Un tel recouvrement ne fournit pas seulement un champ de vecteurs normaux, mais pourrait aussi fournir, s'il est calculé pour plusieurs versions sous-échantillonnées du volume 3D donné en entrée, une manière de déterminer l'échelle à laquelle la présence de bruit est peu probable : un grand nombre de très petits segments de plan digital révèle la présence de bruit, tandis que les parties lisses sont décomposées en un plus petit ensemble de segments. Ce qui est difficile, c'est qu'il y a une explosion combinatoire des morceaux de plan digital et que parmi eux, tous ne sont pas tangents à la surface digitale.

Une opportunité d'avancer sur cette question est de considérer le récent développement des algorithmes dits "plane-probing", proposés par le porteur et ses collaborateurs. Ces algorithmes permettent de décider à la volée comment inspecter la surface digitale et faire croître un segment de plan digital tangent par construction. La direction de croissance est donnée à la fois par des propriétés arithmétiques et géométriques.

Nous attendons des impacts positifs en informatique graphique, vision par ordinateur et analyse d'image 3D, car les tâches de haut-niveau mentionnées précédemment et bien d'autres, comme l'extraction de primitive ou la compréhension de scène, dépendent de la qualité de l'estimation des normales. De plus, comme de nombreuses images 3D sont susceptibles d'être dégradées par du bruit, notamment en imagerie médicale, la détection du bruit est une tâche cruciale qui pourrait devenir une étape incontournable du traitement des images 3D.