Appareiller des points rapidement en les projetant
Publié par Redbran le 04/08/2019 à 08:00
Source: CNRS INS2I

© 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 d'activité scientifique, technique et industriel en rapport avec...) 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é (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et...) entre les points mis en correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le terme désigne des échanges de courrier personnels plutôt qu'administratifs.) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de points des deux ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme...) 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 (Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au moyen d'un ordinateur tout problème d'optimisation dont la fonction objectif se décrit comme la somme de...). 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 l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).) dynamique (Le mot dynamique est souvent employé désigner ou qualifier ce qui est relatif au mouvement. Il peut être employé comme :) 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 soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie, dégénèrent sous...) 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 changement dans le monde.) 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 (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce...) 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 homogènes, stables et possédant des...) 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 souvent en utilisant des véhicules et des voies...) optimal.

Une application en informatique consiste à recaler un nuage (Un nuage est une grande quantité de gouttelettes d’eau (ou de cristaux de glace) en suspension dans l’atmosphère. L’aspect d'un...) 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 artificiels au sein duquel se déroule la vie humaine. Avec les enjeux écologiques actuels, le terme 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 (En géométrie, la développée d'une courbe plane est le lieu de ses centres de courbure. On peut aussi la décrire comme l'enveloppe...): 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.203 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique