An algorithm for optimal transport between a simplex soup and a point cloud

Quentin Mérigot 1 Jocelyn Meyron 2, 3, * Boris Thibert 3
* Auteur correspondant
2 GIPSA-AGPIG - AGPIG
GIPSA-DIS - Département Images et Signal
3 CVGI - Calcul des Variations, Géométrie, Image
LJK - Laboratoire Jean Kuntzmann
Abstract : We propose a numerical method to find the optimal transport map between a measure supported on a lower-dimensional subset of R^d and a finitely supported measure. More precisely, the source measure is assumed to be supported on a simplex soup, i.e. on a union of simplices of arbitrary dimension between 2 and d. As in [Aurenhammer, Hoffman, Aronov, Algorithmica 20 (1), 1998, 61–76] we recast this optimal transport problem as the resolution of a non-linear system where one wants to prescribe the quantity of mass in each cell of the so-called Laguerre diagram. We prove the convergence with linear speed of a damped Newton's algorithm to solve this non-linear system. The convergence relies on two conditions: (i) a genericity condition on the point cloud with respect to the simplex soup and (ii) a (strong) connectedness condition on the support of the source measure defined on the simplex soup. Finally, we apply our algorithm in R^3 to compute optimal transport plans between a measure supported on a triangulation and a discrete measure. We also detail some applications such as optimal quantization of a probability density over a surface, remeshing or rigid point set registration on a mesh.
Type de document :
Article dans une revue
SIAM Journal on Imaging Sciences, Society for Industrial and Applied Mathematics, 2018, 11 (2), pp.1363-1389. 〈10.1137/17M1137486〉
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01556544
Contributeur : Jocelyn Meyron <>
Soumis le : mercredi 5 juillet 2017 - 11:34:31
Dernière modification le : samedi 22 septembre 2018 - 01:14:08
Document(s) archivé(s) le : mardi 23 janvier 2018 - 20:33:02

Fichiers

simplex-soup.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Quentin Mérigot, Jocelyn Meyron, Boris Thibert. An algorithm for optimal transport between a simplex soup and a point cloud. SIAM Journal on Imaging Sciences, Society for Industrial and Applied Mathematics, 2018, 11 (2), pp.1363-1389. 〈10.1137/17M1137486〉. 〈hal-01556544〉

Partager

Métriques

Consultations de la notice

627

Téléchargements de fichiers

111