A generalized model for optimal transport of images including dissipation and density modulation

Maas, Jan; Rumpf, Martin; Schönlieb, Carola; Simon, Stefan

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

In this paper the optimal transport and the metamorphosis perspectives are combined. For a pair of given input images geodesic paths in the space of images are defined as minimizers of a resulting path energy. To this end, the underlying Riemannian metric measures the rate of transport cost and the rate of viscous dissipation. Furthermore, the model is capable to deal with strongly varying image contrast and explicitly allows for sources and sinks in the transport equations which are incorporated in the metric related to the metamorphosis approach by Trouvé and Younes. In the non-viscous case with source term existence of geodesic paths is proven in the space of measures. The proposed model is explored on the range from merely optimal transport to strongly dissipative dynamics. For this model a robust and effective variational time discretization of geodesic paths is proposed. This requires to minimize a discrete path energy consisting of a sum of consecutive image matching functionals. These functionals are defined on corresponding pairs of intensity functions and on associated pairwise matching deformations. Existence of time discrete geodesics is demonstrated. Furthermore, a finite element implementation is proposed and applied to instructive test cases and to real images. In the non-viscous case this is compared to the algorithm proposed by Benamou and Brenier including a discretization of the source term. Finally, the model is generalized to define discrete weighted barycentres with applications to textures and objects.

Classification : 68U10, 65K10, 35K55
Mots clés : Optimal transport, flow of diffeomorphism, metamorphosis, variational time discretization

L. Ambrosio, Lecture notes on optimal transport problems. Mathematical aspects of evolving interfaces, Lectures given at the C.I.M.-C.I.M.E. joint Euro-summer school, Madeira, Funchal, Portugal, July 3–9, 2000, edited by P. Colli. Vol. 1812 of Lect. Notes Math. Springer, Berlin (2003) 1–52. | MR | Zbl

L. Ambrosio and G. Buttazzo, Weak lower semicontinuous envelope of functionals defined on a space of measures. Ann. Mat. Pura Appl. 150 (1988) 311–339. | DOI | MR | Zbl

L. Ambrosio, N. Fusco and D. Pallara, Functions of bounded variation and free discontinuity problems. Oxford Math. Monogr. The Clarendon Press, Oxford University Press, New York (2000). | MR | Zbl

L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows: in Metric Spaces and in the Space of Probability Measures. Springer (2006). | MR | Zbl

S. Angenent, S. Haker and A. Tannenbaum, Minimizing flows for the Monge–Kantorovich problem. SIAM J. Math. Anal. 35 (2003) 61–97. | DOI | MR | Zbl

V. Arnold, Sur la géométrie différentielle des groupes de lie de dimension infinie et ses applications à l’hydrodynamique des fluides parfaits. Ann. Institut Fourier 16 (1966) 319–361. | DOI | Numdam | MR | Zbl

V. Arnold and B. Khesin, Topological Methods in Hydrodynamics. Springer (1998). | MR | Zbl

M.F. Beg, M.I. Miller, A. Trouvé and L. Younes, Computational anatomy: Computing metrics on anatomical shapes. In Proc. of 2002 IEEE ISBI (2002) 341–344.

M.F. Beg, M.I. Miller, A. Trouvé and L. Younes, Computing large deformation metric mappings via geodesic flows of diffeomorphisms. Int. J. Comput. Vision 61 (2005) 139–157. | DOI | 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

B. Berkels, Al. Effland and M. Rumpf, Time discrete geodesic paths in the space of images. SIAM J. Imag. Sci. 8 (2015) 1457–1488. | DOI | MR | Zbl

M. Burger, J.A. Carrillo and M.-T. Wolfram, A mixed finite element method for nonlinear diffusion equations. Kinet. Relat. Models 3 (2010) 59–83. | DOI | MR | Zbl

M. Burger, M. Franek and C.-B. Schönlieb, Regularized regression and density estimation based on optimal transport. Appl. Math. Res. Express 2012 (2012) 209–253. | MR | Zbl

G. Buttazzo and F. Santambrogio, A model for the optimal planning of an urban area. SIAM J. Math. Anal. 37 (2005) 514–530. | DOI | MR | Zbl

T. Chan, S. Esedoglu and K. Ni, Histogram Based Segmentation Using Wasserstein Distances. Scale Space and Variational Methods in Computer Vision. Springer (2007) 697–708.

R. Chartrand, B. Wohlberg, K. Vixie, and E. Bollt, A gradient descent solution to the Monge−Kantorovich problem. Appl. Math. Sci. 3 (2009) 1071–1080. | MR

Ph.G. Ciarlet, Mathematical Elasticity, I: Three-dimensional elasticity. Vol. 20 of Stud. Math. Appl. Elsevier (1988). | MR | Zbl

E.J. Dean and R. Glowinski, Numerical methods for fully nonlinear elliptic equations of the Monge–Ampère type. Comput. Methods Appl. Mech. Eng. 195 (2006) 1344–1386. | DOI | MR | Zbl

J. Dolbeault, B. Nazaret and G. Savaré, A new class of transport distances between measures. Calc. Var. Partial Differ. Equ. 34 (2009) 193–231. | DOI | MR | Zbl

P. Dupuis, U. Grenander and M.I. Miller, Variational problems on flows of diffeomorphisms for image matching. Quart. Appl. Math. 56 (1998) 587. | DOI | MR | Zbl

D. Dupuis, U. Grenander and M.I. Miller, Variational problems on flows of diffeomorphisms for image matching. Quart. Appl. Math. 56 (1998) 587–600. | DOI | MR | Zbl

B. Düring, D. Matthes and J.P. Milišic, A gradient flow scheme for nonlinear fourth order equations. Discrete Contin. Dyn. Syst. Ser. B 14 (2010) 935–959. | MR | Zbl

L.C. Evans, Partial Differential Equations and Monge-Kantorovich Mass Transfer, Current Developments in Mathematics. Papers from the conference held in Cambridge, MA, USA, 1997. Edited by R. Bott et al. International Press, Boston, MA (1999) 65–126. | MR | Zbl

S. Ferradans, N. Papadakis, J. Rabin, G. Peyré and J.-F. Aujol, Regularized Discrete Optimal Transport, Scale Space and Variational Methods in Computer Vision. In Lect. Notes Comput. Sci. Springer (2013) 428–439. | MR | Zbl

P.T. Fletcher, C. Lu, S.M. Pizer and S. Joshi, Principal geodesic analysis for the study of nonlinear statistics of shape. IEEE Trans. Medical Imaging 23 (2004) 995–1005. | DOI

K. Grauman and T. Darrell, Fast Contour Matching Using Approximate Earth Mover’s Distance. In Proc. of the 2004 IEEE Computer Society Conference on. Computer Vision and Pattern Recognition CVPR 2004. IEEE 1 (2004) I–220.

U. Grenander, Lectures in Pattern Theory. Appl. Math. Sci. Springer-Verlag (1981). | MR | Zbl

E. Haber, T. Rehman and A. Tannenbaum, An efficient numerical method for the solution of the L2 optimal mass transfer problem. SIAM J. Sci. Comput. 32 (2010) 197–211. | DOI | 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

S.C. Joshi and M.I. Miller, Landmark matching via large deformation diffeomorphisms. IEEE Trans. Image Process. 9 (2000) 1357–1370. | DOI | MR | Zbl

L.V. Kantorovitch, On the translocation of masses. Dokl. Akad. Nauk. USSR 37 (1942) 227–229. | MR | Zbl

L.V. Kantorovich, On a problem of monge. Usp. Mat. Nauk 3 (1948) 225–226. | Zbl

M. Kilian, N.J. Mitra and H. Pottmann. Geometric modeling in shape space. In ACM Trans. Graph. 26 (2007) 1–8. | DOI

H. Ling and K. Okada, An efficient earth mover’s distance algorithm for robust histogram comparison. IEEE Trans. Pattern Anal. Mach. Intelligence 29 (2007) 840–853. | DOI

Y. Lipman and I. Daubechies, Conformal Wasserstein distances: Comparing surfaces in polynomial time. Adv. Math. 227 (2011) 1047–1077. | DOI | MR | Zbl

G. Loeper and F. Rapetti, Numerical solution of the Monge–Ampère equation by a Newton’s algorithm. C. R. Math. 340 (2005) 319–324. | DOI | MR | Zbl

F. Mémoli, On the use of Gromov-Hausdorff distances for shape comparison. In Eurographics symposium on point-based graphics. The Eurographics Association (2007) 81–90.

F. Mémoli, Gromov–Wasserstein distances and the metric approach to object matching. Found. Comput. Math. 11 (2011) 417–487. | DOI | MR | Zbl

M.I. Miller and L. Younes, Group actions, homeomorphisms and matching: a general framework. Int. J. Comput. Vision 41 (2001) 61–84. | DOI | Zbl

M.I. Miller, A. Trouvé and L. Younes, On the metrics and Euler−Lagrange equations of computational anatomy. Ann. Rev. Biomed. Eng. 4 (2002) 375–405. | DOI

G. Monge, Mémoire sur la théorie des déblais et des remblais. De l’Imprimerie Royale (1781).

J. Moser, On the volume elements on a manifold. Tran. Amer. Math. Soc. 120 (1965) 286–294. | DOI | MR | Zbl

J. Nečas and M. Šilhavý, Multipolar viscous fluids. Quart. Appl. Math. 49 (1991) 247–265. | DOI | MR | Zbl

K. Ni, X. Bresson, T. Chan and S. Esedoglu, Local histogram based segmentation using the Wasserstein distance. Int. J. Comput. Vision 84 (2009) 97–111. | DOI

A.M. Oberman, Wide stencil finite difference schemes for the elliptic Monge-Ampere equation and functions of the eigenvalues of the Hessian. Discrete Contin. Dyn. Syst. Ser. B 10 (2008) 221–238. | MR | Zbl

L. Oudre, J. Jakubowicz, P. Bianchi and Ch. Simon, Classification of periodic activities using the Wasserstein distance. IEEE Trans. Biomed. Eng. 59 (2012) 1610–1619. | DOI

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

G. Peyré, M. Péchaud, R. Keriven and L.D. Cohen, Geodesic methods in computer vision and graphics. Found. Trends Comput. Graph. Vision 5 (2010) 197–397. | DOI | Zbl

G. Peyré, J. Fadili and J. Rabin, Wasserstein active contours. In Image Proc. of 19th IEEE International Conference (2012) 2541–2544.

J. Rabin and G. Peyré, Wasserstein Regularization of Imaging Problem. In 18th IEEE International Conf. of Image Processing ICIP (2011) 1541–1544.

J. Rabin, G. Peyré and L.D. Cohen, Geodesic Shape Retrieval via Optimal Mass Transport. In Computer Vision–ECCV 2010. Springer (2010) 771–784.

J. Rabin, G. Peyré, J. Delon and M. Bernot, Wasserstein Barycenter and its Application to Texture Mixing. In Scale Space and Variational Methods in Computer Vision. Springer (2012) 435–446.

Y. Rubner, C. Tomasi and L.J. Guibas, The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vision 40 (2000) 99–121. | DOI | Zbl

M. Rumpf and B. Wirth, Variational time discretization of geodesic calculus. IMA J. Numer. Anal. 35 (2015) 1011–1046. | DOI | MR | Zbl

L.-Ph. Saumier, M. Agueh and B. Khouider, An efficient numerical algorithm for the L2 optimal transport problem with applications to image processing. Preprint arXiv:1009.6039 (2010). | MR

B. Schmitzer and Ch. Schnörr, A Hierarchical Approach to Optimal Transport. In Scale Space and Variational Methods in Computer Vision. Springer (2013) 452–464.

B. Schmitzer and Ch. Schnörr, Modelling convex shape priors and matching based on the Gromov-Wasserstein distance. J. Math. Imaging and Vision 46 (2013) 143–159. | DOI | MR | Zbl

B. Schmitzer and Ch. Schnörr, Object segmentation by shape matching with Wasserstein modes. In Energy Minimization Methods in Computer Vision and Pattern Recognition. Springer (2013) 123–136.

J.W. Strutt. Theory of sound. Vol. 2. Dover Publications (1945).

A. Trouvé and L. Younes, Metamorphoses through Lie group action. Found. Comput. Math. 5 (2005) 173–198. | DOI | MR | Zbl

C. Villani,Topics in optimal transportation. American Mathematical Soc. (2003) 58. | MR | Zbl

C. Villani,Optimal transport: old and new. Vol. 338. Springer (2008). | MR | Zbl

B. Wirth, L. Bar, M. Rumpf and G. Sapiro, A continuum mechanical approach to geodesics in shape space. Int. J. Comput. Vision 93 (2011) 293–318. | DOI | MR | Zbl

L. Zhu, S. Haker and A. Tannenbaum, Area-preserving mappings for the visualization of medical structures. Springer (2003).

L. Zhu, Y. Yang, S. Haker and A. Tannenbaum, An image morphing technique based on optimal mass preserving mapping. IEEE Trans. Image Process. 16 (2007) 1481–1495. | DOI | MR