Apparier des points : nos travaux présentés à SIGGRAPH 2019

Le LIRIS est encore à SIGGRAPH, la conférence phare de l'informatique graphique, cette fois pour présenter les travaux de Nicolas Bonneel et David Coeurjolly sur l'appariement de points. Un algorithme très rapide a été développé, utilisant des projections 1-d de nuages de points de plus hautes dimensions, et basé sur des notions de transport optimal.

Nous avons présenté cet été un nouvel algorithme rapide d'appariment de points, avec des applications en traitement des couleurs, et en recalage de nuages de points 3-D. Cet algorithme consiste à projeter les points sur des droites de directions aléatoires, puis, une fois le problème réduit à une seule dimension, à procéder à un appariment 1-D.

Lorsque le nombre de points dans les deux ensembles est le même, cet appariment 1-D est trivial : il suffit d'ordonner les points, puis de les apparier par ordre croissant. Cependant, lorsque le nombre de points est différent, les méthodes existantes sont moins triviales et bien plus couteuses -- typiquement, des méthodes de programmation dynamique sont utilisées. Nous avons développé un algorithme qui est plusieurs ordres de grandeur plus rapide que ces méthodes. Il résout ainsi un problème dit de transport optimal "partiel" 1-D.

Nous revenons sur cet algorithme dans un article de vulgarisation pour le CNRS : https://ins2i.cnrs.fr/fr/cnrsinfo/apparier-des-points-rapidement-en-les-projetant