Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Sparse Multiscale Algorithm for Dense Optimal Transport

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

Discrete optimal transport solvers do not scale well on dense large problems since they do not explicitly exploit the geometric structure of the cost function. In analogy to continuous optimal transport, we provide a framework to verify global optimality of a discrete transport plan locally. This allows the construction of an algorithm to solve large dense problems by considering a sequence of sparse problems instead. The algorithm lends itself to being combined with a hierarchical multiscale scheme. Any existing discrete solver can be used as internal black-box. We explicitly describe how to select the sparse sub-problems for several cost functions, including the noisy squared Euclidean distance. Significant reductions in run-time and memory requirements have been observed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Notes

  1. https://www.ceremade.dauphine.fr/~schmitzer/

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River (1993)

    MATH  Google Scholar 

  2. Ambrosio, L., Gigli, N.: A user’s guide to optimal transport. Modelling and Optimisation of Flows on Networks. Lecture Notes in Mathematics, pp. 1–155. Springer, Berlin (2013)

    Chapter  Google Scholar 

  3. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics, 1st edn. Springer, New York (2011)

    Book  MATH  Google Scholar 

  4. Benamou, J.-D., Brenier, Y.: A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84(3), 375–393 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., Peyré, G.: Iterative Bregman projections for regularized transportation problems. https://hal.archives-ouvertes.fr/hal-01096124 (2014)

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

    Article  MathSciNet  Google Scholar 

  7. Bernard, P., Buffoni, B.: Optimal mass transportation and Mather theory. J. Eur. Math. Soc. 9(1), 85–121 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bertsekas, D.P.: A distributed algorithm for the assignment problem. Technical report, Lab. for Information and Decision Systems Report, MIT (1979)

  9. Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization. Athena Scientific, Belmont (1997)

    Google Scholar 

  10. Brenier, Y.: Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44(4), 375–417 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  11. Burger, M., Franek, M., Schönlieb, C.-B.: Regularised regression and density estimation based on optimal transport. Appl. Math. Res. Express 3, 209–253 (2012)

    MATH  Google Scholar 

  12. Burkhard, R.E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discr. Appl. Math. 70(2), 95–161 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Carlier, G., Galichon, A., Santambrogio, F.: From Knothe’s transport to Brenier’s map and a continuation method for optimal transport. SIAM J. Math. Anal. 41, 2554–2576 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. CPLEX. http://www.ilog.com

  15. Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transportation distances. In: Advances in Neural Information Processing Systems 26 (NIPS 2013), pp. 2292–2300, (2013). http://arxiv.org/abs/1306.0895

  16. Dezsőa, B., Jüttnerb, A., Kovácsa, P.: LEMON—an open source C++ graph template library. In: Proceedings of the Second Workshop on Generative Technologies (WGT) 2010, vol. 264 of Electronic Notes in Theoretical Computer Science, pp. 23–45 (2011)

  17. Fitschen, J.H., Laus, F., Steidl, G.: Transport between RGB images motivated by dynamic optimal transport. http://arxiv.org/abs/1509.06142 (2015)

  18. Gangbo, W., McCann, R.J.: The geometry of optimal transportation. Acta Math. 177(2), 113–161 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  19. Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Oper. Res. 15(3), 430–466 (1990)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  21. Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. 2, 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  22. Ling, H., Okada, K.: An efficient earth mover’s distance algorithm for robust histogram comparison. IEEE Trans. Pattern Anal. Mach. Intell. 29(5), 840–853 (2007)

    Article  Google Scholar 

  23. Maas, J., Rumpf, M., Schönlieb, C., Simon, S.: A generalized model for optimal transport of images including dissipation and density modulation. submitted (2014)

  24. McCann, R.J.: Polar factorization of maps on Riemannian manifolds. Geom. Funct. Anal. 11(3), 589–608 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mérigot, Q.: A multiscale approach to optimal transport. Comput. Graph. Forum 30(5), 1583–1592 (2011)

    Article  Google Scholar 

  26. Oberman, A.M., Ruan, Y.: An efficient linear programming method for optimal transportation. http://arxiv.org/abs/1509.03668

  27. Pele, O., Werman, W.: Fast and robust Earth Mover’s Distances. In: International Conference on Computer Vision (ICCV 2009) (2009)

  28. Rabin, J., Peyré, G., Cohen, L.D.: Geodesic shape retrieval via optimal mass transport. In: European Conference on Computer Vision (ECCV 2010), pp. 771–784 (2010)

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

    Article  MATH  Google Scholar 

  30. Santambrogio, F.: Optimal Transport for Applied Mathematicians, volume 87 of Progress in Nonlinear Differential Equations and Their Applications. Birkhäuser, Boston (2015)

    Google Scholar 

  31. Schmitzer, B.: A sparse algorithm for dense optimal transport. In: Scale Space and Variational Methods (SSVM 2015), pp. 629–641 (2015)

  32. Schmitzer, B., Schnörr, C.: A hierarchical approach to optimal transport. In: Scale Space and Variational Methods (SSVM 2013), pp. 452–464 (2013)

  33. Schmitzer, B., Schnörr, C.: Globally optimal joint image segmentation and shape matching based on Wasserstein modes. J. Math. Imaging Vis. 52(3), 436–458 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  34. Shirdhonkar, S., Jacobs, D.W.: Approximate earth mover’s distance in linear time. In: Computer Vision and Pattern Recognition (CVPR 2008) (2008)

  35. Vasconcelos, C.N., Rosenhahn, B.: Bipartite graph matching computation on GPU. In: Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR 2009), pp. 42–55 (2009)

  36. Villani, C.: Optimal Transport: Old and New, Volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin (2009)

    Book  Google Scholar 

  37. Wang, W., Slepčev, D., Basu, S., Ozolek, J.A., Rohde, G.K.: A linear optimal transportation framework for quantifying and visualizing variations in sets of images. Int. J. Comput. Vision 101, 254–269 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The author gratefully acknowledges support by a public grant overseen by the French National Research Agency (ANR) as part of the ‘Investissements d’avenir’, program-reference ANR-10-LABX-0098 and the European Research Council (project SIGMA-Vision).

Author information

Authors and Affiliations

  1. CEREMADE, Université Paris-Dauphine, Paris, France

    Bernhard Schmitzer

Authors
  1. Bernhard Schmitzer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bernhard Schmitzer.

Appendix: Additional Proofs

Appendix: Additional Proofs

Proof of Proposition 5.9

For \(y \in \mathbf {y}\) write \(y = \mathrm {rep}(\mathbf {y}) + \delta \) with \(|\delta |\le \mathrm {rad}(\mathbf {y})\). \(h(z) = |z|^p\) is differentiable on \(\mathbb {R}^n\) with

$$\begin{aligned} \partial h(z) = \{\nabla h(z) \} = \big \{ p\,|z|^{p-1}\,n(z) \big \}, \end{aligned}$$

where n(z) denotes normalizing the vector z to unit length. The ambiguity of n(z) at \(z=0\) is irrelevant as \(|z|^{p-1}=0\) in that case. Therefore, for convenience, we define n(0) to be some arbitrary vector of unit length. From (5.9a), one finds

$$\begin{aligned} \psi _{(x_A,x_s)}(y) >&p\,|x_s-\mathrm {rep}(\mathbf {y}) - \delta |^{p-1} \\&\quad \left\langle n(x_s-\mathrm {rep}(\mathbf {y}) - \delta ), x_A-x_s \right\rangle . \end{aligned}$$

We now separately bound the inner product and the absolute value term. One has:

$$\begin{aligned}&\left\langle n(x_s-\mathrm {rep}(\mathbf {y}) - \delta ), x_A-x_s \right\rangle \\&\quad = |x_A-x_s|\cdot \cos \big (\measuredangle (x_A-x_s,x_s-\mathrm {rep}(\mathbf {y}) - \delta )\big ). \end{aligned}$$

We need to find an upper bound for the angle (using the triangle inequality on the 2-sphere):

$$\begin{aligned}&\measuredangle \big (x_A-x_s,x_s-\mathrm {rep}(\mathbf {y}) - \delta \big ) \\&\quad \le \measuredangle \big (x_A-x_s,x_s-\mathrm {rep}(\mathbf {y})\big ) \\&\qquad + \measuredangle \big (x_s-\mathrm {rep}(\mathbf {y}),x_s-\mathrm {rep}(\mathbf {y}) - \delta \big ) \\&\quad \measuredangle \big (x_s-\mathrm {rep}(\mathbf {y}),x_s-\mathrm {rep}(\mathbf {y}) - \delta \big ) \\&\quad \le {\left\{ \begin{array}{ll} \arcsin (|\delta |/|x_s-\mathrm {rep}(\mathbf {y})|) &{} \text {for } |\delta | < |x_s-\mathrm {rep}(\mathbf {y})| \\ \pi &{} \text {else} \end{array}\right. } \le \theta . \end{aligned}$$

Since the maximal (unsigned) angle is \(\pi \), we eventually find:

$$\begin{aligned}&\measuredangle (x_A-x_s,x_s-\mathrm {rep}(\mathbf {y}) - \delta )\\&\quad \le \min \big \{ \pi , \measuredangle \big (x_A-x_s,x_s-\mathrm {rep}(\mathbf {y}) \big ) + \theta \big \} = \varphi . \end{aligned}$$

Depending on the sign of \(\cos (\varphi )\), we found \(|x_s-\mathrm {rep}(y)-\delta |\) from above or below which yields the expression for R. \(\square \)

Proof of Proposition 5.11

Let \({\mathcal {S}_1}\) be the unit circle which we identify with the interval \((-\pi ,\pi ]\) ‘with its ends connected’. Denote by \(F : [0,\pi ] \times {\mathcal {S}_1}\rightarrow {\mathcal {S}_2}\) the map from spherical coordinates onto \({\mathcal {S}_2}\):

$$\begin{aligned} F(\theta ,\varphi ) = \begin{pmatrix} \sin \theta \cdot \cos \varphi \\ \sin \theta \cdot \sin \varphi \\ \cos \theta \end{pmatrix}. \end{aligned}$$
(7.1)

For some \(y \in \mathbf {y}\) with \(d(y,\mathrm {rep}(\mathbf {y})) \le \mathrm {rad}(\mathbf {y})\), we clearly have:

$$\begin{aligned} d(x_A,y) - d(x_s,y) \ge&\inf \Big \{ d \big (x_A,y' \big ) - d \big (x_s,y' \big ) : y' \in {\mathcal {S}_2}, \\&d \big (y',\mathrm {rep}(\mathbf {y}) \big ) \le \mathrm {rad}(\mathbf {y}) \Big \}. \end{aligned}$$

Now find a relaxation of the feasible set on the r.h.s. to obtain a tractable lower bound. It can be shown that the metric ball around \(\mathrm {rep}(\mathbf {y})\) is contained in a sufficiently large ‘rectangle’ in spherical coordinates. More precisely:

$$\begin{aligned} \Big \{ y' \in {\mathcal {S}_2}, d \big (y',\mathrm {rep}(\mathbf {y}) \big ) \le \mathrm {rad}(\mathbf {y}) \Big \} \subset F(\mathcal {D}) \end{aligned}$$

with

$$\begin{aligned}&\mathcal {D} = \mathcal {D}_\theta \times \mathcal {D}_\varphi \\&\mathcal {D}_\theta = \Big [\max \big \{0,\theta _B - \mathrm {rad}(\mathbf {y}) \big \}, \theta _B + \mathrm {rad}(\mathbf {y}) \Big ] \\&\mathcal {D}_{\varphi } = {\left\{ \begin{array}{ll} [\varphi _B - \hat{\varphi }, \varphi _B + \hat{\varphi }] &{} \text {if } \cos ^2 \mathrm {rad}(\mathbf {y}) > \cos ^2 \theta _B \\ {\mathcal {S}_1}&{} \text {else} \end{array}\right. } \\&\hat{\varphi } = \arccos \sqrt{ \frac{ \cos ^2 \mathrm {rad}(\mathbf {y}) - \cos ^ 2 \theta _B}{1-\cos ^2 \theta _B}}, \end{aligned}$$

where in \([\varphi _B - \hat{\varphi }, \varphi _B + \hat{\varphi }]\) we have to take into account the ‘wrapping around’ at \(-\pi \). The angle \(\hat{\varphi }\) can be obtained by computing the distance between the point \(\mathrm {rep}(\mathbf {y})\) and a ‘meridian’ \(F([0,\pi ] \times \{\varphi '\})\) and demanding that this distance may not be smaller than \(\mathrm {rad}(\mathbf {y})\). This yields \(\hat{\varphi }\) as a minimal difference in longitude.

Let \(y' = F(\theta ',\varphi ')\). Recall that \(d(x,y) = \arccos \left\langle x,y \right\rangle \) where \(\left\langle \cdot , \cdot \right\rangle \) denotes the usual Euclidean inner product in \(\mathbb {R}^3\). Then

$$\begin{aligned} d \big (x_A,y' \big ) - d \big (x_s,y' \big )&= \theta ' - \arccos \big ( \sin \theta _s \cdot \sin \theta ' \cdot \cos \varphi '\\&\quad + \cos \theta _s \cdot \cos \theta ' \big ). \end{aligned}$$

Minimize this over \(F(\mathcal {D})\). For every \(\theta ' \in \mathcal {D}_\theta \) the minimizing \(\varphi '\) is as close to \(-\pi \) (in the \({\mathcal {S}_1}\)-sense) as possible. For any \(\varphi ' \in \mathcal {D}_{\varphi }\) the minimizing \(\theta '\) is as close to 0 as possible. This yields \(\theta _{B,\text {min}}\) and \(\varphi _{B,\text {max}}\). Then, depending on the sign of \(\Delta d_{\text {min}}\) pick \(\xi \) from the sub-differential at either the minimal or maximal end of possible distances. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Schmitzer, B. A Sparse Multiscale Algorithm for Dense Optimal Transport. J Math Imaging Vis 56, 238–259 (2016). https://doi.org/10.1007/s10851-016-0653-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-016-0653-9

Keywords

Search

Navigation