“DS++: a flexible, scalable and provably tight relaxation for matching problems” by Dym, Maron and Lipman
Conference:
Type(s):
Title:
- DS++: a flexible, scalable and provably tight relaxation for matching problems
Session/Category Title: Geometry and Shape
Presenter(s)/Author(s):
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. Cross 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. Cross 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.
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.
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).
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.
9. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems. 2292–2300.
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.
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.
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.
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. Cross 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. Cross 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.
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. Cross 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.
19. Andrew H Gee and Richard W Prager. 1994. Polyhedral combinatorics and neural networks. Neural computation 6, 1 (1994), 161–180.
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.
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.
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.
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.
27. Yaron Lipman and Thomas Funkhouser. 2009. Möbius voting for surface correspondence. In ACM Transactions on Graphics (TOG), Vol. 28. ACM, 72.
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. Cross 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.
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.
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.
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.
33. Facundo Mémoli. 2011. Gromov-Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11, 4 (2011), 417–487.
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.
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. Cross 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.
37. Omkar M Parkhi, Andrea Vedaldi, and Andrew Zisserman. 2015. Deep face recognition. In British Machine Vision Conference, Vol. 1. 6. Cross Ref
38. Novi Quadrianto, Le Song, and Alex J Smola. 2009. Kernelized sorting. In Advances in neural information processing systems. 1289–1296.
39. Anand Rangarajan, Steven Gold, and Eric Mjolsness. 1996. A novel optimizing network architecture with applications. Neural Computation 8, 5 (1996), 1041–1060.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
52. Yong Xia. 2008. Second order cone programming relaxation for quadratic assignment problems. Optimization Methods & Software 23, 3 (2008), 441–449.
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.
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. Cross 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. Cross 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. Cross Ref
