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

A Stochastic Multi-layer Algorithm for Semi-discrete Optimal Transport with Applications to Texture Synthesis and Style Transfer

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

Abstract

This paper investigates a new stochastic algorithm to approximate semi-discrete optimal transport for large-scale problem, i.e., in high dimension and for a large number of points. The proposed technique relies on a hierarchical decomposition of the target discrete distribution and the transport map itself. A stochastic optimization algorithm is derived to estimate the parameters of the corresponding multi-layer weighted nearest neighbor model. This model allows for fast evaluation during synthesis and training, for which it exhibits faster empirical convergence. Several applications to patch-based image processing are investigated: texture synthesis, texture inpainting, and style transfer. The proposed models compare favorably to the state of the art, either in terms of image quality, computation time, or regarding the number of parameters. Additionally, they do not require any pixel-based optimization or training on a large dataset of natural images.

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
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21

Similar content being viewed by others

References

  1. Angenent, S., Haker, S., Tannenbaum, A.: Minimizing flows for the Monge–Kantorovich problem. SIAM J. Math. Anal. 35(1), 61–97 (2003)

    Article  MathSciNet  Google Scholar 

  2. Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20(1), 61–76 (1998)

    Article  MathSciNet  Google Scholar 

  3. Bercu, B., Bigot, J.: Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures. arXiv preprint arXiv:1812.09150 (2019)

  4. Buyssens, P., Daisy, M., Tschumperlé, D., Lézoray, O.: Exemplar-based inpainting: technical review and new heuristics for better geometric reconstructions. IEEE Trans. Image Process. 24(6), 1809–1824 (2015)

    MathSciNet  MATH  Google Scholar 

  5. Carlier, G., Oberman, A., Oudet, E.: Numerical methods for matching for teams and wasserstein barycenters. ESAIM Math. Model. Numer. Anal. 49(6), 1621–1642 (2015)

    Article  MathSciNet  Google Scholar 

  6. Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. In: Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS’13), vol. 2. Curran Associates Inc., Red Hook, NY (2013)

  7. Delon, J.: Midway image equalization. J. Math. Imaging Vis. 21(2), 119–134 (2004)

    Article  MathSciNet  Google Scholar 

  8. Efros, A., Freeman, W.: Image quilting for texture synthesis and transfer. In: ACM TOG, pp. 341–346 (2001)

  9. Elad, M., Milanfar, P.: Style transfer via texture synthesis. IEEE Trans. Image Process. 26(5), 2338–2351 (2017)

    Article  MathSciNet  Google Scholar 

  10. Feydy, J., Charlier, B., Vialard, F., Peyré, G.: Optimal transport for diffeomorphic registration. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 291–299. Springer, Berlin (2017)

  11. Feydy, J., Roussillon, P., Trouvé, A., Gori, P.: Fast and scalable optimal transport for brain tractograms. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 636–644. Springer, Berlin (2019)

  12. Fitschen, J., Laus, F., Steidl, G.: Transport between RGB images motivated by dynamic optimal transport. J. Math. Imaging Vis. 56(3), 409–429 (2016)

    Article  MathSciNet  Google Scholar 

  13. Frigo, O., Sabater, N., Delon, J., Hellier, P.: Split and match: example-based adaptive patch sampling for unsupervised style transfer. In: Proceedings of the IEEE CVPR, pp. 553–561 (2016)

  14. Galerne, B., Leclaire, A.: Texture inpainting using efficient Gaussian conditional simulation. SIAM J. Imaging Sci. 10(3), 1446–1474 (2018)

    Article  MathSciNet  Google Scholar 

  15. Galerne, B., Leclaire, A., Rabin, J.: A texture synthesis model based on semi-discrete optimal transport in patch space. SIAM J. Imaging Sci. 11(4), 2456–2493 (2018)

    Article  MathSciNet  Google Scholar 

  16. Gatys, L., Ecker, A.S., Bethge, M.: Texture synthesis using convolutional neural networks. In: Proceedings of NIPS, pp. 262–270 (2015)

  17. Gatys, L.A., Ecker, A.S., Bethge, M.: Image style transfer using convolutional neural networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2414–2423 (2016)

  18. Geirhos, R., Rubisch, P., Michaelis, C., Bethge, M., Wichmann, F.A., Brendel, W.: Imagenet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness. In: International Conference on Learning Representations (2019)

  19. Genevay, A., Cuturi, M., Peyré, G., Bach, F.: Stochastic optimization for large-scale optimal transport. In: Proceedings of NIPS, pp. 3432–3440 (2016)

  20. Gerber, S., Maggioni, M.: Multiscale strategies for computing optimal transport. J. Mach. Learn. Res. 18(1), 2440–2471 (2017)

    MathSciNet  MATH  Google Scholar 

  21. Glimm, T., Henscheid, N.: Iterative scheme for solving optimal transportation problems arising in reflector design. Mathematics (2013). https://doi.org/10.1155/2013/635263

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

    Article  Google Scholar 

  23. Hertzmann, A., Jacobs, C.E., Oliver, N., Curless, B., Salesin, D.H.: Image analogies. In: ACM (ed.) Proceedings of SIGGRAPH’01, pp. 327–340. ACM Press, Cambridge (2001)

  24. Johnson, J., Alahi, A., Fei-Fei, L.: Perceptual losses for real-time style transfer and super-resolution. In: European Conference on Computer Vision, pp. 694–711. Springer, Berlin (2016)

  25. Kitagawa, J.: An iterative scheme for solving the optimal transportation problem. Calc. Var. Partial Differ. Equ. 51(1–2), 243–263 (2014)

    Article  MathSciNet  Google Scholar 

  26. Kitagawa, J., Mérigot, Q., Thibert, B.: Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. 21, 2603–2651 (2019). https://doi.org/10.4171/JEMS/889

    Article  MathSciNet  MATH  Google Scholar 

  27. Kosowsky, J.J., Yuille, A.L.: The invisible hand algorithm: solving the assignment problem with statistical physics. Neural Netw. 7(3), 477–490 (1994)

    Article  Google Scholar 

  28. Kuhn, H.W.: The hungarian method for the assignment problem. Naval Res. Logist. Q. 2(1–2), 83–97 (1955)

    Article  MathSciNet  Google Scholar 

  29. Leclaire, A., Rabin, J.: A fast multi-layer approximation to semi-discrete optimal transport. In: Proceedings of SSVM, pp. 341–353. Springer, Berlin (2019)

  30. Lellmann, J., Lorenz, D.A., Schönlieb, C., Valkonen, T.: Imaging with Kantorovich–Rubinstein discrepancy. SIAM J. Imaging Sci. 7(4), 2833–2859 (2014)

    Article  MathSciNet  Google Scholar 

  31. Lévy, B.: A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM: M2AN 49(6), 1693–1715 (2015)

    Article  Google Scholar 

  32. Li, Y., Fang, C., Yang, J., Wang, Z., Lu, X., Yang, M.H.: Diversified texture synthesis with feed-forward networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3920–3928 (2017)

  33. Lisani, J.L., Buades, A., Morel, J.M.: Image color cube dimensional filtering and visualization. Image Process. On Line 1, 57–69 (2011). https://doi.org/10.5201/ipol.2011.blm-cdf

    Article  Google Scholar 

  34. Liu, G., Gousseau, Y., Xia, G.: Texture synthesis through convolutional neural networks and spectrum constraints. In: International Conference on Pattern Recognition (ICPR), pp. 3234–3239. IEEE (2016)

  35. Maas, J., Rumpf, M., Schönlieb, C., Simon, S.: A generalized model for optimal transport of images including dissipation and density modulation. ESAIM Math. Model. Numer. Anal. 49(6), 1745–1769 (2015)

    Article  MathSciNet  Google Scholar 

  36. McLachlan, G., Krishnan, T.: The EM Algorithm and Extensions, vol. 382. Wiley, New York (2007)

    MATH  Google Scholar 

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

    Article  Google Scholar 

  38. Monge, G.: Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris (1781)

  39. Mordvintsev, A., Pezzotti, N., Schubert, L., Olah, C.: Differentiable image parameterizations. Distill (2018). https://doi.org/10.23915/distill.00012

  40. Newson, A., Almansa, A., Fradet, M., Gousseau, Y., Pérez, P.: Video inpainting of complex scenes. SIAM J. Imaging Sci. 7(4), 1993–2019 (2014). https://doi.org/10.1137/140954933

    Article  MathSciNet  MATH  Google Scholar 

  41. Newson, A., Almansa, A., Gousseau, Y., Pérez, P.: Non-local patch-based image inpainting. Image Process. On Line 7, 373–385 (2017). https://doi.org/10.5201/ipol.2017.189

    Article  MathSciNet  Google Scholar 

  42. Oberman, A.M., Ruan, Y.: An efficient linear programming method for optimal transportation. arXiv preprint arXiv:1509.03668 (2015)

  43. Papadakis, N., Peyré, G., Oudet, E.: Optimal transport with proximal splitting. SIAM J. Imaging Sci. 7(1), 212–238 (2014)

    Article  MathSciNet  Google Scholar 

  44. Papadakis, N., Provenzi, E., Caselles, V.: A variational model for histogram transfer of color images. IEEE Trans. Image Process. 20(6), 1682–1695 (2010)

    Article  MathSciNet  Google Scholar 

  45. Peyré, G., Cuturi, M.: Computational optimal transport. Found. Trends Mach. Learn. 11(5–6), 355–607 (2019)

    Article  Google Scholar 

  46. Raad, L., Desolneux, A., Morel, J.: A conditional multiscale locally Gaussian texture synthesis algorithm. J. Math. Imaging Vis. 56(2), 260–279 (2016)

    Article  MathSciNet  Google Scholar 

  47. Rabin, J., Delon, J., Gousseau, Y.: A statistical approach to the matching of local features. SIAM J. Imaging Sci. 2(3), 931–958 (2009)

    Article  MathSciNet  Google Scholar 

  48. Rabin, J., Delon, J., Gousseau, Y.: Removing artefacts from color and contrast modifications. IEEE Trans. Image Process. 20(11), 3073–3085 (2011)

    Article  MathSciNet  Google Scholar 

  49. Rabin, J., Papadakis, N.: Convex color image segmentation with optimal transport distances. In: International Conference on Scale Space and Variational Methods in Computer Vision, pp. 256–269. Springer, Berlin (2015)

  50. Rangarajan, A., Chui, H., Bookstein, F.L.: The softassign procrustes matching algorithm. In: Biennial International Conference on Information Processing in Medical Imaging, pp. 29–42. Springer, Berlin (1997)

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

    Article  Google Scholar 

  52. Santambrogio, F.: Optimal Transport for Applied Mathematicians. Birkäuser, New York (2015)

    Book  Google Scholar 

  53. Schmitzer, B.: A sparse multiscale algorithm for dense optimal transport. J. Math. Imaging Vis. 56(2), 238–259 (2016)

    Article  MathSciNet  Google Scholar 

  54. Schmitzer, B.: Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM J. Sci. Comput. 41(3), A1443–A1481 (2019)

    Article  MathSciNet  Google Scholar 

  55. Sendik, O., Cohen-Or, D.: Deep correlations for texture synthesis. ACM Trans. Graph. 36(5), 161:1–161:15 (2017). https://doi.org/10.1145/3015461

    Article  Google Scholar 

  56. Simonyan, K., Zisserman, A.: Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014)

  57. Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., Guibas, L.: Convolutional wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans. Graph. (TOG) 34(4), 66 (2015)

    Article  Google Scholar 

  58. Tartavel, G., Peyré, G., Gousseau, Y.: Wasserstein loss for image synthesis and restoration. SIAM J. Imaging Sci. 9(4), 1726–1755 (2016)

    Article  MathSciNet  Google Scholar 

  59. Ulyanov, D., Lebedev, V., Vedaldi, A., Lempitsky, V.: Texture networks: feed-forward synthesis of textures and stylized images. In: Proceedings of the International Conference on Machine Learning, vol. 48, pp. 1349–1357 (2016)

  60. Ulyanov, D., Vedaldi, A., Lempitsky, V.: Improved texture networks: Maximizing quality and diversity in feed-forward stylization and texture synthesis. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6924–6932 (2017)

  61. Ulyanov, D., Vedaldi, A., Lempitsky, V.: Deep image prior. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9446–9454 (2018)

  62. Ustyuzhaninov, I., Brendel, W., Gatys, L., M., B.: What does it take to generate natural textures? In: Proceedings of ICLR (2017)

  63. Villani, C.: Topics in Optimal Transportation. American Mathematical Society, Providence (2003)

    Book  Google Scholar 

  64. Xia, G., Ferradans, S., Peyré, G., Aujol, J.: Synthesizing and mixing stationary Gaussian texture models. SIAM J. Imaging Sci. 7(1), 476–508 (2014)

    Article  MathSciNet  Google Scholar 

  65. Yu, G., Sapiro, G., Mallat, S.: Solving inverse problems with piecewise linear estimators: from Gaussian mixture models to structured sparsity. IEEE Trans. Image Process. 21(5), 2481–2499 (2012)

    Article  MathSciNet  Google Scholar 

  66. Zhang, H., Dana, K.: Multi-style generative network for real-time transfer. arXiv preprint arXiv:1703.06953 (2017)

Download references

Acknowledgements

We would like to thank Claire Brécheteau, Nicolas Papadakis, Simone Parisotto for helpful discussion. This project has been carried out with support from the French State, managed by the French National Research Agency under Projects GOTMI (ANR-16-CE33-0010-01), MISTIC (ANR-19-CE40-0005) and PostProdLEAP (ANR-19-CE23-0027-01).

Author information

Authors and Affiliations

  1. University of Bordeaux, IMB, Bordeaux INP, CNRS, UMR 5251, 33-400, Talence, France

    Arthur Leclaire

  2. ENSICAEN, CNRS, GREYC, Normandie University, Caen, France

    Julien Rabin

Authors
  1. Arthur Leclaire
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julien Rabin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arthur Leclaire.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Leclaire, A., Rabin, J. A Stochastic Multi-layer Algorithm for Semi-discrete Optimal Transport with Applications to Texture Synthesis and Style Transfer. J Math Imaging Vis 63, 282–308 (2021). https://doi.org/10.1007/s10851-020-00975-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-020-00975-4

Keywords

Search

Navigation