“Entropic metric alignment for correspondence problems”
Conference:
Type(s):
Title:
- Entropic metric alignment for correspondence problems
Session/Category Title: CORRESPONDENCE & MAPPING
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Many shape and image processing tools rely on computation of correspondences between geometric domains. Efficient methods that stably extract “soft” matches in the presence of diverse geometric structures have proven to be valuable for shape retrieval and transfer of labels or semantic information. With these applications in mind, we present an algorithm for probabilistic correspondence that optimizes an entropy-regularized Gromov-Wasserstein (GW) objective. Built upon recent developments in numerical optimal transportation, our algorithm is compact, provably convergent, and applicable to any geometric domain expressible as a metric measure matrix. We provide comprehensive experiments illustrating the convergence and applicability of our algorithm to a variety of graphics tasks. Furthermore, we expand entropic GW correspondence to a framework for other matching problems, incorporating partial distance matrices, user guidance, shape exploration, symmetry detection, and joint analysis of more than two domains. These applications expand the scope of entropic GW correspondence to major shape analysis problems and are stable to distortion and noise.
References:
1. Aflalo, Y., and Kimmel, R. 2013. Spectral multidimensional scaling. PNAS 110, 45, 18052–18057.Google ScholarCross Ref
2. Aflalo, Y., Bronstein, A. M., and Kimmel, R. 2014. Graph matching: relax or not? CoRR abs/1401.7623.Google Scholar
3. Aflalo, Y., Bronstein, A., and Kimmel, R. 2015. On convex relaxation of graph isomorphism. Proc. National Academy of Sci. 112, 10, 2942–2947.Google ScholarCross Ref
4. Attouch, H., Bolte, J., Redont, P., and Soubeyran, A. 2010. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35, 2 (May), 438–457. Google ScholarDigital Library
5. Bauschke, H., and Combettes, P. 2011. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS. Google ScholarDigital Library
6. Bauschke, H. H., Combettes, P. L., and Noll, D. 2006. Joint minimization with alternating Bregman proximity operators. Pacific J. Optim. 2, 3, 401–424.Google Scholar
7. Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G. 2015. Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comp. 37, 2, A1111–A1138.Google ScholarCross Ref
8. Berg, A. C., Berg, T. L., and Malik, J. 2005. Shape matching and object recognition using low distortion correspondences. In Proc. CVPR, vol. 1, 26–33. Google ScholarDigital Library
9. Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using Lagrangian mass transport. ACM Trans. Graph. 30, 6 (Dec.), 158:1–158:12. Google ScholarDigital Library
10. Boţ, R. I., Csetnek, E. R., and László, S. C. 2015. An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions. EURO J. Comp. Optim., 1–23.Google Scholar
11. Bregman, L. M. 1967. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR comp. math. and math. phys. 7, 3, 200–217.Google Scholar
12. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. PNAS 103, 5, 1168–1172.Google ScholarCross Ref
13. Bronstein, A. M., Bronstein, M. M., Kimmel, R., Mah-moudi, M., and Sapiro, G. 2010. A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching. IJCV 89, 2-3, 266–286. Google ScholarDigital Library
14. Bronstein, A. M., Bronstein, M. M., Guibas, L. J., and Ovsjanikov, M. 2011. Shape Google: Geometric words and expressions for invariant shape retrieval. TOG 30, 1 (Feb.), 1:1–1:20. Google ScholarDigital Library
15. Çela, E. 2013. The Quadratic Assignment Problem: Theory and Algorithms. Combinatorial Optim. Springer.Google Scholar
16. Chen, Q., and Koltun, V. 2015. Robust nonrigid registration by convex optimization. In Proc. ICCV, 2039–2047. Google ScholarDigital Library
17. Chen, Y., Guibas, L., and Huang, Q. 2014. Near-optimal joint object matching via convex relaxation. In Proc. ICML, JMLR Workshop and Conference Proceedings, 100–108.Google Scholar
18. Combettes, P. L., and Pesquet, J.-C. 2011. Proximal splitting methods in signal processing. In Fixed-point algorithms for inverse problems in science and engineering. 185–212.Google Scholar
19. Coste, M. 1999. An introduction to O-minimal geometry. Tech. rep., Institut de Recherche Mathematiques de Rennes, November.Google Scholar
20. Cuturi, M. 2013. Sinkhorn distances: Lightspeed computation of optimal transportation. In Proc. NIPS, vol. 26. 2292–2300.Google Scholar
21. De Goes, F., Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. In CGF, vol. 30, 1593–1602.Google ScholarCross Ref
22. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (Nov.), 171:1–171:11. Google ScholarDigital Library
23. de Goes, F., Wallez, C., Huang, J., Pavlov, D., and Desbrun, M. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (July), 50:1–50:11. Google ScholarDigital Library
24. Fried, O., DiVerdi, S., Halber, M., Sizikova, E., and Finkelstein, A. 2015. IsoMatch: Creating informative grid layouts. In CGF, vol. 34, 155–166. Google ScholarDigital Library
25. Gaussier, E., and Goutte, C. 2005. Relation between pLSA and NMF and implications. In Proc. SIGIR, 601–602. Google ScholarDigital Library
26. Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. Shrec: shape retrieval contest: Watertight models track. http://watertight.ge.imati.cnr.it.Google Scholar
27. Gold, S., and Rangarajan, A. 1996. A graduated assignment algorithm for graph matching. PAMI 18, 4 (Apr.), 377–388. Google ScholarDigital Library
28. Gromov, M. 2001. Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Math. Birkhäuser.Google Scholar
29. Hofmann, T. 1999. Probabilistic latent semantic indexing. In Proc. SIGIR, 50–57. Google ScholarDigital Library
30. Huang, Q., and Guibas, L. 2013. Consistent shape maps via semidefinite programming. In Proc. SGP, 177–186. Google ScholarDigital Library
31. Hunter, D., and Lange, K. 2000. Quantile regression via an MM algorithm. J. Comp. and Graphical Stats. 9, 1, 60–77.Google Scholar
32. Kezurer, I., Kovalsky, S. Z., Basri, R., and Lipman, Y. 2015. Tight relaxation of quadratic matching. CGF.Google Scholar
33. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. ACM Trans. Graph. 30, 4 (July), 79:1–79:12. Google ScholarDigital Library
34. Kim, V. G., Li, W., Mitra, N. J., DiVerdi, S., and Funkhouser, T. 2012. Exploring collections of 3d models using fuzzy correspondences. ACM Trans. Graph. 31, 4 (July), 54:1–54:11. Google ScholarDigital Library
35. Kurdyka, K. 1998. On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier 48, 3, 769–783.Google Scholar
36. Lanckriet, G. R., and Sriperumbudur, B. K. 2009. On the convergence of the concave-convex procedure. In Proc. NIPS, 1759–1767.Google Scholar
37. Leordeanu, M., and Hebert, M. 2005. A spectral technique for correspondence problems using pairwise constraints. In Proc. ICCV, 1482–1489. Google ScholarDigital Library
38. Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., and Querido, T. 2007. A survey for the quadratic assignment problem. European J. Operational Research 176, 2, 657–690.Google ScholarCross Ref
39. Łojasiewicz, S. 1963. Une propriété topologique des sousensembles analytiques réels. Les équations aux dérivées partielles, 87–89.Google Scholar
40. Łojasiewicz, S. 1993. Sur la géométrie semi-et sous-analytique. In Annales de l’institut Fourier, vol. 43, 1575–1595.Google Scholar
41. Lyzinski, V., Fishkind, D., Fiori, M., Vogelstein, J., Priebe, C., and Sapiro, G. 2015. Graph matching: Relax at your own risk. PAMI. Google ScholarDigital Library
42. Mémoli, F. 2007. On the use of Gromov–Hausdorff distances for shape comparison. In Symposium on Point Based Graphics. 81–90.Google Scholar
43. Mémoli, F. 2008. Gromov–Hausdorff distances in Euclidean spaces. In Proc. CVPR Workshops, 1–8.Google ScholarCross Ref
44. Mémoli, F. 2009. Spectral Gromov-Wasserstein distances for shape matching. In Proc. ICCV Workshops, 256–263.Google ScholarCross Ref
45. Mémoli, F. 2011. Gromov–Wasserstein distances and the metric approach to object matching. Foundations of Comp. Math. 11, 4, 417–487. Google ScholarDigital Library
46. Mémoli, F. 2014. The Gromov–Wasserstein distance: A brief overview. Axioms 3, 3.Google ScholarCross Ref
47. Mérigot, Q. 2011. A multiscale approach to optimal transport. In CGF, vol. 30, 1583–1592.Google ScholarCross Ref
48. Meyer, R. R. 1976. Sufficient conditions for the convergence of monotonic mathematical programming algorithms. J. Comput. Syst. Sci. 12, 1 (Feb.), 108–121. Google ScholarDigital Library
49. Ovsjanikov, M., Mérigot, Q., Mémoli, F., and Guibas, L. 2010. One point isometric matching with the heat kernel. In CGF, vol. 29, 1555–1564.Google ScholarCross Ref
50. Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., and Guibas, L. 2012. Functional maps: A flexible representation of maps between shapes. ACM Trans. Graph. 31, 4 (July), 30:1–30:11. Google ScholarDigital Library
51. Pachauri, D., Kondor, R., and Singh, V. 2013. Solving the multi-way matching problem by permutation synchronization. In Proc. NIPS. 1860–1868.Google Scholar
52. Pardalos, P., and Wolkowicz, H., Eds. 1994. Quadratic Assignment and Related Problems. AMS.Google Scholar
53. Pauly, M., 2015. The beauty of geometry (SGP keynote), July.Google Scholar
54. Quadrianto, N., Song, L., and Smola, A. J. 2009. Kernelized sorting. In Proc. NIPS, vol. 21. 1289–1296.Google Scholar
55. Rangarajan, A., Gold, S., and Mjolsness, E. 1996. A novel optimizing network architecture with applications. Neural Comp. 8, 5, 1041–1060. Google ScholarDigital Library
56. Rangarajan, A., Yuille, A. L., Gold, S., and Mjolsness, E. 1997. A convergence proof for the softassign quadratic assignment algorithm. Proc. NIPS, 620–626.Google Scholar
57. Rangarajan, A., Yuille, A., and Mjolsness, E. 1999. Convergence properties of the softassign quadratic assignment algorithm. Neural Comput. 11, 6 (Aug.), 1455–1474. Google ScholarDigital Library
58. Rubner, Y., Tomasi, C., and Guibas, L. J. 2000. The earth mover’s distance as a metric for image retrieval. IJCV 40, 2 (Nov.), 99–121. Google ScholarDigital Library
59. Rustamov, R. M., Ovsjanikov, M., Azencot, O., Ben-Chen, M., Chazal, F., and Guibas, L. 2013. Map-based exploration of intrinsic shape differences and variability. TOG 32, 4 (July), 72:1–72:12. Google ScholarDigital Library
60. Sahni, S., and Gonzalez, T. 1976. P-complete approximation problems. J. ACM 23, 3 (July), 555–565. Google ScholarDigital Library
61. Sahni, S. 1974. Computationally related problems. SIAM J. Comp. 3, 4, 262–279.Google ScholarCross Ref
62. Schwartzburg, Y., Testuz, R., Tagliasacchi, A., and Pauly, M. 2014. High-contrast computational caustic design. ACM Trans. Graph. 33, 4 (July), 74:1–74:11. Google ScholarDigital Library
63. Smola, A., Gretton, A., Song, L., and Schölkopf, B. 2007. A Hilbert space embedding for distributions. In Algorithmic Learning Theory, vol. 4754 of LNCS. 13–31. Google ScholarDigital Library
64. Solomon, J., Nguyen, A., Butscher, A., Ben-Chen, M., and Guibas, L. 2012. Soft maps between surfaces. CGF 31, 5 (Aug.), 1617–1626. Google ScholarDigital Library
65. Solomon, J., Guibas, L., and Butscher, A. 2013. Dirichlet energy for analysis and synthesis of soft maps. In CGF, vol. 32, 197–206. Google ScholarDigital Library
66. Solomon, J., Rustamov, R., Guibas, L., and Butscher, A. 2014. Earth mover’s distances on discrete surfaces. ACM Trans. Graph. 33, 4 (July), 67:1–67:12. Google ScholarDigital Library
67. Solomon, J., de Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., and Guibas, L. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. TOG 34, 4 (July), 66:1–66:11. Google ScholarDigital Library
68. Sturm, K.-T. 2012. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. Preprint 1208.0434, arXiv.Google Scholar
69. Sun, J., Qu, Q., and Wright, J. 2015. When are nonconvex problems not scary? arXiv:1510.06096.Google Scholar
70. Tangelder, J. W., and Veltkamp, R. C. 2008. A survey of content based 3d shape retrieval methods. Multimedia Tools Appl. 39, 3 (Sept.), 441–471. Google ScholarDigital Library
71. Thakoor, N., Gao, J., and Jung, S. 2007. Hidden Markov model-based weighted likelihood discriminant for 2-D shape classification. Trans. Image Proc. 16, 11, 2707–2719. Google ScholarDigital Library
72. Tropp, J. A., 2003. An alternating minimization algorithm for non-negative matrix approximation.Google Scholar
73. Urakawa, H. 2013. Calculus of Variations and Harmonic Maps. Translations of Math. Monographs. AMS.Google Scholar
74. van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2011. A survey on shape correspondence. CGF 30, 6, 1681–1707.Google ScholarCross Ref
75. Villani, C. 2003. Topics in Optimal Transportation. Graduate studies in Math. AMS.Google Scholar
76. Waltz, R. A., Morales, J. L., Nocedal, J., and Orban, D. 2006. An interior algorithm for nonlinear optimization that combines line search and trust region steps. Math. Program. 107, 3 (July), 391–408.Google ScholarCross Ref
77. Wei, L., Huang, Q., Ceylan, D., Vouga, E., and Li, H. 2015. Dense human body correspondences using convolutional networks. CoRR abs/1511.05904.Google Scholar
