Posté par Redbran le Dimanche 04/08/2019 à 08:00
Appareiller des points rapidement en les projetant

© Nicolas Bonneel, David Coeurjolly (Univ. Lyon - CNRS)
Deux chercheurs du CNRS du laboratoire LIRIS 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'appareiller 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 appareillé 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.

SPOT: Sliced Partial Optimal Transport 29.07.2019 Partager Audiodescription

Référence publication:
SPOT: Sliced Partial Optimal Transport
Dernières news
Le déménagement vers des chambres individuelles au site Glen du Centre universitaire de santé McGill (CUSM) a permis de réduire considérablement les taux...
D’une taille de 2 060 km, le noyau de Mercure est plus gros de 50 km qu’on ne le croyait jusqu’ici: c’est ce qu’ont découvert trois chercheurs du Laboratoire...
Des embryons de poulet mettent en temps normal une vingtaine de jours pour devenir poussins. En observant la formation de leurs pattes, une équipe du CNRS et de...
Près de 40 % des 40 principaux oléoducs et gazoducs transnationaux qui traversent l’Europe sont en exploitation depuis plus de 40 ans. Une initiative de l’UE a...
La dépression peut être associée à des comportements comme l’évitement social, c’est-à-dire le refus d’être confronté aux situations d’interactions avec...
Des études ont montré qu’il est possible d’atténuer les manifestations du trouble déficitaire de l’attention avec hyperactivité (TDAH) chez l’enfant en...
Une équipe d’astronomes dirigée par Anne-Marie Lagrange, chercheuse du CNRS à l’Institut de planétologie et d’astrophysique de Grenoble (CNRS/Université...
Les anti-inflammatoires non stéroïdiens (ibuprofène) et les analgésiques comme le paracétamol sont parmi les médicaments les plus prescrits pendant les premiers...
Afin d'améliorer les performances des super condensateurs, des chercheurs de l'lnstitut de recherche interdisciplinaire de Grenoble (lRlG) ont eu l’idée d’espacer...
Des chercheurs de l’UNIGE, du CHUV, de l’EPFL, du CIBM, des HUG et de l’UNIL démontrent comment des maladies chroniques du foie provoquent un changement...
Des ingénieurs ont mis au point un processus de chargement par conduction et de paiement automatisé pour les véhicules électriques (VE). Cette solution permettra...
Le Supersynchrotron à protons recevra un nouvel arrêt de faisceaux avant la fin du deuxième long arrêt du complexe d’accélérateurs du CERN. D’ici la fin du...
La thèse de doctorat de feu Bernard Arcand, gardée sous scellés à l'Université Cambridge pendant un demi-siècle, met en lumière un peuple de chasseurs-cueilleurs...
Longtemps considéré par les experts en aérodynamique comme le Saint-Graal de la discipline, l’écoulement laminaire naturel permettra, on l’espère, aux...
Un remorqueur letton abrite le premier banc d’essai d’une nouvelle technologie visant à purifier les gaz d’échappement des bateaux. À lui seul, le trafic...
Des scientifiques sont parvenus à caractériser des composantes essentielles qui masquent les rayonnements primordiaux émis par le Big Bang. Ces résultats...
Grâce à une étude basée sur l’analyse des comportements et de l’activité cérébrale (EEG), les chercheurs démontrent que les chevaux ont une mémoire...
Il est rare que les ingénieurs prennent la peine de modéliser les incendies du fait de la complexité et du coût que cela représente. Un système récemment mis au...
L’amélioration des paliers lisses est l’un des facteurs clés permettant de renforcer la sécurité des aéronefs. Le projet AOrbit s’emploie à construire un...
Si une partie du contenu de l’étoile à neutrons commence à se déplacer vers l’extérieur, la rotation de l’étoile s’accélère. C’est ce que les...
Ce site fait l'objet d'une déclaration à la CNIL
sous le numéro de dossier 1037632
Informations légales