“Entropic metric alignment for correspondence problems”

  • ©Justin Solomon, Gabriel Peyré, Vladimir G. Kim, and Suvrit Sra




    Entropic metric alignment for correspondence problems





    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.


    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

ACM Digital Library Publication: