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.
- 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 Scholar
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems. 2292--2300. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Nadav Dym and Yaron Lipman. 2016. Exact Recovery with Symmetries for Procrustes Matching. arXiv preprint arXiv:1606.01548 (2016).Google Scholar
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- Andrew H Gee and Richard W Prager. 1994. Polyhedral combinatorics and neural networks. Neural computation 6, 1 (1994), 161--180. Google ScholarDigital Library
- Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi. 2007. Shape retrieval contest 2007: Watertight models track. SHREC competition 8 (2007).Google Scholar
- 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 Scholar
- 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 Scholar
- Vladimir G Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended intrinsic maps. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 79. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Yaron Lipman and Thomas Funkhouser. 2009. Möbius voting for surface correspondence. In ACM Transactions on Graphics (TOG), Vol. 28. ACM, 72. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Facundo Mémoli. 2011. Gromov-Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11, 4 (2011), 417--487. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman. 2015. Deep face recognition. In British Machine Vision Conference, Vol. 1. 6.Google ScholarCross Ref
- Novi Quadrianto, Le Song, and Alex J Smola. 2009. Kernelized sorting. In Advances in neural information processing systems. 1289--1296. Google ScholarDigital Library
- Anand Rangarajan, Steven Gold, and Eric Mjolsness. 1996. A novel optimizing network architecture with applications. Neural Computation 8, 5 (1996), 1041--1060. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 Scholar
- 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 ScholarDigital Library
- Yong Xia. 2008. Second order cone programming relaxation for quadratic assignment problems. Optimization Methods & Software 23, 3 (2008), 441--449. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- 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 ScholarCross Ref
Index Terms
DS++: a flexible, scalable and provably tight relaxation for matching problems
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