Thesis of Agathe Herrou

Symmetric semi-discrete optimal transport for mesh interpolation

Defense date: 20/10/2022

Advisor: Nicolas Bonneel
Coadvisor: Julie Digne


This thesis aims to develop geometric methods to approximate displacement interpolation, derived from optimal transport. Optimal transport is a mathematical theory modeling movements of matter under a cost minimization constraint, with many applications in physics, computer graphics and geometry. The minimum displacement cost between two distributions defines a distance, which itself is at the origin of displacement interpolation. This interpolation may under certain conditions present discontinuities, that the discretized approximations of the optimal transport do not always successfully capture. The work of this thesis aims to develop an approximation that captures these discontinuities well.  Our method relies on semi-discrete optimal transport, where only one of the distributions is discretized, thus accurately capturing the discontinuities of  the distribution that remains continuous. The transport plans thus obtained partition the continuous distribution into cells associated with the samples  of the discretization. A semi-discrete optimal transport plan can thus be assimilated to a power diagram made up of these cells. This variant of optimal transport however has the disadvantage of breaking the symmetry between the two distributions. We start by formalizing our problem as the search for a pair of transport plans coupled through the barycenters of their cells. We then present an algorithm for calculating these coupled transport plans. This first algorithm is based on a classical alternating algorithm scheme, successively computing the transport plans and the barycenters of their cells until convergence. The results obtained from this algorithm allow to interpolate between the initial distributions while maintaining a satisfactory precision, in particular when it comes to discontinuities, including when the discretization of the distributions is done with relatively few points. We then present our exploration of optimization methods for solving the same problem. These methods express the constraints of our problem as a critical point of a functional, and aim to reach these points using algorithms such as Newton's method. However, this approach did not yield conclusive results, as the functions involved were too noisy to lend themselves well to optimization algorithms.

Mme Delon Julie (rapportrice)Professeur(e)Université Paris CitéRapporteur(e)
M. Thibert BorisMaître de conférenceUniversité Grenoble AlpesRapporteur(e)
Dominique AttaliDirecteur(trice) de rechercheCNRS/Université Grenoble AlpesExaminateur​(trice)
M. Santambrogio Filippo Professeur(e)Université Lyon 1Examinateur​(trice)
M. Bonneel NicolasChargé(e) de RechercheLIRIS CNRS UMR 5205 - Université Lyon 1Directeur(trice) de thèse
Mme Digne JulieChargé(e) de RechercheLIRIS CNRS UMR 5205 - Université Lyon 1Co-directeur (trice)
M. Lévy Bruno LévyDirecteur(trice) de rechercheInria Nancy Grand EstCo-directeur (trice)