Appareiller des points rapidement en les projetant

Publié par Redbran le 04/08/2019 à 08:00
Source: CNRS INS2I
2
Restez toujours informé: suivez-nous sur Google Actualités (icone ☆)


© 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 (L´informatique - contraction d´information et automatique - est le domaine...) 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 (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) de telle sorte qu'un point (Graphie) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) 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 (En bio-informatique, l'alignement de séquences (ou alignement séquentiel) est une...) d'ADN, de pistes audio, ou de textes) qui se résout classiquement avec des algorithmes de programmation dynamique (Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au...). La contribution principale a été de fournir un algorithme bien plus rapide que la programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent...) dynamique (Le mot dynamique est souvent employé désigner ou qualifier ce qui est relatif au mouvement. Il...) pour résoudre ce problème de manière exacte, ainsi qu'une méthode de décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils...) du problème en sous-problèmes indépendants en temps (Le temps est un concept développé par l'être humain pour appréhender le...) 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 (La formulation est une activité industrielle consistant à fabriquer des produits...) dite "sliced" d'un problème de transport (Le transport est le fait de porter quelque chose, ou quelqu'un, d'un lieu à un autre, le plus...) 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 (L'environnement est tout ce qui nous entoure. C'est l'ensemble des éléments naturels et...) 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 (En géométrie, la développée d'une courbe plane est le lieu de ses centres de...): 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
Page générée en 0.205 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise