Apparier des points rapidement en les projetant
Deux chercheurs du CNRS du Laboratoire d'Informatique en Images et Systèmes d'Information (LIRIS - CNRS/INSA de Lyon/Université de Lyon/École Centrale de Lyon) iront présenter leurs travaux à SIGGRAPH à Los Angeles aux États-Unis cet été. SIGGRAPH est une conférence phare, et réunit régulièrement environ 20000 participants autours des principaux thèmes de l'informatique graphique.
Le problème étudié est celui d'apparier deux ensembles de points de manière optimale, c'est-à-dire en minimisant la somme des distances au carré entre les points mis en correspondance de telle sorte qu'un point ne peut être apparié qu'à un seul point (critère de surjectivité).
Lorsque le problème est 1-d, et que le nombre de points des deux ensemble est le même, il existe une solution triviale qui consiste à les mettre progressivement en correspondance un à un de gauche à droite le long de la ligne 1-d (le premier point le plus à gauche du premier ensemble est mis en correspondance avec le premier point le plus à gauche du second ensemble, etc.). Cependant, lorsque le nombre de points des deux ensembles n'est pas le même, le problème est beaucoup plus complexe : il s'agit alors d'un problème d'alignement (similaire au problème d'alignement de séquences d'ADN, de pistes audio, ou de textes) qui se résout classiquement avec des algorithmes de programmation dynamique. La contribution principale a été de fournir un algorithme bien plus rapide que la programmation dynamique pour résoudre ce problème de manière exacte, ainsi qu'une méthode de décomposition du problème en sous-problèmes indépendants en temps quasi-linéaire.
L'intuition derrière cette méthode est qu'une assignation du type "plus proche voisin" minimise la somme voulue et peut être obtenue en temps linéaire. Cependant, deux points peuvent avoir le même plus proche voisin, et cette assignation ne respecte donc pas le critère de surjectivité. L'algorithme proposé procède à des ajustements locaux qui viennent résoudre les problèmes de surjectivité de l'assignation par plus proche voisin.
Lorsque les ensembles de points ne sont pas unidimensionnels mais que les points vivent dans un espace de dimension deux ou plus, une solution approchée consiste à les projeter itérativement sur plusieurs droites et opérer des appariements 1-d le long de ces droites. C'est une formulation dite « sliced » d’un problème de transport optimal.
Une application en informatique consiste à recaler un nuage de points (par exemple issus d'acquisitions 3d d'un robot) parmi un nuage de points plus gros (par exemple un environnement virtuel 3d scanné). Dans ce cas, le problème est de retrouver une transformation rigide (ou un autre modèle de transformation) qui permet d'aligner le premier nuage de points vers le second. Il a fallu adapter un algorithme classique (dit "Iterative Closest Point" ou ICP) pour bénéficier de la méthode d'appariement optimale développée : les résultats sont beaucoup plus précis qu'avec la méthode ICP.
D'autres applications en traitement de couleurs ont été proposées.
Publication :
SPOT: Sliced Partial Optimal Transport - Nicolas Bonneel1 , David Coeurjolly2