Multi-physics optimal transportation and image interpolation

Hug, Romain; Maitre, Emmanuel; Papadakis, Nicolas

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 6, pp. 1671-1692.

Optimal transportation theory is a powerful tool to deal with image interpolation. This was first investigated by [Benamou and Brenier, Numer. Math. 84 (2000) 375–393.] where an algorithm based on the minimization of a kinetic energy under a conservation of mass constraint was devised. By structure, this algorithm does not preserve image regions along the optimal interpolation path, and it is actually not very difficult to exhibit test cases where the algorithm produces a path of images where high density regions split at the beginning before merging back at its end. However, in some applications to image interpolation this behaviour is not physically realistic. Hence, this paper aims at studying how some physics can be added to the optimal transportation theory, how to construct algorithms to compute solutions to the corresponding optimization problems and how to apply the proposed methods to image interpolation.

Classification : 68U10, 65K10, 35D05
Mots clés : Optimal transportation, image multiphysics, proximal splitting method, non-convex optimization

H. Attouch, J. Bolte and B. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward backward splitting, and regularized gauss-seidel methods. Math. Program. 137 (2013) 91–129. | DOI | MR | Zbl

H.H. Bauschke and P.L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces. Springer (2011). | MR | Zbl

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84 (2000) 375–393. | DOI | MR | Zbl

J.-D. Benamou, B.D. Froese and A.M. Oberman, Two numerical methods for the elliptic Monge-Ampère equation. ESAIM: M2AN 44 (2010) 737–758. | DOI | Numdam | MR | Zbl

J.-D. Benamou, B.D. Froese and A.M. Oberman, Numerical solution of the optimal transportation problem via viscosity solutions for the Monge-Ampère equation. CoRR, abs/1208.4873 (2012).

J.-D. Benamou, B.D. Froese and A.M. Oberman, Numerical solution of the optimal transportation problem using the Monge-Ampère equation. J. Comput. Phys. 260 (2014) 107–126. | DOI | MR | Zbl

N. Bonnotte, From Knothe’s rearrangement to Brenier’s optimal transport map. SIAM J. Math. Anal. 45 (2013) 64–87. | DOI | MR | Zbl

R.I. Bot, E.R. Csetnek and A. Heinrich, On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. CoRR, abs/1303.2875 (2013).

A. Bouharguane, E. Maitre, E. Oudet and N. Papadakis, Multiphysics optimal transportation and image analysis. Technical Report hal-00740671 (2012).

A. Bouharguane, An. Iollo and L. Weynans, Numerical solution of the Monge−Kantorovich problem by Picard iterations. Technical Report RR-8477, INRIA (2014).

Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44 (1991) 375–417. | DOI | MR | Zbl

C. Brune, 4D imaging in tomography and optical nanoscopy. Ph.D. thesis, University of Münster, Germany (2010). | Zbl

G. Carlier, A. Galichon and F. Santambrogio, From knothe’s transport to brenier’s map and a continuation method for optimal transport. SIAM J. Math. Anal. 41 (2010) 2554–2576. | DOI | MR | Zbl

A. Chambolle, Rates of convergence for accelerated primal-dual algorithms. Presented in SIAM Conference on Imaging Sciences (2014).

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40 (2011) 120–145. | DOI | MR | Zbl

P. Clarysse, B. Delhay, M. Picq and J. Pousin, Optimal extended optical flow subject to a statistical constraint. J. Comput. Appl. Math. 234 (2010) 1291–1302. | DOI | MR | Zbl

L. Condat, A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158 (2013) 460–479. | DOI | MR | Zbl

E.J. Dean and R. Glowinski, An augmented Lagrangian approach to the numerical solution of the dirichlet problem for the elliptic Monge-Ampère equation in two dimensions. Electron. Trans. Numer. Anal. 22 (2006) 71–96. | MR | Zbl

J. Deny and J.-L. Lions, Les espaces du type de beppo levi. Ann. Inst. Fourier 5 (1954) 305–370. | DOI | Numdam | Zbl

R.J. Diperna and P.-L. Lions, Ordinary differential equations, transport theory and sobolev spaces. Inv. Math. 98 (1989) 511–547. | DOI | MR | Zbl

M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. Elsevier Science (1983). | MR | Zbl

V. Girault and P.A. Raviart, Finite element methods for Navier-Stokes equations: theory and algorithms. Springer series in computational mathematics. Springer−Verlag (1986). | MR | Zbl

S. Haker, L. Zhu, A. Tannenbaum and S. Angenent, Optimal mass transport for registration and warping. Int. J. Comput. Vision 60 (2004) 225–240. | DOI | Zbl

F.H. Harlow and J.E. Welch, Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. Phys. Fluids 8 (1965) 2182–2189. | DOI | MR | Zbl

R. Hug, E. Maitre and N. Papadakis, On the convergence of augmented lagrangian method for optimal transport between nonnegative densities. Technical report, hal-01128793 (2015).

A. Iollo and D. Lombardi, A lagrangian scheme for the solution of the optimal mass transfer problem. J. Comput. Phys. 230 (2011) 3430–3442. | DOI | MR | Zbl

R.J. Mccann, Polar factorization of maps on riemannian manifolds. Geom. Funct. Anal. GAFA 11 (2001) 589–608. | DOI | MR | Zbl

A. Moussa, Some variants of the classical aubin-lions lemma. preprint arXiv:1401.7231 (2014). | MR

V.I. Oliker and L.D. Prussner, On the numerical solution of the equation $\frac{{\partial }^{2}z}{\partial x^2}\frac{{\partial }^{2}z}{\partial y^2}-{\left(\frac{{\partial }^{2}z}{\partial x\partial y}\right)}^2=f$ and its discretizations, i. Numer. Math. 54 (1989) 271–293. | DOI | MR | Zbl

N. Papadakis, G. Peyré and É. Oudet, Optimal transport with proximal splitting. SIAM J. Imaging Sci. 7 (2014) 212–238. | DOI | MR | Zbl

H. Raguet, J. Fadili and G. Peyré, A generalized forward-backward splitting. SIAM J. Imaging Sci. 6 (2013) 1199–1226. | DOI | MR | Zbl

G. Strang, Linear Algebra and Its Applications. Brooks Cole (1988).

P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109 (2001) 475–494. | DOI | MR | Zbl

C. Villani, Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer (2008). | MR | Zbl