A Numerical Algorithm for L-2 Optimal Transport in 3D
Résumé
This paper introduces a numerical algorithm to compute the L2 optimal transport map between two measures µ and ν, where µ derives from a density ρ defined as a piecewise linear function (supported by a tetrahedral mesh), and where ν is a sum of Dirac masses. I first give an elementary presentation of some known results on optimal transport and then observe a relation with another problem (optimal sampling). This relation gives simple arguments to study the objective functions that characterize both problems. I then propose a practical algorithm to compute the optimal transport map between a piecewise linear density and a sum of Dirac masses in 3D. In this semi-discrete setting, Aurenhammer et.al [8th Symposium on Computational Geometry conf. proc., ACM (1992)] showed that the optimal transport map is determined by the weights of a power diagram. The optimal weights are computed by minimizing a convex objective function with a quasi-Newton method. To evaluate the value and gradient of this objective function, I propose an efficient and robust algorithm, that computes at each iteration the intersection between a power diagram and the tetrahedral mesh that defines the measure µ. The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses. Résumé. Cet article décrit un algorithme numérique pour calculer l'application de transport optimal L2 entre deux mesures µ et ν, o` u µ dérive d'une densité ρ linéaire par morceaux (supportée par un maillage tétraédrique), et o` u ν est une somme de masses de Dirac. Je donne tout d'abord une présentation elémentaire de quelques résultats connus sur le transport optimal , et observe ensuite une relation avec un autreprobì eme (l'´ echantillonage optimal). Cette relation fournit des arguments simples pour etudier les fonctions objectifs caractérisant les deuxprobì emes. Je propose ensuite un algorithme pratique pour calculer le transport optimal entre une densité linéaire par morceaux et une somme de masses de Dirac en 3D. Dans ce cas semi-discret, Auren-hammer et.al [8th Symposium on Computational Geometry conf. proc., ACM (1992)] ont montré que l'application de transport optimal est déterminée par les poids d'un diagramme de puissance. Les poids optimaux sont calculés en minimisant une fonction objectif convexè a l'aide d'une méthode quasi-Newton. Pour evaluer cette fonction objectif et son gradient, je propose un algorithme efficace et robuste, qui calculè a chaque itération l'intersection entre un diagramme de puissance et le maillage tétrahédrique qui définit la mesure µ. L'algorithme numérique est expérimenté et evalué sur plusieurs jeux de données , comportant jusqu'` a plusieurs centaines de milliers detétrà edres et un million de masses de Dirac.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...