Les histogrammes synthétisent des masses de données en un résumé simple : la fréquence d’apparition de ces données. Ainsi, une pyramide des âges est un histogramme représentant le nombre d’habitants par tranche d’âge, les résultats de sondages politiques se résument souvent par la fraction de votants pour chaque parti…. et un histogramme de couleurs d’une photo décrit la distribution des couleurs dans la photo, par exemple le nombre de pixels bleus, jaunes, violets, rouges, etc. Les histogrammes sont donc présents partout où les données abondent, et c’est particulièrement le cas en informatique graphique !
Le transport optimal est une théorie mathématique visant à mieux comprendre et utiliser ces histogrammes, et a été largement développé par le médaillé Fields Cédric Villani. Le transport optimal permet entre autres de voir ce qui se passe entre deux histogrammes donnés. Par exemple, si nous connaissons la pyramide des âges pour une population qui boit 5 verres d’alcool par jour, ainsi que la pyramide des âges pour une population qui ne boit pas du tout, le transport optimal permet de prédire raisonnablement ce que serait la pyramide des âges d’une population qui boit 1, 2, 3 ou 4 verres d’alcool par jour. Pour cela, cette théorie considère le premier histogramme comme n’étant qu’un gros tas de sable qu’il faut transporter avec une petite cuillère dans un trou qui a la forme du second histogramme, et ce, avec le moindre effort. Si on s’arrête en chemin avec nos petites cuillères à chaque trajet, et que l’on dépose le sable au sol, il se formera un nouveau tas de sable (et donc un histogramme) qui sera un des histogrammes "intermédiaires" entre ces deux histogrammes. En profitant des informations sur l’histogramme de départ et d’arrivée, il est ainsi possible d’en déduire des informations sur les histogrammes « en cours de route ». On appelle cela une "interpolation" entre deux histogrammes, et peut être vu comme une moyenne de deux histogrammes.
Des méthodes numériques récentes permettent de calculer ce "transport de sable" de manière très efficace, et généralisent même pour une interpolation entre plus de deux histogrammes. Ces méthodes permettent d’obtenir des moyennes pondérées de plusieurs histogrammes, à la manière des moyennes avec des coefficients pour le baccalauréat. Dans une publication présentée à SIGGRAPH, les chercheurs développent le procédé inverse : étant donnés un ensemble d’histogrammes et leur moyenne, il est nécessaire de retrouver les coefficients de pondération correspondants à cette moyenne. Mieux, si on ne possède pas exactement une moyenne d’histogrammes, mais seulement un autre histogramme s’en approchant, cette méthode trouvera la moyenne d’histogrammes s’en approchant le plus.
Une application particulièrement intéressante en informatique graphique est la manipulation des couleurs des images. Si nous possédons une photographie de paysage prise en été, aux couleurs verdoyantes, et que nous voulons lui donner un aspect plus automnal, nous pouvons télécharger une base de données de photographies de paysages différents pris en automne pour s’inspirer de leurs couleurs orangées. Pour cela, l’algorithme va construire un histogramme de couleurs du paysage estival verdoyant, et va chercher à trouver de quelle moyenne d’histogrammes automnaux il s’en approche le plus. Partant de là, il sera capable de transformer l’image estivale en image automnale, aux couleurs orangées. Cette méthode a également donné lieu à d’autres applications, en géométrie, imagerie médicale et rendu 3D matériaux.
Publication : Wasserstein Barycentric Coordinates : Histogram Regression Using Optimal Transport, Nicolas Bonneel [1], Gabriel Peyré [2], Marco Cuturi [3]
Un autre article présenté à SIGGRAPH utilise un calcul de transport optimal pour un problème plus général de mise en correspondance entre deux objets 3D. Par exemple, analyser deux mains de façon géométrique pour être capable de reconnaître et de « coupler » ensemble les paumes, pouces, index, ou de la même façon tout autre objet.
Il s’agit ici de profiter des avancées numériques du calcul du transport optimal pour un problème plus complexe, appelé Gromov-Wasserstein. Le but est de trouver un transport entre deux formes qui respecte les distances le long de chaque forme. Les points sont ainsi vus dans une géométrie géodésique, qui estime que les distances ne varient pas : il s’agit de la distance qu’effectuerait une fourmi en suivant le long de l’objet, au contraire de l’abeille qui suivrait une ligne droite. En suivant le long de votre corps, votre index est toujours aussi éloigné de l’auriculaire, que vous ayez la main ouverte ou repliée. Ainsi, deux points de la première forme doivent être transportés sur deux points de la deuxième forme en gardant la même distance que les points d’origine. L’utilisation des distances géodésiques permet de mettre en correspondance de façon quasi exacte des formes articulées telles que des mains, mais aussi d’en déduire les points équivalents sur des objets proches (les autres exemples de l’image). L’algorithme utilisé est similaire aux algorithmes récents de transport optimal. Là encore, d’autres applications ont été développées, tel que pour la visualisation de base de données d’images et de formes.
Publication : Entropic Metric Alignment for Correspondence Problems, Justin Solomon, Gabriel Peyré, Vladimir G. Kim, Suvrit Sra
Voir aussi :
