Optimat transport and wavelets: new algorithms and application to image
Seminar Doctorants
29/03/2016 - 15:00 Mme Morgane HENRY Salle 2 - Tour IRMA
Optimal transport has an increasing number of applications, including image interpolation, which we study in this work. Yet, numerical resolution is still challenging, especially for real size images found in applications. We are interested in the Benamou and Brenier formulation, which rephrases the problem in the context of fluid mechanics by adding a time dimension. It is based on the minimization of a functional on a constraint space, containing a divergence free constraint and the existing algorithms require a projection onto the divergence-free constraint at each iteration. In this thesis, we propose to work directly in the space of constraints for the functional to minimize. Indeed, we prove that the functional we consider has better convexity properties on the set of constraints. To work in this space, we use three different divergence-free vector decompositions. The first in which we got interested is a divergence-free wavelet base. This formulation has been implemented numerically using periodic wavelets and a gradient descent, which lead to an algorithm with a slow convergence but validating the practicability of the method. First, we represented the divergence-free vector fields by their stream function, then we studied the Helmholtz-Hodge decompositions. We prove that both these representations lead to a new formulation of the problem, which in 1D + time, is equivalent to the resolution of a minimal surface equation on every level set of the potential, equipped with appropriate Dirichlet boundary conditions. We use a primal dual algorithm for convex problems developed by Chambolle and Pock, which can be easily adapted to our formulations and can be easily sped up on parallel architectures. Therefore our method will also provide a fast algorithm, simple to implement. Moreover, we show numerical experiments which demonstrate that our algorithms are faster than state of the art methods and efficient with real-sized images.