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