×

Exact recovery with symmetries for procrustes matching. (English) Zbl 1376.90042

Summary: The Procrustes matching (PM) problem is the problem of finding the optimal rigid motion and labeling of two point sets so that they are as close as possible. Both rigid and nonrigid shape matching problems can be formulated as PM problems. Recently H. Maron et al. [ACM Trans. Graph. 35, Paper No. 73, 73 p. (2016; doi:10.1145/2897824.2925913)] presented a novel convex semidefinite programming relaxation (PM-SDP) for PM which achieves state-of-the-art results on common shape matching benchmarks. In this paper we analyze the successfulness of PM-SDP in solving PM problems without noise (exact PM problems): For asymmetric point sets we show that the PM-SDP relaxation returns the correct solution of PM. Symmetric points sets introduce multiple solutions to the PM problem. Therefore, convex relaxations of the PM problem will necessarily admit unwanted solutions, namely, the convex combinations of the correct solutions. To alleviate this issue, standard approaches regularize the nonconvex problem so that it has a unique solution. In contrast, we show that the solutions of PM are precisely the extreme points of the convex solution set of PM-SDP. We then suggest a random algorithm which returns a solution of PM with probability one, and return all solutions of PM with equal probability. By repeatedly applying this algorithm all solutions of PM can be obtained. In addition, we show that the PM-SDP relaxation retains its exactness in the presence of low noise, is invariant to orthogonal change of coordinates and relabeling of points, and is always nonnegative. Finally, exact PM is shown to be computationally equivalent to the graph isomorphism problem.

MSC:

90C22 Semidefinite programming
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Y. Aflalo, A. Bronstein, and R. Kimmel, {\it On convex relaxation of graph isomorphism}, Proc. Natl. Acad. Sci. USA, 112 (2015), pp. 2942-2947. · Zbl 1355.05237
[2] D. Anguelov, P. Srinivasan, D. Koller, S. Thrun, J. Rodgers, and J. Davis, {\it Scape: Shape completion and animation of people}, ACM Trans. Graphics, 24 (2005), pp. 408-416.
[3] L. Babai, {\it Graph Isomorphism in Quasipolynomial Time}, CoRR preprint, , 2015. · Zbl 1376.68058
[4] L. Babai, D. Y. Grigoryev, and D. M. Mount, {\it Isomorphism of graphs with bounded eigenvalue multiplicity}, in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC ’82, ACM, New York, 1982, pp. 310-324.
[5] A. I. Barvinok, {\it Problems of distance geometry and convex properties of quadratic maps}, Discrete Comput. Geom., 13 (1995), pp. 189-202. · Zbl 0829.05025
[6] P. J. Besl and N. D. McKay, {\it Method for registration of 3-d shapes}, in Robotics-DL Tentative, International Society for Optics and Photonics, 1992, pp. 586-606.
[7] J. F. Bonnans and A. Shapiro, {\it Perturbation Analysis of Optimization Problems}, Springer Science & Business Media, New York, 2013. · Zbl 0966.49001
[8] E. J. Candès, Y. C. Eldar, T. Strohmer, and V. Voroninski, {\it Phase retrieval via matrix completion}, SIAM Rev., 57 (2015), pp. 225-251, . · Zbl 1344.49057
[9] M. Fiori and G. Sapiro, {\it On spectral properties for graph matching and graph isomorphism problems}, Inf. Inference, 4 (2015), pp. 63-76. · Zbl 1380.05160
[10] M. A. Fischler and R. C. Bolles, {\it Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography}, Comm. ACM, 24 (1981), pp. 381-395.
[11] M. Fukuda, M. Kojima, K. Murota, and K. Nakata, {\it Exploiting sparsity in semidefinite programming via matrix completion I: General framework}, SIAM J. Optim., 11 (2000), pp. 647-674, . · Zbl 1010.90053
[12] R. Grone, C. R. Johnson, E. M. Sá, and H. Wolkowicz, {\it Positive definite completions of partial Hermitian matrices}, Linear Algebra Appl., 58 (1984), pp. 109-124. · Zbl 0547.15011
[13] Q.-X. Huang and L. Guibas, {\it Consistent shape maps via semidefinite programming}, in Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing, SGP ’13, Aire-la-Ville, Switzerland, 2013, Eurographics Association, pp. 177-186.
[14] I. Kezurer, S. Z. Kovalsky, R. Basri, and Y. Lipman, {\it Tight relaxation of quadratic matching}, Comput. Graph. Forum, 34 (2015), pp. 115-128.
[15] Y. Khoo and A. Kapoor, {\it Towards Non-iterative Closest Point: Exact Recovery of Pose for Rigid 2D/3D Registration Using Semidefinite Programming}, CoRR preprint, , 2015.
[16] J. Lofberg, {\it Yalmip: A toolbox for modeling and optimization in MATLAB}, in Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design, IEEE, 2005, pp. 284-289.
[17] Z.-Q. Luo, W.-k. Ma, A. M.-C. So, Y. Ye, and S. Zhang, {\it Semidefinite relaxation of quadratic optimization problems}, IEEE Signal Process. Mag., 27 (2010), pp. 20-34.
[18] H. Maron, N. Dym, I. Kezurer, S. Kovalsky, and Y. Lipman, {\it Point registration via efficient convex relaxation}, ACM Trans. Graph., 35 (2016), pp. 73:1-73:12.
[19] A. Mosek, {\it The Mosek Optimization Toolbox for Matlab Manual}, Version 7.1 (Revision 28), 2015.
[20] M. Ovsjanikov, J. Sun, and L. Guibas, {\it Global intrinsic symmetries of shapes}, in Proceedings of the Symposium on Geometry Processing, Computer Graphics Forum 27, Wiley Online Library, 2008, pp. 1341-1348.
[21] S. Rusinkiewicz and M. Levoy, {\it Efficient variants of the ICP algorithm}, in Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, 2001, pp. 145-152.
[22] R. M. Rustamov, {\it Laplace-Beltrami eigenfunctions for deformation invariant shape representation}, in Proceedings of the Fifth Eurographics Symposium on Geometry Processing, Eurographics Association, 2007, pp. 225-233.
[23] A. M.-C. So and Y. Ye, {\it Theory of semidefinite programming for sensor network localization}, Math. Program., 109 (2007), pp. 367-384. · Zbl 1278.90482
[24] H. Waki, S. Kim, M. Kojima, and M. Muramatsu, {\it Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity}, SIAM J. Optim., 17 (2006), pp. 218-242, . · Zbl 1109.65058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.