skip to main content
research-article

DS++: a flexible, scalable and provably tight relaxation for matching problems

Published:20 November 2017Publication History
Skip Abstract Section

Abstract

Correspondence problems are often modelled as quadratic optimization problems over permutations. Common scalable methods for approximating solutions of these NP-hard problems are the spectral relaxation for non-convex energies and the doubly stochastic (DS) relaxation for convex energies. Lately, it has been demonstrated that semidefinite programming relaxations can have considerably improved accuracy at the price of a much higher computational cost.

We present a convex quadratic programming relaxation which is provably stronger than both DS and spectral relaxations, with the same scalability as the DS relaxation. The derivation of the relaxation also naturally suggests a projection method for achieving meaningful integer solutions which improves upon the standard closest-permutation projection. Our method can be easily extended to optimization over doubly stochastic matrices, injective matching, and problems with additional linear constraints. We employ recent advances in optimization of linear-assignment type problems to achieve an efficient algorithm for solving the convex relaxation.

We present experiments indicating that our method is more accurate than local minimization or competing relaxations for non-convex problems. We successfully apply our algorithm to shape matching and to the problem of ordering images in a grid, obtaining results which compare favorably with state of the art methods.

We believe our results indicate that our method should be considered the method of choice for quadratic optimization over permutations.

References

  1. Warren P Adams and Terri A Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS series in discrete mathematics and theoretical computer science 16 (1994), 43--75.Google ScholarGoogle Scholar
  2. Yonathan Aflalo, Alexander Bronstein, and Ron Kimmel. 2015. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences 112, 10 (10 March 2015), 2942--2947.Google ScholarGoogle ScholarCross RefCross Ref
  3. Kurt M Anstreicher and Nathan W Brixius. 2001. A new bound for the quadratic assignment problem based on convex quadratic programming. Mathematical Programming 89, 3 (2001), 341--357.Google ScholarGoogle ScholarCross RefCross Ref
  4. Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. 2015. Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing 37, 2 (2015), A1111--A1138.Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Federica Bogo, Javier Romero, Matthew Loper, and Michael J Black. 2014. FAUST: Dataset and evaluation for 3D mesh registration. In Computer Vision and Pattern Recognition (CVPR), 2014 IEEE Conference on. IEEE, 3794--3801. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Emilio Carrizosa, Vanesa Guerrero, and Dolores Romero Morales. 2016. Visualizing proportions and dissimilarities by Space-filling maps: a Large Neighborhood Search approach. Computers & Operations Research (2016). Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Ken Chatfield, Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. 2014. Return of the devil in the details: Delving deep into convolutional nets. arXiv preprint arXiv:1405.3531 (2014).Google ScholarGoogle Scholar
  8. Qifeng Chen and Vladlen Koltun. 2015. Robust Nonrigid Registration by Convex Optimization. In Proceedings of the IEEE International Conference on Computer Vision. 2039--2047. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems. 2292--2300. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Edilson De Aguiar, Carsten Stoll, Christian Theobalt, Naveed Ahmed, Hans-Peter Seidel, and Sebastian Thrun. 2008. Performance capture from sparse multi-view video. In ACM Transactions on Graphics (TOG), Vol. 27. ACM, 98. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Yichuan Ding and Henry Wolkowicz. 2009. A low-dimensional semidefinite relaxation for the quadratic assignment problem. Mathematics of Operations Research 34, 4 (2009), 1008--1022. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Nadav Dym and Yaron Lipman. 2016. Exact Recovery with Symmetries for Procrustes Matching. arXiv preprint arXiv:1606.01548 (2016).Google ScholarGoogle Scholar
  13. Yuval Eldar, Michael Lindenbaum, Moshe Porat, and Yehoshua Y Zeevi. 1997. The farthest point strategy for progressive image sampling. Image Processing, IEEE Transactions on 6, 9 (1997), 1305--1315. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Wei Feng, Jin Huang, Tao Ju, and Hujun Bao. 2013. Feature correspondences using morse smale complex. The Visual Computer 29, 1 (2013), 53--67.Google ScholarGoogle ScholarCross RefCross Ref
  15. Marcelo Fiori and Guillermo Sapiro. 2015. On spectral properties for graph matching and graph isomorphism problems. Information and Inference 4, 1 (2015), 63--76.Google ScholarGoogle ScholarCross RefCross Ref
  16. Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d'Aspremont. 2013. Convex relaxations for permutation problems. In Advances in Neural Information Processing Systems. 1016--1024. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. F. Fogel, R. Jenatton, F. Bach, and A. d'Aspremont. 2015. Convex Relaxations for Permutation Problems. SIAM J. Matrix Anal. Appl. 36, 4 (2015), 1465--1488.Google ScholarGoogle ScholarCross RefCross Ref
  18. Ohad Fried, Stephen DiVerdi, Maciej Halber, Elena Sizikova, and Adam Finkelstein. 2015. IsoMatch: Creating informative grid layouts. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 155--166. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Andrew H Gee and Richard W Prager. 1994. Polyhedral combinatorics and neural networks. Neural computation 6, 1 (1994), 161--180. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi. 2007. Shape retrieval contest 2007: Watertight models track. SHREC competition 8 (2007).Google ScholarGoogle Scholar
  21. Gary B Huang, Manu Ramesh, Tamara Berg, and Erik Learned-Miller. 2007. Labeled faces in the wild: A database for studying face recognition in unconstrained environments. Technical Report. Technical Report 07--49, University of Massachusetts, Amherst.Google ScholarGoogle Scholar
  22. Itay Kezurer, Shahar Z. Kovalsky, Ronen Basri, and Yaron Lipman. 2015. Tight Relaxation of Quadratic Matching. Comput. Graph. Forum 34, 5 (Aug. 2015), 115--128.Google ScholarGoogle Scholar
  23. Vladimir G Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended intrinsic maps. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 79. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Vladimir Kolmogorov. 2006. Convergent tree-reweighted message passing for energy minimization. IEEE transactions on pattern analysis and machine intelligence 28, 10 (2006), 1568--1583. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. JJ Kosowsky and Alan L Yuille. 1994. The invisible hand algorithm: Solving the assignment problem with statistical physics. Neural networks 7, 3 (1994), 477--490. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Marius Leordeanu and Martial Hebert. 2005. A spectral technique for correspondence problems using pairwise constraints. In Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, Vol. 2. IEEE, 1482--1489. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Yaron Lipman and Thomas Funkhouser. 2009. Möbius voting for surface correspondence. In ACM Transactions on Graphics (TOG), Vol. 28. ACM, 72. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Jingen Liu, Jiebo Luo, and Mubarak Shah. 2009. Recognizing realistic actions from videos âĂIJin the wildâĂİ. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 1996--2003.Google ScholarGoogle ScholarCross RefCross Ref
  29. Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. 2007. A survey for the quadratic assignment problem. European journal of operational research 176, 2 (2007), 657--690.Google ScholarGoogle Scholar
  30. Vince Lyzinski, Donniell E. Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, and Guillermo Sapiro. 2016. Graph Matching: Relax at Your Own Risk. IEEE Trans. Pattern Anal. Mach. Intell. 38, 1 (2016), 60--73. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. Haggai Maron, Nadav Dym, Itay Kezurer, Shahar Kovalsky, and Yaron Lipman. 2016. Point Registration via Efficient Convex Relaxation. ACM Trans. Graph. 35, 4, Article 73 (July 2016), 12 pages. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. 2015. Geodesic convolutional neural networks on riemannian manifolds. In Proceedings of the IEEE international conference on computer vision workshops. 37--45. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. Facundo Mémoli. 2011. Gromov-Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11, 4 (2011), 417--487. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. Facundo Mémoli and Guillermo Sapiro. 2005. A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics 5, 3 (2005), 313--347.Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. Richard G Ogier and DA Beyer. 1990. Neural network solution to the link scheduling problem using convex relaxation. In Global Telecommunications Conference, 1990, and Exhibition.'Communications: Connecting the Future', GLOBECOM'90., IEEE. IEEE, 1371--1376.Google ScholarGoogle ScholarCross RefCross Ref
  36. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 30. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman. 2015. Deep face recognition. In British Machine Vision Conference, Vol. 1. 6.Google ScholarGoogle ScholarCross RefCross Ref
  38. Novi Quadrianto, Le Song, and Alex J Smola. 2009. Kernelized sorting. In Advances in neural information processing systems. 1289--1296. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. Anand Rangarajan, Steven Gold, and Eric Mjolsness. 1996. A novel optimizing network architecture with applications. Neural Computation 8, 5 (1996), 1041--1060. Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. Anand Rangarajan, Alan L Yuille, Steven Gold, and Eric Mjolsness. 1997. A convergence proof for the soft assign quadratic assignment algorithm. Advances in neural information processing systems (1997), 620--626. Google ScholarGoogle ScholarDigital LibraryDigital Library
  41. Emanuele Rodola, Alex M Bronstein, Andrea Albarelli, Filippo Bergamasco, and Andrea Torsello. 2012. A game-theoretic approach to deformable shape matching. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 182--189. Google ScholarGoogle ScholarDigital LibraryDigital Library
  42. Emanuele Rodolà, Samuel Rota Bulo, Thomas Windheuser, Matthias Vestner, and Daniel Cremers. 2014. Dense non-rigid shape correspondence using random forests. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 4177--4184. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. Christian Schellewald, Stefan Roth, and Christoph Schnörr. 2001. Evaluation of convex optimization techniques for the weighted graph-matching problem in computer vision. In Joint Pattern Recognition Symposium. Springer, 361--368. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. Tianjia Shao, Wilmot Li, Kun Zhou, Weiwei Xu, Baining Guo, and Niloy J Mitra. 2013. Interpreting concept sketches. ACM Transactions on Graphics (TOG) 32, 4 (2013), 56. Google ScholarGoogle ScholarDigital LibraryDigital Library
  45. 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 Transactions on Graphics (TOG) 34, 4 (2015), 66. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas. 2012. Soft maps between surfaces. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1617--1626. Google ScholarGoogle ScholarDigital LibraryDigital Library
  47. Justin Solomon, Gabriel Peyré, Vladimir G. Kim, and Suvrit Sra. 2016. Entropic Metric Alignment for Correspondence Problems. ACM Trans. Graph. 35, 4, Article 72 (July 2016), 13 pages. Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. Grant Strong and Minglun Gong. 2014. Self-sorting map: An efficient algorithm for presenting multimedia data in structured layouts. IEEE Transactions on Multimedia 16, 4 (2014), 1045--1058. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A survey on shape correspondence. In Computer Graphics Forum, Vol.30. Wiley Online Library, 1681--1707.Google ScholarGoogle Scholar
  50. Lingyu Wei, Qixing Huang, Duygu Ceylan, Etienne Vouga, and Hao Li. 2016. Dense Human Body Correspondences Using Convolutional Networks. In Computer Vision and Pattern Recognition (CVPR).Google ScholarGoogle Scholar
  51. Tomas Werner. 2007. A linear programming approach to max-sum problem: A review. IEEE transactions on pattern analysis and machine intelligence 29, 7 (2007). Google ScholarGoogle ScholarDigital LibraryDigital Library
  52. Yong Xia. 2008. Second order cone programming relaxation for quadratic assignment problems. Optimization Methods & Software 23, 3 (2008), 441--449. Google ScholarGoogle ScholarDigital LibraryDigital Library
  53. Jianxiong Xiao, James Hays, Krista A Ehinger, Aude Oliva, and Antonio Torralba. 2010. Sun database: Large-scale scene recognition from abbey to zoo. In Computer vision and pattern recognition (CVPR), 2010 IEEE conference on. IEEE, 3485--3492.Google ScholarGoogle Scholar
  54. Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. 2009. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 12 (2009), 2227--2242. Google ScholarGoogle ScholarDigital LibraryDigital Library
  55. Yun Zeng, Chaohui Wang, Yang Wang, Xianfeng Gu, Dimitris Samaras, and Nikos Paragios. 2010. Dense non-rigid surface registration using high-order graph matching. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 382--389.Google ScholarGoogle ScholarCross RefCross Ref
  56. Qing Zhao, Stefan E Karisch, Franz Rendl, and Henry Wolkowicz. 1998. Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization 2, 1 (1998), 71--109.Google ScholarGoogle ScholarCross RefCross Ref
  57. Silvia Zuffi and Michael J Black. 2015. The Stitched Puppet: A Graphical Model of 3D Human Shape and Pose. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 3537--3546.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. DS++: a flexible, scalable and provably tight relaxation for matching problems

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in

    Full Access

    • Published in

      cover image ACM Transactions on Graphics
      ACM Transactions on Graphics  Volume 36, Issue 6
      December 2017
      973 pages
      ISSN:0730-0301
      EISSN:1557-7368
      DOI:10.1145/3130800
      Issue’s Table of Contents

      Copyright © 2017 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 20 November 2017
      Published in tog Volume 36, Issue 6

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader