Transport optimal : une méthode simple et efficace pour des problèmes de grande taille

En informatique graphique, le transport optimal permet par exemple de transférer les couleurs d’une image à une autre de manière naturelle et cohérente. Il est aussi utilisé pour le morphing de formes ou l’échantillonnage de surfaces 3D. Ces applications reposent sur une problématique clé : l’assignation optimale de points entre deux ensembles.

L’assignation de points consiste à apparier chaque élément d’un ensemble à un élément d’un autre ensemble, en minimisant un coût global — la somme des distances entre les points ou des mesures de dissimilarité par exemple. On parle alors d’un problème d’assignation par transport optimal. Celui-ci se pose dans de nombreux domaines, comme l’apprentissage automatique (pour aligner des données) ou la vision par ordinateur (pour comparer des formes).
Cependant, les algorithmes classiques de transport optimal, bien qu’efficaces en théorie, deviennent trop coûteux en calcul pour des ensembles de données massifs (comme des millions de points) ou en haute dimension. Une solution courante, le transport « sliced », simplifie le problème en le décomposant en une série de transports 1D pour lesquels un simple tri des points résout le problème, mais au prix d’une précision réduite.

Pour répondre à ce défi, des chercheurs  du LIRIS ont proposé une méthode innovante, primée « meilleur papier » à la conférence ACM SIGGRAPH Asia 2025. Leur approche utilise un arbre BSP (Binary Space Partitioning) pour assigner les points de manière plus précise et efficace. Au lieu de trier les points le long d’une seule droite, ils choisissent à chaque étape du tri une nouvelle direction aléatoire pour diviser l’espace. Ces divisions successives de l’espace produisent un arbre binaire. En construisant simultanément cet arbre sur les deux ensembles de points et en équilibrant le nombre de points dans chaque sous-ensemble, ils obtiennent un appariement de qualité. De plus, en répétant l’opération avec des directions aléatoires différentes, on peut obtenir plusieurs appariements qui peuvent être combinés efficacement pour réduire le coût de transport et atteindre un appariement presque optimal dans beaucoup de situations.

Résultat : leur méthode est plusieurs ordres de grandeur plus rapide que le transport optimal exact, tout en étant bien plus précise que le transport « sliced ». Une avancée qui ouvre de nouvelles perspectives pour l’assignation de points en informatique graphique, en apprentissage automatique et au-delà.