More Web Proxy on the site http://driver.im/

research-article

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

Authors:

Yaron LipmanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 36, Issue 6

Article No.: 184, Pages 1 - 14

https://doi.org/10.1145/3130800.3130826

Published: 20 November 2017 Publication History

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.

[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.

[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.

[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.

Digital 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.

Digital 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).

Digital 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).

[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.

Digital Library

[9]

Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems. 2292--2300.

Digital 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.

Digital 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.

Digital Library

[12]

Nadav Dym and Yaron Lipman. 2016. Exact Recovery with Symmetries for Procrustes Matching. arXiv preprint arXiv:1606.01548 (2016).

[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.

Digital 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.

[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.

[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.

Digital 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.

[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.

Digital Library

[19]

Andrew H Gee and Richard W Prager. 1994. Polyhedral combinatorics and neural networks. Neural computation 6, 1 (1994), 161--180.

Digital Library

[20]

Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi. 2007. Shape retrieval contest 2007: Watertight models track. SHREC competition 8 (2007).

[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.

[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.

[23]

Vladimir G Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended intrinsic maps. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 79.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[27]

Yaron Lipman and Thomas Funkhouser. 2009. Möbius voting for surface correspondence. In ACM Transactions on Graphics (TOG), Vol. 28. ACM, 72.

Digital 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.

[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.

[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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

[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.

Digital Library

[37]

Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman. 2015. Deep face recognition. In British Machine Vision Conference, Vol. 1. 6.

[38]

Novi Quadrianto, Le Song, and Alex J Smola. 2009. Kernelized sorting. In Advances in neural information processing systems. 1289--1296.

Digital Library

[39]

Anand Rangarajan, Steven Gold, and Eric Mjolsness. 1996. A novel optimizing network architecture with applications. Neural Computation 8, 5 (1996), 1041--1060.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

[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).

[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).

Digital Library

[52]

Yong Xia. 2008. Second order cone programming relaxation for quadratic assignment problems. Optimization Methods & Software 23, 3 (2008), 441--449.

Digital 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.

[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.

Digital 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.

[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.

[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.

Cited By

Liu HScaglione AWai H(2024)Blind Graph Matching Using Graph SignalsIEEE Transactions on Signal Processing10.1109/TSP.2024.338284072(1766-1781)Online publication date: 28-Mar-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3382840
Li LMei SMa WLiu XLi JWen G(2024)An Adaptive Point Cloud Registration Algorithm Based on Cross Optimization of Local Feature Point Normal and Global SurfaceIEEE Transactions on Automation Science and Engineering10.1109/TASE.2023.332546621:4(6434-6447)Online publication date: Oct-2024
https://doi.org/10.1109/TASE.2023.3325466
Ehm VGao MRoetzer PEisenberger MCremers DBernard F(2024)Partial-to-Partial Shape Matching with Geometric Consistency2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02595(27478-27487)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02595
Show More Cited By

Index Terms

DS++: a flexible, scalable and provably tight relaxation for matching problems
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Shape analysis

Recommendations

A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives

Recent progress in solving quadratic assignment problems QAPs from the QAPLIB Quadratic Assignment Problem Library test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite ...
Generalized McCormick relaxations

Convex and concave relaxations are used extensively in global optimization algorithms. Among the various techniques available for generating relaxations of a given function, McCormick's relaxations are attractive due to the recursive nature of their ...
Convex Relaxations for Gas Expansion Planning

Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the nonconvex nature of gas transmission constraints, global optimality and infeasibility guarantees can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

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

Editor:
Kavita Bala

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 for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
480
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)2

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu HScaglione AWai H(2024)Blind Graph Matching Using Graph SignalsIEEE Transactions on Signal Processing10.1109/TSP.2024.338284072(1766-1781)Online publication date: 28-Mar-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3382840
Li LMei SMa WLiu XLi JWen G(2024)An Adaptive Point Cloud Registration Algorithm Based on Cross Optimization of Local Feature Point Normal and Global SurfaceIEEE Transactions on Automation Science and Engineering10.1109/TASE.2023.332546621:4(6434-6447)Online publication date: Oct-2024
https://doi.org/10.1109/TASE.2023.3325466
Ehm VGao MRoetzer PEisenberger MCremers DBernard F(2024)Partial-to-Partial Shape Matching with Geometric Consistency2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02595(27478-27487)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02595
Wang RYan JYang X(2023)Unsupervised Learning of Graph Matching With Mixture of Modes via Discrepancy MinimizationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.325783045:8(10500-10518)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TPAMI.2023.3257830
Hu CXu WYuan J(2023)Solving the point cloud registration based on deep learning2023 IEEE 3rd International Conference on Power, Electronics and Computer Applications (ICPECA)10.1109/ICPECA56706.2023.10076094(1049-1055)Online publication date: 29-Jan-2023
https://doi.org/10.1109/ICPECA56706.2023.10076094
Gao MRoetzer PEisenberger MLähner ZMoeller MCremers DBernard F(2023)ΣIGMA: Scale-Invariant Global Sparse Shape Matching2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.00066(645-654)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.00066
Fan ZMao CWu YXu J(2023)Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian AnalysisFoundations of Computational Mathematics10.1007/s10208-022-09570-y23:5(1511-1565)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1007/s10208-022-09570-y
Kamhoua BZhang LChen YYang HMa KHan BLi BCheng JKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Exact shape correspondence via 2D graph convolutionProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601584(18072-18087)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601584
Barthel KHezel NJung KSchall K(2022)Improved Evaluation and Generation Of Grid Layouts Using Distance Preservation Quality and Linear Assignment SortingComputer Graphics Forum10.1111/cgf.1471842:1(261-276)Online publication date: 16-Nov-2022
https://doi.org/10.1111/cgf.14718
Maretic HGheche MMinder MChierchia GFrossard P(2022)Wasserstein-Based Graph AlignmentIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2022.31696328(353-363)Online publication date: 2022
https://doi.org/10.1109/TSIPN.2022.3169632
Show More Cited By

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents