Prix du meilleur papier à la conférence Eurographics 2024 au sein de l'équipe Origami

Lors de la conférence Eurographics 2024, conférence majeure en informatique graphique, qui a eu lieu à Limassol (Chypres) du 22 au 26 avril, le prix Günter Enderle du meilleur article a été décerné au travail mené par Baptiste Genest (Université Claude Bernard Lyon 1, LIRIS UMR 5205), Nicolas Courty (Université de Bretagne Sud, IRISA UMR 6074) et David Coeurjolly (CNRS, LIRIS UMR 5205). Le titre de cette étude est “Non-Euclidean Sliced Optimal Transport Sampling” et elle vise à étendre des stratégies d'échantillonnage de points sur des variétés non euclidiennes via du transport optimal par coupe.

Le transport optimal n'est pas un sujet neuf. Néanmoins, dans les dernières décennies, il a suscité un grand intérêt, en partie grâce aux nombreux progrès théoriques et numériques qui y ont été fait. L'outil majeur qu'apporte la théorie du transport optimal est la distance de Wasserstein. Issue des mathématiques appliquées, elle permet de quantifier la distance entre deux mesures de probabilités au sens du moindre effort pour transporter la masse d'une mesure sur l'autre étant donnée une fonction de coût. L'intérêt de l'outil est sa généricité des mesures que nous pouvons considérer (mesures discrètes --e.g. des ensembles de points--, des histogrammes, ou des mesures continues). Par exemple, si la distance de Wasserstein entre un ensemble de points et une distribution uniforme sur un domaine est très petite, on peut s'attendre à ce que ces points remplissent très harmonieusement ce domaine. Cette caractéristique de remplissage harmonieux de l'espace par un ensemble de points est ce qu'on appelle un "bruit bleu". Générer du bruit bleu de manière générique n'est pas une chose simple, mais la théorie du transport optimal permet de le faire. 

En revanche, le calcul de la distance de Wasserstein peut être lourd. Notre travail repose sur une propriété très intéressante du transport : c'est un problème compliqué en toutes dimensions, sauf en dimension 1 (appariement optimal donné par un simple tri des échantillons). De nombreux travaux ont proposé une approximation avec garanties, dites par "tranche" ou "coupe", de la distance de Wasserstein (Sliced Wasserstein distance). Elle consiste à moyenner des distances de Wasserstein 1d, des mesures projetées sur des directions aléatoires. Cette approche est une très bonne approximation, pour laquelle de nombreux algorithmes efficaces existent et qui dépend très peu de la dimension du problème. 

Ainsi, on peut combiner ces deux idées pour générer du bruit bleu par du transport optimal de manière efficace dans n'importe quelle dimension. On part d'un ensemble de points initial, qui n'est pas bruit bleu mais simple à générer, puis on optimise la position de chaque point de telle sorte qu'à chaque itération on réduise la "Sliced Wasserstein Distance" entre nos points et la distribution cible. Cette idée avait déjà été explorée par des travaux précédents, notamment au LIRIS, mais notre contribution réside dans l'extension de cette procédure à des géométries "non-euclidiennes".

Les géométries non euclidiennes sont des concepts fondamentaux en mathématiques. Ce sont les exemples les plus simples d'espaces qui ne soient pas plats (à l'inverse d'un plan par exemple). Pour les citer : la sphère, dont on dit qu'elle a une courbure positive, et le plan hyperbolique, qui a une courbure négative. Nous n'avons pas inventé la "Sliced Wasserstein Distance" sur ces espaces-là (ce fut le travail mené par Clément Bonet, un doctorant de Nicolas Courty, le 2e co-auteur de l'article), mais nous avons trouvé une "traduction" efficace de cette procédure d’échantillonnage sur ces géométries non euclidiennes.

En termes d'applications, puisque les géométries non euclidiennes sont des espaces intrinsèquement courbés, il désormais plus simple d'échantillonner des géométries plus génériques. En particulier, nous appliquons cette procédure pour échantillonner des maillages (en passant par une correspondance entre le maillage et la sphère, soit le plan hyperbolique) de manière intrinsèque (ce qui signifie que le résultat est indifférent au fait que la surface s'auto-intersecte par exemple). Notre contribution permet également d’échantillonner ce qu'on appelle le "plan projectif", et ainsi générer des ensembles harmonieux de rotations, de directions, etc...