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
Fruit d'une collaboration ESA-NASA associant notamment le Cnes, le CNRS et le CEA, la sonde Solar Orbiter a décollé le 9 février 2020 depuis le centre spatial Kennedy...
On entend souvent les mères raconter que leurs premières rides ou leurs premiers cheveux blancs sont apparus après avoir eu un enfant. Qu’on se le dise: enfanter,...
Une expérience menée auprès de l'installation ISOLDE du CERN montre que le noyau du 222Ra (isotope du radium) a la forme d'une poire. La plupart des noyaux ont la...
"Le pourquoi du sexe" reste encore aujourd’hui une des grandes questions évolutives. La découverte de lignées asexuées chez des espèces animales considérées...
En analysant les images du relevé LoTSS (LOFAR Two Meter Sky Survey), une équipe comprenant un astronome de l’Observatoire de Paris - PSL a découvert des ondes...
Des chercheurs de l’UNIGE et de l’Université de Manchester ont découvert des structures basées sur des matériaux bidimensionnels qui permettent d’émettre de...
Une collaboration entre biologistes et physiciens a permis de décrypter une étape clé de l’infection causée par le méningocoque, un pathogène humain responsable...
Des chercheurs de l’UNIGE et de CY Cergy Paris Université démontrent que les situations présentes évoquent en mémoire des situations passées qui partagent des...
Des scientifiques testent l’expérience NA61/SHINE du CERN avec un appareil construit en briques Lego. Le complexe d’accélérateurs du CERN permet aux...
Une nouvelle étude d’apprentissage automatique suggère la présence d’au moins neuf « expressions » de genre La terminologie conçue pour expliquer et...
Optimiser Euclid: une corrélation croisée entre les observables Pour mesurer les paramètres cosmologiques, le télescope spatial Euclid utilisera deux sondes...
Par Gillian Woodford Une forme de stéatose hépatique qui touche fréquemment les patients atteints du VIH peut être traitée en toute sécurité au moyen de la...
Une équipe internationale d’astronomes comprenant des chercheurs de l’Observatoire de Paris - PSL a obtenu en décembre 2019 une image de la surface de la célèbre...
Océans: la fragmentation des particules joue un rôle majeur dans la séquestration du carbone Une équipe franco-britannique pilotée par le Laboratoire...
La vie en ville peut faire évoluer les populations urbaines différemment des autres. Des chercheurs du laboratoire Biogéosciences (CNRS/EPHE/Université de Bourgogne)...
Les télescopes de l’ESO scrutent la baisse de luminosité de surface de l’étoile Bételgeuse Grâce au Very Large Telescope (VLT) de l’ESO, les astronomes ont...
Une initiative de l’UE a publié un rapport sur les solutions et recommandations adoptées pour répondre aux préoccupations environnementales liées à la production...
"Travailler l’imaginaire est l’une des parties qui m’intéresse le plus dans ma recherche. Si on avait une géométrie qui n’est pas comme la géométrie plate...
Un progrès important vient d'être réalisé en développant un algorithme permettant de calculer le problème quantique à N corps jusqu’à l’ordre 15, très...
L’organisation tridimensionnelle des chromosomes doit être régulée afin d’assurer le bon fonctionnement de processus biologiques tels que la transcription, la...
Ce site fait l'objet d'une déclaration à la CNIL
sous le numéro de dossier 1037632
Informations légales