Mettre en correspondance des points, comparer des distributions, voire trouver des distributions “au milieu” de plusieurs distributions sont des enjeux à la fois en informatique graphique, en apprentissage automatique et dans de nombreux autres domaines. Le transport optimal est une théorie mathématique qui répond à ce problème. Il permet par exemple d’apparier deux ensembles (des points, des personnes, des objets) tout en minimisant le coût total de cet appariement (par exemple la somme des distances entre les points, des affinités entre personnes, similarités d’objets etc.).

Cependant, la complexité des algorithmes résolvant le problème de transport optimal est souvent trop élevée, et ces algorithmes ne peuvent pas être utilisés pour de très gros problèmes (des millions de points par exemple) ou en haute dimension. Une méthode souvent utilisée consiste alors à se ramener à une série de problèmes de transport optimaux en 1D, bien plus faciles à calculer – une méthode de transport “sliced”. Il suffit ainsi de projeter les données sur des droites, de les trier le long de ces droites et de les apparier dans l’ordre du tri. Bien que cette approche soit efficace, elle reste très approximative.

Dans un papier primé “meilleur papier” de la conférence ACM SIGGRAPH Asia 2025, des chercheurs du LIRIS ont proposé une méthode aussi efficace, mais bien plus précise. Une façon de trier des points le long d’une droite consiste à couper en deux la droite en répartissant les points de chaque côté, et de répéter l’opération sur les deux morceaux. À la place, les chercheurs proposent de choisir une nouvelle droite aléatoire à chaque fois que la droite précédente est coupée en deux. Cela produit une structure appelée “arbre BSP” (Binary Space Partitioning), dont la construction a la même complexité algorithmique qu’un simple tri. En construisant ainsi un arbre BSP simultanément sur les deux ensembles de points à apparier, et en s’assurant qu’il y ait bien le même nombre de points dans chaque sous-ensemble, on peut obtenir un appariement acceptable. 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. 

Les applications proposées sont nombreuses, allant du traitement des couleurs dans les images au morphing de formes, ou encore pour l’échantillonnage de surfaces 3D ou d’images. Pour ces applications, le transport “BSP” peut être plusieurs ordres de grandeur plus rapide que le calcul exact de transport optimal, et plusieurs ordres de grandeur plus précis que le transport “sliced”.
 

Plus d'informations : 

• HAL : https://hal.science/hal-05316444v1 
• Code : https://github.com/baptiste-genest/BSP-OT 
• Page de l'article : https://baptiste-genest.github.io/publications/#bsp-ot