[News] Appareiller des points rapidement en les projetant

Informatique et nouvelles technologies...

Modérateur : Modérateurs

Redbran
Messages : 1090
Inscription : 16/05/2015 - 10:01:33
Activité : Profession libérale ou Indépendant

[News] Appareiller des points rapidement en les projetant

Message par Redbran » 04/08/2019 - 8:00:17


Image
© 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

Source: CNRS INS2I

Victor
Messages : 17125
Inscription : 05/06/2006 - 21:30:44
Activité : Retraité
Contact :

Re: [News] Appareiller des points rapidement en les projetant

Message par Victor » 04/08/2019 - 9:50:53

Pas compris ça parle de géométrie avec la vision par un point mais je n'en sais pas plus
En ce qui concerne la recherche en sciences, Je dirais : Cherche encore !

Avatar de l’utilisateur
cisou9
Messages : 10078
Inscription : 12/03/2006 - 15:43:01
Activité : Retraité
Localisation : Pertuis en Lubéron
Contact :

Re: [News] Appareiller des points rapidement en les projetant

Message par cisou9 » 04/08/2019 - 10:08:41

___________ :_salut:
C'est un problème d’algorithme et l'article s'adresse à des personnes qui connaissent parfaitement cette programmation perso je n'utilise pas ce type d'algorithme en programmation et l'article manque de détails pour les néophytes. ____ :_grat2: ____
Un homme est heureux tant qu'il décide de l'être et nul ne peux l'en empêcher.
Alexandre Soljenitsyne.

Répondre