“Displacement interpolation using Lagrangian mass transport”
Conference:
Type(s):
Title:
- Displacement interpolation using Lagrangian mass transport
Session/Category Title: Rendering: Accuracy and Efficiency
Presenter(s)/Author(s):
Abstract:
Interpolation between pairs of values, typically vectors, is a fundamental operation in many computer graphics applications. In some cases simple linear interpolation yields meaningful results without requiring domain knowledge. However, interpolation between pairs of distributions or pairs of functions often demands more care because features may exhibit translational motion between exemplars. This property is not captured by linear interpolation. This paper develops the use of displacement interpolation for this class of problem, which provides a generic method for interpolating between distributions or functions based on advection instead of blending. The functions can be non-uniformly sampled, high-dimensional, and defined on non-Euclidean manifolds, e.g., spheres and tori. Our method decomposes distributions or functions into sums of radial basis functions (RBFs). We solve a mass transport problem to pair the RBFs and apply partial transport to obtain the interpolated function. We describe practical methods for computing the RBF decomposition and solving the transport problem. We demonstrate the interpolation approach on synthetic examples, BRDFs, color distributions, environment maps, stipple patterns, and value functions.
References:
1. Ahmad, N., Hwa Kil, K., and McCann, R., 2010. Optimal transportation, topology and uniqueness. arXiv:1008.4419vl.Google Scholar
2. Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Google ScholarDigital Library
3. Ashikhmin, M., and Shirley, P. 2000. An anisotropic phong BRDF model. J. Graph. Tools 5, 2, 25–32. Google ScholarDigital Library
4. Benamou, J. D., and Brenier, Y. 2000. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84, 3, 375–393.Google ScholarCross Ref
5. Bieling, J., Peschlow, P., and Martini, P. 2010. An efficient GPU implementation of the revised simplex method. 1–8.Google Scholar
6. Bursal, F. 1996. On interpolating between probability distributions. Applied Mathematics and Computation 77, 213–244. Google ScholarDigital Library
7. Cantarella, J., and Piatek, M. 2004. Tsnnls: A solver for large sparse least squares problems with non-negative variables. CoRR cs.MS/0408029.Google Scholar
8. da Silva, M., Durand, F., and Popovic, J. 2009. Linear Bellman combination for control of character animation. ACM Trans Graph (SIGGRAPH’09) 28, 3, 1–10. Google ScholarDigital Library
9. Dong, Y., Wang, J., Tong, X., Snyder, J., Lan, Y, Ben-Ezra, M., and Guo, B. 2010. Manifold bootstrapping for SVBRDF capture. ACM Trans Graph (SIGGRAPH’10) 29, 4, 1–10. Google ScholarDigital Library
10. Flood, M. M. 1953. On the Hitchcock distribution problem. Pacific J. Math. 3, 2, 369–386.Google ScholarCross Ref
11. Haker, S., Zhu, L., Tannenbaum, A., and Angenent, S. 2004. Optimal mass transport for registration and warping. International Journal on Computer Vision 60, 3, 225–240. Google ScholarDigital Library
12. Han, C., Sun, B., Ramamoorthi, R., and Grinspun, E. 2007. Frequency domain normal map filtering. ACM Trans on Graphics (SIGGRAPH’07) 26, 3, 28:1–28:12. Google ScholarDigital Library
13. HDRShop,. LightGen plug-in. http://gl.ict.usc.edu/HDRShop/lightgen/.Google Scholar
14. Hlllier, F. S., AND Lieberman, G. J. 1990. Introduction to Operations Research, 5th ed. McGraw-Hill.Google Scholar
15. Kanters, F., Platel, B., Florack, L., and Romeny, B. M. T. H. 2003. Content based image retrieval using multiscale top points a feasibility study. In Proc. of the 4th Int. Conf. on Scale space methods in Computer Vision, 33–43. Google ScholarDigital Library
16. Kelly, D. J., and O’Neill, G. M., 1991. The minimum cost flow problem and the network simplex method, September.Google Scholar
17. Lawson, C. L., and Hanson, R. J. 1995. Solving least squares problems, 3 ed.Google Scholar
18. LEMON, 2010. LEMON: Library for efficient modeling and optimization in networks, http://lemon.cs.elte.hu/trac/lemon.Google Scholar
19. Lensch, H. P. A., Kautz, J., Goesele, M., Heidrich, W., and Seidel, H.-P. 2001. Image-based reconstruction of spatially varying materials. Rendering Techniques. Proc. of Eurographics Rendering Workshop. Google ScholarDigital Library
20. Lipman, Y., and Daubechies, I. Conformal Wasserstein distances: comparing surfaces in polynomial time. Advances in Mathematics (In Press).Google Scholar
21. Luo, Y., and Duraiswami, R. 2010. Efficient parallel non-negative least squares on the GPU. submitted to the SIAM Journal on Scientific Computing. Google ScholarDigital Library
22. MacDonald, D., 2006. A C++ implementation of the transportation simplex algorithm, http://www.site.uottawa.ca/~dmacd070/emd/.Google Scholar
23. Makihara, Y, and Yagi, Y. 2011. Earth mover’s morphing: topology-free shape morphing using cluster-based emd flows. In Proc. 10th Asian conference on Computer vision, 202–215. Google ScholarDigital Library
24. Matusik, W., Pfister, H., Brand, M., and McMillan, L. 2003. A data-driven reflectance model. ACM Trans Graph (SIGGRAPH’03) 22, 3, 759–769. Google ScholarDigital Library
25. Matusik, W., Zwicker, M., and Durand, F. 2005. Texture design using a simplicial complex of morphable textures. ACM Trans Graph (SIGGRAPH’05) 24, 3, 787–794. Google ScholarDigital Library
26. McCann, R. J. 1997. A convexity principle for interacting gases. Advances in Mathematics 128, 153–179.Google ScholarCross Ref
27. Morovic, J., and Sun, P.-L. 2003. Accurate 3D image colour histogram transformation. Pattern Recognition Letters 24, 11, 1725–1735. Google ScholarDigital Library
28. Ngan, A., Durand, F., and Matusik, W. 2006. Image-driven navigation of analytical brdf models. In Proc. of the Eurographics Symposium on Rendering. Google ScholarDigital Library
29. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans Graphics (SIGGRAPH’04) 23, 3, 488–495. Google ScholarDigital Library
30. Pele, O., and Werman, M. 2009. Fast and robust earth mover’s distances. In ICCV.Google Scholar
31. Pellacini, F., Ferwerda, J. A., and Greenberg, D. P. 2000. Toward a psychophysically-based light reflection model for image synthesis. In Proc. ACM SIGGRAPH 2000, 55–64. Google ScholarDigital Library
32. Pharr, M., and Humphreys, G. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation. Morgan Kaufmann, July. Google ScholarDigital Library
33. Pitié, F., Kokaram, A. C., and Dahyot, R. 2005. N-dimensional probablility density function transfer and its application to colour transfer. IEEE ICCV 2, 1434–1439. Google ScholarDigital Library
34. Preetham, A. J., Shirley, P., and Smits, V. 1999. A practical analytic model for daylight. In Proc. ACM SIGGRAPH 99. Google ScholarDigital Library
35. Rabin, J., Peyré, G., Delon, J., and Bernot, M. 2010. Wasserstein Barycenter and its Application to Texture Mixing. Tech. rep.Google Scholar
36. Read, A. L. 1999. Linear interpolation of histograms. Nuclear Instruments and Methods in Physics Research A 425 (Apr.), 357–360.Google ScholarCross Ref
37. Rehman, T. u., Pryor, G., and Tannenbaum, A. 2007. Fast multigrid optimal mass transport for image registration and morphing. In Proc. of the 18th British Machine Vision Conference, 102–111.Google Scholar
38. Rehman, T. u., Haber, E., Pryor, G., Melonakos, J., and Tannenbaum, A. 2009. 3D nonrigid registration via optimal mass transport on the GPU. Medical Image Analysis 13, 6, 931–940.Google ScholarCross Ref
39. Rubner, Y, Tomasi, C., and Guibas, L. J. 2000. The Earth Mover’s Distance as a metric for image retrieval. Int. J. Comput. Vision 40, 2, 99–121. Google ScholarDigital Library
40. Rubner, Y, 1998. Code for the Earth Mover’s Distance (EMD). http://vision.Stanford.edu/~rubner/emd/.Google Scholar
41. Rusinkiewicz, S. 1998. A new change of variables for efficient BRDF representation. In Rendering Techniques (Proc. Eurographics Workshop on Rendering).Google ScholarCross Ref
42. Secord, A., Heidrich, W., and Streit, L. 2002. Fast primitive distribution for illustration. In Rendering Techniques (Proc. Eurographics Workshop on Rendering), 215–226. Google ScholarDigital Library
43. Subr, K., Soler, C., and Durand, F. 2009. Edge-preserving multiscale image decomposition based on local extrema. ACM Trans Graph (SIGGRAPHASIA’09) 28, 147:1–147:9. Google ScholarDigital Library
44. Tan, P., Lin, S., Quan, L., Guo, B., and Shum, H.-Y 2005. Multiresolution reflectance filtering. In Rendering Techniques, 111–116. Google ScholarCross Ref
45. Villani, C. 2003. Topics in Optimal Transportation (Graduate Studies in Mathematics, Vol. 58). American Mathematical Society, March.Google Scholar
46. Villani, C. 2008. Optimal Transport: Old and New, 1 ed. Grundlehren der mathematischen Wissenschaften. Springer, November.Google Scholar
47. Wills, L, Agarwal, S., Kriegman, D., and Belongie, S. 2009. Toward a perceptual space for gloss. ACM Trans Graph 28, 4, 1–15. Google ScholarDigital Library
48. Zhao, Q., Yang, Z., and Tao, H. 2010. Differential earth mover’s distance with its applications to visual tracking. IEEE Trans Patt. Analysis and Machine Intelligence 32, 2, 274–287. Google ScholarDigital Library
49. Zhu, L., Yang, Y, Haker, S., and Tannenbaum, A. 2007. An image morphing technique based on optimal mass preserving mapping. IEEE Trans Image Process 16, 6 (06), 1481–1495. Google ScholarDigital Library
