“SPOT: sliced partial optimal transport” by Bonneel and Coeurjolly
Conference:
Type:
Title:
- SPOT: sliced partial optimal transport
Session/Category Title: Transport: Parallel and Optimal
Presenter(s)/Author(s):
Abstract:
Optimal transport research has surged in the last decade with wide applications in computer graphics. In most cases, however, it has focused on the special case of the so-called “balanced” optimal transport problem, that is, the problem of optimally matching positive measures of equal total mass. While this approach is suitable for handling probability distributions as their total mass is always equal to one, it precludes other applications manipulating disparate measures. Our paper proposes a fast approach to the optimal transport of constant distributions supported on point sets of different cardinality via one-dimensional slices. This leads to one-dimensional partial assignment problems akin to alignment problems encountered in genomics or text comparison. Contrary to one-dimensional balanced optimal transport that leads to a trivial linear-time algorithm, such partial optimal transport, even in 1-d, has not seen any closed-form solution nor very efficient algorithms to date. We provide the first efficient 1-d partial optimal transport solver. Along with a quasilinear time problem decomposition algorithm, it solves 1-d assignment problems consisting of up to millions of Dirac distributions within fractions of a second in parallel. We handle higher dimensional problems via a slicing approach, and further extend the popular iterative closest point algorithm using optimal transport – an algorithm we call Fast Iterative Sliced Transport. We illustrate our method on computer graphics applications such a color transfer and point cloud registration.
References:
1. Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. 2010. Slic superpixels. Technical Report.Google Scholar
2. Martin Arjovsky, Soumith Chintala, and Léon Bottou. 2017. Wasserstein GAN. (2017). arXiv:1701.07875.Google Scholar
3. Jean-David Benamou. 2003. Numerical resolution of an “unbalanced” mass transport problem. ESAIM: Mathematical Modelling and Numerical Analysis 37, 5 (2003).Google Scholar
4. Nicolas Bonneel, Julien Rabin, G. Peyré, and Hanspeter Pfister. 2015. Sliced and Radon Wasserstein Barycenters of Measures. J. of Math. Imaging and Vision 51, 1 (2015). Google ScholarDigital Library
5. Nicolas Bonneel, Kalyan Sunkavalli, Sylvain Paris, and Hanspeter Pfister. 2013. Example-Based Video Color Grading. ACM Trans. on Graphics (SIGGRAPH) 32, 4 (2013). Google ScholarDigital Library
6. Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. 2011. Displacement interpolation using Lagrangian mass transport. In ACM Trans. on Graphics (SIGGRAPH Asia), Vol. 30. Google ScholarDigital Library
7. Kevin Charter, Jonathan Schaeffer, and Duane Szafron. 2000. Sequence alignment using FastLSA. In International conference on mathematics and engineering techniques in medicine and biological sciences. 239–245.Google Scholar
8. Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. 2016. Scaling Algorithms for Unbalanced Transport Problems. Math. Comp. 87 (07 2016).Google Scholar
9. Ishan Deshpande, Ziyu Zhang, and Alexander Schwing. 2018. Generative Modeling using the Sliced Wasserstein Distance. In IEEE Conf. on Comp. Vis. and Patt. Recognition (CVPR).Google ScholarCross Ref
10. Shaoyi Du, Nanning Zheng, Shihui Ying, Qubo You, and Yang Wu. 2007. An extension of the ICP algorithm considering scale factor. In IEEE Int. Conf. on Image Processing (ICIP), Vol. 5.Google ScholarCross Ref
11. Alessio Figalli. 2010. The optimal partial transport problem. Archive for rational mechanics and analysis 195, 2 (2010), 533–560.Google Scholar
12. William A Gale and Kenneth W Church. 1991. Identifying word correspondences in parallel texts. In Speech and Natural Language: Proceedings of a Workshop Held at Pacific Grove, California, February 19–22, 1991. Google ScholarDigital Library
13. Xianfeng Gu, Feng Luo, Jian Sun, and S-T Yau. 2013. Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampere equations. arXiv:1302.5472 (2013).Google Scholar
14. Daniel S. Hirschberg. 1975. A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 6 (1975), 341–343. Google ScholarDigital Library
15. Berthold KP Horn, Hugh M Hilden, and Shahriar Negahdaripour. 1988. Closed-form solution of absolute orientation using orthonormal matrices. JOSA A 5, 7 (1988).Google Scholar
16. Hagen Kaprykowsky and Xavier Rodet. 2006. Globally optimal short-time dynamic time warping, application to score to audio alignment. In IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), Vol. 5.Google ScholarCross Ref
17. Jun Kitagawa, Quentin Mérigot, and Boris Thibert. 2016. Convergence of a Newton algorithm for semi-discrete optimal transport. arXiv:1603.05579 (2016).Google Scholar
18. Soheil Kolouri, Charles E Martin, and Gustavo K Rohde. 2018. Sliced-Wasserstein Autoencoder: An Embarrassingly Simple Generative Model. arXiv:1804.01947 (2018).Google Scholar
19. Soheil Kolouri, Yang Zou, and Gustavo K Rohde. 2016. Sliced wasserstein kernels for probability distributions. In IEEE Conf. on Comp. Vis. and Patt. Recognition (CVPR).Google ScholarCross Ref
20. Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, Vol. 10. 707–710.Google Scholar
21. Bruno Lévy. 2015. A Numerical Algorithm for L2 semi-discrete optimal transport in 3D. ESAIM M2AN (Mathematical Modeling and Numerical Analysis) (2015).Google Scholar
22. Tyler Lu and Craig Boutilier. 2015. Value-Directed Compression of Large-Scale Assignment Problems. In AAAI Conf. on Artificial Intelligence. Google ScholarDigital Library
23. Edgar Maass. 2016. Point cloud alignment: ICP methods compared. Technical Report.Google Scholar
24. Quentin Mérigot. 2011. A Multiscale Approach to Optimal Transport. Computer Graphics Forum (2011).Google Scholar
25. Georges Nader and Gael Guennebaud. 2018. Instant Transport Maps on 2D Grids. ACM Trans. on Graphics (SIGGRAPH Asia) 249 (2018). Google ScholarDigital Library
26. Sylvain Paris and Frédo Durand. 2009. A fast approximation of the bilateral filter using a signal processing approach. International journal of computer vision 81, 1 (2009). Google ScholarDigital Library
27. Gabriel Peyré, Marco Cuturi, et al. 2017. Computational optimal transport. arXiv:1803.00567 (2017).Google Scholar
28. Francois Pitié, Anil C. Kokaram, and Rozenn Dahyot. 2005. N-Dimensional Probablility Density Function Transfer and Its Application to Colour Transfer. In IEEE Int. Conf. on Computer Vision (ICCV). Google ScholarDigital Library
29. François Pitié, Anil C Kokaram, and Rozenn Dahyot. 2007. Automated colour grading using colour distribution transfer. Comp. Vis. and Im. Understanding 107, 1–2 (2007). Google ScholarDigital Library
30. Julien Rabin, Julie Delon, and Yann Gousseau. 2010. Regularization of transportation maps for color and contrast transfer. In IEEE Int. Conf. on Image Processing (ICIP).Google ScholarCross Ref
31. Julien Rabin, Sira Ferradans, and Nicolas Papadakis. 2014. Adaptive color transfer with relaxed optimal transport. In IEEE Int. Conf. on Image Processing (ICIP).Google ScholarCross Ref
32. Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. 2011. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision. Springer, 435–446. Google ScholarDigital Library
33. Filippo Santambrogio. 2015. Optimal transport for applied mathematicians. Birkäuser, NY (2015).Google Scholar
34. Peter H Schönemann. 1966. A generalized solution of the orthogonal procrustes problem. Psychometrika 31, 1 (1966), 1–10.Google ScholarCross Ref
35. Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. on Graphics (SIGGRAPH) 34, 4 (2015). Google ScholarDigital Library
36. Robert E Tarjan and Jan Van Leeuwen. 1984. Worst-case analysis of set union algorithms. Journal of the ACM (JACM) 31, 2 (1984), 245–281. Google ScholarDigital Library
37. Shinji Umeyama. 1991. Least-squares estimation of transformation parameters between two point patterns. IEEE Trans. on Patt. Analysis & Machine Intelligence 4 (1991). Google ScholarDigital Library
38. Cédric Villani. 2003. Topics in optimal transportation. American Mathematical Soc.Google Scholar
39. Jiaolong Yang, Hongdong Li, and Yunde Jia. 2013. Go-icp: Solving 3d registration efficiently and globally optimally. In IEEE Int. Conf. on Computer Vision (ICCV). Google ScholarDigital Library
40. Timo Zinßer, Jochen Schmidt, and Heinrich Niemann. 2003. A refined ICP algorithm for robust 3-D correspondence estimation. In IEEE Int. Conf. on Image Processing.Google ScholarCross Ref
